1. deque——双向队列容器

1.deque的内存模型

如图1-1所示，deque的内存模型与vector极为相似，是一种双向开口的连续线性容器。由于deque可在头尾两端进行元素的插入和删除操作，因此被称为双向队列。vector虽然也可在头部进行此操作，但需要将所有元素向后移动，因此效率很差；而deque可在常数时间复杂度在头部进行元素的插入和删除。

图1-1 deque的前后插入图解

stack和queue是在deque的基础上进行了包装，实际调用的也是deque的函数接口。因此，首先对deque容器进行深入的剖析。

1.2 deque中控器

不难发现，deque与vector最本质的差别在于，vector的内存增长只能向后增长，而deque可以双向增长。为了实现双向增长，deque以动态地分段连续空间组合而成，随时可以增加一段新的空间并链接起来。这赋予了deque没有容量限制的特性，同时分段连续空间较之vector少了所谓的新旧空间配置和释放问题，可以灵活配置空间。但随之而来的就是复杂的中央控制，来对多个deque的分段枢纽管理。

因此，deque逻辑上来看是连续空间，其实是分段连续空间，通过中控器将各个分段进行链接，从而造成这种整体连续假象。

如图1-2所示：map作为deque的中控器，管理了4段连续空间，使得用户感知不到分段，而是整体连续。

图1-2 deque的中控器图解

1.3 deque迭代器

deque作为连续分段空间，如何维持迭代器的连续性，需要对operator++与operator--两个运算进行特殊处理：

图1-3 deque的迭代器图解

如图1-3所示，deque迭代器iterator包含四个要素，cur指向当前分段的现行元素，first指向当前分段缓冲区的头部，last指向当前分段缓冲区的尾部，node指向当前的map节点。

• 1. 首先，通过迭代器中的node成员判断出缓冲区在中控器的位置;
• 2. 其次，通过迭代器中的cur成员判断出当前元素在分段缓冲区的位置；
• 3. 最后，在进行operator++与operator--时进行顺序移动或跳跃动作。

以上图举例，当4要operator++到5时，由于4已经在当前缓冲区的尾部，所以需先通过中控器map先找到下一节点，然后切换到下一节点进行操作。

deque迭代器源码如下所示：

struct __deque_iterator {
    ……
    T *cur;						// 指向当前分段缓冲区的现行元素指针
    T *first;   				   // 指向当前分段缓冲区的头部指针
    T *last;				   	// 指向当前分段缓冲区的尾部指针
    map_pointer node;			  // 指向中控器节点的指针
    
    /**
     * 缓冲区切换函数
     * 参数为中控器节点指针
     */
    void set_node(map_pointer new_node) {
        node = new_node;  // 中控器指针指向新缓冲区
        first = *new_node;									// first指向当前缓冲区的头部
        last = first + difference_type(buffer_size());		// last指针指向缓冲区尾部 头部+缓冲区大小=当前缓冲区的尾部
    }
    
    // 实现解引用操作符 返回cur指针的指向对象
    reference opeartor*() const {
        return *cur;
    }
    
    // 实现解指针操作成员方法 依靠解引用操作符
    pointer operator->() const {
        return &(operator*());
    }
    
    // 实现前缀自增操作符
    self& operator++() {
        ++cur;							// cur指针指向下一元素
        if(cur == last)				   // 如果到达此缓冲区末尾
        {
            set_node(node + 1);		   // 切换至下一缓冲区
            cur = first;				  // cur指针设置为新缓冲区的头部
        }
        return *this;
    }

    // 实现后缀自增操作符
    self operator++(int) {				
        self tmp = *this;
        ++*this;   // 借助前缀自增操作符实现
        return tmp;
    }

    // 实现前缀自减操作符
    self& operator--() {
        if(cur == first)				// 如果此时在缓冲区的头部
        {
            set_node(node - 1);		 // 切换到上一缓冲区的末尾
            cur == last;				
        }
        --cur;						  // 向前移动一个元素
        return *this;
    }

