std :: vector与std :: list与std :: slist的相对表现？

对于一个简单的链表,其中不需要随机访问列表元素,是否有任何显着的优势(性能或其他)使用std::list而不是std::vector？如果需要向后遍历,那么在迭代其元素之前使用std::slist和reverse()列表会更有效吗？

1> Motti..：

---

像往常一样,性能问题的最佳答案是为您的用例分析两种实现,并查看哪种更快.

一般情况下,如果你有插入到数据结构中(除了最后),那么vector可能会更慢,否则在大多数情况下vector预期比list仅仅针对数据局部性问题表现更好,这意味着如果两个元素相邻数据集在内存中相邻,然后下一个元素已经在处理器的缓存中,并且不必将内存页面故障放入缓存中.

还要记住,a的空间开销vector是常量(3个指针),而a的空间开销list是为每个元素支付的,这也减少了任何一个可以驻留在缓存中的完整元素(数据加上开销)的数量时间.

---

链接列表更快的唯一地方就是当你进行大量的拼接时,因为这不涉及大量的缓存未命中,并且每个拼接都是一个恒定时间操作(它可以移动大量的从一个链表到另一个链表的项目).

---

还要记住,如果必须搜索要插入的位置,甚至插入在矢量中比在链表中更快.例如,取一堆随机整数并按排序顺序将它们插入到矢量或链表中 - 由于在搜索插入点时缓存未命中,因此无论总项数是多少,矢量总是会更快链表.

2> Sam..：

---

在C++中要考虑的默认数据结构是Vector.

考虑以下几点......

1]遍历:
列表节点分散在内存中,因此列表遍历会导致缓存未命中.但矢量的遍历是平滑的.

2]插入和删除:
当您对Vector执行此操作时,必须移动平均50%的元素,但缓存非常擅长!但是,对于列表,您需要遍历插入/删除点......所以再次......缓存未命中!令人惊讶的是,矢量也赢得了这个案例!

3]存储:
当你使用列表时,每个元素有2个指针(向前和向后),所以List比Vector大得多!向量只需要比实际元素需要更多的内存.

Yout应该有理由不使用矢量.

---

参考:
我在The Lord Bjarne Stroustrup的演讲中了解到这一点:https://youtu.be/0iWb_qi2-uI？t = 2680

---

我认为你的意思是缓存未命中,但作为一个独立游戏开发者,我写的代码也有一些现金未命中.

---

http://java.dzone.com/articles/c-benchmark-%E2%80%93-stdvector-vs与Bjarne说的有点相似,但测试的数字和源代码更好.

3> gbjbaanb..：

---

根本没有.列表优于Vector,但顺序访问不是其中之一 - 如果这就是你所做的一切,那么矢量就更好了.

然而,添加额外元素而不是列表的向量更昂贵,特别是如果您插入中间.

了解这些集合是如何实现的:向量是一个连续的数据数组,列表是一个包含数据和指向下一个元素的指针的元素.一旦你理解了这一点,你就会明白为什么列表对插入有好处,对随机访问有害.

(因此,向量的反向迭代与正向迭代完全相同 - 迭代器每次只减去数据项的大小,列表仍然必须通过指针跳转到下一个项目)

---

这是显而易见的,并且99%的时间都是正确答案.如果你需要向后遍历,则向后运行你的for循环.阵列/向量提供随机访问,非常快速的顺序访问,以及从向量中的任何随机起始点同样快速的顺序访问.喜欢的列表只有一个强项,即删除成员或在列表中的某个位置插入成员.他们非常厌恶其他一切.慢,慢,慢.增长数组/向量就像新的malloc()和memmove()一样简单.使用Vprime,Vgrow,您可以重新分配它们并来回复制.