4

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

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

提前感谢您的帮助。

4

2 回答 2

7

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

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

但是我不能说这两种情况之间的确切界限在哪里。

此外，如果您可以通过交换元素而不是插入来摆脱困境，那么这很容易：始终使用std::vector.

于 2012-12-05T11:24:50.170 回答
2

基于这个答案：https ://stackoverflow.com/a/471481/1284631 （以及，在这个：https ://stackoverflow.com/a/471461/1284631 ），我会去一份清单。追加、迭代、插入和删除都很便宜。

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

所以：如果在不迭代列表的情况下知道位置，那么就去寻找一个向量。如果该位置需要遍历集合，请查看列表。

于 2012-12-05T11:19:33.620 回答