我应该使用哪个STL容器？C++

Question

我有一个对象“列表”，我想从中随机选择一个对象并将其推到该列表的前面。只执行这种操作。因此，我不需要快速访问列表末尾，只需访问它的前面和任何其他位置的平均访问。

哪种容器最适合这种情况？我考虑过std :: vector，但我读到insert操作效率不高。然后我想到了std :: deque，因为它可以快速访问前面，但是它的erase特定位置方法的效率如何？

提前感谢您的帮助。

- Piotr Chojnacki

---

你的容器将存储多少数据？如果不到1MB，请选择简单的“vector”。这样做不会有太大的性能差异。 - Didier Trosset

如果对象很大，那么进行优化的第一步可能是使用指向它们的（智能）指针的向量/双端队列。您的 erase 仍然是 O(n)，但要移动的数据量更小。 - Steve Jessop

如果您使用的是vector，那么将其推到后面并使用反向迭代器。将其推到前面是愚蠢的。 - Pubby

你是需要将它置于列表顶部，还是将这个元素与顶部的元素交换？后者更为高效。 - user1773602

@Mosquito，那就使用向量（最好是指针）。 - user1773602

Answer 1

我们可以给你指导方针，但无法给出明确的答案 - 你需要自己进行基准测试，因为这取决于你的集合和对象大小：

- 对于小对象和/或相对较小的集合，std::vector 将更快，因为即使你需要复制更多的数据，更好的随机访问时间（std::list 的 O(n) 对比 std::vector 的O（1））和缓存局部性将占主导地位。

- 对于大对象和/或大集合，std::list 将更快，因为虽然你需要 O(n) 来选择一个随机对象，但插入会更快，因为复制许多大对象非常慢。

但是这两种情况之间的分界点在哪里我不能说。

此外，如果你能够通过交换元素而不是插入来解决问题，那么这是显而易见的：总是使用std::vector。

- Konrad Rudolph

Answer 2

基于这个答案: https://dev59.com/TXRB5IYBdhLWcg3w6LV2#471481 (还有这个: https://dev59.com/TXRB5IYBdhLWcg3w6LV2#471461)，我会选择使用列表。它很容易添加、迭代、插入和删除。

PS：这取决于随机位置是否基于索引（也就是说，如果您通过对列表进行迭代并测试其属性来了解位置的数字位置或要移动到前面的对象）。

所以：如果位置已知而不需要迭代列表，则选择向量。 如果需要迭代集合才能确定位置，则选择列表。

- user1284631

---

即使在第二种情况下，由于缓存局部性，对于许多场景来说，std::vector 也会更快。 - Konrad Rudolph

@KonradRudolph：你是对的，因为它也取决于数据结构的大小。向量的真正问题在于当元素被移动（即从当前位置删除）时，会触发向量重排的不良行为。如果OP可以规避该操作，则向量是首选。另一方面，对于小型数据结构，它可以简单地使用两个向量：一个包含感兴趣的值，另一个包含指示这些值当前顺序的置换。"删除和插入"过程只需将第二个向量中的值更改即可。 - user1284631