C++ 我在哪种情况下使用特定的 STL 容器？

In which scenario do I use a particular STL container?

提问by Daniel Sloof

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.

我一直在我关于 C++ 的书中阅读 STL 容器，特别是关于 STL 及其容器的部分。现在我确实了解它们中的每一个都有自己的特定属性，而且我已经接近记住所有这些......但我还没有掌握的是它们各自在哪种情况下使用。

What is the explanation? Example code is much prefered.

解释是什么？示例代码更受欢迎。

回答by zdan

This cheat sheetprovides 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 Mooreand licensed CC BY-SA 3.0}

_{由David Moore创建并获得 CC BY-SA 3.0 许可}

回答by Mikael Persson

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:

这是一个受我创建的 David Moore 版本（见上文）启发的流程图，它是最新的（大部分）与新标准 (C++11)。这只是我个人的看法，并非无可争议，但我认为这对本次讨论可能很有价值：

回答by David Thornley

Simple answer: use std::vectorfor everything unless you have a real reason to do otherwise.

简单的答案：std::vector除非你有真正的理由不这样做，否则使用一切。

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.

当你发现一个你在想“哎呀，std::vector因为 X 在这里工作不好”的情况时，请以 X 为基础。

回答by Mark Krenitsky

Look at Effective STL by Scott Meyers. It's good at explaining how to use the STL.

看看 Scott Meyers 的 Effective STL。它很好地解释了如何使用 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().

如果您想存储确定/未确定数量的对象并且永远不会删除任何对象，那么向量就是您想要的。它是 C 数组的默认替代品，它的工作原理类似，但不会溢出。您也可以使用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.

它不在 STL 中，但在 STL 的 TR1 更新中：如果您有很多键值对要按键查找，并且不关心它们的顺序，则可能想使用一个散列——它是 tr1::unordered_map。我在 Visual C++ 7.1 中使用过它，在那里它被称为 stdext::hash_map。它查找 O(1) 而不是查找 O(log n) 的 map。

回答by Ebrahim

I redesigned the flowchart to have 3 properties:

我重新设计了流程图，使其具有 3 个属性：

1. I think STL containers are devided to 2 main classes. The basic containers and those leverages the basic containers to implement a policy.
2. At first the flowchart should divide the decision process to the main situations we should decide on and then elaborate on each case.
3. Some extended containers have the possibility of choosing different basic container as their inner container. The Flowchart should consider the situations in which each of the basic containers can be used.

1. 我认为 STL 容器分为 2 个主要类。基本容器和那些利用基本容器来实施策略的容器。
2. 首先，流程图应该将决策过程划分为我们应该决定的主要情况，然后对每个案例进行详细说明。
3. 一些扩展容器可以选择不同的基本容器作为其内部容器。Flowchart 应该考虑可以使用每个基本容器的情况。

The flowchart:

流程图：

More info provided in this link.

此链接中提供了更多信息。

回答by Jonathan Wakely

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, or string.

到目前为止只简要提到的一个要点是，如果您需要连续内存（如 C 数组提供），那么您只能使用vector, array, 或string。

Use arrayif the size is known at compile time.

array如果在编译时已知大小，请使用。

Use stringif you only need to work with character types and need a string, not just a general-purpose container.

使用string，如果你只需要使用字符类型的工作，需要一个字符串，而不是只是一个通用的容器。

Use vectorin all other cases (vectorshould be the default choice of container in most cases anyway).

使用vector在所有其他情况下（vector应该是在大多数情况下，默认选择容器的反正）。

With all three of these you can use the data()member function to get a pointer to the first element of the container.

通过所有这三个，您可以使用data()成员函数来获取指向容器第一个元素的指针。

回答by Bids

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 use reserve()before adding a lot of objects to the container.

vector：紧凑的布局，每个包含的对象几乎没有内存开销。高效迭代。追加、插入和擦除可能很昂贵，尤其是对于复杂对象。通过索引查找包含的对象很便宜，例如 myVector[10]。在 C 中使用数组的地方使用。在有很多简单对象（例如 int）的地方很好。reserve()在向容器中添加大量对象之前不要忘记使用。

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.

list：每个包含对象的内存开销很小。高效迭代。追加、插入和擦除都很便宜。在 C 语言中使用链表的地方使用。

set(and multiset): 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.

set（和multiset）：每个包含对象的显着内存开销。在需要快速确定该容器是否包含给定对象或有效合并容器的地方使用。

map(and multimap): Significant memory overhead per contained object. Use where you want to store key-value pairs and look up values by key quickly.

map（和multimap）：每个包含对象的显着内存开销。使用要存储键值对的位置并快速按键查找值。

The flow chart on the cheat sheetsuggested by zdan provides a more exhaustive guide.

zdan 建议的备忘单上的流程图提供了更详尽的指南。

回答by vrdhn

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.

我学到的一个教训是：试着把它包装在一个班级中，因为在一个晴朗的日子改变容器类型会产生很大的惊喜。

class CollectionOfFoo {
    Collection<Foo*> foos;
    .. delegate methods specifically 
}

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.

它不会预先花费太多，并且当您想在有人在此结构上执行操作 x 时中断时节省调试时间。

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.

O(1)、O(lg N)、O(N) 等。

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).

您基本上必须做出最佳猜测，对哪些操作将执行得最多，并使用该操作为 O(1) 的数据结构。

Simple, isn't it (-:

很简单，是不是 (-:

回答by John DiFini

I expanded on Mikael Persson'sfantastic flowchart. I added some container categories, the array container, and some notes. If you'd like your own copy, hereis the Google Drawing. Thanks, Mikael for doing the groundwork! C++ Container Picker

我扩展了Mikael Persson 的奇妙流程图。我添加了一些容器类别、数组容器和一些注释。如果您想要自己的副本，这里是 Google 绘图。谢谢，Mikael 做了基础工作！ C++ 容器选择器

回答by CS Pei

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.

我在另一个问题中回答了这个问题，该问题被标记为 dup of this one。但是我觉得参考一些关于选择标准容器的决定的好文章是很好的。

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.

正如@David Thornley 回答的那样，如果没有其他特殊需求， std::vector 是可行的方法。这是 C++ 的创建者 Bjarne Stroustrup 在 2014 年的博客中给出的建议。

Here is the link for the article https://isocpp.org/blog/2014/06/stroustrup-lists

这是文章的链接 https://isocpp.org/blog/2014/06/stroustrup-lists

and quote from that one,

并引用那个人的话，

And, yes, my recommendation is to use std::vector by default.

而且，是的，我的建议是默认使用 std::vector。

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.

在评论中，用户@NathanOliver 还提供了另一个不错的博客，里面有更具体的测量。https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html。