c++ - 为什么我插入 STL 列表运行缓慢？

Question

我正在尝试使用邻接表实现无向图。我使用了以下代码:

int v,e;
scanf("%d%d",&v,&e);
list<int> graph[3000];
for(int i=0;i<e;i++){
    int a,b;
    scanf("%d%d",&a,&b);
    graph[a].push_back(b);
    graph[b].push_back(a);
}

为了测试我的代码的运行时间，我创建了一个包含 3000 个顶点和所有可能边的输入文件。运行需要 2.2 秒。我尝试通过将其更改为二维数组来进行优化，如下所示

int graph[3000][3000];

for(int i=0;i<e;i++){
    int a,b;
    scanf("%d%d",&a,&b);
    graph[a][p[a]]=b;
    graph[b][p[b]]=a;
    p[a]++;
    p[b]++;
}

其中“p”的大小为 3000，初始化为全零。对于相同的输入文件，此代码仅需 0.35 秒即可运行。我正在使用 gcc-4.3.2 编译器。我知道列表末尾的插入可以在恒定时间内完成，那么为什么第一个代码运行缓慢？是否有机会优化链表实现？

提前致谢

Answer 1

避免 std::list。这是一个双向链表，对缓存非常不友好(节点随机分布在内存中)并且涉及大量开销(每个元素 2 个指针)。因此，每次附加内容时，列表都会分配 2*sizeof(void*)+sizeof(int) 字节以及 operator new 的额外内存管理开销。

在算法的后期，当您迭代这些值时，您实际上是在整个内存中跳跃，这会更慢。

二维数组没有这个问题，但确实会浪费一些内存。

我通常将邻接表表示为 vector 的 vector 。

std::vector<std::vector<int> > graph;

请注意， vector 还可以 push_back O(1) 中的值(以及 std::deque，它可以追加甚至更快，但在遍历时更慢)。如果期望图是密集的，那么邻接矩阵可能是更好的选择。