c++ - STL 向量与列表：图邻接列表最有效？

Question

push_back 时，列表会花费大部分时间来分配内存。另一方面，当需要调整大小时，向量必须复制它们的元素。因此，哪个容器最有效地存储邻接表？

Answer 1

我认为这不能绝对肯定地回答。尽管如此，我估计至少有 90% 的机会 avector会做得更好。邻接列表实际上倾向于支持vector更多的应用程序，因为邻接列表中元素的顺序通常并不重要。这意味着当你添加元素时，它通常在容器的末尾，当你删除一个元素时，你可以先将它交换到容器的末尾，所以你只能在末尾添加或删除。

是的，avector在扩展时必须复制或移动元素，但实际上这几乎不是一个实质性的问题。特别是，a 的指数扩展率vector意味着元素被复制/移动的平均次数趋向于一个常数——在典型的实现中，该常数约为 3。

如果您处于诚实复制是一个真正问题的情况（例如，复制元素非常昂贵），那么我之后的下一个选择vector仍然不是list. 相反，我可能会考虑std::deque使用¹。它基本上是一个指向对象块的指针向量。它很少需要复制任何东西来进行扩展，而且在极少数情况下，它只需要复制指针，而不是对象。除非您需要 a 的其他独特功能deque（在任一端以恒定时间插入/删除），avector通常是更好的选择，但即便如此，adeque几乎总是比列表更好的选择（即，vector通常是首选，deque一个相当接近的第二个，而list最后一个相当遥远）。

---

^{1. 除了一个小问题：至少在过去，微软的 `std::deque` 实现有我认为的缺陷。如果 `deque` 中一个元素的大小大于 16，它最终会存储指向每个元素的“块”的指针，这往往会否定使用 `deque` 的大部分优势。不过，这通常不会对其用于邻接列表产生太大影响。}

Answer 2

答案取决于用例。PS @quasiverse - 当您“::reserve”的内存隐式或显式耗尽时，向量调用 realloc

如果您有一个不断变化的邻接列表（插入和删除），最好使用列表。如果您有或多或少的静态邻接列表，并且大多数时候您都在进行遍历/查找，那么向量将为您提供最佳性能。

Answer 3

STL 容器没有严格定义，因此实现会有所不同。如果你很小心，你可以编写你的代码，这样它就不会关心它是一个正在使用的向量还是一个列表，你可以尝试它们来看看哪个更快。考虑到缓存效果等的复杂性，几乎不可能准确地预测相对速度。

Answer 4

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

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

Answer 5

本教程网站建议使用列表数组，或者我想您可以使用列表元素向量代替： 列表数组 adj 列表