第四章：序列式容器 deque
deque概述
deque（double-ended queue，双端队列）是一种具有队列和栈的性质的数据结构。相比于vector单向开口的连续线性空间而言，deque则是一种双向开口的连续线性空间，可以在头尾两端分别做元素的插入和删除操作。虽然vector从技术层面也可以对头部操作，但是效率极低。即deque与vector的最大差异在于:
- deque可以在常数时间内完成对头部元素的插入或删除操作；
- deque没有容量的概念，它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。
deque的中控器
deque由一段一段的定量连续空间构成。一旦有必要在dequer前端或尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或尾端。deque的最大任务是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。避开了“重新配置、复制、释放”的轮回，代价则是复杂的迭代器架构。
deque采用一块所谓的map作为主控。这里所谓map是一小块连续空间，其中每个元素(此处称为一个节点，node)都是指针，指向另一段(较大的)连续线性空间，称为缓冲区。缓冲区才是deque的储存空间主体。
template<class T, class Alloc = alloc, size_t BufSiz = 0>
class deque{
public :
typedef T value_type ;
typedef value_type* pointer ;
...
protected :
//元素的指针的指针(pointer of pointer of T)
typedef pointer* map_pointer ; //其实就是T**
protected :
map_pointer map ; //指向map,map是块连续空间，其内的每个元素
//都是一个指针(称为节点)，指向一块缓冲区
size_type map_size ;//map内可容纳多少指针
...
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
deque的迭代器
deque是分段连续空间，维持”整体连续“假象的任务，落在迭代器的operator++和operator—两个运算子上。
template<class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator{ //未继承std::iterator
typedef __deque_iterator<T,T&,T*,BufSize> iterator ;
typedef __deque_iterator<T,const T&,const T*,BufSize> const_iterator ;
static size_t buffer_size() {return __deque_buf_size(BufSize,sizeof(T)) ;}
//未继承std::iterator，所以必须自行撰写五个必要的迭代器相应型别
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 *cut ; //此迭代器所指之缓冲区中的现行(current)元素
T *first ; //此迭代器所指之缓冲区的头
T *last ; //此迭代器所指之缓冲区的尾(含备用空间)
map_pointer 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
deque的数据结构
deque除了维护一个指向map的指针外，也维护start，finish两个迭代器，分别指向第一缓冲区的第一个元素和最后缓冲区的最后一个元素(的下一个位置)。
template<class T, class Alloc = alloc, size_t BufSiz = 0>
class deque{
public :
typedef T value_type ;
typedef value_type* pointer ;
typedef size_t size_type ;
public :
typedef __deque_iterator<T,T&,T*,BufSiz> iterator ;
protected :
//元素的指针的指针(pointer of pointer of T)
typedef pointer* map_pointer ;
protected:
iterator start ; //表现第一节点
iterator finish ; //表现最后一个节点
map_pointer map ; //指向map,map是块连续空间，其每个元素都是个指针，指向一个节点(缓冲区)
size_type map_size ; //map内有多少指针
...
} ;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
deque的构造与内存管理
以程序实现来初步了解deque的构造和内存管理：
#include <deque>
#include <iostream>
#include <algorithm>
using namespace std;
class alloc {
};
int main() {
deque<int, allocator<int>> ideq(20, 9);
//deque<int,alloc,8> ideq(20, 9);//在linux下不支持alloc
cout << "size=" << ideq.size() << endl;
for (int i = 0; i < ideq.size(); ++i)
cout << ideq[i] << ' ';
cout << endl;
for (int i = 0; i < 3; ++i)
ideq.push_back(i);
for (int i = 0; i < ideq.size(); ++i)
cout << ideq[i] << ' ';
cout << endl;
cout << "size=" << ideq.size() << endl;
ideq.push_back(3);
for (int i = 0; i < ideq.size(); ++i)
cout << ideq[i] << ' ';
cout << endl;
cout << "size=" << ideq.size() << endl;
ideq.push_front(99);
for (int i = 0; i < ideq.size(); ++i)
cout << ideq[i] << ' ';
cout << endl;
cout << "size=" << ideq.size() << endl;
ideq.push_front(98);
ideq.push_front(97);
for (int i = 0; i < ideq.size(); ++i)
cout << ideq[i] << ' ';
cout << endl;
cout << "size=" << ideq.size() << endl;
deque<int, allocator<int>>::iterator itr;
itr = find(ideq.begin(), ideq.end(), 99);
cout << *itr << endl;
cout << *(itr._M_cur) << endl;
}
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
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
执行结果:
[root@192 4_STL_sequence_container]# ./4_4_5_deque-test
size=20
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 0 1 2
size=23
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 0 1 2 3
size=24
99 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 0 1 2 3
size=25
97 98 99 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 0 1 2 3
size=27
99
99
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
上述程序的处理过程可以表现为如下图像：
deque的构造和析构函数：
deque():start(),finish(),map_size(0),map(0)
{
create_map_and_nodes(0);
}
deque(int n,const value_type& value):start(),finish(),map(0),map_size(0)
{
fill_initialize(n,value);
}
~deque(){}
void fill_initialize(size_type n,const value_type& value)
{ //负责产生并安排好deque的结构，并将元素的初值设定好
create_map_and_nodes(n); //把deque的结构都安排好
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);
}
void creat_map_and_nodes(size_type num_elements)
{ //产生并安排好deque的结构
size_type num_nodes=num_elements/buffer_size()+1;
//一个map要管理几个节点，最少8个，最多是“所需节点数+2”，前后各预留一个，扩充时用
map_size=max(initial_map_size(),num_nodes+2);
map=map_allocator::allocate(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();
}
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
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
deque的元素操作
void push_back(const value_type &t)
{
if (finish.cur != finish.last - 1)
{
construct(finish.cur, t);
++finish.cur;
}
else //需要配置新的缓冲区
{
push_back_aux(t);
}
}
void push_front(const value_type &t)
{
if (start.cur != start.first)
{
construct(start.cur - 1, t);
}
else
{
push_front_aux(t);
}
}
void pop_back()
{
if (finish.cur != finish.first)
{
--finish.cur;
destroy(finish.cur); //将最后元素析构,左开右闭
}
else
{
//最后缓冲区没有任何元素
pop_back_aux(); //这里将进行缓冲区的释放工作
}
}
void pop_front()
{
if (start.cur != start.last - 1)
{
destroy(start.cur);
++start.cur;
}
else
pop_front_aux();
}
void push_back_aux(const value_type &t) //只剩最后一个缓冲区的最后一个备用缓冲区
{ //先配置一块新的缓冲区，再设新元素内容，更改迭代器finish的状态
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;
}
void 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);
}
void reserve_map_at_back(size_type nodes_to_add = 1)
{
if (nodes_to_add + 1 > map_size - (finish.node - map)) //map尾端的节点备用空间不足
{
//换一个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);
}
}
void pop_back_aux()
{ //finish.cur==finish.first 释放该缓冲区
deallocate_node(finish.first); //释放最后一个缓冲区
finish.set_node(finish.node - 1);
finish.cur = finish.last - 1;
destroy(finish.cur); //析构
}
void pop_front_aux()
{
destory(start.cur);
deallocate_node(start.last);
start.set_node(start.node + 1);
start.cur = start.first;
}
void clear()
{
for (map_pointer node = start.node + 1; node < finish.node; ++node)
{
destory(*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;
}
iterator begin() { return start; }
iterator end() { return finish; }
reference operator[](size_type n)
{
//调用_deque_iterator<>::operator[]
return *(start + n);
}
reference front() { return *start; }
reference back() { return *(finish - 1); }
size_type size() const { return finish - start; }
size_type max_size() const { return size_type(-1); }
bool empty() const { return finish == start; }
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142