STL向量与列表：对于图邻接列表最有效？
列表在 Push_back 时消耗了大部分时间来分配内存。另一方面，当需要调整大小时，向量必须复制其元素。因此，哪个容器存储邻接列表最有效？
Lists consume most of their time in allocating memory when pushing_back. On the other hand, vectors have to copy their elements when a resize is needed. Which container is, therefore, the most efficient for storing an adjacency list?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
我认为这个问题不能绝对肯定地回答。尽管如此，我估计
向量至少有 90% 的机会会做得更好。实际上，邻接列表比许多应用程序更倾向于向量，因为邻接列表中元素的顺序通常并不重要。这意味着当您添加元素时，它通常位于容器的末尾，而当您删除元素时，您可以先将其交换到容器的末尾，因此您只能在末尾添加或删除。是的，向量在扩展时必须复制或移动元素，但实际上这几乎从来都不是一个重要的问题。特别是，
向量的指数扩展率意味着元素被复制/移动的平均次数趋向于一个常数——在典型的实现中，该常数约为 3。如果您'在诚实地复制是一个真正问题的情况下（例如，复制元素非常昂贵），我在
vector之后的下一个选择仍然不会是list。相反，我可能会考虑使用std::deque代替1。它基本上是一个指向对象块的指针向量。它很少需要复制任何内容来进行扩展，并且在极少数情况下，它所需要复制的只是指针，而不是对象。除非您需要双端队列的其他独特功能（在任一端以恒定时间插入/删除），否则向量通常是更好的选择，但即便如此， >deque 几乎总是比列表更好的选择（即，vector通常是第一选择，deque紧随其后，list相当遥远的最后）。1. One minor aside though: at least in the past, Microsoft's implementation of `std::deque` had what I'd consider sort of a defect. If the size of an element in the `deque` is greater than 16, it ends up storing pointers to "blocks" of only a single element apiece, which tends to negate much of the advantage of using `deque` in the first place. This generally won't have much effect on its use for an adjacency list though.
I don't think this can be answered with absolute certainty. Nonetheless, I'd estimate that there's at least a 90% chance that a
vectorwill do better. An adjacency list actually tends to favor avectormore than many applications, because the order of elements in the adjacency list doesn't normally matter. This means when you add elements, it's normally to the end of the container, and when you delete an element, you can swap it to the end of the container first, so you only ever add or delete at the end.Yes, a
vectorhas to copy or move elements when it expands, but in reality this is almost never a substantial concern. In particular, the exponential expansion rate of avectormeans that the average number of times elements get copied/moved tends toward a constant -- and in a typical implementation, that constant is about 3.If you're in a situation where the copying honestly is a real problem (e.g., copying elements is extremely expensive), my next choice after
vectorstill wouldn't belist. Instead, I'd probably consider usingstd::dequeinstead1. It's basically a vector of pointers to blocks of objects. It rarely has to copy anything to do an expansion, and on the rare occasion that it does, all it has to copy is the pointers, not the objects. Unless you need the other unique capabilities of adeque(insert/delete in constant time at either end), avectoris usually a better choice, but even so adequeis almost always a better choice than a list (i.e.,vectoris generally the first choice,dequea fairly close second, andlistquite a distant last).1. One minor aside though: at least in the past, Microsoft's implementation of `std::deque` had what I'd consider sort of a defect. If the size of an element in the `deque` is greater than 16, it ends up storing pointers to "blocks" of only a single element apiece, which tends to negate much of the advantage of using `deque` in the first place. This generally won't have much effect on its use for an adjacency list though.
答案取决于用例。
PS @quasiverse - 当您“::reserve”的内存隐式或显式耗尽时，向量调用 realloc
如果您有一个不断变化的邻接列表（插入和删除），那么列表将是最好的。
如果您有或多或少的静态邻接列表，并且大多数时候您都在进行遍历/查找，那么向量将为您提供最佳性能。
The answer depends on use-case.
P.S. @quasiverse - vectors call realloc when the memory you "::reserve", implicitly or explicitly, runs out
If you have a constantly changing adjacency list (inserts and deletes), a list would be best.
If you have a more or less static adjacency list, and most of the time you are doing traversals/lookups, then a vector would give you the best performance.
STL 容器没有严格定义，因此实现各不相同。如果你小心的话，你可以编写你的代码，这样它就不会关心正在使用的是向量还是列表，你可以尝试它们，看看哪个更快。考虑到缓存效应等的复杂性，几乎不可能准确地预测相对速度。
STL containers are not rigidly defined, so implementations vary. If you're careful you can write your code so that it doesn't care whether it's a vector or a list that's being used, and you can just try them to see which is faster. Given the complexity of cache effects, etc., it's nearly impossible to predict the relative speeds with any accuracy.
您可以向此比较添加第三个选项：带有专用分配器的列表。
对固定大小的小对象使用分配器可能会大大提高分配/释放的速度......
You can add third option to this comparison: list with specialized allocator.
Using allocators for small objects of fixed size may greatly increase speed of allocation/deallocation...
本教程网站建议使用列表数组，或者我想您可以使用列表元素向量： 列表数组 adj 列表
This tutorial site recommends using an array of lists or I guess you can use a vector of list elements instead: array of lists adj list