Ps:此文为本人学习《STL源码剖析》的心得,希望能帮助到有需要的人,欢迎大牛指正:)
序列式容器(Sequence Containers)
array
vector
--heap
----priority-queue
list
slist(非标准)
deque
--stack 配接器
--queue 配接器
以内缩的方式来表达基层与衍生层的关系
vector:
vector特征:begin,end,current
各种功能函数就围绕这三个迭代器进行构造,数据移动为单向
扩充空间步骤:配置新空间/移动数据/释放旧空间
list:
通过以结点构造链表。
struct node{
T* pre;
T* next;
size_t date;
}
不支持随机迭代器,所以只能自己构造对应的算法。
deque:
双向开口连续线性空间,与vector单向开口对比理解。
动态地以分段连续空间组成,而非vector那样(上文提及)工程浩大。
复杂度较高,尽可能使用vector,而非deque。
该容器实质并非连续存储,是通过适当的中控器构成的假象。该中控器为一个T** map(非关联式容器),指向不同的T* node,最终由node指向缓冲区。看图之后更能理解,请自行google或看书。迭代器是有两个,start和finish。主要内部功能如下:
struct __deque_iterator{
T* first;
T* cur;
T* last;
...
}
整个容器便是通过中控器map以及两个迭代器构成。
接下来的内容为配置器。配置器,就是通过以上的容器,改装成新特性的数据结构
stack:
特性:FILO(先进后出,也是我们所说的栈)
通过封闭某些容器的头端开口,达到该效果,缺省情况下,以deque为底部结构,书本上也有list为底部结构的例子。
queue:
特性:FIFO(First In First Out),不允许有遍历行为。
底层容器:list,deque
heap:
不属于STL的容器组件。以complete binary tree(完全二叉树)构成,图请自行google。
通过一定规则可轻易形成comlete binary tree。以array 为例,我们一颗利用array来存储所有节点。将array的0#元素保留(最大值或最小值),那么当complete binary tree的某个节点为主array的i处,其左子节点必位于array的2i处,其有节点则位于2i+1,
其父节点必位于“i/2”(取其整数)。
由于array无法动态改变大小,vector是更好的选择。
若heap经过sort排序就不再是合法的heap。
priority_queue:
缺省情况下,利用一个max-heap完成,经过pop所有元素,得到一个“依权值高低自动递减排序”的特性配置器。
slist:
对比list容器,该容器非只是单向,利用价值不大。
学习方法:
以客户端程序代码引导,通过观察实验结果并实证其源码,是一个良好的学习路径。