STL源码剖析: 第4章 序列式容器
4.1 容器的概观与分类
4.2 vector
4.2.1 迭代器
vector的迭代器只是一个指针，因为空间连续，所有的++，–操作都有了，不需要新建类型来重载
4.3 list
双向链表
4.3.1 迭代器
list空间不连续，没法直接进行指针的++，–来达到前一个后一个元素，所以必须设计iterator类，重载++,–，以及operator*()，统一成类指针形式
4.3.2 关键函数解析
在position处连续插入n个值为x的对象
insert(position, n, x)
4.4 deque
4.4.1 迭代器
主要精髓是用了迭代器来做一层封装，迭代器重载了++，–等运算符
1) 在外层看来，用迭代器进行++就能遍历整个deque空间
2) 在内部实现，用了两个迭代器，start 和 finish，
真正的元素数据就存放在[start.cur,finish.cur)之间
其中，每个迭代器维护了4个指针, cur, first, last, node
其中
| 指针 | 含义 |
|---|---|
| cur | 指向实际的数据内存位置 |
| [first,last) | 只是用来指示空间范围，在cur超过这个范围的时候，需要切换到上一个或者下一个node所指向的那边缓存区 |
| node | 指向了map，类型为T**,*node表示元素数据缓存区的起始地址，node本身在map段里是连续的，可以直接++,– |
这样在用户写程序的时候，构造一个迭代器，在迭代器start和finish范围内遍历，实际上就是利用构造的迭代器的cur指针，在[start.cur, finish.cur)，这样就能遍历所有deque空间的元素,用户看起来像是和用vector一样一段连续的空间；
这种遍历，通过对迭代器类重载==, !=来实现，比较迭代器的cur指针是否相同，比如判断是否超出最后一个元素,可以判断user_ite.cur == finish.cur,如果相等则表示确实到达了最后一个元素的下一个元素位置。
4.4.2 内存分布与扩展
4.4.2.1 creat_map_and_nodes
creat_map_and_nodes(size_type num_elements)
参数解析，num_elements表示deque要保存的元素个数
其中node在map居中放置，两端预留空间，如上图map所示，黑节点居中放置
4.4.2.2 reserve_map_at_back
判断map空间是否不足，不足的话换一张新的map，将原来的map里的内容复制到新map的居中位置，同样保留两端的预留空间，然后重新设置迭代器first,和finish，使之和新map对应
iterator _M_reserve_elements_at_back(size_type __n) {
size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1;
if (__n > __vacancies)
_M_new_elements_at_back(__n - __vacancies);
return _M_finish + difference_type(__n);
}
4.4.2.3 reallocate_map
reserve_map_at_back内部判断出后端的map备用空间不够用时，会调用reallocate_map函数
后端map备用空间满足不了用户要求的nodes_to_add个预留空间的需求，但是map还是可能能容纳增加了预留个数的node节点，因为左边可能很空，整体变得很偏右侧，只要调整居中即可，这就是if的由来
4.4.3 insert
其实就是多增加一个元素，然后用前移或者后移覆盖，然后再对指定位置处的元素赋值
4.5 stack
不作为一个容器，而作为一个配接器,本身没有迭代器
4.6 queue
不作为一个容器，而作为一个配接器，本身没有迭代器
4.7 heap
不作为一个容器，只是作为算法，这样隐式的存在,需要配合vector使用
floyd建堆：
总体思想，通过一个节点将两个现有堆进行合并，合成为一个堆
通过根节点连接两个堆，然后对根节点进行下滤调整，使堆合法
实际上，需要从最后一个节点的父节点开始，从后往前，将左右子堆合并，直到根节点，这样，其合并的复杂度为堆中各节点的高度之和，效率为
template <class _RandomAccessIterator, class _Tp, class _Distance>
void
__make_heap(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Tp*, _Distance*)
{
if (__last - __first < 2) return;
_Distance __len = __last - __first;
_Distance __parent = (__len - 2)/2; //找最后一个节点的父节点
while (true) {
__adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
if (__parent == 0) return;
__parent--;
}
}4.8 priority_queue
跟heap差不多，主要增加了可以选择构造大顶堆还是小顶堆
4.9 slist
4.9.1 slist特点
不是STL的标准
单向链表，只能从前往后走
4.9.2 slist迭代器架构
4.9.3 slist end()
end()返回的迭代器永远指向0