4.4-deque

deque 允许在常数时间内对头尾两端进行元素的插入或删除操作，deque 没有容量的概念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来

deque 系由一段一段的定量连续空间构成。一旦有必要在 deque 的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个 deque 的头端或尾端。deque 的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。避开了“重新配置、复制、释放”的轮回，代价则是复杂的迭代器架构

deque 采用一块所谓的 map 作为主控。这里所谓 map 是一小块连续空间，其中每个元素（node）都是指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是 deque 的储存空间主体。SGI STL允许我们指定缓冲区大小，默认值0表示将使用 512bytes 缓冲区

4.4.3 deque的迭代器

template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {
    typedef __deque_iterator<T, T&, T*, BufSiz>             iterator;
    typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iterator;
    static size_t buffer_size() {return __deque_buf_size(BufSiz, sizeof(T)); }

    typedef random_access_iterator_tag iterator_category;
    typedef T           value_type;
    typedef Ptr         pointer;
    typedef Ref         reference;
    typedef size_t      size_type;
    typedef ptrdiff_t   difference_type;
    typedef T**         map_pointer;

    typedef __deque_iterator self;

    T* cur;     // 缓冲区现行元素
    T* first;   // 缓冲区的头
    T* last;    // 缓冲区的尾（含备用空间）
    map_pointer node;   // 指向map里面的节点
};

buffer_size决定缓冲区大小，调用全局函数__deque_buf_size

inline size_t __deque_buf_size(size_t n, size_t sz) {
  return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));
}

• 如果n不为0，传回n，表示buffer size由用户自定义
• 如果n为0，表示buffer size使用默认值，那么
  • 如果sz（元素大小，sizeof (value_type))小于512，传回 512/sz，如果sz不小于512，传回1

如果一个缓冲区遍历完了，就要跳到下一个缓冲区

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

迭代器的运算符重载

reference operator*() const { return *cur; }
pointer operator->() const { return &(operator*()); }
difference_type operator-(const self& x) const {
    return difference_type(buffer_size()) * (node - x.node - 1) +
    (cur - first) + (x.last - x.cur);
}
self& operator++() {
    ++cur;                  // 切换到下一个元素
    if (cur == last) {      // 如果到了缓冲区的尾端
        set_node(node + 1); // 就跳到下一个缓冲区
        cur = first;
    }
    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;
}
self& operator+=(difference_type n) {
    difference_type offset = n + (cur - first);
    if (offset >= 0 && offset < difference_type(buffer_size()))
        cur += n;   // 在同一个缓冲区中就直接跳
    else {  // 不在同一个缓冲区就要先跳到对应的缓冲区
        difference_type node_offset =
            offset > 0 ? offset / difference_type(buffer_size())
                    : -difference_type((-offset - 1) / buffer_size()) - 1;
        set_node(node + node_offset);   // 跳到对应的节点
        cur = first + (offset - node_offset * difference_type(buffer_size()));
    }
    return *this;
}
self operator+(difference_type n) const {
    self tmp = *this;
    return tmp += n;
}

self& operator-=(difference_type n) { return *this += -n; }

self operator-(difference_type n) const {
    self tmp = *this;
    return tmp -= n;
}
reference operator[](difference_type n) const { return *(*this + n); }

bool operator==(const self& x) const { return cur == x.cur; }
bool operator!=(const self& x) const { return !(*this == x); }
bool operator<(const self& x) const {
    return (node == x.node) ? (cur < x.cur) : (node < x.node);
}

4.4.4 deque的数据结构

deque 除了维护一个先前说过的指向 map 的指针外，也维护start和finish两个迭代器，分别指向第一缓冲区的第一个元素和最后缓冲区的最后一个元素（的下一位置）。此外，它当然也必须记住目前的 map 大小。因为一旦 map 所提供的节点不足，就必须重新配置更大的一块 map

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
public:                         // Basic types
    typedef T           value_type;
    typedef value_type* pointer;
    typedef value_type& reference;
    typedef size_t      size_type;
    typedef ptrdiff_t   difference_type;

public:                         // Iterators
    typedef __deque_iterator<T, T&, T*, BufSiz> iterator;

protected:                      // Internal typedefs
    typedef pointer* map_pointer;
    typedef simple_alloc<value_type, Alloc> data_allocator;
    typedef simple_alloc<pointer, Alloc> map_allocator;

