STL-deque

deque概述

deque是一个双向开口的线性连续空间，简单的说，deque是一个双端队列，在头尾两端都可以进行插入和删除的操作。

其实，vector也可以在头部进行操作，但是其效率很差，deque和vector最大的差别就在于deque能够在线性时间内在其头部进行插入和删除操作。其次，由于deque设计成的是以分段的连续空间组合而成，随时可以增加一段新的空间连接进来，所以，它就不会像vector那样存在一旦旧的空间不足，就需要重新配置一块更大的空间，然后复制元素并释放旧的空间。正是因为这种设计，造成了deque的迭代器设计很复杂，影响到了其运算层面的效率。在实际使用中，能使用vector都尽量使用vector。

deque总体结构

由于deque的设计是将分段的连续空间组合起来，那么肯定有一个将这些分段的空间连接起来的控制器，实质上，这个控制器就是一个指针数组，数组的每一项都指向一段连续的空间，称之为缓冲区，如下图所示：

如果map的空间用完了，那么只需要重新分配一个map，然后将其指向各个缓冲区即可，无需对每个缓冲区进行操作。

看一下deque的数据结构的定义：

    template<typename Tp, typename Allocator=allocator<Tp>, size_t BufSiz = 0>
    class deque
    {
    public:
        typedef Tp                 value_type;
        typedef Tp*                pointer;
        typedef Tp&                reference;
        typedef const Tp&          const_reference;
        typedef deque_iterator<Tp, Tp*, Tp&, BufSiz>  iterator;
        typedef deque_iterator<Tp, const Tp*, const Tp&, BufSiz>  const_iterator;
        typedef size_t             size_type;
        typedef ptrdiff_t                   difference_type;
        typedef Tp**               map_pointer;
        typedef allocator<Tp>          allocator_type;
        typedef allocator<Tp*>         map_allocator_type;

    protected:
        iterator       start;
        iterator       finish;
        Tp**           mmap;
        size_type      map_size;
        allocator_type  data_allocator;
        map_allocator_type map_allocator;

        enum { E_initial_map_size = 8 };
    }

定义中，二级指针mmap就是控制器，BufSiz是指缓冲区的大小，默认大小为512。

deque迭代器设计

由于deque是分段的连续空间，要维护其“连续空间”的假象，其最重要的任务就落在了迭代器的设计上，主要在于operator++和operator–的实现。

deque的迭代器该如何设计呢？首先，需要知道当前处于哪一块缓冲区，迭代器处于当前缓冲区的哪个位置；其次，还要知道当前是否处于缓冲区的边界，这样，一个插入或者删除就会导致从当前缓冲区跳转到临近的缓冲区，要实现缓冲区间的跳转，迭代器必须要掌控控制器（map）。

看一下deque迭代器的结构：

    template<typename Tp, typename Ptr, typename Ref, size_t BufSiz>
    struct deque_iterator
    {
        typedef deque_iterator<Tp, Tp*, Tp&, BufSiz> iterator;
        typedef deque_iterator<Tp, const Tp*, const Tp&, BufSiz> const_iterator;
        typedef Tp                          value_type;
        typedef Ptr                         pointer;
        typedef Ref                         reference;
        typedef ptrdiff_t                   difference_type;
        typedef size_t                      size_type;
        typedef random_access_iterator_tag  iterator_category;

        typedef Tp**       map_pointer;

        typedef  deque_iterator    self;

        map_pointer   node;
        Tp*           cur;
        Tp*           first;
        Tp*           last;
    }

结构中node指明了当前处于哪一段缓冲区，cur指明了在当前缓冲区的哪个位置，first和last分别为当前缓冲区的起点和终点，用于判断是否临界。deque中控制器、迭代器和缓冲区的关系如下图所示：

deque中的迭代器start和finish就指向当前deque的首尾位置。

再来看一下迭代器中关键的operator++的实现：

void set_node(map_pointer new_node)
{
    node = new_node;
    first = *new_node;
    last = first + buffer_size();
}

self& operator++()
{
    ++cur;
    if (cur == last)
    {
        set_node(node + 1);
        cur = first;
    }
    return *this;
}

从代码中看，执行了++cur之后，需要判断是否当前缓冲区已经用完，如果已经用完，则需要跳转到下一个缓冲区，通过函数set_node()来实现，同时将cur置为下一缓冲区的头。同理，operator–的实现也是如此：

