C++ STL 容器
在 C++ 中，容器就是保存其他对象的对象，STL 容器即是将运用最广的一些数据结构实现出来。不同的容器有其特定的数据结构和操作算法，常见的容器数据结构包括：数组（array）、链表（list）、树（tree）、栈（stack）、队列（queue）、散列表（hash table）、集合（set）、映射（map）等等。
STL 容器
在实际的开发过程中，数据结构本身的重要性不会逊于操作于数据结构的算法的重要性，当程序中存在着对时间要求很高的部分时，数据结构的选择就显得更加重要。经典的数据结构数量有限，但是我们常常重复着一些为了实现向量、链表等结构而编写的代码，这些代码都十分相似，只是为了适应不同数据的变化而在细节上有所出入。
STL 容器就为我们提供了这样的方便，它允许我们重复利用已有的实现构造自己的特定类型下的数据结构，通过设置一些模版类，STL容器对最常用的数据结构提供了支持，这些模板的参数允许我们指定容器中元素的数据类型，可以将我们许多重复而乏味的工作简化。
容器部分主要由头文件 <vector>, <list>, <deque>, <set>, <map>, <stack> 和 <queue> 组成。对于常用的一些容器和容器适配器（可以看作由其它容器实现的容器），下表对这些容器做了大致的总结。
| 容器 | 类名 | 描述 |
|---|---|---|
| 向量 | vector | 连续存储的元素。 |
| 列表 | list | 由节点组成的双向链表，每个结点包含着一个元素。 |
| 双队列 | deque | 连续存储的指向不同元素的指针所组成的数组。 |
| 集合 | set | 由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元素对的谓词排列，没有两个不同的元素能够拥有相同的次序。 |
| 多重集合 | multiset | 允许存在两个次序相等的元素的集合。 |
| 栈 | stack | 后进先出的值的排列。 |
| 队列 | queue | 先进先出的执的排列。 |
| 优先队列 | priority_queue | 元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列。 |
| 映 射 | map | 由 {key, value} 键值对组成的集合，以某种作用于键对上的谓词排列。 |
| 多重映射 | multimap | 允许键对有相等的次序的映射。 |
根据数据在容器中的排列特性，这些数据结构可分为序列式和关联式两种。
图：SGI STL 的各种容器，以内缩方式来表达基层和衍生层的关系
序列式容器
序列式容器（Sequential Containers）中的元素都可序的（ordered），但未必有序（sorted）。例如 array 就是 C++ 语言内置的一个序列式容器 ，STL 则提供了 vector、list、deque、stack、queue、priority-queue 等序列式容器。其中，stack、queue 是在 deque 的基础上修改而成，技术上归为一种适配器（adapter）。
适配器是标准库中的一个通用概念，容器、迭代器和函数都有适配器。本质上，一个适配器是一种机制，能使某种事物的行为看起来像另外一种事物一样。
关联式容器
关联式容器（Associative Containers）在概念上与关联式数据库类似，每个元素都有一个键值（key）和一个实值（value）。当元素被插入到关联式容器中时，容器内部结构便依照其键值大小，以某种特定规则将这个元 素放置于适当位置。
标准的 STL 关联式容器分为 map（映射表）和 set（集合）两大类，以及衍生体 multiset（多键集合）和 multimap（多键映射表），底层均为 RB-Tree（红黑树完成）。
- map 中的元素是一些“关键字-值”对（key-value），关键字起到索引的作用，值则表示与索引相关联的数据。
- set 中每个元素只包含一个关键字，set 支持高效的关键字查询操作 —— 检查一个给定关键字是否在 set 中。
标准库提供了 8 个关联容器，体现在三个不同的维度：
- 或者是一个 map，或者是一个 set；
- 允许关键字重复，或者不允许；
- 按照顺序保存元素，或者无序保存。
具体情况如下表：
