30.STL中的deque的实现

1.deque简介

双端队列deque，与vector的最大差异在于：

1.deque运行常数时间对头端或尾端进行元素的插入和删除操作

2.deque没有所谓的容器概念，因为它是动态地以分段连续空间组合而成随时可以增加一块新的内存空间并拼接起来

虽然deque也提供随机访问的迭代器，但它的迭代器与list和vector的不一样，其设计相当复杂而精妙。因此，会对各种运算产生一定影响，厨房必要，尽可能的选择使用vetor而非deque

2. deque核心类别设计(部分)

3.内存模型

●介绍:

deque在逻辑上看起来是连续的空间，内部确实是一段一段的定量连续空间构成。

一旦有必要在deque的前端或尾端增加新空间，deque会配置一段定量的连续空间，串联在整个deque的头部或尾部。

deque的设计大师最大的调整应该就是如何在这段分段的定量连续空间上还能维护其整体连续的假象，并提供其随机存取的接口，从而避开了像vector那样的“重新配置-复制-释放”开销三部曲。———这样一来，虽然开销降低，却提高了复杂的迭代器架构。

因此，deque数据结构的设计和迭代前进或后退等操作都非常复杂。

deque采用一块所谓的map（注意，不是stl里面的map容器）作为中控器，其实就是一小块连续空间，其中的每一个元素都是指针，指向另外一段较大的连续线性空间，称之为缓冲区。在后面我们将看到，缓冲区才是deque的存储空间主体

●当一个连续的内存块存储满之后first迭代器会重新指向_M_map的下一个内存位置

注:上图表示当前连续块已经存储满
first迭代器的_M_node指针会重新指向 _M_map的下一个连续内存位置

4. deque的构造和析构函数

template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque
{
    ...
public:                         // Basic types
    deque() : start(), finish(), map(0), map_size(0)
    {
        create_map_and_nodes(0);
    }  // 默认构造函数
    deque(const deque& x) : start(), finish(), map(0), map_size(0)
    {
        create_map_and_nodes(x.size());
        __STL_TRY
        {
          uninitialized_copy(x.begin(), x.end(), start);
        }
        __STL_UNWIND(destroy_map_and_nodes());
    }
    // 接受 n:初始化大小, value:初始化的值
    deque(size_type n, const value_type& value) : start(), finish(), map(0), map_size(0)
    {
        fill_initialize(n, value);
    }
    deque(int n, const value_type& value) : start(), finish(), map(0), map_size(0)
    {
        fill_initialize(n, value);
    }
    deque(long n, const value_type& value) : start(), finish(), map(0), map_size(0)
    {
        fill_initialize(n, value);
    }
}

5. deque的插入和删除元素函数

因为deque是能够双向操作，所以其push和pop操作都类似于list，都可以直接有对应的操作，需要注意的是list是链表，并不会涉及到界线的判断，而deque是由数组来存储的，所以需要随时对界限进行判断。
push的实现：

template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque 
{
    ...
public:                         // push_* and pop_*
    // 对尾进行插入
    // 判断函数是否达到了数组尾部. 没有达到就直接进行插入
    void push_back(const value_type& t) 
    {
        if (finish.cur != finish.last - 1) 
        {
            construct(finish.cur, t);
            ++finish.cur;
        }
        else
            push_back_aux(t);
    }
    // 对头进行插入
    // 判断函数是否达到了数组头部. 没有达到就直接进行插入
    void push_front(const value_type& t) 
    {
        if (start.cur != start.first) 
        {
            construct(start.cur - 1, t);
            --start.cur;
        }
        else
            push_front_aux(t);
    }
    ...
};
``

- pop的实行:

```cpp
template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque {
    ...
public:
    // 对尾部进行操作
    // 判断是否达到数组的头部. 没有到达就直接释放
    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();
    }
    ...
};

●pop和push都先调用了reserve_map_at_XX函数，这些函数主要为了判断前后空间是否足够。

删除操作

构造函数都会调用create_map_and_nodes函数，考虑到deque实现前后插入时间复杂度为O(1)，保证了在前后留出了空间，所以push和pop都可以在前面的数组进行操作。

现在来分析erase，因为deque是由数组构成，所以地址空间是连续的，删除也就像vector一样，需要移动所有的元素。

deque为了保证效率尽可能高，就判断删除的位置上中间偏后还是中间偏前来进行移动。

template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque 
{
    ...
public:                         // erase
    iterator erase(iterator pos) 
    {
        iterator next = pos;
        ++next;
        difference_type index = pos - start;
        // 删除的地方是中间偏前, 移动前面的元素
        if (index < (size() >> 1)) 
        {
            copy_backward(start, pos, next);
            pop_front();
        }
        // 删除的地方是中间偏后, 移动后面的元素
        else
        {
            copy(next, finish, pos);
            pop_back();
        }
        return start + index;
    }
    // 范围删除, 实际也是调用上面的erase函数.
    iterator erase(iterator first, iterator last);
    void clear();
    ...
};

●最后说一下insert函数。

deque源码，基本每一个insert重载函数都会调用insert_auto判断插入的位置离头还是尾比较近。

如果离头近，则先将头往前移动，调整将要移动的距离，用copy进行调整。

如果离尾近，则将往前移动，调整将要移动的距离，用copy进行调整。

注意：

push_back则先执行构造再移动node，而push_front是先移动node再进行构造，实现的差异主要是finish是指向最后一个元素的后一个地址，而first指向的是第一个元素的地址，下面pop也是一样的。

deque源码里还有一些其它的成员函数：

reallocate_map：判断中考的容量是否够用，如果不够用，申请更大的空间，拷贝元素过去，修改map和start，finish的指向。

fill_initialize：申请空间，对每个空间进行初始化，最后一个数组单独处理。毕竟最后一个数组一般不会全部填满。

clear：删除所有的元素，分两步执行：

首先，从第二个数组开始到倒数第二个数组一次性全部删除，这样做是考虑到中间的数组肯定都是满的，前后两个数组则不一定是满的，最后删除前后两个数组元素。

deque的swap操作：只是交换了start，finish，map，并没有交换所有的元素。