protected:                      // Data members
    iterator start;     // 表现第一个节点
    iterator finish;    // 表现最后一个节点

    map_pointer map;    // 指向map
    size_type map_size; // map内有多少个指针
};

简单的成员函数

iterator begin() { return start; }
iterator end() { return finish; }
reference operator[](size_type n) { return start[difference_type(n)]; }
reference front() { return *start; }
reference back() {
    iterator tmp = finish;
    --tmp;
    return *tmp;
}
size_type size() const { return finish - start;; }
size_type max_size() const { return size_type(-1); }
bool empty() const { return finish == start; }

4.4.5 deque的构造与内存管理

deque 自行定义了两个专属的空间配置器

typedef simple_alloc<value_type, Alloc> data_allocator; // 每次配置一个元素
typedef simple_alloc<pointer, Alloc> map_allocator;     // 每次配置一个指针

构造函数

deque(int n, const value_type& value): 
    start(), finish(), map(0), map_size(0) {
    fill_initialize(n, value);
}

内部调用fill_initialize负责产生并安排 deque 的结构，并设置初值

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::fill_initialize(size_type n,
                                               const value_type& value) {
    create_map_and_nodes(n);
    map_pointer cur;
    for (cur = start.node; cur < finish.node; ++cur)
        uninitialized_fill(*cur, *cur + buffer_size(), value);
    uninitialized_fill(finish.first, finish.cur, value);
}

create_map_and_nodes负责安排 deque 的结构

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::create_map_and_nodes(size_type num_elements) {
    // 需要的节点数=(元素个数/每个缓冲区可容纳个数)+1
    size_type num_nodes = num_elements / buffer_size() + 1;

    map_size = max(initial_map_size(), num_nodes + 2);  // (8, num_nodes + 2)
    map = map_allocator::allocate(map_size);    // 配置map_size个节点

    map_pointer nstart = map + (map_size - num_nodes) / 2;  // 从中间开始 
    map_pointer nfinish = nstart + num_nodes - 1;

    map_pointer cur;
    for (cur = nstart; cur <= nfinish; ++cur)
        *cur = allocate_node(); // 给每个节点配置缓冲区

    start.set_node(nstart);     // 设置迭代器初值
    finish.set_node(nfinish);
    start.cur = start.first;
    finish.cur = finish.first + num_elements % buffer_size();
}

push_back如果还有两个以上的备用空间，直接在备用空间上构造，否则调用push_back_aux

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

push_back_aux会配置新的 map 节点

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::push_back_aux(const value_type& t) {
    value_type t_copy = t;
    reserve_map_at_back();  // 符合某些条件时必须重换一个map
    *(finish.node + 1) = allocate_node();   // 配置一个新节点
    construct(finish.cur, t_copy);      // 对缓冲区的最后一个元素设置
    finish.set_node(finish.node + 1);   // 然后移动到新的缓冲区
    finish.cur = finish.first;
}

push_front在头部插入元素，没有空间会调用push_front_aux

void push_front(const value_type& t) {
    if (start.cur != start.first) {     // 第一个缓冲区还有备用空间
        construct(start.cur - 1, t);    // 就直接构造
        --start.cur;
    }
    else
        push_front_aux(t);
}

类似地，配置新节点，迭代器移动到新的节点上

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::push_front_aux(const value_type& t) {
    value_type t_copy = t;
    reserve_map_at_front();
    *(start.node - 1) = allocate_node();
    start.set_node(start.node - 1);
    start.cur = start.last - 1;
    construct(start.cur, t_copy);
}

在一定条件下需要重新分配 map 空间

void reserve_map_at_back (size_type nodes_to_add = 1) {
    // 尾部备用节点不足
    if (nodes_to_add + 1 > map_size - (finish.node - map))
        reallocate_map(nodes_to_add, false);
}

void reserve_map_at_front (size_type nodes_to_add = 1) {
    // 前端的备用节点不足
    if (nodes_to_add > start.node - map)
        reallocate_map(nodes_to_add, true);
}

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::reallocate_map(size_type nodes_to_add,
                                              bool add_at_front) {
    size_type old_num_nodes = finish.node - start.node + 1;
    size_type new_num_nodes = old_num_nodes + nodes_to_add;

    map_pointer new_nstart;
    if (map_size > 2 * new_num_nodes) {
        new_nstart = map + (map_size - new_num_nodes) / 2 
                            + (add_at_front ? nodes_to_add : 0);
        if (new_nstart < start.node)
            copy(start.node, finish.node + 1, new_nstart);
        else
            copy_backward(start.node, finish.node + 1, new_nstart + old_num_nodes);
    }
    else {
        size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2;
        // 配置一块新的空间
        map_pointer new_map = map_allocator::allocate(new_map_size);
        new_nstart = new_map + (new_map_size - new_num_nodes) / 2
                                + (add_at_front ? nodes_to_add : 0);
        copy(start.node, finish.node + 1, new_nstart);  // 把原map拷贝过来
        map_allocator::deallocate(map, map_size);       // 释放原map

        map = new_map;
        map_size = new_map_size;
    }

    start.set_node(new_nstart);
    finish.set_node(new_nstart + old_num_nodes - 1);
}

