【温故而知新】C和C++5:STL容器技术综述

容器类是可以包含其他对象的类。STL中提供的较为常用的容器类有向量、链表、队列、集合和图等，每一种容器类都是一个模板，可以包含各种类型的对象。这些容器可以分为序列式和关联式两大类。

序列式容器主要有：

1、vector：向量类，可以认为是一种容量可变的数组，可以提供对元素的随机访问，而且可以在序列尾部快速插入和删除数据，并且在需要的时候可以方便地改变容器的大小；

2、list：双向链表类，不支持随机访问的数组类，遍历链表的元素需要从某个端点开始向前或向后遍历；

3、queue：队列，实现先进先出的功能。使用deque和list实现。所有元素占用连续存储控件，但是不能提供随机存取；

4、stack：栈容器，实现先进后出功能。使用vector、list和deque实现；

5、deque：双端队列，实现数据的先进先出功能，可以随机访问；

6、priority_queue：按值排序的队列容器，使用vector和deque创建了排序队列，依照优先级决定下一个元素。

关联式容器的数据存储按照顺序进行，其余序列式容器不同的地方在于使用关键字查找元素，主要分类有：

1、set：集合，该容器中的关键字和数据是同一个值因此不能包含相同元素；由于各个元素经过了排序，因此不能直接修改其中的元素，只能删除后重新添加；

2、multiset：多重集合，同set类似，区别在于可以包含相同元素；

3、map：映射类，由一组键值对组成的集合，每一个键只能与一个特定的值相联系，且不能存在重复的键；

4、multimap：多重映射类，同map类似，区别在于可以存在重复的键；

5、hash table：散列表，通常可以用于大数据搜索。

一、向量容器vector：

向量容器vector是STL提供的最简单的容器之一，可以提供类似数组的随机访问功能，此外比数组更强大之处在于可以方便地动态调整容器的容量。由于vector的存储结构是顺序存储，因此虽然vector可以在任意位置增删数据，但是只有在末尾进行操作时效率最高。vector类定义在头文件<vector.h>中。

vector定义了两个最常用的成员：

其他成员可参照相关文档；

二、双端队列deque：

一种动态数组的形式，可以高效率地向两端增删数据，同时在需要时可以动态地调整大小。deque类定义在<deque.h>中。

deque类完全继承自其基类，没有添加派生成员，其所有的变量和方法定义在随机接入容器random access、前向插入序列front insertion sequence、反向插入序列back insertion sequence中。

与vector相比，deque除了可以方便地使用push_back()在末尾添加数据之外，也可以使用push_front()在头部添加数据。

三、链表list：

list实现了双向链表功能。由于list采用链式存储结构，因此不支持随机存取，但是其优点是在链表的任何位置插入和删除元素都非常迅速。list结构定义在<list.h>中。

list类主要继承自双向容器Reversible、前向插入序列front insertion sequence和反向插入序列back

insertion sequence。此外还定义了多种自有方法，如splice/remove/unique/merge/reverse/sort等，具体可以查看官方文档。

以上三类是STL提供的基本容器，除此之外STL还在这些基本容器的基础上提供了stack、queue、priority_queue、slist等容器，分别实现了栈、队列、优先级队列和双向迭代链表等功能。其使用方法大同小异，具体可搜索官方文档。

四、关联式容器：

set、map等关联式容器相比于序列式应用稍少一些。从总的思想上来看，序列式容器可以认为是数组、链表等结构的扩展，倾向于以排列的形式组织数据；而关联式容器通常没有这种先后继的关系，更倾向于一种集合的形式，因此可以处理更加复杂的数据结构。具体各个类的方法可以参考官方文档。

ps：看到这里，感觉STL跟Objective-C中的Foundation Framework有些神似的感觉……