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

Question

我一直在阅读关于C++ STL容器的书籍，尤其是关于STL及其容器的部分。现在我已经理解了它们每个具有自己特定的属性，并且我快要记住它们所有的内容……但我还没有完全理解在哪种情况下使用每个容器。

可以用示例代码来说明吗？

- Daniel

---

你是指map、vector、set等吗？ - Thomas Tempelmann

即使看了这个图表，我也无法确定在我的问题中使用哪一个最好http://stackoverflow.com/questions/9329011/mfc-dictionary-collection-with-key-unicity-and-ordering-by-position - sergiol

我已经创建了一个Mikael的C++容器速查表的可编辑版本。这是@MikaelPersson的速查表。不幸的是，我还没有50个声望值，因此无法在他的答案下发表评论。 - Parker Shamblin

Answer 1

这个速查表提供了不同容器的相当全面的概述。请参考底部的流程图，以了解在不同使用场景中应该使用哪种容器：

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

- zdan

---

这个流程图太棒了，我希望我能在C#中拥有类似的东西。 - Bruno

更新链接：C++容器速查表。 - Bill Door

起始点必须是“向量”，而不是空的。https://dev59.com/BGgv5IYBdhLWcg3wTvE- - eonil

现在有unordered_map和unordered_set（以及它们的多重变体），它们不在流程图中，但当您不关心顺序但需要按键查找元素时，它们是不错的选择。 它们的查找通常是O(1)，而不是O(log n)。 - Aidiakapi

@shuttle87 不仅仅是大小永远不会变化，更重要的是这个大小在编译时就已经确定，并且永远不会改变。 - YoungJohn

Answer 2

这里是我根据 David Moore 版本（参见上文）创作的流程图，它基本符合新标准（C++11）。这仅仅是我的个人看法，不具争议性，但我认为它可能对这个讨论有价值：

- Mikael Persson

---

你能提供原始文件吗？这是一张很棒的图表。也许可以放在博客或GitHub上？ - kevinarpe

这是一张很棒的图表。但是，有人能解释一下“持久位置”是什么意思吗？ - IDDQD

"持久位置"意味着如果你有指向容器中某个元素的指针或迭代器，那么这个指针或迭代器将始终有效(并指向相同的元素)，无论你添加或删除容器中的元素(只要不是所指的那个元素)。 - Mikael Persson

这确实是一个很棒的图表，但我认为“vector (sorted)”与其他部分有点不一致。它并不是一种不同类型的容器，只是已排序的std::vector。更重要的是，如果有序迭代是集合的标准行为，我不明白为什么不能使用std::set进行有序迭代。当然，如果答案谈到通过[]有序访问容器的值，那么你只能使用已排序的std::vector。但无论哪种情况，决策都应该在“需要顺序”问题之后做出。 - RAs

@user2019840 我想将图表限制为标准容器。在“排序向量”的位置应该出现“flat_set”（来自Boost.Container），或者等效的（据我所知，每个主要库或代码库都有一个flat_set等效）。但是这些都是非标准的，而且STL中缺少了这些内容。你不想频繁地遍历std::set或std::map的原因是这样做非常低效（http://lafstern.org/matt/col1.pdf）。 - Mikael Persson

Answer 3

简单回答：除非你有真正的理由，否则请在所有情况下使用std::vector。

当你发现一个情况，你在想：“天啊，因为X，std::vector在这里表现不佳”，那么就基于X去选择其他方法。

- David Thornley

---

然而，要小心在迭代时不要删除/插入项目...尽可能使用const_iterator来避免这种情况发生。 - vrdhn

嗯...我认为人们过度使用向量。原因是，“不起作用”的情况不容易发生 - 所以人们坚持使用最常用的容器并滥用它来存储列表、队列等。在我看来 - 与流程图相符 - 应该根据预期使用选择容器，而不是应用“一个似乎适用于所有”的容器。 - Black

通常情况下，向量化操作即使在理论上应该较慢的操作中也往往更快。 - Bartek Banachewicz

@Vardhan std::remove_if 函数几乎总是优于“迭代期间删除”的方法。 - fredoverflow

一些基准测试会帮助这个讨论变得更客观。 - Felix D.

Answer 4

看看Scott Meyers的Effective STL，它很好地解释了如何使用STL。

如果你想存储一定数量或不确定数量的对象并且不会删除任何一个，那么vector就是你想要的。它是C数组的默认替代品，并且像数组一样工作，但不会溢出。你也可以用reserve()预先设置它的大小。

如果你想存储不确定数量的对象，并且你将添加和删除它们，那么你可能需要一个list...因为你可以删除元素而不移动任何后续元素-不像vector。但它占用的内存比vector多，而且不能顺序访问元素。

如果你想取一堆元素，并只找到这些元素的唯一值，全部读入set中就可以，而且它还会为你排序。

如果你有很多键值对，并且想按键排序，那么map很有用...但它每个键只能持有一个值。如果你需要每个键持有多个值，你可以在map中使用vector/list作为值，或者使用multimap。

虽然不在STL中，但它在STL的TR1更新中：如果你有很多键值对，将通过键进行查找，并且不关心它们的顺序，你可能想使用哈希 - 这是tr1::unordered_map。我在Visual C++ 7.1中使用过它，当时它被称为stdext::hash_map。它的查找时间复杂度是O(1)，而不是map的O(log n)。

