在什么情况下我需要使用特定的 STL 容器？
我一直在阅读有关 C++ 的书中有关 STL 容器的内容，特别是有关 STL 及其容器的部分。 现在我确实明白它们中的每一个都有自己特定的属性，并且我已经接近记住所有它们......但我还不掌握的是它们中的每一个都在什么场景中使用。
解释是什么？ 示例代码是更受欢迎的。
I've been reading up on STL containers in my book on C++, specifically the section on the STL and its containers. Now I do understand each and every one of them have their own specific properties, and I'm close to memorizing all of them... But what I do not yet grasp is in which scenario each of them is used.
What is the explanation? Example code is much prefered.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（10）
此备忘单提供了一个漂亮的对不同容器的很好的总结。
请参阅底部的流程图，作为在不同使用场景中使用的指南：
由 David Moore 和 许可 CC BY-SA 3.0
This cheat sheet provides a pretty good summary of the different containers.
See the flowchart at the bottom as a guide on which to use in different usage scenarios:
Created by David Moore and licensed CC BY-SA 3.0
这是受我创建的 David Moore 版本（见上文）启发的流程图，该流程图（大部分）与新标准 (C++11) 保持同步。 这只是我个人的看法，并非无可争议，但我认为这对本次讨论很有价值：
Here is a flowchart inspired by David Moore's version (see above) that I created, which is up-to-date (mostly) with the new standard (C++11). This is only my personal take on it, it's not indisputable, but I figured it could be valuable to this discussion:
简单的答案：使用
std::vector来处理所有事情，除非你有真正的理由不这样做。当您发现某个案例时您会想，“哎呀，由于 X，std::vector 在这里无法正常工作”，请以 X 为基础。
Simple answer: use
std::vectorfor everything unless you have a real reason to do otherwise.When you find a case where you're thinking, "Gee,
std::vectordoesn't work well here because of X", go on the basis of X.查看 Scott Meyers 的《Effective STL》。 它很好地解释了如何使用STL。
如果您想存储确定/不确定数量的对象并且永远不会删除任何对象，那么向量就是您想要的。 它是 C 数组的默认替代品，其工作原理与数组类似，但不会溢出。 您也可以使用 Reserve() 预先设置其大小。
如果您想存储不确定数量的对象，但要添加和删除它们，那么您可能需要一个列表......因为您可以删除一个元素而不移动任何后续元素 - 与向量不同。 但是，它比向量需要更多的内存，并且您无法顺序访问元素。
如果您想获取一堆元素并仅查找这些元素的唯一值，将它们全部读入一个集合中就可以做到，并且它也会为您对它们进行排序。
如果你有很多键值对，并且你想按键对它们进行排序，那么映射很有用......但它只会为每个键保存一个值。 如果每个键需要多个值，则可以使用向量/列表作为映射中的值，或使用多重映射。
它不在STL中，但在STL的TR1更新中：如果你有很多键值对，你要通过键查找，并且你不关心它们的顺序，你可能会想要使用哈希 - tr1::unordered_map。 我在 Visual C++ 7.1 中使用了它，它被称为 stdext::hash_map。 它的查找时间为 O(1)，而不是 Map 的查找时间为 O(log n)。
Look at Effective STL by Scott Meyers. It's good at explaining how to use the STL.
If you want to store a determined/undetermined number of objects and you're never going to delete any, then a vector is what you want. It's the default replacement for a C array, and it works like one, but doesn't overflow. You can set its size beforehand as well with reserve().
If you want to store an undetermined number of objects, but you'll be adding them and deleting them, then you probably want a list...because you can delete an element without moving any following elements - unlike vector. It takes more memory than a vector, though, and you can't sequentially access an element.
If you want to take a bunch of elements and find only the unique values of those elements, reading them all into a set will do it, and it will sort them for you as well.
If you have a lot of key-value pairs, and you want to sort them by key, then a map is useful...but it will only hold one value per key. If you need more than one value per key, you could have a vector/list as your value in the map, or use a multimap.
It's not in the STL, but it is in the TR1 update to the STL: if you have a lot of key-value pairs that you're going to look up by key, and you don't care about their order, you might want to use a hash - which is tr1::unordered_map. I've used it with Visual C++ 7.1, where it was called stdext::hash_map. It has a lookup of O(1) instead of a lookup of O(log n) for map.
我重新设计了流程图，使其具有 3 个属性：
流程图：
中提供的更多信息此链接。
I redesigned the flowchart to have 3 properties:
The flowchart:
More info provided in this link.
到目前为止仅简要提到的一个要点是，如果您需要连续的内存（如 C 数组提供的那样），那么您只能使用
vector、array或>字符串。如果编译时大小已知，则使用数组。
如果您只需要使用字符类型并且需要一个字符串，而不仅仅是一个通用容器，请使用
string。在所有其他情况下使用矢量（无论如何，矢量应该是大多数情况下容器的默认选择）。
通过所有这三个，您可以使用
data()成员函数来获取指向容器第一个元素的指针。An important point only briefly mentioned so far, is that if you require contiguous memory (like a C array gives), then you can only use
vector,array, orstring.Use
arrayif the size is known at compile time.Use
stringif you only need to work with character types and need a string, not just a general-purpose container.Use
vectorin all other cases (vectorshould be the default choice of container in most cases anyway).With all three of these you can use the
data()member function to get a pointer to the first element of the container.这完全取决于您想要存储什么以及您想要使用容器做什么。 以下是我最常使用的容器类的一些（非常非详尽的）示例：
vector：紧凑布局，每个包含的对象很少或没有内存开销。 迭代效率高。 追加、插入和删除的成本可能很高，特别是对于复杂的对象。 通过索引查找包含的对象很便宜，例如 myVector[10]。 在 C 中使用数组的地方使用。在有很多简单对象（例如 int）的地方很好。 在向容器添加大量对象之前，不要忘记使用reserve()。list：每个包含的对象的内存开销较小。 迭代效率高。 追加、插入和删除都很便宜。 在 C 中使用链表的地方使用。set（和multiset）：每个包含的对象会产生大量内存开销。 在您需要快速找出该容器是否包含给定对象的地方使用，或者有效地合并容器。map（和multimap）：每个包含的对象会产生大量内存开销。 使用您想要存储键值对的位置并通过键快速查找值。zdan 建议的 cheatsheet 上的流程图提供了更详尽的信息指导。
It all depends on what you want to store and what you want to do with the container. Here are some (very non-exhaustive) examples for the container classes that I tend to use most:
vector: Compact layout with little or no memory overhead per contained object. Efficient to iterate over. Append, insert and erase can be expensive, particularly for complex objects. Cheap to find a contained object by index, e.g. myVector[10]. Use where you would have used an array in C. Good where you have a lot of simple objects (e.g. int). Don't forget to usereserve()before adding a lot of objects to the container.list: Small memory overhead per contained object. Efficient to iterate over. Append, insert and erase are cheap. Use where you would have used a linked list in C.set(andmultiset): Significant memory overhead per contained object. Use where you need to find out quickly if that container contains a given object, or merge containers efficiently.map(andmultimap): Significant memory overhead per contained object. Use where you want to store key-value pairs and look up values by key quickly.The flow chart on the cheat sheet suggested by zdan provides a more exhaustive guide.
我学到的一个教训是：尝试将其包装在一个类中，因为在一个晴朗的日子更改容器类型可能会产生巨大的惊喜。
它的前期成本并不高，并且当您想在有人对此结构执行 x 操作时中断时，可以节省调试时间。
为作业选择完美的数据结构：
每种数据结构都提供一些操作，这些操作的时间复杂度可能有所不同：
O(1)、O(lg N)、O (N) 等。
您本质上必须采取最好的方法猜测哪些操作将被执行最多，并使用该操作为 O(1) 的数据结构。
很简单，不是吗（-：
One lesson I've learned is: Try to wrap it in a class, since changing the container type one fine day can yield big surprises.
It doesn't cost much up front, and saves time in debugging when you want to break whenever somebody does operation x on this structure.
Coming to selecting the perfect data structure for a job:
Each data structure provides some operations, which can be varying time complexity:
O(1), O(lg N), O (N), etc.
You essentially have to take a best guess, on which operations will be done most, and use a data structure which has that operation as O(1).
Simple, isn't it (-:
我在另一个问题中回答了这个问题，该问题被标记为这个问题的重复。 但我觉得参考一些关于选择标准容器的决定的好文章是很好的。
正如@David Thornley 回答的那样，如果没有其他特殊需求，std::vector 是可行的方法。 这是 C++ 创始人 Bjarne Stroustrup 在 2014 年博客中给出的建议。
这是文章的链接
https://isocpp.org/blog/2014/06/stroustrup-lists
并引用那句话，
在评论中，用户@NathanOliver 还提供了另一个很好的博客，其中有更具体的测量。 https://baptiste-wicht.com/ posts/2012/12/cpp-benchmark-vector-list-deque.html 。
I answered this in another question which is marked as dup of this one. But I feel that it is nice to refer to some good articles regarding the decision to choose a standard container.
As @David Thornley answered, std::vector is the way to go if there are no other special needs. This is the advice given by the creator of C++, Bjarne Stroustrup in a 2014 blog.
Here is the link for the article
https://isocpp.org/blog/2014/06/stroustrup-lists
and quote from that one,
In the comments, user @NathanOliver also provides another good blog, which has more concrete measurements. https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html .
我扩展了 Mikael Persson 精彩的流程图。 我添加了一些容器类别、数组容器和一些注释。 如果您想要自己的副本，此处是 Google 绘图。 谢谢 Mikael 所做的基础工作！
C++ 容器选择器
I expanded on Mikael Persson's fantastic flowchart. I added some container categories, the array container, and some notes. If you'd like your own copy, here is the Google Drawing. Thanks, Mikael for doing the groundwork!
C++ Container Picker