C 该标准提供以下容器或容器配接器：

array是静态连续空间，一旦配置，尺寸不能改变。

是数组，除了缺乏空间灵活性外，还有其他的vector很像。用的少，一般用。vector这里就不多说了。

vector数据安排和操作模式array非常相似。两者唯一的区别在于空间使用的灵活性。

• array一旦配置不能改变，就是静态空间；
• vector它是一个动态空间。随着元素的加入，内部机制将扩大空间以容纳新元素。

vector维护的是连续线性空间，指针是普通指针。

vector<int>::iterator iter; 

那么iter其实就是int*类型。

两个迭代器start和finish它们是连续空间中使用的空间，end_of_storage指向整个连续空间的末端。

为降低频繁空间配置带来的成本，vector实际配置的大小会比客户需求的更大一些，以备将来可能的扩充。这便是capacity的概念。

• [start,finish]是size();
• [start, end_of_storage]是capacity();
• [finish, end_of_storage]是备用空间。

一旦size() == capacity()，满载。下次会有新的元素，整个元素。vector就要另觅他所了。“另觅他所”的过程会经历“重新配置大空间，元素移动，释放原空间”这一系列动作，工程浩大。

所谓的动态增加不是在原始空间后继续新的空间（因为原始空间后不能保证可供配置的空间），而是为了原始空间大小的两倍此外，配置大空间，然后复制原始内容，然后开始在原始内容后面构建新元素，释放原始空间。

因此，对vector一旦空间重新配置，任何操作都指向原始vector所有迭代器都失效了，这是一个常见的错误，一定要小心。

list它是环形双向链表。它的优点是每次插入或删除一个元素时，都会配置或释放一个元素空间和vector相比，list更准确地利用空间，绝不浪费。并且插入或移除任何位置的元素，list永远是常数时间。

vector和list适用场景如下：

• 元素多寡
• 元素的结构复杂性(是否有non-trival copy constructor， non-trival copy assignment operator）
• 元素存取行为的特征

list节点结构如下：

template <class T> struct __list_node{ 
             typedef void* void_pointer;     void_pointer prev;     void_pointer next;     T data; }; 

由于list内存空间不能保证是连续的，此其迭代器不再是普通指针。list迭代器必须有能力指向list并进行正确的递增、递减、取值、成员访问等操作。

list大多数操作不会使迭代器失效。即使删除了操作，也只有指向被删除元素的迭代器失效。

由于list它是一个环形双向链表，所以它只需要一个指针就能完全遍历整个链表。

对于insert操作时，新节点将位于哨兵迭代器(标记插入点)所指节点的前方STL插入操作的标准和规范。

vector是单向开口的连续线性空间，deque它是一个双向开口的线性连续空间。所谓双向开口，就是元素的插入和删除可以头尾两端进行。

deque其实是动态的分段连续空间的组合。然而，在用户看来，这些分段的连续空间确实是整个连续空间，这实际上是deque假象。这种假象是由deque的中控器map(注意，不STL中的map负责维护的容器)。

这个map可以理解为映射，指向一小段连续内存空间，空间中的每个元素都是指针，每个指针都指向deque在连续空间中的某一段。每段默认为512字节。

forward_list是单向链表。

前面说过，对insert操作时，新节点将位于哨兵迭代器(标记插入点)所指节点的前方STL插入操作的标准和规范。

但是forward_list作为一个单向链表，它没有方便的方法回头确定前一个位置，它只能从头开始，所以除了forward_list在起点附近的区域外，在其他位置insert()或erase()很慢，对此，forward_list特别提供了insert_after()和erase_after()。

出于效率考虑，它不提供push_back()，只提供push_front()。

queue是先进先出（FIFO）的数据结构。它有两个出入口，但都是被限制的，尾端只进不出，头端只出不进。除了尾端进，头端出之外，没有其他方法存取queue的其他元素，即queue也是不允许遍历的，自然也就没有迭代器了。

queue也是一种adapter，它同stack一样，默认以deque作为底层结构，list同样也可以做其底层结构。

把deque的头端入口和尾端出口，就成了一个queue。

priority_queue是拥有权值观念的queue。

所谓拥有权值观念，可以理解为有序的，其内的元素并非按照加入的次序排列，而是按照元素的权值排列，权值最高者排在最前边。

默认状态下，priority_queue是用一个大根堆（max-heap）来完成，而大根堆是一个以vector表现得完全二叉树。

大根堆：max-heap，父节点值大于或等于子节点值的完全二叉树；
小根堆：min-heap，父节点值小于或等于子节点值的完全二叉树。

所以，priority_queue是以vector为底层结构，辅以heap处理规则来实现的，所以它也是一种adapter。

priority_queue也不允许遍历，自然也没有迭代器。