http://www.360doc.com/content/12/0705/08/6828497_222338600.shtml
容器（container）是装有其他对象的对象。容器里面的对象必须是同一类型，该类型必须是可拷贝构造和可赋值的，包括内置的基本数据类型和带有公用拷贝构造函数和赋值操作符的类。典型的容器有队列、链表和向量等。
在标准C++中，容器一般用模版类来表示。不过STL不是面向对象的技术，不强调类的层次结构，而是以效率和实用作为追求的目标。所以在STL并没有一个通用的容器类，各种具体的容器也没有统一的基类。
容器可以视为是数组的推广，即对象的数组（广义数组），其中的元素（对象）可以用下标（索引）来访问。
容器的设计有两条准则：一是在各个容器的设计中，提供尽可能大的自由度；二是使各 种容器能够向用户呈现出一个公共的界面/接口。目的是，使容器的实现能达到最佳效率，同时也使用户能写出不依赖于所使用的特定容器类型的通用代码。容器的 设计通常只能满足这两条中的一条，但是STL却提供了一个同时具有通用性和执行效率的解决方案。
标准C++的STL框架中的容器主要有两大类：
l 序列容器（sequence container顺序容器）—— 将一组具有相同类型T的对象，以严格的线性形式组织在一起。序列容器可以视为数组和链表的推广。STL中的序列容器有3种：
n vector<T>（向量）——提供对变长序列的快速随机访问 （即对第i个元素的访问时间，是与i无关的常量），对序列末尾的插入和删除操作的时间是分摊常量；（似变长数组）（对应于vector类，定义在<vector>头文件中）；
n deque<T>（double-ended queue双端队列）—— 提供对变长序列的快速随机访问，对序列头尾的插入和删除操作的时间都是分摊常量；（似双向变长数组）（对应于deque类，定义 在<deque>头文件中）；
n list<T>（表）—— 提供对变长序列的线性时间访问（O(N)，N为序列的当前长度），但是在序列的任意位置的插入和删除操作均为常量时间。（似双向链表）（对应于list类，定义在<list>头文件中）。
l 关联容器（associative container联合容器）—— 关联容器的特点是（键）有序的，即元素是按预定义的键顺序（如升序）插入的。关联容器具有从基于键的集 合中快速提取对象的能力，其中集合的大小在运行时是可变的。关联容器可以视为关联数组、映射或字典的推广，它们保存的都是值的对偶，给定了其中的一个被称
为键（key）的值，就可以快速访问与其对偶的另一个被称为映射值（mapped value）的值。STL中的关联容器有4种：
n set<Key>（集合）—— 支持唯一键值，并提供对键本身的快速检索；例如set<long>：{学号}（对应于set类，定义在<set>头文件中）；
n multiset<Key>（多重集合）—— 支持可重复键值，并提供对键本身的快速检索；例如set<string>：{姓名}（可能有同名的）（对应于multiset类，也定义在<set>头文件中）；
n map<Key, T>（映射/映像）—— 支持唯一Key类型的键值，并提供对另一个基于键的类型T的快速检索；例如map<long, string>：{(学号, 姓名)}、{(电话号码, 姓名)}等（对应于map类，定义在<map>头文件中）；
n multimap<Key, T>（多重映射）—— 支持可重复Key类型的键值，并提供对另一个基于键的类型T的快速检索；例如map<string, string>：{(姓名, 地址)}、{(姓名, 年龄)}等（对应于multimap类，也定义在<map>头文件中）。
为了改进搜索的时间，有些编译器(包括VC2005)增加了4种对应的散列（hash）关联容器类型：
n hash_set<Key, H>（散列集）（对应于hash_set类，定义在<hash_set>头文件中）
n hash_multiset<Key, H>（散列多集）（对应于hash_multiset类，也定义在<hash_set>头文件中）
n hash_map<Key, T, H>（散列映射）（对应于hash_map类，定义在<hash_map>头文件中）
n hash_multimap<Key, T, H>（散列多映射）（对应于hash_multimap类，也定义在<hash_map>头文件中）
除了这两大类容器外，STL还有另外两大类容器：
l 容器适配器（container adapter）—— 不是独立的容器，只是某种容器的变种，它提供原容器的一个专用的受限接口。特别是，容器适配器不提供迭代器。在STL中有3种容器适配器：
n stack<T>（栈）—— 只支持top()（读取栈顶元素）、push()（在栈顶处加入新元素）和pop()（取出栈顶元素）操作（先入后出）的一种序列容器。可以是对任意一种 序列容器（缺省为双端队列deque）的限制实现：删除非栈操作，将原来序列容器的标准操作back()、push_back()和pop_back() 重新命名为top()、push()和pop()。（对应于stack类，定义在<stack>头文件中）；
n queue<T>（队列）—— 与stack类似，queue也是对序列容器（缺省也为双端队列deque）的限制实现。与栈相比，队列也支持back()（读取队尾处的元素）和 push_back()（在队尾处插入新元素）操作，但是不再支持pop_back()（取出队尾处的元素）操作。不过，队列却允许front()（读取 队首处的元素）和pop_front()（取出队首处的元素）操作（前出后入）。由于矢量vector容器不支持pop_front()操作，所以不能作
为队列queue的基础容器。与前后都可出入的双端队列deque相比，队列queue缺少push_front()和pop_back()操作。（对应 于queue类，定义在<queue>头文件中）；
n priority_queue<T>（优先队列）—— 也是一种队列queue，不过其中的每个元素都被给定了一个优先级，用来控制元素到达队首top()的顺序。默认情况下，优先队列简单地使用运算 符<进行元素比较，top()返回最大的元素。注意，优先队列，并不要求其全部元素都是有序的，而只要求其第一个元素是最大的。（对应于 priority_queue类，也定义在<queue>头文件中）。
l 似容器（almost container拟容器）—— 在许多情况下可视为容器，但是又缺乏标准容器界面的某些方面和特性，不能与开发完全的容器进行全面互换。除了内置数组外，STL中的似容器有3种：
n string（串）—— 是实例化模版类basic_string<char>的类型定义typedef（另一个常用的wstring类，则是实例化模版类 basic_string<wchar_t>的类型定义typedef）。基本串basic_string提供下标操作、随机访问迭代器和其 他序列容器的几乎所有功能，但是它不像容器那样支持广泛的元素类型选择，而且它还为作为字符串使用而进行了优化，所以其典型使用方式与容器有着显著差
异。（对应于string类，定义在<string>头文件中）。有关string的更详细内容，会在本节后面的4.3）中介绍；
n valarray<T>（值数组）—— 是为数值计算而进行了优化的向量，并不是一个具有通用性的容器。valarray提供了许多有用的数值运算和常用的数学函数，但是它只提供了标准容器操作 中的size()和下标操作，此外，其中元素的指针是一种随机迭代器。（对应于valarray类，定义在<valarray>头文件中）；
n bitset<N>（位集）—— 是标志位字段的扩展，它通过提供在N个二进制位的集合（下标0~N-1）上的各种操作，使对标志位的运算更为方便。bitset可视为一个N位的二进制 数，位取值0/1代表真假或开关，每一位从低位向高位进行编号。（对应于bitset类，定义在<bitset>头文件中）。
STL是C/C++开发中一个非常重要的模板，而其中定义的各种容器也是非常方便我 们大家使用。下面，我们就浅谈某些常用的容器。这里我们不涉及容器的基本操作之类，只是要讨论一下各个容器其各自的特点。STL中的常用容器包括：顺序性 容器（vector、deque、list）、关联容器（map、set）、容器适配器（queue、stac）。
1、顺序性容器
（1）vector
vector是一种动态数组，在内存中具有连续的存储空间，支持快速随机访问。由于具有连续的存储空间，所以在插入和删除操作方面，效率比较 慢。vector有多个构造函数，默认的构造函数是构造一个初始长度为0的内存空间，且分配的内存空间是以2的倍数动态增长的，即内存空间增长是按照20,21,22,23..... 增长的，在push_back的过程中，若发现分配的内存空间不足，则重新分配一段连续的内存空间，其大小是现在连续空间的2倍，再将原先空间中的元素复
制到新的空间中，性能消耗比较大，尤其是当元素是非内部数据时(非内部数据往往构造及拷贝构造函数相当复杂)。vector的另一个常见的问题就是 clear操作。clear函数只是把vector的size清为零，但vector中的元素在内存中并没有消除，所以在使用vector的过程中会发现 内存消耗会越来越多，导致内存泄露，现在经常用的方法是swap函数来进行解决： vector<int> V;
V.push_back(1); V.push_back(2);V.push_back(1); V.push_back(2);
vector<int>().swap(V); 或者 V.swap(vector<int>());
利用swap函数，和临时对象交换，使V对象的内存为临时对象的内存，而临时对象的内存为V对象的内存。交换以后，临时对象消失，释放内存。
（2）deque
deque和vector类似，支持快速随机访问。二者最大的区别在于，vector只能在末端插入数据，而deque支持双端插入数据。 deque的内存空间分布是小片的连续，小片间用链表相连，实际上内部有一个map的指针。deque空间的重新分配要比vector快，重新分配空间 后，原有的元素是不需要拷贝的。
（3）list
list是一个双向链表，因此它的内存空间是可以不连续的，通过指针来进行数据的访问，这使list的随机存储变得非常低效，因此list没有提供[]操作符的重载。但list可以很好地支持任意地方的插入和删除，只需移动相应的指针即可。
（4）在实际使用时，如何选择这三个容器中哪一个，应根据你的需要而定，一般应遵循下面的原则：
1) 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
2) 如果你需要大量的插入和删除，而不关心随即存取，则应使用list
3) 如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque
2、关联容器
（1）map
map是一种关联容器，该容器用唯一的关键字来映射相应的值，即具有key-value功能。map内部自建一棵红黑树（一种自平衡二叉树），这棵树具有数据自动排序的功能，所以在map内部所有的数据都是有序的，以二叉树的形式进行组织。这是map的模板：
template < class Key, class T, class Compare= less<Key>, class Allocator=allocator< pair<const Key,T> > > class map;
从模板中我们可以看出，再构造map时，是按照一定的顺序进行的。map的插入和删除效率比其他序列的 容器高，因为对关联容器来说，不需要做内存的拷贝和移动，只是指针的移动。由于map的每个数据对应红黑树上的一个节点，这个节点在不保存你的数据时，是 占用16个字节的，一个父节点指针，左右孩子指针，还有一个枚举值（标示红黑色），所以map的其中的一个缺点就是比较占用内存空间。
（2）set
set也是一种关联性容器，它同map一样，底层使用红黑树实现，插入删除操作时仅仅移动指针即可，不涉及内存的移动和拷贝，所以效率比较高。 set中的元素都是唯一的，而且默认情况下会对元素进行升序排列。所以在set中，不能直接改变元素值，因为那样会打乱原本正确的顺序，要改变元素值必须 先删除旧元素，再插入新元素。不提供直接存取元素的任何操作函数，只能通过迭代器进行间接存取。set模板原型：
template <class Key, class Compare=class<Key>, class Alloc=STL_DEFAULT_ALLOCATOR(Key) > class set;
set支持集合的交(set_intersection)、差(set_difference)、并(set_union)及对称差(set_symmetric_difference) 等一些集合上的操作。
3、容器适配器
（1）queue
queue是一个队列，实现先进先出功能，queue不是标准的STL容器，却以标准的STL容器为基础。queue是在deque的基础上封 装的。之所以选择deque而不选择vector是因为deque在删除元素的时候释放空间，同时在重新申请空间的时候无需拷贝所有元素。其模板为：
template < TYPENAME _Sequence="deque<_TP" typeneam _Tp,> > class queue;
（2）stack
stack是实现先进后出的功能，和queue一样，也是内部封装了deque，这也是为啥称为容器适配器的原因吧（纯属猜测）。自己不直接维护被控序列的模板类，而是它存储的容器对象来为它实现所有的功能。stack的源代码原理和实现方式均跟queue相同。