- Mark Krenitsky

---

我现在听到了几个轶事，表明微软的hash_map实现并不是很好。我希望他们在unordered_map上做得更好。 - Mark Ransom

关于列表 - “你不能按顺序访问元素。” - 我认为你的意思是你不能直接随机访问或索引到一个元素。 - Tony Delroy

是的，因为顺序访问正是list所做的。那里有一个相当明显的错误。 - underscore_d

Answer 5

我重新设计了流程图，使其具有以下三个特点：

1. 我认为STL容器分为两个主要类别。基本容器和那些利用基本容器实现策略的容器。
2. 首先，流程图应将决策过程分成我们需要决定的主要情况，然后详细阐述每种情况。
3. 一些扩展容器有选择不同的基本容器作为其内部容器的可能性。流程图应考虑可以使用每个基本容器的情况。

流程图：

更多信息见此链接。

- Ebrahim

---

嗯，我认为你的std::array应该改为std::unique_ptr<T[]>。简单概述：vector大小可变，unique_ptr<T[]>在创建时确定大小，而array需要其大小为编译时常量。 - Ben Voigt

Answer 6

迄今为止只简要提到了一个重要的点，即如果需要连续的内存（如 C 数组），那么只能使用 vector、array 或 string。

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

如果您只需要处理字符类型并且需要一个字符串而不是通用容器，请使用 string。

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

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

- Jonathan Wakely

Answer 7

这完全取决于您想要存储什么以及您想要对容器进行什么操作。以下是我经常使用的一些（非常不详尽的）容器类的示例：

- vector：紧凑的布局，每个包含对象很少或没有内存开销。迭代效率高。附加、插入和删除可能很昂贵，特别是对于复杂对象。通过索引查找包含对象很便宜，例如 myVector[10]。在C中使用数组的地方也适用。适用于有大量简单对象（例如 int）的情况。在添加许多对象到容器之前不要忘记使用 reserve()。

- list：每个包含对象的内存开销较小。迭代效率高。附加、插入和删除很便宜。在C中使用链表的地方也适用。

- set（和 multiset）：每个包含对象的内存开销很大。用于需要快速查找该容器是否包含给定对象或有效合并容器的情况。

- map（和 multimap）：每个包含对象的内存开销很大。用于存储键值对并快速按键查找值的情况。

zdan提供的速查表上的流程图提供了更详尽的指南。

- Bids

---

“Small memory overhead per contained object”对于列表来说并不成立。std::list实现为双向链表，因此它维护每个存储对象的2个指针，这是不能忽略的。 - Hanna Khalil

我仍然认为每个存储对象的两个指针是“小”的。 - Bids

相比之下是什么？std::forward_list 是一个容器，主要建议每个对象存储较少的元数据（仅一个指针）。 而 std::vector 每个对象不包含任何元数据。因此，与其他容器相比，2 个指针是不可协商的。 - Hanna Khalil

这完全取决于你的对象大小。我已经说过，向量具有“紧凑布局，每个包含对象几乎没有或没有内存开销”。相比集合和映射，我仍然会说列表具有较小的内存开销，并且比向量略微大一些。老实说，我不太确定你想表达什么观点！ - Bids

所有基于模式的容器由于动态分配而具有显着的开销，这很少是免费的。当然，除非您使用自定义分配器。 - MikeMB

再次强调，这取决于您要存储什么。在我的经验中（主要是处理多GB数据集的3D科学成像应用程序），动态内存分配速度很少成为瓶颈。如果您基于动态内存性能的假设选择STL容器而没有进行分析，则几乎肯定会过早地进行优化。如果您遇到性能问题，需要进行分析以找出瓶颈，然后才开始优化。 - Bids

Answer 8

我在另一个被标记为重复的问题中已经回答了这个问题。但是我觉得引用一些关于选择标准容器的好文章也是很不错的建议。

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

以下是文章链接： https://isocpp.org/blog/2014/06/stroustrup-lists 并且在该文章中引用他的话：

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

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

- CS Pei

Answer 9

我学到的一课是：尽量将它包装成一个类，因为某一天改变容器类型可能会带来很大的惊喜。

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

这不需要很多前期成本，当您想要在此结构上的某些操作时进行断点调试时，可以节省时间。

选择完美的数据结构：

每种数据结构都提供一些操作，其时间复杂度可能会有所不同：

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

您需要猜测哪些操作最常用，并使用具有O(1)操作的数据结构。

简单吧 (-:

- VardhanDotNet

---

难道这不是我们使用迭代器的原因吗？ - Platinum Azure

@PlatinumAzure 即使是迭代器也应该是成员 typedef.. 如果你改变容器类型，你还必须去改变所有的迭代器定义... 不过这在 C++1x 中已经得到了修复！ - vrdhn

对于好奇的人，这是C++11中的修复方法：auto myIterator = whateverCollection.begin(); // <-- 不受容器类型更改的影响 - Black

typedef Collection<Foo*> CollectionOfFoo;够用吗？ - Craig McQueen

你很有可能不能仅仅改变想法并将其委托给另一个容器：警惕容器无关代码的幻觉。 - fredoverflow

Answer 10

我在Mikael Persson精彩的流程图基础上进行了扩展。我添加了一些容器类别、数组容器和一些注释。如果你想要自己的副本，这里是Google绘图。感谢Mikael为我们奠定了基础！ C++容器选择器

- John DiFini