前言
STL 中，deque 是一种双向开口连续线性空间（逻辑上），deque 和 vector 的最大差异，一在于 deque 允许于常数时间内对起头端进行元素的插入或移除操作，二在于 deque 没有所谓容量 (capacity) 观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，功能十分强大；但对应的代价则是：deque 的迭代器与数据结构为了维持其 “整体连续” 的假象，被设计得异常复杂。
———— 《STL源码剖析》侯捷
值得一提的是，在 MYTinySTL 原始仓库中，deque 部分的实现也与原始 STL 的区别也比较大，比如 insert 与 reallocate 部分的逻辑等，这部分内容博主也进行了一些修改。
本节将会分析 deque 设计、迭代器、构造及析构等内容。
deque
deque 由一段一段的定量连续空间构成，并使用中控器 ( map ) 与迭代器来维护与访问它们。
deque 的中控器
deque 采用一块所谓的 map (注意，不是 STL 的 map 容器) 作为主控。这里所谓 map 是一小块连续空问，其中每个元素 (此处称为一个节点，node) 都是指针，指向另一段 (较大的) 连续线性空间，称为缓冲区。缓冲区才是 deque 的储存空间主体。可以使用一些全局函数与宏定义来规定 map 的大小及缓冲区大小。
1
2
3
4
5
6
7
8
9
10
11
|
#ifndef DEQUE_MAP_INIT_SIZE
#define DEQUE_MAP_INIT_SIZE 8
#endif
template <class T>
struct deque_buf_size {
static constexpr size_t value = sizeof(T) < 256 ? 4096 / sizeof(T) : 16;
};
|
这张图比较清晰地展示了 deque 的数据结构。其中，中控器（map），管理着所有的节点（node），每一个 node 都指向一块 buffer，buffer 是真正存放数据的地方，deque 的迭代器维护 buffer 的首尾以及目前迭代器位置的信息，同时还要维护一个指向目前所在 node 的指针，在遍历到当前 buffer 末尾需要跳到另一个 buffer 时需要使用到这个信息。
deque 的迭代器
deque 是分段连续空间。维持其 “整体连续” 假象的任务，落在了迭代器的 opcrator++ 和 operator-- 两个运算子身上，
让我们思考一下，deque 迭代器应该具备什么结构。首先，它必须能够指出分段连续空间 (亦即缓冲区) 在哪里，其次它必须能够判断自己是否已经处于其所在缓冲区的边缘，如果是，一旦前进或后退时就必须跳跃至下一个或上一个缓冲区。为了能够正确跳跃，deque 必须随时掌握管控中心 (map)。以下是部分 deque_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
103
104
105
106
107
108
109
110
111
112
113
114
|
template <class T, class Ref, class Ptr>
struct deque_iterator : public iterator<random_access_iterator_tag, T> {
typedef deque_iterator<T, T&, T*> iterator;
typedef deque_iterator<T, const T&, const T*> const_iterator;
typedef deque_iterator self;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T* value_pointer;
typedef T** map_pointer;
static const size_type buffer_size = deque_buf_size<T>::value;
value_pointer cur;
value_pointer first;
value_pointer last;
map_pointer node;
void set_node(map_pointer new_node) {
node = new_node;
first = *new_node;
last = first + difference_type(buffer_size);
}
difference_type operator-(const self& x) const {
return static_cast<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) {
const auto offset = n + (cur - first);
if (offset >= 0 && offset < static_cast<difference_type>(buffer_size)) {
cur += n;
}
else {
const auto node_offset = offset > 0 ? offset / static_cast<difference_type>(buffer_size)
: -static_cast<difference_type>((-offset - 1) / buffer_size) - 1;
set_node(node + node_offset);
cur = first + (offset - node_offset * static_cast<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);
}
};
|
-
首先，不难看出，deque 的迭代器是 RandomAccessIterator 类型，这意味着可以随机访问 deque 中的任意元素。回想一下之前实现过的容器，vector 的迭代器是普通指针，并不需要重载各种运算符，list 的迭代器仅仅为 BidirectionalIterator，只需要重载 operator-- 与 operator++。而 deque_iterator 则需要重载各种运算符以符合随机访问迭代器的要求。同时可以看出，为了处理跳转到其他缓冲区的情况，操作符的重载会比较复杂。
-
在迭代器的型别定义中，map_pointer 的定义比较重要。在 deque 中，中控器 map 实际上是一个 “指针的指针”，维护分段的缓冲区。
1
| typedef T** map_pointer;
|
- 迭代器所包含的成员数据有以下四个，分别维护当前缓冲区的数据及指向中控器。
1
2
3
4
5
|
value_pointer cur;
value_pointer first;
value_pointer last;
map_pointer node;
|
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
|
template <class T>
class deque {
public:
typedef tinystl::allocator<T> allocator_type;
typedef tinystl::allocator<T> data_allocator;
typedef tinystl::allocator<T*> map_allocator;
typedef typename allocator_type::value_type value_type;
typedef typename allocator_type::pointer pointer;
typedef typename allocator_type::const_pointer const_pointer;
typedef typename allocator_type::reference reference;
typedef typename allocator_type::const_reference const_reference;
typedef typename allocator_type::size_type size_type;
typedef typename allocator_type::difference_type difference_type;
typedef pointer* map_pointer;
typedef const pointer* const_map_pointer;
typedef deque_iterator<T, T&, T*> iterator;
typedef deque_iterator<T, const T&, const T*> const_iterator;
typedef tinystl::reverse_iterator<iterator> reverse_iterator;
typedef tinystl::reverse_iterator<const_iterator> const_reverse_iterator;
allocator_type get_allocator() { return allocator_type(); }
static const size_type buffer_size = deque_buf_size<T>::value;
private:
iterator start_;
iterator finish_;
map_pointer map_;
size_type map_size_;
}
|
deque 除了维护一个先前说过的指向 map 的指针外,也维护 start，finish 两个迭代器，分别指向第一缓冲区的第一个元素和最后缓冲区的最后一个元素 (的下一位置)。此外，它当然也必须记住目前的 map 大小。因为一旦 map 所提供的节点不足，就必须重新配置更大的一块 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| template <class T>
class deque {
public:
deque() { fill_init(0, value_type()); }
explicit deque(size_type n) { fill_init(n, value_type()); }
deque(size_type n, const value_type& value) { fill_init(n, value); }
template <class InputIterator, typename std::enable_if<
tinystl::is_input_iterator<InputIterator>::value, int>::type = 0>
deque(InputIterator first, InputIterator last) {
copy_init(first, last, iterator_category(first));
}
deque(std::initializer_list<value_type> ilist) {
copy_init(ilist.begin(), ilist.end(), tinystl::forward_iterator_tag());
}
deque(const deque& rhs) {
copy_init(rhs.begin(), rhs.end(), tinystl::forward_iterator_tag());
}
deque(deque&& rhs) noexcept
: start_(rhs.start_), finish_(rhs.finish_), map_(rhs.map_), map_size_(rhs.map_size_) {
rhs.start_ = iterator();
rhs.finish_ = iterator();
rhs.map_ = nullptr;
rhs.map_size_ = 0;
}
deque& operator=(const deque& rhs);
deque& operator=(deque&& rhs) noexcept;
deque& operator=(std::initializer_list<value_type> ilist) {
deque tmp(ilist);
swap(tmp);
return *this;
}
~deque() {
if (map_ != nullptr) {
clear();
data_allocator::deallocate(*start_.node, buffer_size);
start_.node = nullptr;
map_allocator::deallocate(map_, map_size_);
map_ = nullptr;
}
}
}
|
deque 提供多种构造方式以满足不同的需求，可以看出，构造基本都交由 fill_init() 及 copy_init() 完成，下面分析这两个函数：
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
|
template <class T>
void deque<T>::fill_init(size_type n, const value_type& value) {
map_init(n);
if (n != 0) {
for (auto cur = start_.node; cur <= finish_.node; ++cur) {
tinystl::uninitialized_fill(*cur, *cur + buffer_size, value);
}
tinystl::uninitialized_fill(finish_.first, finish_.cur, value);
}
}
template <class T>
template <class InputIterator>
void deque<T>::copy_init(InputIterator first, InputIterator last, tinystl::input_iterator_tag) {
const difference_type n = tinystl::distance(first, last);
map_init(n);
for (; first != last; ++first) {
emplace_back(*first);
}
}
template <class T>
template <class ForwardIterator>
void deque<T>::copy_init(ForwardIterator first, ForwardIterator last, tinystl::forward_iterator_tag) {
const difference_type n = tinystl::distance(first, last);
map_init(n);
for (auto cur = start_.node; cur < finish_.node; ++cur) {
auto next = first;
tinystl::advance(next, buffer_size);
tinystl::uninitialized_copy(first, next, *cur);
first = next;
}
tinystl::uninitialized_copy(first, last, finish_.first);
}
|
可以看出这两个函数的逻辑都是逐个填充元素。其中，copy_init() 根据迭代器种类有两个重载，对于 InputIterator 类型（最低要求），使用逐个 push_back() 的方法，对于 ForwardIterator 则采取逐段插入的方式，同时对最后一个数组单独处理。毕竟最后一个数组一般不是会全部填充满。其次，在执行插入元素操作之前，都调用了 map_init() 用于初始化 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
32
33
34
35
36
37
38
39
40
|
template <class T>
void deque<T>::map_init(size_type nElem) {
const auto nNode = nElem / buffer_size + 1;
map_size_ = tinystl::max(static_cast<size_type>(DEQUE_MAP_INIT_SIZE), nNode + 2);
try {
map_ = create_map(map_size_);
}
catch (...) {
map_ = nullptr;
map_size_ = 0;
throw;
}
map_pointer nstart = map_ + (map_size_ - nNode) / 2;
map_pointer nfinish = nstart + nNode - 1;
try {
create_buffer(nstart, nfinish);
}
catch (...) {
map_allocator::deallocate(map_, map_size_);
map_ = nullptr;
map_size_ = 0;
throw;
}
start_.set_node(nstart);
finish_.set_node(nfinish);
start_.cur = start_.first;
finish_.cur = finish_.first + nElem % buffer_size;
}
|
初始化 map 的操作有一些需要注意的地方：
-
节点（缓冲区）个数为（元素数 / 缓冲区大小） + 1，如果刚好整除，会多分配一个节点。这是为了在任何条件下都能满足前闭后开的原则；最终分配的节点个数会在此基础上在收尾各添加两个，以方便扩容。
-
map_init() 也具有 commit or rollback 的特性，要么全部成功，要么一个不留。
-
start_ 与 finish_ 两个指针都被初始化至 map 的中央区域，方便向收尾扩容。
以下是创建及销毁 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
32
33
34
35
36
37
38
|
template <class T>
typename deque<T>::map_pointer deque<T>::create_map(size_type size) {
map_pointer map = nullptr;
map = map_allocator::allocate(size);
for (auto cur = map; cur < map + size; ++cur) {
*cur = nullptr;
}
return map;
}
template <class T>
void deque<T>::create_buffer(map_pointer nstart, map_pointer nfinish) {
map_pointer cur;
try {
for (cur = nstart; cur <= nfinish; ++cur) {
*cur = data_allocator::allocate(buffer_size);
}
}
catch (...) {
while (cur != nstart) {
--cur;
data_allocator::deallocate(*cur, buffer_size);
*cur = nullptr;
}
throw;
}
}
template <class T>
void deque<T>::destroy_buffer(map_pointer nstart, map_pointer nfinish) {
for (auto cur = nstart; cur <= nfinish; ++cur) {
data_allocator::deallocate(*cur, buffer_size);
*cur = nullptr;
}
}
|
这里再分析一下 deque 的析构函数：
这里析构函数的实现与 STL 中也不相同，但原理类似，只是这里复用了 clear 函数，但代价就是要在之后针对头部缓冲区进行特殊处理。
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
| ~deque() {
if (map_ != nullptr) {
clear();
data_allocator::deallocate(*start_.node, buffer_size);
start_.node = nullptr;
map_allocator::deallocate(map_, map_size_);
map_ = nullptr;
}
}
template <class T>
void deque<T>::clear() {
for (auto cur = start_.node + 1; cur < finish_.node; ++cur) {
data_allocator::destroy(*cur, *cur + buffer_size);
data_allocator::deallocate(*cur, buffer_size);
}
if (start_.node != finish_.node) {
data_allocator::destroy(start_.cur, start_.last);
data_allocator::destroy(finish_.first, finish_.cur);
data_allocator::deallocate(finish_.first, buffer_size);
}
else data_allocator::destroy(start_.cur, finish_.cur);
finish_ = start_;
}
|
析构函数调用了 clear() 用于清除除了头部缓冲区外的所有缓冲区，随后释放头部缓冲区空间与中控器 map 的空间。
clear() 用于清除整个 deque。请注意，deque 的最初状态（无任何元素时）保有一个缓冲区，因此，clear() 完成之后回复初始状态，也一样要保留一个缓冲区。
