STL向量与列表:图形邻接列表最有效吗？

Question

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

Answer 1

我不认为这可以绝对肯定地回答.尽管如此,我估计一个载体至少有90%的可能性会更好.邻接列表实际上倾向于支持向量而不是许多应用程序,因为邻接列表中的元素顺序(通常)不重要.这意味着当你添加元素时,它通常是在容器的末尾,当你删除一个元素时,你可以先将它交换到容器的末尾,所以你只能在最后添加或删除.

是的,矢量必须在扩展时复制元素,但实际上这几乎不是一个重要的问题.特别是,向量的指数扩展率意味着元素被复制的平均次数倾向于常数 - 并且在典型的实现中,该常量约为3.

如果你真的存在真正的问题(例如,复制元素非常昂贵),我在矢量后的下一个选择仍然不会是列表.相反,我可能会考虑使用std :: deque.它基本上是指向对象块的指针向量.它很少需要复制任何东西来进行扩展,并且在罕见的情况下,它必须复制的只是指针,而不是对象.除非你需要deque的其他独特功能(在两端的常量时间插入/删除),矢量通常是更好的选择,但即使如此,deque几乎总是比列表更好的选择(即,矢量通常第一个选择,deque一个相当接近的第二个,并列出相当遥远的最后).