    // 实现后缀自减操作符
    self operator--（int）{				// 后置式
        self tmp = *this;
        --*this;
        return tmp;
    }
};

上述代码为迭代器的实现，deque容器维护了start和finish两个迭代器，start指向第一个分段缓冲区的第一个元素；finish指向最后分段缓冲区的最后一个元素的下一位置。

class deque {
    iterator start;		 // 开始迭代器，指向首部分段缓冲区，其中cur指向头部元素
    iterator finish;		// 结束迭代器，指向尾部分段缓冲区，其中cur指向尾部元素后面的一个元素
    
    map_pointer map;		// 中控器指针
    
    size_type map_size;	 // 标识map内有多少个分段缓冲区
    
    iterator begin() {	  // 获取首部分段缓冲区迭代器
        return start;
    }

    iterator end() {		// 获取尾部分段缓冲区迭代器的后一位置
        return finish;
    }

    size_type size() {	  // 通过迭代器的减法操作计算deque中的元素个数
        return finish - start;
    }

    bool empty() const {	// 起点==终点则为空
        return finish == start;
    }
};

1.4 deque的元素操作源码剖析

1.4.1 尾插push_back()

函数项	说明
函数功能	用于在deque容器尾部插入一个元素
参数	1.待插入的元素
返回值	void
时间复杂度	O(1)

由于deque的可以在首尾添加元素，也就是两端的内存都需要进行管理。先看一下尾部的内存管理：

void push_back(const value_type& t) {
    // finish迭代器指向中控器的最后一个分段缓冲区
    if(finish.cur != finish.last - 1) {		// 如果尾部分段缓冲区还有大于2个空间，即当前节点指针非last-1时
        construct(finish.cur,t);		   	// 在当前节点构造元素
        ++finish.cur;				      	// 调整finish迭代器 cur指针向后移 
    }
    else {
        push_back_aux(t);				  	// 如果尾部分段缓冲区没有足够空间 则需要新增缓冲区
    }
}

// 向中控器扩展缓冲区
void push_back_aux(const value_type& t) {
    value_type t_copy = t;						
    reserve_map_at_back();			   	// 判断map尾部是否还有能力增加新的分段
    // 此时，finish迭代器指向当前中控器的最后一个分段缓冲区
    *(finish.node + 1) = allocate_node();	// finish.node+1则在尾部向后再申请一个新分段缓冲区
    __STL_TRY {
        construct(finish.cur,t_copy);		// 在当前节点构造插入的对象
        finish.set_node(finish.node + 1);	// 改变finish迭代器，指向新的尾部分段缓冲区
        finish.cur = finish.first;		   // 调整finish的cur节点为first节点
    }
    catch(...) {
        // 异常则全部回滚
        ......
        throw;
    }
}

// 向中控器尾部预留分段缓冲区
void reserve_map_at_back(size_type nodes_to_add = 1)
{
    if(nodes_to_add + 1 > map_size - (finish.node - map))  // 若中控器map尾端的节点备用空间不足，则必须重新分配一个中控器map
        reallocate_map(nodes_to_add,false); 
}

如图所示：在进行尾插元素8时，首先判断当前分段缓冲区最后有两个及以上备用空间，若有空间则直接在当前分段构造元素，调整迭代器即可。否则需要向中控器申请增加分段缓冲区：

1.4.2 头插push_front()

函数项	说明
函数功能	用于在deque容器头部插入一个元素
参数	1.待插入的元素
返回值	void
时间复杂度	O(1)

void push_front(const value_type& t) {
    if(start.cur != start.first) {			 // 判断头部分段是否有两个及以上备用空间
        construct(start.cur - 1,t);			// 有备用空间，直接构造元素
        --start.cur;					   	// 调整迭代器状态
    }
    else {
        push_front_aux(t);					 // 没有备用空间，申请新分段
    }
}

void push_front_aux(const value_type& t) {
    value_type t_copy = t;
    reserve_map_at_front();