好贷网好贷款

序列型容器

发布时间:2016-12-5 18:31:21 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"序列型容器",主要涉及到序列型容器方面的内容,对于序列型容器感兴趣的同学可以参考一下。

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容器,该容器非只是单向,利用价值不大。 学习方法: 以客户端程序代码引导,通过观察实验结果并实证其源码,是一个良好的学习路径。

上一篇:Spring获取WebApplicationcontext,ApplicationContext几种方法详解
下一篇:OJ_1096

相关文章

关键词: 序列型容器

相关评论