STL

STL解析 —— deque

Standard Template Library —— deque

ZingLix May 7, 2018

vector 是 STL 中常用的一个容器,它可以在尾部快速添加和移除元素,但是在头部进行相关操作效率便十分糟糕。deque (双端队列)用于弥补 vector 的不足,在首尾两端都可以快速添加和删除,当然底层结构也有区别。

底层数据结构

与 vector 连续空间不同,deque 没有所谓容量的概念,因为它是动态地由多个连续空间组合而成。

deque 的结构类似于一个二维数组,左侧 map 指向一个指针数组,其中每个节点( node )都指向一块连续内存空间(缓冲区)用于存储数据,后面我们可以看到如何利用 map 使得我们可以将多个分开的空间从逻辑上看作一个连续空间。

在 deque 中还需要有 startfinish 两个迭代器用于指示开始与结束的位置,以及一个 map_size 用来记录 map 内可容纳多少指针。

deque 声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
template <class T, class Alloc=allocator<T>, size_t Bufsiz=0>
class deque
{
public:
    // traits 相关
    using value_type = T;
    using allocator_type = Alloc;
    using size_type = size_t;
    using difference_type = ptrdiff_t;
    using reference = value_type & ;
    using pointer =typename allocator_traits<Alloc>::pointer;
    using iterator = __deque_iterator<T, T&, T*, Bufsiz>;

    const static size_type INI_MAP_SIZE = 8;

protected:
    using map_pointer = pointer * ;
    using data_allocator = Alloc;
    // 将Alloc重新绑定为pointer的分配器
    using map_allocator = typename allocator_traits<Alloc>::template 
        rebind_alloc<pointer>;
    
    iterator start;
    iterator finish;
    map_pointer map;
    size_type map_size;
    Alloc alloc_;    //存储一个分配器实例,可忽略
}

内存分配策略

在模板参数中还提供了一个Bufsiz用于自定义缓冲区大小,所以在这里引入一个函数用于获取缓冲区大小。0 表示未指定,sz为元素大小,在这种情况下一个缓冲区512字节,所以能够存储512/sz个元素或者在元素过大时只有一个。当然这一策略并没有规定,例如 64 位 libstdc++ 上为对象大小 8 倍, 64 位 libc++ 上为对象大小 16 倍或 4096 字节的较大者。

1
2
3
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));
}

此外还有一个常量INI_MAP_SIZE用来指示初始化时中控器最小的大小。在本文实现中将其定义为 8 ,即表示即使只有一个元素,deque 中也有 8 个缓冲区,以提高扩充元素时的效率。

1
2
static size_type buffer_size() { return _deque_buf_size(Bufsiz, sizeof(T)); }
static size_type initial_map_size() { return INI_MAP_SIZE; }

此外 deque 有两种不同的分配内存策略,一种是在构造时便对所有中控器中指针都分配好缓冲区,另一种是仅分配用到的缓冲区。前者在添加元素时更少的遇到分配内存的情况,所以效率更高,但代价是闲置的内存会过多。这两种策略不同不影响到内存结构,本文采用后者。

迭代器

迭代器最为靠近底层数据结构,所以是使得我们能够造就 deque 是一个连续空间假象的关键。为了使得其看起来是连续的,我们只需要控制好需要调整缓冲区的情况即可。从上图可以看出,迭代器中有如下四个成员:

  • cur :用于指向迭代器所指元素。
  • first & last :指向当前缓冲区的头与尾。
  • node :指向中控器中指向本缓冲区的指针。

有了如上信息我们就可以掌握何时需要调整缓冲区。

声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<class T, class Ref, class Ptr, size_t Bufsiz>
struct __deque_iterator
{
    using iterator = __deque_iterator<T, T&, T*, Bufsiz>;
    using const_iterator = __deque_iterator<T, const T&, const T*, Bufsiz>;

    using iterator_category = random_access_iterator_tag;
    using value_type = T;
    using pointer = value_type * ;
    using reference = value_type & ;
    using size_type = size_t;
    using difference_type = ptrdiff_t;
    using map_pointer = T **;

    using self = __deque_iterator;

    T* cur;
    T* first;
    T* last;
    map_pointer node;

    // 获得缓冲区大小
    static size_type buffer_size() { return _deque_buf_size(Bufsiz, sizeof(T)); }
}

私有操作

set_node 操作用于将迭代器本身调整到新的节点,为了下面实现方便,这一函数并不应被外部使用。

1
2
3
4
5
void set_node(map_pointer new_node) {
    node = new_node;
    first = *node;
    last = first + difference_type(buffer_size());
}

operator* & ->

用于得到迭代器所指元素。

1
2
reference operator*()const { return *cur; }
pointer operator->() const { return &(operator*()); }

operator-

用于获得两个迭代器之间相差元素数量。

1
2
3
difference_type operator-(const self& x) {
    return difference_type(buffer_size())*(node - x.node - 1) + (cur - first) + (x.last - x.cur);
}

operator++ & –

