C++ 使用哪个 STL 容器？

Which STL Container to use?

提问by mister

Which STL container should i use if:

如果出现以下情况，我应该使用哪个 STL 容器：

1. Data is inserted and removed regularly.
2. Data is accessed regularly at random.

1. 数据会定期插入和删除。
2. 数据被定期随机访问。

E.g : dataset(4,10,15) if i want to find the closest number to 9, then it should return me 10.

例如：dataset(4,10,15) 如果我想找到最接近 9 的数字，那么它应该返回 10。

1. I am only storing an integer.
2. It needs to be sorted
3. Can go to 100k datasets

1. 我只存储一个整数。
2. 它需要排序
3. 可以去 10 万个数据集

I thought of using vector, but vector insertion and removing is expensive.

我想过使用向量，但向量插入和删除很昂贵。

   vector<int>

If i were to use list, i would have to access O(n) elements before reaching the data.

如果我要使用列表，则必须在访问数据之前访问 O(n) 个元素。

   list<int>

I was thinking of using set as it will be good if it is sorted, but im not very sure about the efficiencies for using SET

我正在考虑使用 set 因为如果它被排序会很好，但我不太确定使用 SET 的效率

So i hope someone can give a good solution!

所以我希望有人能给出一个好的解决方案！

回答by EdChum

I think you should check this SO post: In which scenario do I use a particular STL container?for small sizes vector will suit most scenarios irrespective of what you intend to do.

我认为您应该查看这篇 SO 帖子：在哪种情况下我使用特定的 STL 容器？对于小尺寸 vector 将适合大多数情况，无论您打算做什么。

The chart is a guide though, the fact that the container is accessed regularly does not affect container choice, the fact that you are storing int is unimportant unless you care about the size of the container, in which case does the overhead of the pointers in a list container or map matter to you?

该图表是一个指南，定期访问容器这一事实不会影响容器选择，除非您关心容器的大小，否则存储 int 的事实并不重要，在这种情况下，指针的开销会增加列表容器或地图对您来说很重要吗？

Sorting is done automatically by map but sorting a vector and list can be very fast if the container size is small enough to fit in memory.

排序由地图自动完成，但如果容器大小足够小以适合内存，则对向量和列表进行排序可能会非常快。

Data insertion is optimised for lists and maps anywhere in the container, for maps you get the benefit that it will sort itself but again if the size is small enough then constructing a new vector with the new entry could be very fast still.

数据插入针对容器中任何位置的列表和地图进行了优化，对于地图，您可以获得它会自行排序的好处，但如果大小足够小，那么使用新条目构建新向量仍然会非常快。

You may also want to consider hash maps, you would still be best to profile your code, trying to second guess what is optimal depends on your usage and you really need to measure and profile.

您可能还想考虑哈希映射，您仍然最好分析您的代码，尝试根据您的使用情况再次猜测什么是最佳的，并且您确实需要测量和分析。

You could also just decide that an STL <map>is a fine enough balance or a <set>and use those containers as they automatically sort on insertion and deletion and look up is fast but there is the overhead of maintaining the pointers in each entry that increases the size of the memory used compared to vector, if you don't care about this then you could consider these containers.

您也可以决定 STL<map>是一个足够好的平衡或<set>使用这些容器，因为它们在插入和删除时自动排序并且查找速度很快，但是维护每个条目中的指针会增加开销，从而增加了与向量相比使用的内存，如果您不关心这一点，那么您可以考虑这些容器。

Still if it matters then test and profile and compare the performance of each container, you will be surprised by how the code will perform against your assumptions.

尽管如此，如果它很重要，那么测试和分析并比较每个容器的性能，您会惊讶于代码将如何根据您的假设执行。

回答by jalf

If the requirement is just performance, the choice should basically always be a std::vector.

如果要求只是性能，则选择基本上应该始终是std::vector.

It avoids the many memory allocations of node-based data structures (trees and lists), and it exploits spatial locality for much more efficient traversal.

它避免了基于节点的数据结构（树和列表）的许多内存分配，并且它利用空间局部性进行更有效的遍历。

Of course, insertions/removals at the middle of the vector require elements to be moved, but even that is rarely enough to make the vector slower than other data structures.

当然，向量中间的插入/删除需要移动元素，但即使这样也很少足以使向量比其他数据结构慢。

The only real reasons I see for using other data structures are these:

我认为使用其他数据结构的唯一真正原因是：

• std::map/std::set: those are great for convenience. Nice and easy to use, so if optimal perfomance isn't required, I use those when I need a sorted container, or a key/value map. (for best performance, a sorted vector may very well be preferable)
• all other containers: may be useful for the correctness guarantees the offer in the face of modifications: the vector frequently reallocates and moves its contents, which invalidates both pointers and iterators into the vector. The other data structures offer stronger guarantees there (for a deque, pointers are guaranteed to stay valid after after insertion/removal at the ends, but iterators may still be invalidated. For list, setand map, both pointers and iterators are guaranteed to stay valid during insertion/removal)

• std::map/ std::set：这些非常方便。很好且易于使用，因此如果不需要最佳性能，我会在需要排序容器或键/值映射时使用它们。（为了获得最佳性能，排序向量可能更可取）
• 所有其他容器：可能有助于在面临修改时保证提供的正确性：向量经常重新分配和移动其内容，这会使指针和迭代器都无效到向量中。其他数据结构在那里提供了更强的保证（对于 a deque，在末尾插入/删除后，指针保证保持有效，但迭代器可能仍然无效。对于list,set和map，指针和迭代器都保证在插入期间保持有效/移动）

Of course, these are just rules of thumb.

当然，这些只是经验法则。

The only universally true rule when performance is involved is "benchmark it yourself". I can tell you how a vectortypically performs in many common scenarios, but I can't tell you how it performs in yourcode, with yourcompiler and yourstandard library. So if you worry about performance, measure it. Try out the different alternatives, and see which is faster.

涉及性能时唯一普遍适用的规则是“自己进行基准测试”。我可以告诉你 avector在许多常见场景中的典型表现，但我无法告诉你它在你的代码中的表现，你的编译器和你的标准库。因此，如果您担心性能，请对其进行衡量。尝试不同的替代方案，看看哪个更快。

回答by stefaanv

A set is efficient enough to insert/remove/access and it is always sorted. The only thing to consider is that entries in sets are const (so the ordering is not broken), so to change, you should remove, update and insert

一个集合足以插入/删除/访问，并且它总是被排序的。唯一需要考虑的是集合中的条目是常量（因此顺序不会被破坏），因此要更改，您应该删除、更新和插入

回答by johnathan

The answer to your question is completely dependent on your data set size, as a list grows to to huge sizes , the time it takes to do the linear traversal to get to the element you need to remove / insert at far outweighs the time it takes for a vector to do a removal/ insertion. So if your data set is small, go with lists, if it's huge, go with vector.

您的问题的答案完全取决于您的数据集大小，随着列表增长到巨大的大小，进行线性遍历以到达您需要删除/插入的元素所需的时间远远超过所需的时间用于向量进行删除/插入。因此，如果您的数据集很小，请使用列表，如果数据集很大，请使用向量。

回答by Greg Flynn

If it needs to be sorted, use a Binary Search Tree

如果需要排序，使用二叉搜索树