Post

C++ STL Container Deque

Posted
By soong
8 min read
C++ STL Container Deque

Deque

  • based on gnu 2.9
  • 双向队列
  • 对外表现为连续随机访问, 内部实现为分段连续, 由(map + buffer)组成

Iterator

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

/*
    typedef __deque_iterator<T, T&, T*, BufSiz>             iterator;
    typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iterator;
    
    typedef T value_type;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

    typedef __deque_iterator self;
*/

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

template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {
    static size_t buffer_size() {return __deque_buf_size(BufSiz, sizeof(T)); }
    
    typedef random_access_iterator_tag iterator_category;
    typedef T** map_pointer;
    
    T* cur;
    T* first;
    T* last;
    map_pointer node;

    difference_type operator-(const self& x) const {
        return difference_type(buffer_size()) * (node - x.node - 1) // 差了多少个buffer
                            + (cur - first) + (x.last - x.cur);
    }

    self& operator++() {
        ++cur;
        // 需要换到下一个buffer
        if (cur == last) {
            set_node(node + 1);
            cur = first;
        }
        return *this; 
    }
    self operator++(int)  {
        self tmp = *this;
        ++*this;
        return tmp;
    }

    self& operator--() {
        // 需要换到上一个buffer
        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);
        // 不会切换buffer
        if (offset >= 0 && offset < difference_type(buffer_size())) 
            cur += n;
        else {
            // 要切换多少个buffer
            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); }

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

Container

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

/*
    typedef T value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    
    typedef pointer* map_pointer;
    typedef simple_alloc<value_type, Alloc> data_allocator;
    typedef simple_alloc<pointer, Alloc> map_allocator;
*/
template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    static size_type initial_map_size() { return 8; }

    iterator start;
    iterator finish;

    map_pointer map;
    size_type map_size;
    // iterator
    iterator begin() { return start; }
    iterator end() { return finish; }
    reverse_iterator rbegin() { return reverse_iterator(finish); }
    reverse_iterator rend() { return reverse_iterator(start); }
    // reference
    reference front() { return *start; }
    reference back() {
        iterator tmp = finish;
        --tmp;
        return *tmp;
    }
    // size
    size_type size() const { return finish - start; }
    size_type max_size() const { return size_type(-1); }
    bool empty() const { return finish == start; }
    // 访问元素
    reference operator[](size_type n) { 
        return start[difference_type(n)]; // 从start往后走距离n
    }
    // 添加元素
    void push_back(const value_type& t) {
        // 无需切换buffer
        if (finish.cur != finish.last - 1) {
            construct(finish.cur, t);
            ++finish.cur;
        }
        else push_back_aux(t);
    }

    void push_front(const value_type& t) {
        // 无需切换buffer
        if (start.cur != start.first) {
            construct(start.cur - 1, t);
            --start.cur;
        }
        else push_front_aux(t);
    }

    iterator insert(iterator position, const value_type& x) {
        // 插入到首位置, 相当与push_front
        if (position.cur == start.cur) {
            push_front(x);
            return start;
        }
        // 插入到尾位置, 相当于push_back
        else if (position.cur == finish.cur) {
            push_back(x);
            iterator tmp = finish;
            --tmp;
            return tmp;
        }
        else {
            return insert_aux(position, x);
        }
    }
    // 删除元素
    void pop_back() {
        // 无需切换buffer
        if (finish.cur != finish.first) {
            --finish.cur;
            destroy(finish.cur);
        }
        else pop_back_aux();
    }

    void pop_front() {
        // 无需切换buffer
        if (start.cur != start.last - 1) {
            destroy(start.cur);
            ++start.cur;
        }
        else pop_front_aux();
    }

    iterator erase(iterator pos) {
        iterator next = pos;
        ++next;
        difference_type index = pos - start;
        // 判断要删除的元素位置是离start近还是离finish近
        if (index < (size() >> 1)) {
            copy_backward(start, pos, next);
            pop_front();
        }
        else {
            copy(next, finish, pos);
            pop_back();
        }
        return start + index;
    }

}

Auxiliary Function

node allocate/deallocate

1
2
3
4
5
6
7
8

// 在map中加一个buffer
pointer allocate_node() { 
    return data_allocator::allocate(buffer_size()); 
}
// 删一个buffer
void deallocate_node(pointer n) {
    data_allocator::deallocate(n, buffer_size());
}

map reallocate

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
36
37
38
39
40
41
42
43
44
45
46

void reserve_map_at_back (size_type nodes_to_add = 1) {
    // map_size不足, 扩容map
    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) {
    // map_size不足, 扩容map
    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 {
        // new_map_size扩容至少2倍
        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的中间分配, 方便之后前后allocate_node
        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_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);
}

push_aux

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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();
    *(finish.node + 1) = allocate_node();
    try {
        construct(finish.cur, t_copy);
        finish.set_node(finish.node + 1);
        finish.cur = finish.first;
    }
}

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();
    try {
        start.set_node(start.node - 1);
        start.cur = start.last - 1;
        construct(start.cur, t_copy);
    }
}

pop_aux

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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);
}

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;
}

insert_aux

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

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;
    // 靠近start
    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);
    }
    // 靠近finish
    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;
}
C++, STL
STL
This post is licensed under CC BY 4.0 by the author.