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的可以在首尾添加元素，也就是两端的内存都需要进行管理。先看一下尾部的内存管理：

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()

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();                 // 判断map头部是否有能力增加新的分段
    *(start.node - 1) = allocate_node();    // 申请新的分段缓冲区
    __STL_TRY {
        start.set_node(start.node - 1);     // 改变start迭代器指向新节点
        start.cur = start.last - 1;         // 设定start迭代器状态
        construct(start.cur,t_copy);        // 构建新元素
    }
    catch(...) {
        // 异常则全部回滚
        ......
        throw;
    }
}
void reserve_map_at_front(size_type nodes_to_add = 1){
    if(nodes_to_add > start.node - map)  // 若map前端的节点备用空间不足，则必须从新换一个map
        reallocate_map(nodes_to_add,true); 
}

1.4.3 删除元素

1.4.3.1 pop_back() & pop_front()

void pop_back() {
    if(finish.cur != finish.first) {        // 如果最后的分段缓冲区不只一个元素
        --finish.cur;                       // 调整迭代器
        destroy(finish.cur);                // 释放对象
    }
    else {                                     // 如果最后的分段只有一个元素
        pop_back_aux();                        // 需要对分段缓冲区空间的释放，此处不再细讲解，为上述的逆过程
    }
}
void pop_front() {
    if(start.cur != start.last - 1) {          // 如果第一缓冲区不只有一个元素
        destroy(start.cur);                    // 直接释放元素
        ++start.cur;                           // 调整迭代器
    }
    else {                                     // 需要释放分段空间
        pop_front_aux();
    }
}

1.4.3.2 erase()

iterator erase(iterator first,iterator last) {
    if(first == start && last == finish) {                                    //整个deque空间的清除
        clear();                                                              //直接调用clear方法
        return finish;
    }
    else {
        difference_type n = last - first;                                    // 清除区间的长度
        difference_type elems_before = first - start;                        // 清除区间前方元素个数
        if(elems_before < (size() - n) / 2) {                                // 如果前方元素比较少
            copy_backward(start,first,last);                                 // 向后移动前方元素（覆盖清除区间）
            iterator new_start = start + n;                                  // 标记新起点
            destroy(start,new_start);                                        // 消除冗余元素

            for(map_pointer cur = start.node; cur < new_start.node; ++cur) {  //释放冗余缓冲区
                data_allocator::deallocate(*cur,buffer_size());
            }    
            start = new_start;                                                // 设定新起点
        }
        else 
        {                                                                    // 如果清除区间后方元素比较少
            copy(last,finish,first);                                          // 前移后方元素
            iterator new_finish = finish - n;                                 // 标记新尾点
            destroy(new_finish,finish);                                       // 消除冗余元素

            for(map_pointer cur = new_finish.node; cur <= finish.node; ++cur) {   // 释放冗余缓冲区
                data_allocator::deallocate(*cur,buffer_size());
            }
            finish = new_finish;                                                // 设定新尾点
        }
        return start + elems_before;
    }
}

iterator erase(iterator position) {
    iterator next = position;
    ++next;
    difference_type elems_before = position - first;                     // 清除区间前方元素个数
    if(elems_before < (size() - n) / 2) {                                // 如果前方元素比较少
            copy_backward(start,position,next);                                 // 向后移动前方元素（覆盖清除区间）
            pop_front();
    }
    else {                                                                // 如果清除区间后方元素比较少
            copy(next,finish,position);                                          // 前移后方元素
            pop_back();
    }
    return start + elems_before;
}

可以看到，在清除元素时，由于两端均可以进行移动，所以deque采取了清除区间左右两侧元素较少的一侧进行移动的策略，然后将多余的空间释放。

1.4.4 insert()

