对于不需要随机访问列表元素的简单链表，使用std::list而不是有任何显着优势（性能或其他方面）std::vector吗？如果需要向后遍历，在迭代其元素之前使用std::slist和列表会更有效吗？reverse()
Andrew
问问题
79919 次
7 回答
29
在 C++ 中要考虑的默认数据结构是Vector。
考虑以下几点...
1] 遍历：
列表节点分散在内存中的任何地方，因此列表遍历会导致缓存未命中。但是向量的遍历是平滑的。
2] 插入和删除：
当您对 Vector 执行此操作时，平均 50% 的元素必须移动，但缓存非常擅长此操作！但是，对于列表，您需要遍历到插入/删除点......所以再次......缓存未命中！令人惊讶的是，向量也赢得了这个案子！
3] 存储：
当您使用列表时，每个元素有 2 个指针（向前和向后），因此列表比向量大得多！向量只需要比实际元素多一点的内存。
你应该有理由不使用向量。
参考：
我在 Bjarne Stroustrup 的演讲中了解到这一点：https ://youtu.be/0iWb_qi2-uI?t=2680
于 2013-01-25T16:45:23.327 回答
13
根本没有。List 比 Vector 有优势，但顺序访问不是其中之一——如果这就是你所做的一切，那么向量会更好。
但是.. 添加其他元素的向量比列表更昂贵，尤其是在中间插入时。
了解这些集合是如何实现的：向量是数据的顺序数组，列表是包含数据和指向下一个元素的指针的元素。一旦你理解了这一点，你就会明白为什么列表对插入有利，而对随机访问不利。
（因此，向量的反向迭代与前向迭代完全相同——迭代器每次只是减去数据项的大小，列表仍然必须通过指针跳转到下一项）
于 2008-10-26T13:41:22.460 回答
4
如果您需要向后遍历，则 slist 不太可能成为您的数据结构。
传统的（双）链表为您在列表中的任何位置提供恒定的插入和删除时间；向量仅在列表末尾提供摊销的常数时间插入和删除。对于向量的插入和删除时间，除了末端以外的任何地方都是线性的。这不是全部。也有恒定的因素。向量是一种更简单的数据结构，其优点和缺点取决于上下文。
理解这一点的最好方法是了解它们是如何实现的。链表的每个元素都有一个 next 和一个 previous 指针。向量具有由索引寻址的元素数组。从中可以看出两者都可以进行高效的前向和后向遍历，而只有一个向量才能提供高效的随机访问。您还可以看到，链表的内存开销是每个元素的，而向量的内存开销是恒定的。您还可以看到为什么两个结构之间的插入时间不同。
于 2008-10-26T13:42:31.787 回答
4
关于该主题的一些严格基准：http: //baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html
正如其他人所指出的，连续的内存存储意味着 std::vector 对大多数事情都更好。几乎没有充分的理由使用 std::list 除了少量数据（它可以全部放入缓存中）和/或擦除和重新插入频繁的地方。由于缓存和主内存速度（200x）之间的差异以及连续内存访问如何影响缓存使用，复杂性保证与实际性能无关。请参阅 Chandler Carruth (google) 在此处讨论该问题： https ://www.youtube.com/watch?v=fHNmRkzxHWs
Mike Acton 的面向数据设计的演讲在这里： https ://www.youtube.com/watch?v=rX0ItVEVjHc
于 2016-04-02T07:35:37.707 回答
2
有关成本的详细信息，请参阅此问题：
标准容器的复杂性保证是什么
如果您有一个 slist 并且您现在想以相反的顺序遍历它，为什么不将类型更改为到处列出呢？
于 2008-10-26T15:19:17.863 回答
0
- std::vector 查找元素的速度比 std::list 快得多
- 对于非常小的数据，std::vector 总是比 std::list 执行得更快
- std::vector 总是比 std::list 更快地将元素推到后面
- std::list 处理大元素非常好，特别是排序或插入在前面
注意：如果您想了解有关性能的更多信息，我建议您查看此内容
于 2021-05-14T11:36:42.617 回答