现在的位置: 首页 > 综合 > 正文

序列型容器

2018年02月11日 ⁄ 综合 ⁄ 共 1210字 ⁄ 字号 评论关闭

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容器,该容器非只是单向,利用价值不大。



学习方法:

以客户端程序代码引导,通过观察实验结果并实证其源码,是一个良好的学习路径。

【上篇】
【下篇】

抱歉!评论已关闭.