自增操作符用于指向下一个元素。当下一个元素是last,即到了一个缓冲区结尾便意味着需要调整到下一个缓冲区。自减操作符同理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
self& operator++() {
    ++cur;
    if(cur==last) {
        set_node(node + 1);
        cur = first;
    }
    return *this;
}

self operator++(int) {
    const self tmp = *this;
    ++*this;
    return tmp;
}

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

self operator--(int) {
    const self tmp = *this;
    --*this;
    return tmp;
}

operator+=

这一操作符是其他所有操作的关键,使得这一迭代器能够成为Random Access Iterator。如果移动数量使得仍在同一缓冲区内那么简单的增加cur即可,如果跨越缓冲区就须先算出偏移量,再调整cur以及node

1
2
3
4
5
6
7
8
9
10
11
12
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;
}

operator+ & -

加减操作符只需要利用 += 就可以轻易实现。注意这里operator-与之前不同,前者是两个迭代器间相减得到相差的数量,而这里是减掉一个偏移量得到另一个迭代器。

1
2
3
4
5
6
7
8
9
10
11
self operator+(difference_type n) const {
    self tmp = *this;
    return tmp += n;
}

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

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

operator== & != & <

指向同一个元素,即cur相等即代表相等。比较操作符在同一缓冲区下比较cur,不同缓冲区则比较node

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

构造函数

在明确内存结构后便可以很简单的构造出一个 deque 。首先分配出中控器,即大小为map_size的指针数组,并使map指向他,之后依次对其中用到的指针分配缓冲区即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 分配节点
pointer allocate_node() {
    return data_allocator::allocate(buffer_size());
}

// 分配map及缓冲区
void create_map_and_nodes(size_type elements_num) {
    const size_type nodes_num = elements_num / buffer_size() + 1;
    // 如果数量大于默认数量会多分配两个节点以提高添加元素时效率
    map_size = initial_map_size() < nodes_num ? nodes_num + 2 : initial_map_size();
    map = map_allocator::allocate(map_size);
    // 使开始与结尾节点位于中控器中央,从而无论向前或向后添加元素都可应对
    map_pointer nstart = map + (map_size - nodes_num) / 2;
    map_pointer nfinish = nstart + nodes_num - 1;
    for(map_pointer cur = nstart;cur<=nfinish;++cur) {
        *cur = allocate_node();
    }
    start.set_node(nstart);
    finish.set_node(nfinish);
    start.cur = start.first;
    finish.cur = finish.first + elements_num % buffer_size();
}

//填充元素
void fill_initialize(size_type n,const value_type& val) {
    create_map_and_nodes(n);
    for (map_pointer cur = start.node; cur < finish.node; ++cur) {
        uninitialized_fill(*cur, *cur + buffer_size(), val);
    }
    uninitialized_fill(finish.first, finish.cur, val);
}

如上三个函数依次分工明确,所以构造函数可以简单的如下实现。

1
2
3
4
5
6
7
8
9
10
11
12
deque() :start(), finish(), map(nullptr), map_size(0),alloc_() {
    fill_initialize(0, value_type());
}

deque(int n, const value_type& val,
    const Alloc& alloc = Alloc()) :start(), finish(), map(nullptr), map_size(0), alloc_(alloc) {
    fill_initialize(n, val);
}

explicit deque(size_type count, const Alloc& alloc = Alloc()) :start(), finish(), map(nullptr), map_size(0), alloc_(alloc) {
    fill_initialize(count, value_type());
}

析构函数

先使得所有元素析构,之后将所有缓冲区释放,最后释放中控器即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
~deque() {
    _clear();
}

void _clear() {
    if (map != nullptr) {
        for (map_pointer node = start.node + 1; node<finish.node; ++node) {
            auto p = *node;
            for (; p != *node + buffer_size(); ++p) {
                allocator_traits<Alloc>::destroy(alloc_, p);
            }
            data_allocator::deallocate(*node, buffer_size());
        }
        if (start.node != finish.node) {
            auto p = start.cur;
            for (; p != start.last; ++p) {
                allocator_traits<Alloc>::destroy(alloc_, p);
            }
            data_allocator::deallocate(start.first, buffer_size());
            p = finish.first;
            for (; p != finish.cur; ++p) {
                allocator_traits<Alloc>::destroy(alloc_, p);
            }
            data_allocator::deallocate(finish.first, buffer_size());
        }
        else {
            auto p = start.cur;
            for (; p != finish.cur; ++p) {
                allocator_traits<Alloc>::destroy(alloc_, p);
            }
            data_allocator::deallocate(start.first, buffer_size());
        }
        map_allocator::deallocate(map);
    }
}

push

push 操作有两个版本push_backpush_front,对应于向后和向前插入元素,两者类似,所以只讨论push_back

finish的缓冲区还有空间时直接在最后构造即可,而当需要跳转缓冲区时则较为复杂。

1
2
3
4
5
6
7
8
9
void push_back(const value_type& t) {
    if (finish.cur != finish.last - 1) {
        allocator_traits<Alloc>::construct(alloc_, finish.cur, t);
        ++finish.cur;
    }
    else {
        push_back_aux(t);
    }
}

