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

Question

我有一个对象的“列表”，我想从其中获取任意位置的对象，并将其推送到该列表的前面。只有这种操作才会被执行。所以我不需要快速访问列表的末尾，只需要访问它的前面和平均访问任何其他地方。

哪个容器是最好的呢？我在想std::vector，但我读到过insert操作效率不高。然后我提出了std::deque，因为它访问前端的速度很快，但是它在特定位置的erase方法的效率如何呢？

提前感谢您的帮助。

Answer 1

我们可以为您提供指导，但没有明确的答案-您需要自己进行基准测试，因为它关键取决于您的集合和对象大小：

• 对于小对象和/或相对较小的集合，std::vector将更快，因为即使您需要复制更多数据，但更好的随机访问时间(对于std::list为O(1) vs O(n) )和缓存局部性将占主导地位。
• 对于大对象和/或大集合，std::list将更快，因为虽然您需要O(n)来挑选随机对象，但插入将更快，因为许多大对象的复制非常慢。

但我不能说这两种情况之间的分界线到底在哪里。

此外，如果您可以轻松地交换元素而不是插入，这是不需要动脑筋的:始终使用std::vector。

Answer 2

基于这个答案：https://stackoverflow.com/a/471481/1284631 (还有这个：https://stackoverflow.com/a/471461/1284631)，我会列出一个列表。追加、迭代、插入和删除都很便宜。

PS:这取决于随机位置是否是基于索引的(也就是说，如果您通过对列表进行迭代并测试其属性，从数字上知道要移动到前面的位置或对象的结果)。

所以:如果位置是已知的，而不需要迭代列表，那么就去找一个向量。如果这个位置需要遍历集合，那么就去找一个列表。