self& operator--()
{
    if (cur == first)
    {
        set_node(node - 1);
        cur = last;
    }
    --cur;

    return *this;
}

deque内存管理

至于deque的内存管理，主要从push_back和push_front的两个函数的操作说起，先说push_back：
情形1：如果当前deque的内部存储如下图所示，这时，需要执行push_back(22)，很简单，因为这时当前缓冲区后面还有两个备用元素，直接在其后面一个置上22即可；

情形2：上面执行push_back(22)后如下图：

这时如果需要执行push_back(23)的操作，虽然后还有一个备用元素，但是这个备用元素用完后，当前的缓冲区也就用完了，就需要重新配置一块缓冲区，因为迭代器finish永远指向的是最后一个元素的下一个，这是finish就需要指向下一个缓冲区的头部了。

再来看push_front，和push_back类似，在上述基础上如果需要执行push_front(24)，由于当前缓冲区已经用完，所以也需要重新分配一块缓冲区，如下图所示：

情形3：其实还有一种情况，就是当前的map所对应的所有缓冲区都已经用完了，如下图所示，这个时候就需要重新分配一块更大的map，然后将原来的缓冲区都连接到新的map上来。

具体如何进行重新分配，可以看代码：

        void reallocate_map(size_t nodes_to_add, bool add_to_front)
        {
            size_t old_nodes_num = finish.node - start.node + 1;
            size_t new_nodes_num = old_nodes_num + nodes_to_add;
            map_pointer new_start;

            if (map_size > 2 * new_nodes_num)
            {
                new_start = mmap + (map_size - new_nodes_num)/2 + (add_to_front ? nodes_to_add : 0);
                if (new_start < start.node)
                {
                    std::copy(start.node, finish.node + 1, new_start);
                }
                else
                {
                    std::copy_backward(start.node, finish.node + 1, new_start + old_nodes_num);
                }
            }
            else
            {
                size_t new_map_size = map_size + std::max(nodes_to_add, map_size) + 2;
                map_pointer new_map = allocate_map(new_map_size);
                new_start = new_map + (new_map_size - new_nodes_num) / 2 + (add_to_front ? nodes_to_add : 0);
                std::copy(start.node, finish.node + 1, new_start);
                destroy_nodes(start.node, finish.node);
                deallocate_map(mmap, map_size);
                mmap = new_map;
                map_size = new_map_size;
            }

            start.set_node(new_start);
            finish.set_node(new_start + old_nodes_num - 1);
        }

if的内容是一个重新分配的判断，如果map的前端满了，但是后端还有比较大的空间未用，那么就重新调整当前的map和缓冲区的映射关系，尽量使前后的未用空间差不多平衡。重点看else的部分，从代码中可以看到，在重新分配了一块map之后，通过一个copy的操作就将原来的缓冲区重新连接到新的map上了，然后重新设置start和finish迭代器即可。

再看一下push_back函数的实现：

void push_back(const value_type& value)
{
    if (finish.cur != finish.last - 1)
    {
        construct(finish.cur, value);
        ++finish.cur;
    }
    else
    {
        push_back_aux(value);
    }
}

其中if中的内容就是上面说的情形1的情况，再看push_back_aux

void push_back_aux(const value_type& value)
{
    reserve_map_at_back();
    construct(finish.cur, value);
    *(finish.node + 1) = allocate_nodes(0);
    finish.set_node(finish.node + 1);
    finish.cur = finish.first;
}

void reserve_map_at_back(size_t nodes_to_add = 1)
{
    if (mmap + map_size - finish.node < (1 + nodes_to_add))
    {
        reallocate_map(nodes_to_add, false);
    }
}

push_back_aux函数中首先判断是否属于情形3，如果是的话，则调用reallocate_map重新分配map，然后按照情形2进行操作。push_front的操作也是类似的，主要代码如下：

void push_front(const value_type& value)
{
    if (start.cur != start.first)
    {
        --start.cur;
        construct(start.cur, value);
    }
    else
    {
        push_front_aux(value);
    }
}

void push_front_aux(const value_type& value)
{
    reserve_map_at_front();
    *(start.node - 1) = allocate_nodes(0);
    start.set_node(start.node - 1);
    start.cur = start.last - 1;
    construct(start.cur, value);
}

void reserve_map_at_front(size_t nodes_to_add = 1)
{
    if (start.node - mmap < (1 + nodes_to_add))
    {
        reallocate_map(nodes_to_add, true);
    }
}