因为我们选择按需分配缓冲区,所以当最后已无处构造元素时,我们必须分配新的缓冲区。

1
2
3
4
5
6
7
8
void push_back_aux(const value_type& t) {
    value_type t_value = t;
    reserve_map_at_back();
    *(finish.node + 1) = allocate_node();
    allocator_traits<Alloc>::construct(alloc_, finish.cur, t_value);
    finish.set_node(finish.node + 1);
    finish.cur = finish.first;
}

在构造时还会遇到另一个情况,即中控器中已无空间再指向新的缓冲区,所以我们必须换一个新的map,所以在上面调用了reserve_map_at_back()以判断是否需要处理这一情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void reserve_map_at_back(size_type new_nodes_num=1) {
    if (new_nodes_num + 1 > map_size - (finish.node - map)) reallocate_map(new_nodes_num, false);
}
void reallocate_map(size_type new_nodes_num,bool add_front) {
    auto old_num_nodes = finish.node - start.node + 1;
    auto new_num_nodes = old_num_nodes + new_nodes_num;
    map_pointer new_nstart;
    if(map_size>2*new_num_nodes) {
        new_nstart = map + (map_size - new_num_nodes) / 2 + (add_front ? new_nodes_num : 0);
        if (new_nstart < start.node) {
            std::copy(start.node, finish.node + 1, new_nstart);
        } else {
            std::copy_backward(start.node, finish.node + 1, new_nstart + old_num_nodes);
        }
    } else {
        size_type new_map_size = map_size + max(map_size, new_nodes_num) + 2;
        const map_pointer new_map = map_allocator::allocate(new_map_size);
        new_nstart = new_map + (new_map_size - new_num_nodes) / 2 + (add_front ? new_nodes_num : 0);
        std::copy(start.node, finish.node + 1, new_nstart);
        map_allocator::deallocate(map, map_size);
        map = new_map;
        map_size = new_map_size;
    }
    start.set_node(new_nstart);
    finish.set_node(new_nstart + old_num_nodes - 1);
}

重新分配时对于已有元素不需要做任何动作,我们只需要将新的map中对应位置指向原来的缓冲区,并调整startfinish中的node。相对而言, vector 面对这一情况需要将原来的元素全部拷贝到新的内存中,所以 deque 效率更高。

push_front 类似地向前调整start,并注意到上述两个情况即可。

pop

与 push 一样,pop 也有pop_frontpop_back两个版本,这里以pop_front为例。

1
2
3
4
5
6
7
8
9
10
void pop_front() {
    if (start.cur != start.last - 1) {
        allocator_traits<Alloc>::destroy(alloc_, start.cur);
        destroy(start.cur);
        ++start.cur;
    }
    else {
        pop_front_aux();
    }
}

不涉及跨越缓冲区,那么直接析构元素即可。然而当跨越缓冲区时说明最前的缓冲区已为空,根据我们按需分配的策略需要将其释放。

1
2
3
4
5
6
void pop_front_aux() {
    allocator_traits<Alloc>::destroy(alloc_, start.cur);
    deallocate_node(start.first);
    start.set_node(start.node +1);
    start.cur = start.first;
}

相对于 push 操作,pop 不必担心map不满足条件的情况。

insert

insert 是另一重要操作,可以在pos前插入一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
iterator insert(iterator pos,const value_type& x) {
    if(pos.cur==start.cur) {
        push_front(x);
        return start;
    }else if(pos.cur==finish.cur) {
        push_back(x);
        iterator tmp = finish;
        return --tmp;
    }else {
        return insert_aux(pos, x);
    }
}

为了保证效率,在头尾的操作交由 push 完成,其他再涉及拷贝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
iterator insert_aux(iterator pos,const value_type& x) {
    size_type idx = pos - start;
    value_type x_copy = x;
    if(idx<size()/2) {
        push_front(front());
        iterator front1 = start;
        ++front1;
        iterator front2 = front1;
        ++front2;
        pos = start + idx;
        iterator pos1 = pos;
        ++pos1;
        copy(front2, pos1, front1);
    }else {
        push_back(back());
        iterator back1 = finish;
        --back1;
        iterator back2 = back1;
        --back2;
        pos = start + idx;
        copy_backward(pos, back2, back1);
    }
    *pos = x_copy;
    return pos;
}

其实insert的实现就是最为粗暴的将后面的元素后移,从而腾出新位置给新元素。为了提高效率,作了个判断以决定是前面的元素向前移动还是后面的元素向后移动。借助于迭代器的良好实现造就的连续空间假象,我们可以直接利用copy函数完成复制而不必关注于跳跃缓冲区。

后记

虽然 deque 在头部添加和删除元素效率上优于 vector,但是复杂度也远远超过 vector ,迭代器也并非普通的指针,所以不是特别需要 deque 的某一特性时,应尽量优先使用 vector 。

更多其它函数实现