4.4.6 deque的元素操作

pop_back和pop_front删除尾部和头部的元素，如果删掉后缓冲区没有元素了，就要释放该缓冲区

void pop_back() {
    if (finish.cur != finish.first) {   // 缓冲区还有元素
        --finish.cur;
        destroy(finish.cur);
    }
    else
        pop_back_aux();
}

// 只有当finish.cur==finish.first时才会调用
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>:: pop_back_aux() {
    deallocate_node(finish.first);      // 释放最后一个缓冲区
    finish.set_node(finish.node - 1);   // 移动到上一个缓冲区
    finish.cur = finish.last - 1;       // 指向最后一个元素
    destroy(finish.cur);                // 将其析构掉
}

void pop_front() {
    if (start.cur != start.last - 1) {
        destroy(start.cur);
        ++start.cur;
    }
    else 
        pop_front_aux();
}

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::pop_front_aux() {
    destroy(start.cur);
    deallocate_node(start.first);
    start.set_node(start.node + 1);
    start.cur = start.first;
}

clear清除到只剩一个缓冲区

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::clear() {
    // 先清除填满元素的缓冲区
    for (map_pointer node = start.node + 1; node < finish.node; ++node) {
        destroy(*node, *node + buffer_size());
        data_allocator::deallocate(*node, buffer_size());
    }

    if (start.node != finish.node) {    // 再清除头尾两个缓冲区
        destroy(start.cur, start.last);
        destroy(finish.first, finish.cur);
        data_allocator::deallocate(finish.first, buffer_size());    // 清除尾缓冲区，保留头缓冲区
    }
    else
        destroy(start.cur, finish.cur);

    finish = start;
}

erase清除某个元素

iterator erase(iterator pos) {
    iterator next = pos;
    ++next;
    difference_type index = pos - start;    // 清除点之前的元素个数
    if (index < (size() >> 1)) {            // 如果前面的元素比较少
        copy_backward(start, pos, next);    // 就将[start,pos)往后移一格
        pop_front();    // 然后将最前面的元素弹出
    }
    else {
        copy(next, finish, pos);
        pop_back();
    }
    return start + index;
}

erase清除区间[first, end)内的所有元素

template <class T, class Alloc, size_t BufSize>
deque<T, Alloc, BufSize>::iterator 
deque<T, Alloc, BufSize>::erase(iterator first, iterator last) {
    if (first == start && last == finish) {
        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 + 1; cur <= finish.node; ++cur)
                data_allocator::deallocate(*cur, buffer_size());
            finish = new_finish;
        }
        return start + elems_before;
    }
}

insert在某个迭代器之前插入一个元素，并设定其值，如果是在中间位置插入就调用insert_aux

iterator insert(iterator position, const value_type& x) {
    if (position.cur == start.cur) {
        push_front(x);
        return start;
    }
    else if (position.cur == finish.cur) {
        push_back(x);
        iterator tmp = finish;
        --tmp;
        return tmp;
    }
    else {
        return insert_aux(position, x);
    }
}

template <class T, class Alloc, size_t BufSize>
typename deque<T, Alloc, BufSize>::iterator
deque<T, Alloc, BufSize>::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());    // 先在前端插入一个相同元素
        iterator front1 = start;    
        ++front1;
        iterator front2 = front1;
        ++front2;
        pos = start + index;
        iterator pos1 = pos;
        ++pos1;
        copy(front2, pos1, front1); // 再把插入点前面的元素往前移一格，空出插入的位置
    }
    else {
        push_back(back());
        iterator back1 = finish;
        --back1;
        iterator back2 = back1;
        --back2;
        pos = start + index;
        copy_backward(pos, back2, back1);
    }
    *pos = x_copy;  // 在插入点上设定新值
    return pos;
}