c++ STL之 Dequeue

原创
2014/07/10 13:46
阅读数 936

dequeue

deque是一种双向开口的连续线性空间,是一种分段连续空间,  deque是有一段一段的定量连续空间构成,采用一块所谓的map(当然不是map容器)作为主控。map是一小块连续空间,其中每一个元素都是一个指针,指向另一段连续性空间(缓冲区)。缓冲区才是deque的储存空间主体。我们可以指定缓冲区大小,默认值0表示使用512字节缓冲区。

 deque除了维护map的指针外,也要维护start,finish两个迭代器,分别指向第一缓冲区的第一个元素和最后缓冲区的最后一个元素(的下一个位置)。此外,它还要记录当前map的大小,因为当map结点不够的时候,需要另外配置一个更大的map

push_back():当最后缓冲区有两个(含)以上的空间,直接在缓冲区增加新元素;当最后缓冲区只剩一个备用空间时,push_back()调用push_back_aux(),先配置一个新的缓冲区,然后再在那个仅剩的备用空间定义新元素,并更改finish的状态,令其指向新结点。

push_front():当第一缓冲区有备用空间时,直接在备用空间增加新元素;当第一缓冲区无备用空间时,调用push_front_aux()配置新结点(缓冲区),增加新元素,并改变start状态。

pop_back():当最后缓冲区有一个(含)以上元素,就将finish向前移一位并将最后那个元素析构掉;当最后缓冲区没有任何元素,就调用push_pop_aux()将这个缓冲区释放。解释一下:第一种情况finish指向最后缓冲区的first位置,第二种情况finish指向最后第二个缓冲区的last位置。

pop_front():第一缓冲区有两个(含)以上元素,将第一个元素析构,将start后移;否则,将这个缓冲区释放,start指向下一个缓冲区第一个元素。

clear():deque的最初状态(即无任何元素时)保有一个缓冲区,因此clear()之后也一样要保留一个缓冲区,finish=start。

erase():先判断清除空间前后元素个数,移动较少一端。

insert():若在最前端,即push_front(),最后端类似;判断插入点前后元素个数,移动较少的一端

与stack、queue、list、vector的关系

stack是一种先进后出(FILO)的数据结构,它只有一个出口。deque是双向开口的数据结构,所以SGI STL便以deque作为缺省情况下的stack底部结构,封闭其头端开口。stack没有迭代器,所以除了顶部元素,无法存取其它元素,即不能遍历stack。

stack的成员函数都是针对其顶部元素进行操作:push(),pop(),top()。

queue是一种先进先出(FIFO)的数据结构,它有两个出口。queue也是以deque作为底部结构,封闭其底端的出口和前端的入口。queue,只有顶端(两端)的元素能被外部使用,所以queue也没有迭代器,不提供遍历功能。

queue的成员函数有:front(),back(),push(),pop()。


vector


 向量 相当于一个数组, SGI版本使用malloc
在内存中分配一块连续的内存空间进行存储。支持不指定vector大小的存储。STL内部实现时,首先分配一个非常大的内存空间预备进行存储,即capacituy()函数返回的大小,当超过此分配的空间时再整体重新放分配一块内存存储,这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。
优点:

(1) 不指定一块内存大小的数组的连续存储,即可以像数组一样操作,但可以对此数组进行动态操作。通常体现在push_back() pop_back()
(2) 随机访问方便,即支持[ ]操作符和vector.at()
(3) 节省空间。
缺点:

(1) 在内部进行插入删除操作效率低。
(2) 只能在vector的最后进行push和pop,不能在vector的头进行push和pop。
(3) 当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释放


list


双向链表 

每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。
优点:

(1) 不使用连续内存完成动态操作。
(2) 在内部方便的进行插入和删除操作
(3) 可在两端进行push、pop
缺点:

(1) 不能进行内部的随机访问,即不支持[ ]操作符和vector.at()
(2) 相对于verctor占用内存多


deque


 双端队列 double-end queue
deque是在功能上合并了vector和list。
优点:

(1) 随机访问方便,即支持[ ]操作符和vector.at()
(2) 在内部方便的进行插入和删除操作
(3) 可在两端进行push、pop
缺点:

(1) 占用内存多

使用区别:


1 如果你需要高效的随即存取,而不在乎插入和删除的效率,使用vector 
2 如果你需要大量的插入和删除,而不关心随即存取,则应使用list 
3 如果你需要随即存取,而且关心两端数据的插入和删除,则应使用deque

内部实现:


1. vector: 内部实现是数组,一段连续的内存。
2. list, 内部实现是双链表
3. deque 内部实现是内存块的链表。
4. string: 连续的内存
5. set,map: 红黑树(平衡二叉树的一种)
6. hash_map, hash_set 用哈希表(散列表)来实现。
7. stack: 用vector或者是deque来实现
8. queue,用deque实现


参考: http://www.cnblogs.com/biyeymyhjob/archive/2012/07/22/2603525.html

http://blog.csdn.net/moooxin/article/details/16941771

http://www.cnblogs.com/alionxd/articles/3028711.html



展开阅读全文
打赏
0
1 收藏
分享
加载中
更多评论
打赏
0 评论
1 收藏
0
分享
返回顶部
顶部