具有 >100.000 个键的 Vector C++ unordered_map
C++ unordered_map of Vector with >100.000 Keys
我必须阅读一个边列表，其中包含 100.000 个顶点和大约 200.000 个边的形式：
顶点 A---> 成本 X 的顶点 B
我有一个带有 int 键（顶点 A）的 unordered_map，并将键映射到边向量，其中边包含顶点 B 和成本 X，如下所示：unordered_map<int, vector<Edge> > adjList
我用来填充 adjList 的方法是
(... read Vertex A, B and Cost X out of file...)
Edge e(Vertex B, Cost X) //create a new Object Edge
adj[Vertex A].push_back(e); //put it into the vector
用 100.000 个顶点和边填充 adjList 需要相当长的时间，我的 VS-Performance Profiler 告诉我，unordered_map 的 operator[] 函数是我的瓶颈。还有其他方法可以将我的数据放入 unodre_map 吗？或者甚至是用于此应用程序的其他数据结构？
谢谢
以下是您可以按顺序尝试的方法。
确保您正在构建发布配置。默认情况下，STL 集合在 VS 中的调试构建中非常慢。你也可以用 some #defines.
如果您事先知道需要多少元素，请在您的 unordered_map
非常小，可能已被编译器优化，但您仍然最好将两行替换为使用 vector::emplace_back 在该向量内创建新边的一行。
如果这还不够，请转向更好的哈希映射。虽然易于使用、便携且标准，但 STL 集合并不是特别快。在 Windows 我推荐 CAtlMap，它快得多。
我必须阅读一个边列表，其中包含 100.000 个顶点和大约 200.000 个边的形式： 顶点 A---> 成本 X 的顶点 B
我有一个带有 int 键（顶点 A）的 unordered_map，并将键映射到边向量，其中边包含顶点 B 和成本 X，如下所示：unordered_map<int, vector<Edge> > adjList
我用来填充 adjList 的方法是
(... read Vertex A, B and Cost X out of file...)
Edge e(Vertex B, Cost X) //create a new Object Edge
adj[Vertex A].push_back(e); //put it into the vector
用 100.000 个顶点和边填充 adjList 需要相当长的时间，我的 VS-Performance Profiler 告诉我，unordered_map 的 operator[] 函数是我的瓶颈。还有其他方法可以将我的数据放入 unodre_map 吗？或者甚至是用于此应用程序的其他数据结构？
谢谢
以下是您可以按顺序尝试的方法。
确保您正在构建发布配置。默认情况下，STL 集合在 VS 中的调试构建中非常慢。你也可以用 some #defines.
做同样的事情
如果您事先知道需要多少元素，请在您的 unordered_map
上调用 reserve
非常小，可能已被编译器优化，但您仍然最好将两行替换为使用 vector::emplace_back 在该向量内创建新边的一行。
如果这还不够，请转向更好的哈希映射。虽然易于使用、便携且标准，但 STL 集合并不是特别快。在 Windows 我推荐 CAtlMap，它快得多。