如何选择合适的STL容器？

悠悠 2022-07-29 11:56 164阅读 0赞

声明：  
这是个仁者见仁智者见智的事儿，没有正确的答案。只有适合和不适合。

这是在google上扒的一张图，耐心观看：  
![这里写图片描述][20160417121225060]

你肯定听过一本书叫《Effective STL》，我么看看Meyers大师怎么描述的：

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().  
如果只是存储确定或不确定的objects，而不去删除它们，我们可以选用vector。就是因为vector是数组的替代品，是连续内存的，不适合频繁的删除。

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.  
如果频繁的插入和删除，可以选用list。也就是我们所说的链表，内存不是连续的，可以方便的插入和删除，但是不支持索引访问。

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.  
如果是key-value形式的，可以使用map。但是需要注意的是map的key是唯一的。

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  
数据量很大，不在乎他们的排序，那么我们可以选用hash

首先需要明确每个stl容器的数据结构、以及优缺点。

其次是要明确自己对数据的操作，数量确定还是不确定，需不需要频繁的插入和删除，需不要进行排序，需不需要进行快速的查找，以及数据量是什么级别，几千条还是百万级等等。

接下来就是完成自己的工作了。

很多时候，在stl的世界里，只有两种人，一种是使用vector，另一种是使用list。

所有的根源还是在于**数组和链表的区别**：  
连续和非连续  
快速查找和非快速查找  
索引访问和非索引访问  
插入效率低和插入效率高  
删除效率低和删除效率高  
排序效率高和排序效率低

这里补充一下**map和set的区别**：  
说实话，在工作中我从来没有接触过set这个容器。

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.

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.

set（集合）——包含了经过排序了的数据，这些数据的值(value)必须是唯一的。

map（映射）——经过排序了的二元组的集 合，map中的每个元素都是由两个值组成，其中的key（键值，一个map中的键值必须是唯一的）是在排序或搜索时使用，它的值可以在容器中重新获取；而 另一个值是该元素关联的数值。比如，除了可以ar\[43\] = “overripe”这样找到一个数据，map还可以通过ar\[“banana”\] = “overripe”这样的方法找到一个数据。如果你想获得其中的元素信息，通过输入元素的全名就可以轻松实现。

map是映射集合中的元素不能重复，set可以进行集合的各种操作（交并补等），当然你也可以用list或vector实现set，但是效率会很低。set一般是用平衡树或哈西表实现的。  
映射是一种一一对应的关系，哈西表也可以看作是映射的一种。映射通常可用来实现字典结构（dictionary）

综上所述：  
**数据结构是王道**

**明确每个stl容器的数据结构以及优缺点**

**读一些stl的源码**

[20160417121225060]: /images/20220724/9ed11cc387aa4c00b034e02e5e358412.png