结合查找和有序数据的 C++ 数据结构

Question

我有一个排序图，当我加载边时，我使用哈希表查找顶点。边缘按来源排序，因此我只需要查找“更深”的顶点。如果给定边的源顶点位于 n 层，则汇点必须位于 m 层，其中 m > n。我需要利用此行为来提高性能。

“理想的”朴素解决方案是每个级别的哈希表，我可以在其中使用级别找到正确的表，然后在表中找到元素。当源级别 n 大于级别时，这也让我能够回收内存的额外好处。不幸的是，该图对于这种方法来说太大了，10^6 个级别和 10^9 个顶点。

有人对我应该查看哪种数据结构有任何建议吗？谢谢

Answer 1

根据您对该问题的大小估计，我建议使用一个 vector 的 vector :外部 vector 包含每个级别的一个内部 vector ，因此它包含大约 100 万个条目；内部 vector (每个包含大约 1000 个条目？)应该按排序顺序保存，并使用 lower_bound() 等使用排序插入。

您可以通过复制/交换技巧回收内存，用空 vector 替换旧的、未使用的内部 vector 。

typedef std::vector<Node> level_nodes;
typedef std::vector<level_nodes> graph_nodes;

graph_nodes g;
r.reserve(1000000); // OK, just a few MB

// ...

g[12].insert(std::lower_bound(g[12].begin(), g[12].end(), x), x);

level_nodes().swap(g[11]); // kill level 11 and reclaim memory