C++ STL 之 deque

转载地址：http://our2848884.blog.163.com/blog/static/146854834201169102525501/

2.1 deque简介

deque是双向开口的连续性存储空间。虽说是连续性存储空间，但这种连续性只是表面上的，实际上它的内存是动态分配的，它在堆上分配了一块一块的动态储存区，每一块动态存储去本身是连续的，deque自身的机制把这一块一块的存储区虚拟地连在一起。

它首次插入一个元素，默认会动态分配512字节空间，当这512字节空间用完后，它会再动态分配自己另外的512字节空间，然后虚拟地连在一起。deque的这种设计使得它具有比vector复杂得多的架构、算法和迭代器设计。它的性能损失比之vector，是几个数量级的差别。所以说，deque要慎用。

2.2 deque数据结构

deque是连续线性空间。但这种连续不同于数组和vector的连续，deque只是逻辑上的连续空间，它把一块一块独立的空间逻辑地连在一起，仿佛整个deque空间是一块完整的连续空间，让我们来看一下deque的数据结构，了解deque是怎么做到这一点的。

template<class _Ty, class _A= allocator<_Ty> > 
class deque 
{ 
    ... 
protected: 
    iterator _First, _Last; 
    _Mapptr _Map; 
    size_type _Mapsize, _Size; 
};

我们发现这里有一个_Map成员变量。大家注意，这可不是STL中的map。这个_Map是一个指针，指向一块特殊的内存地址，这里保存着指向deque动态申请的所有512字节内存空间的首地址。deque先用一段小的连续空间顺序存放了一个一个指针，然后这些顺序存放的指针再各自指向用来真正存放数据的512字节连续性空间。当_Map指向的这块空间不够存放内存指针的时候，就会另觅一块更大的连续性空间，然后把指针一个一个复制过去，并销毁旧的空间。利用这种数据结构，deque就能方便地模拟自身的存储区是连续性空间的假象，并且可以实现双向插入删除的功能。deque没有vector所谓的容量的概念。我们看一下deque的数据结构图，如图1所示。

 

deque通过一套复杂的机制实现了双向开口的连续性空间，增加了编程灵活性，但是也降低了效率。所以一定要慎用deque。

2.3 stack和queue

用于STL中的stack和queue都是建立在deque数据结构基础上的，所以我们再来看看stack和queue。

2.3.1 栈stack

它是一种先进后出（First In Last Out）的数据结构。因为stack不允许对容器的遍历操作，所以stack没有迭代器。只能通过压栈和出栈的办法存取stack中的元素。

2.3.2 队列

它是一种先进先出（First In First Out）的数据结构。因为queue不允许容器的遍历操作，所以queue没有迭代器，只能通过queue的最顶端和最低端操作数据。