c++ - 在 C++ 中使用 STL 创建邻接表的有效方法是什么？

Question

我目前使用如下 vector 的 vector :

typedef pair<int, int> vertex;
vector < vector<vertex> > adj_list(n); // n is number of vertices

// Input graph
for (int i = 0; i < edges; i++ )
{
   cin >> source >> target >> weight;
   vertex v(target, weight);
   adj_list[source].push_back(v);
}

是列表的 vector 即。

vector < list<vertex> > adj_list(n);

更好的选择？如果是，为什么？我主要关心的是有效地创建邻接表，并能够快速读取连接到特定顶点的所有顶点，以实现 Dijkstra 算法。

Answer 1

为此我会使用 std::deque<>，因为您很可能不需要从中间移除元素(这就是为什么有人会想要使用 std::list<>)。它应该比 std::vector<> 或 std::list<> 更有效。拥有连续的内存( vector )和可移动的项目(列表)是有代价的—— vector 的大小调整和列表的指针取消引用/分散内存是昂贵的。

另请参阅:http://www.gotw.ca/gotw/054.htm

请注意，如果您的目标是算法竞赛，您可能会对这种基于 STL 的数据结构占用的内存量感到惊讶。