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

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


当前回答

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

其他回答

看看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)操作的数据结构。

很简单,不是吗?

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

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

简单的回答是:对所有东西都使用std::vector,除非你有真正的理由不这么做。

当你遇到这样的情况,你会想,“哎呀,std::vector因为X的原因在这里不能很好地工作”,那就以X为基础。