STL向量vs列表：对图邻接列表最有效？

当push_back时，列表消耗大部分时间分配内存。另一方面，当需要调整大小时，矢量必须复制它们的元素。因此，哪个容器对于存储邻接列表最有效？STL向量vs列表：对图邻接列表最有效？

2011-03-26 Alexandros

谁说向量做副本？ – quasiverse 2011-03-26 06:22:39

@quasiverse：对“vector”的要求本质上需要一个副本，随着它的增长。 'vector's需要连续存储它们的元素。在添加元素时，最终会占用分配的空间，在下一次添加时，您将获得新内存分配，然后是当前元素的副本到新空间，然后是旧空间的释放。 – 2011-03-26 07:51:18

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

是的，矢量在扩展时必须复制元素，但实际上这几乎不是一个实质性的问题。特别是，矢量的指数扩展率意味着元素被复制的平均次数趋于恒定 - 在典型的实施中，该常数大约为3.

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

来源

2011-03-26 06:47:08

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

如果你有一个不断变化的邻接列表（插入和删除），列表将是最好的。如果你有一个或多或少的静态邻接列表，并且大部分时间你正在进行遍历/查找，那么一个向量会给你最好的性能。

来源

2011-03-26 06:28:23 Sandeep

STL容器没有严格定义，因此实现方式各不相同。如果你非常小心，你可以编写代码，以便它不关心它是一个矢量还是一个正在使用的列表，你可以试着看看哪个更快。考虑到缓存效果等的复杂性，以任何精度预测相对速度几乎是不可能的。

来源

2011-03-26 06:29:58

您可以添加第三个选项到这个比较：带有专门分配器的列表。

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

来源

2011-03-26 07:23:56 maxim1000

STL向量vs列表：对图邻接列表最有效？

回答

相关问题