在哪种情况下我使用特定的STL容器?

我一直在读我c++书中关于STL容器的内容，特别是关于STL及其容器的部分。现在我明白了每一个都有自己特定的属性，我也快记住它们了……但我还不明白的是，它们分别在哪个场景中使用。

怎么解释呢?最好是示例代码。

79007 次浏览
小开
最佳答案

这个小抄提供了不同容器的很好的摘要。

请参阅底部的流程图，作为在不同使用场景中使用的指南:

http://linuxsoftware.co.nz/containerchoice.png

由David Moore and licensed CC BY-SA 3.0

小开

这完全取决于你想存储什么以及你想用容器做什么。下面是一些我最常用的容器类的例子(非常不详尽):

vector:紧凑的布局，每个包含的对象很少或没有内存开销。有效的迭代。追加、插入和擦除操作的开销可能很大，特别是对于复杂的对象。通过索引查找包含的对象，例如myVector[10]。如果你有很多简单的对象(例如int)，可以使用你在c语言中使用数组的地方。在向容器中添加大量对象之前，不要忘记使用reserve()。

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

set(和multiset):每个包含对象的显著内存开销。在需要快速查找容器是否包含给定对象的地方使用，或者有效地合并容器。

map(和multimap):每个包含对象的显著内存开销。使用您想要存储键-值对和快速按键查找值的位置。

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

小开

看看Scott Meyers的《Effective STL》。它擅长解释如何使用STL。

如果你想存储一个确定或不确定数量的对象，并且你永远不会删除任何对象，那么向量就是你想要的。它是C数组的默认替换，它的工作方式与C数组类似，但不会溢出。您也可以使用reserve()预先设置它的大小。

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

如果你想取一堆元素并且只找到这些元素的唯一值，把它们都读入一个集合就可以了，它也会帮你排序。

如果您有很多键-值对，并且您想按键对它们排序，那么映射是有用的……但是每个键只能保存一个值。如果每个键需要多个值，可以在map中使用vector/list作为值，或者使用multimap。

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

小开

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

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

它的前期成本不高，并且在调试时节省了时间，当有人在这个结构上执行x操作时就会中断。

接下来是为工作选择完美的数据结构:

每个数据结构都提供了一些操作，这些操作可以随时间复杂度变化:

O(1) O(lgn) O(N)等等。

本质上，您必须进行最佳猜测，即哪些操作将被执行最多，并使用具有O(1)操作的数据结构。

很简单，不是吗?

小开

简单的答案:使用std::vector来处理所有事情，除非你有真正的理由这样做。

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

小开

下面是我创建的David Moore版本(见上文)的流程图，它是最新的(大部分)新标准(c++ 11)。这只是我个人的观点，这并不是无可争议的，但我认为这对我们的讨论很有价值:

enter image description here

小开

到目前为止只简单提到的一点是，如果你需要连续的内存(就像C数组那样)，那么你只能使用vector， array，或string。

如果在编译时知道大小，则使用array。

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

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

有了这三种方法，你可以使用data()成员函数来获取指向容器第一个元素的指针。

小开

我扩展了米凯尔佩尔森的奇妙的流程图。我添加了一些容器类别、数组容器和一些注释。如果你想要自己的副本，在这里是谷歌绘图。谢谢你，Mikael做了基础工作! c++容器选择器 < / p >

小开

我重新设计了流程图，有3个属性:

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

操作流程图:enter image description here

更多信息在这个链接中提供。

小开

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

正如@David Thornley回答的那样，如果没有其他特殊需求，std::vector是一种选择。这是c++的创始人Bjarne Stroustrup在2014年的一篇博客中给出的建议。

这里是文章链接 https://isocpp.org/blog/2014/06/stroustrup-lists < / p >

引用这句话，

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

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


提交答案