问题描述

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

I have a 'list' of objects, from which I want to take object at random position and push it on front of this list. Only this kind of operation will be performed. So I don't need a fast access to end of the list, only to it's front and average access to any other place.

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

Which container would be the best for this? I was thinking about std::vector, but I've read that insert operation is not efficient. Then I came up with std::deque because of it's fast access to front, but what about efficiency of it's erase at specific position method?

提前感谢您的帮助.

推荐答案

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

We can give you guidelines, but no definitive answer – you need to benchmark that yourself because it crucially depends on your collection and object size:

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

• For small objects and/or a relatively small collection, std::vector will be faster because even though you need to copy more data, the better random access time (O(1) vs O(n) for std::list) and the cache locality will dominate.
• For large objects and/or a large collection, std::list will be faster because although you need O(n) to pick a random object, insertion will be much faster since the copying of many large objects is very slow.

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

But where exactly the cut-off between these two scenarios lies I cannot say.

此外，如果您可以交换元素而不是插入，那么这很容易:始终使用 std::vector.

Furthermore, if you can get away with swapping the elements instead of insertion, this is a no-brainer: always use a std::vector.

这篇关于我应该使用哪个 STL 容器?C++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！