STL vector和list：哪个更适合用于图的邻接表？

Question

在push_back时，列表大部分时间都用于分配内存。另一方面，当需要调整大小时，向量必须复制它们的元素。因此，哪种容器最适合存储邻接表？

- Alexandros

---

@quasiverse：对于vector的要求基本上需要在其增长时进行复制。vector需要存储它们的元素连续。随着您添加元素，最终会用完分配的空间，在下一次添加时，您将获得一个新的内存分配，然后将当前元素复制到新空间，最后释放旧空间。 - Max Lybbert

Answer 1

我认为无法绝对确定这个问题的答案。尽管如此，我的估计是使用 vector 至少有90%的机会表现更好。实际上，邻接表比许多应用程序更加偏好于 vector ，因为邻接表中元素的顺序通常并不重要。这意味着当你添加元素时，通常是添加到容器的末尾；而当你删除一个元素时，你可以先将其交换到容器的末尾，这样你只需要在末尾添加或删除。

是的，vector 在扩展时必须复制或移动元素，但实际上这几乎从来不是一个重大问题。特别是，vector 的指数扩展速率意味着元素被复制/移动的平均次数趋向于一个常数 - 并且在典型的实现中，这个常数约为3。

如果你处于一个复制实际上是一个真正的问题的情况下（例如，复制元素非常昂贵），我的下一个选择仍然不会是 list。相反，我可能会考虑使用 std::deque¹。实际上，它就是对象块指针的向量。它很少需要复制任何东西来进行扩展，并且在偶尔需要复制时，它只需要复制指针而不是对象即可。除非你需要 deque 的其他独特功能（能够以常数时间在两端插入/删除），否则 vector 通常是更好的选择，但即使如此，deque 几乎总是比 list 更好（即，vector 通常是第一选择，deque 是相当接近的第二选择，而 list 则遥远地排在最后）。

---

^{一个小问题：至少在过去，微软对 `std::deque` 的实现存在着一种我认为有点缺陷的做法。如果 `deque` 中元素的大小大于16，则它最终会存储指向仅包含单个元素的“块”的指针，这往往会抵消使用 `deque` 的优势。但这通常不会对其用作邻接列表产生太多影响。}

- Jerry Coffin

Answer 2

答案取决于使用情况。 P.S. @quasiverse - 当您“::reserve”隐式或显式地耗尽内存时，向量会调用realloc

如果您有一个不断变化的邻接表（插入和删除），则列表是最好的选择。 如果您有一个相对静态的邻接表，并且大部分时间都在进行遍历/查找，则向量将为您提供最佳性能。

- Sandeep

Answer 3

这个教程网站建议使用一个列表数组，或者你也可以使用一个列表元素的向量代替：列表数组 adj 列表

- mLstudent33

Answer 4

STL容器没有严格的定义，因此实现会有所不同。如果你小心一点，可以编写代码，使其不关心使用的是向量还是列表，并且可以尝试它们以查看哪个更快。鉴于缓存效应等复杂性，几乎不可能准确预测相对速度。

- Tim Sylvester

Answer 5

您可以在此比较中添加第三个选项：使用专用分配器的列表。

对于固定大小的小对象使用分配器可能会大大提高分配/释放速度...

- maxim1000