iterator insert(iterator position,const value_type& x) {
    if(position.cur == start.cur) {            // 如果是插入最前端，则
        push_front(x);                         // 交给push_front()
        return start;
    }
    else if(position.cur == finish.cur) {    // 插入最后端，则
        push_back(x);                        // 交给push_back()
        iterator tmp = finish;
        --tmp;
        return tmp;
    }
    else {
        return insert_aux(positon,x);        // 需要元素移动
    }
}
iterator insert_aux(iterator pos,const value_type& x) {
    difference_type index = pos - start;       // 插入点之前的元素个数
    value_type x_copy = x;
    if(index < size() / 2) {                   // 如果插入点之前元素少
        push_front(front());                   // 在最前端加入与第一元素同值的一个元素，目的是改变start迭代器位置，方便之后计算
        iterator front1 = start;               // 标记开头
        ++front1;
        iterator front2 = front1;              // 标记原开头
        ++front2;
        pos = start + index;                   // 由于start已变化，所以重新标记pos位置
        iterator pos1 = pos;                   // 记录pos位置
        ++pos1;
        copy(front2,pos1,front1);              // 将元素前移，空出pos位置
    }  
    else {                                     // 如果插入点之后元素少
        push_back(back());                     // 最后端加入与最后元素同值的一个元素，改变finish迭代器位置，为之后计算
        iterator back1 = finish;               // 标记此时finish位置
        --back1;
        iterator back2 = back1;                // 标记原finish位置
        --back2;
        pos = start + index;                   // 标记pos位置
        copy_backward(pos,back2,back1);        // 元素后移，空出pos位置
    }
    *pos = x_copy;                             // pos位置赋值
    return pos;
}

可以看到，插入时也选取元素少的一端移动，这也是deque独特的操作手法所在。

2.stack容器适配器(adapter)

2.1 stack内存模型

stack是一种先进后出的数据结构，它只有一个出口，因此它的操作也很简单，只能动最后一个元素，推入、弹出、获得最顶端元素，无法获取顶端以外的别的元素，因此也无法遍历。

以某种既有容器作为底部结构，将其接口进行一定修改，使之符合“先进后出”的特性，便可形成一个stack。deque作为一个两端开口的数据结构，若是以deque为底部结构并封闭其头部端口，便是stack，因此STL以deque为stack的底部结构，其功能接口依靠deque提供能力，因此stack是”修改deque接口，形成自身特性“，被称为容器适配器adapter。

2.2 stack的源码剖析

template <class T, class Sequence = deque<T>>
class stack {
    Sequence c;                // deque作为底层容器
    // 借用deque完成容器元素的操作
    bool empty() const {
        return c.empty();
    }
    size_type size() const {
        return c.size();
    }
    reference top() {
        return c.back();
    }
    // 开放末端进行push和pop操作，达到后进先出的效果，对应到deque就是在尾端进行操作
    void push(const value_type& x) {
        c.push_back(x);
    }
    void pop() {
        c.pop_back();
    }
};

不难看出，借助deque的实现，stack的实现变的十分简单。

2.3 stack迭代器

stack只有一个出口，正如上述，无法进行遍历，因此也没有随机访问能力，不需要提供迭代器。

3. queue容器适配器

3.1 queue内存模型

queue是一种先进先出的数据结构，有两个出口，且只允许前端取出元素，后端插入元素，与stack不同的是，它能获得两个元素，一个最先进去的，一个最后进去的，其余元素均无法获取。

同样，queue也是一种容器适配器，以deque为底部结构，并封闭其前端的入口和尾端的出口。

3.2 queue的源码剖析

template <class T, class Sequence = deque<T>>
class queue {
    Sequence c;            // 以duque为底层容器
    // 借用deque完成容器元素的操作
    bool empty() const {
        return c.empty();
    }
    size_type size() const {
        return c.size();
    }
    reference front() {
        return c.front();
    }
    reference back() {
        return c.back();
    }
    // queue为前端出后端入，封装deque的接口
    void push(const value_type& x) {
        c.push_back(x);        // deque的尾端入
    }
    void pop() {
        c.pop_front();        // deque的头端出
    }
};
与stack类似的，借助deque的实现，queue的实现变的十分简单。

3.3 queue迭代器

queue所有元素都符合”先进先出“的条件，不提供遍历功能，也没有迭代器。

4. 面试热点

4.1. vector和deque的区别

【出现频度】★★★

【难度】☆☆

【参考答案】

1. deque两端均能在常数时间完成l插入和删除工作，vector在头部插入元素需要进行后面元素的移动。
2. deque的迭代器需要在不同的缓冲区跳转，较之vector的迭代器更麻烦。（也可从内存分配上：vector是连续线性空间，deque是伪连续线性空间）
3. deque除了两端，在任何位置插入和删除都会使原所有迭代器失效。

4.2 deque的底部实现

【出现频度】★★★

【难度】☆☆☆☆

【参考答案】
主要答出以下几点:

1. 内存模型：伪连续线性空间，通过中控器map进行分段管理
2. 迭代器的运算：迭代器移动时涉及分段的跳转
3. 元素操作：插入、删除相关方法的实现、复杂度等

4.3 stack和queue容器的联系与区别

【出现频度】★★★

【难度】☆☆

【参考答案】