# 第4章 序列式容器
## 4.1 容器的概观与分类
根据“数据在容器中的排列“特性，这些数据结构分为序列式（sequence）和关联式（associative）两种。
C++ 语言本身提供了一个序列式容器 array，STL 另外再提供 vector、list、deque、stack、queue、priority-queue 等等序列式容器。其中 stack 和queue 由于只是将 deque 改头换面而成，技术上被归类为一种配接器（adapter）。
## 4.2 vector
array 式静态空间，一旦配置了就不能改变；vector 是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。
vector 使用线性连续空间，它以两个迭代器 `start` 和 `finish` 分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器 `end_of_storage` 指向整块连续空间的尾端：
```c++
template <class T, class Alloc = alloc>
class vector {
protected:
iterator start;
iterator finish;
iterator end_of_storage;
};
```
当以 `push_back()` 函数将元素插入 vector 尾端时，该函数首先检查是否还有备用空间，如果有就直接在备用空间上构造元素，并调整迭代器 `finish`；如果没有备用空间，就扩充空间（重新配置空间、移动数据、释放原空间）。
配置新空间的原则是：如果原大小为0，则配置1，如果不为0，则配置原空间大小的两倍。注意，所谓动态增加大小，并不是在原空间之后接续新空间，而是重新申请了一块空间，所以一旦引起空间重新配置，指向原 vector 的所有迭代器将失效。
## 4.3 list
相较于 vector 的连续空间，list 在每次插入或删除一个元素时，会单独配置或释放一个空间，所以对于每次插入和删除操作均为常数级别耗时。
```c++
template <class T>
struct __list_node {
typedef void* void_pointer;
void_pointer prev;
void_pointer next;
T data;
};
```
SGI list 不仅是一个双向链表，而且还是一个双向链表，所以它只要一个指针即可（node指向刻意置于尾端的一个空白节点，即可满足 STL 的 “前闭后开“要求）：
```c++
template <class T, class Alloc = alloc>
class list {
protected:
typedef __list_node<T> list_node;
list_type node; // 只要一个指针
};
```
## 4.4 deque
deque 是一种双向开口的连续线性空间，即可以在头尾两端分别做元素的插入和删除操作。对 deque 进行的排序操作，为了提高效率，可将 deque 先完整复制到一个vector上，排序后在复制回deque。
deque 采用一块所谓的map作为主控，这里的map是一小块连续空间，其中每个元素都是一个指针，指向另一段连续线性空间，称为缓冲区。缓冲区才是deque的存储空间主体，默认为 512 bytes。
**deque 迭代器**
```c++
template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {
T* cur; // 指向当前缓冲区中的现行元素；
T* first; // 指向但前缓冲区的头；
T* last; // 指向但前缓冲区的尾；
map_pointer node; // 指向管控中心；
};
```
**deque 数据结构**
```c++
template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque {
protected:
iterator start; // 首元素；
iteraotr end; // 尾元素；
map_pointer; // 指向map，即管理中心；
size_type map_size; // map 内有多少个指针，即缓冲区；
};
```
当deque新增元素时，如果缓冲区仍有备用空间，则使用备用空间；否则新增一个缓冲区，并在map（中控）中记录。当map空间不足时，需要为map重新配置一块更大的空间，拷贝原来的数据后释放原空间。
## 4.5 stack
stack 是一种先进后出（First In Last Out，FILO）的数据结构。它允许新增元素、移除元素、取得最顶端元素。SGI STL 便以 deque 作为缺省情况下的 stack 底部结构。stack 不提供走访功能，也不提供迭代器。
## 4.6 queue
queue 是一种先进先出（First In First Out，FIFO）的数据结构。queue允许新增元素、移除元素、从最底端加入元素、取得最顶端元素，不允许有遍历行为。SGI STL 以deque 作为缺省情况下的底部结构。
## 4.7 heap
binary heap 是一种 complete binary tree（完全二叉树）。complate binary 整棵树内没有任何节点漏洞，所以可以使用 array 来储存所有节点。对于某个位于 `i` 位置的节点，其左子节点必位于 `2i` 处，其右子节点必位于 `2i+1` 处，其父节点必位于 `i/2` 处。
heap 底层以 vector作为数据存储的结构。
**push_heap算法**：新加入的元素插入在底层 vector 的 end 处，然后执行一个 `percolate up`（上溯）程序，将新节点拿来与其父节点比较，如果其键值（key）比父节点大，就父子兑换位置。如此一直上溯，直到不需要兑换或直到根节点为止。
**pop_heap算法**：将根节点取走放置vector 尾端的节点，并将原来尾端节点放于根节点，最后执行 percolate down（下溯）程序，将空间节点和其较大子节点对调，并持续下放，直至叶节点为止。然后将之前被割舍（即vector尾端节点）设给这个“已到达叶层的空洞节点“，再对它执行一次上述程序。
`pop_heap` 之后，最大元素只是被置放于底部容器的最尾端，尚未被取走。如果要取值，可使用底部容器（vector）所提供的 `back()` 操作函数。如果要移除它，可使用底部容器所提供的 `pop_back()`。如果持续对整个 heap 做 `pop_heap` 操作，每次将操作范围从后向前缩减一个元素，当整个程序执行完毕时，便得到一个递增序列。
heap 不提供遍历功能，也不提供迭代器。
## 4.8 priority_queue
`priority_queue` 是一个拥有权值观念的 queue，它允许加入新元素、移除旧元素、审视元素值等功能。`priority_queue` 带有权值观念，其内的元素并非依照被推入的次序排列，而自动依照元素的权值排列。权值最高者，排在最前面。
由于 `priority_queue` 完全以底部容器为根据，在加上 heap 处理规则，缺省情况下，以vector为容器。
queue 以底层容器完成其所有工作，具有这种“修改某物接口，行成另一种风貌“，称为adapter（配接器）。
`priority_queu` 不提供遍历功能，也不提供迭代器。
## 4.9 slist
SGI STL 另提供了一个单向链表（single linked list），名为slist。slist 和 list 的主要差别在于前者的迭代器属于单向 Forward Iterator，后者的迭代器属于双向的 Bidirectional Iterator。单向链表所耗用的空间更小，某些操作更快。
