**侯捷老师的C++笔记2--STL**
Deque && Queue && Stack
deque: 双向queue
- 模拟连续空间, 实际是多个连续空间拼接
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// bufsiz: 每个buffer所容纳的元素个数
template <class T, class Alloc = alloc, size_t BufSize = 0>
class deque {
public:
typedef T value_type;
typedef __deque_iterator<T,T&,T*,BufSize> iterator;
protected:
typedef pointer* map_pointer; // T**
protected:
iterator start;
iterator finish;
map_pointer map;
size_type map_size;
public:
iterator begin() {return start;}
iterator end() {return finish;}
size_type size() const {return finish - start;}
};
// deque<T>::insert() ---> 会根据pos的位置判断从前面插入还是后边插入
iterator insert(iterator position, const value_type& x) {
if (position.cur == start.cur) {
push_front(x); // deque最前端
return start;
}
else if (position.cur == finish.cur) {
push_back(x); // deque最尾端
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>::__deque_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()); // 给insert的元素挪出一个位置
...
copy(front2, pos1, front1); // move element
}
else {
push_back(back()); // 同上
...
copy_backward(pos, back2, back1);
}
*pos = x_copy; // insert x at position
return pos;
}
// iterator 如何模拟连续空间
difference_type operator-(const self& x) const
{
// 两个ite之间buffer的总长度 + itr到buffer末尾的长度 + x到buffer起始的长度
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;
}
void set_node(map_pointer new_node)
{
node = new_node;
first = *new_node;
last = first + difference_type(buffer_size());
}
// +=
self& operator+=(difference_type n) {
difference_type offset = n + (cur - first);
if (offset > 0 && offset < difference_type(buffer_size()))
// 目标位置在同一个buffer上
cur += n;
else {
// -= 通用此函数
difference_type node_offset =
offset > 0 ? offset / difference_type(buffer_size()) :
-difference_type((-offset - 1) / buffer_size() - 1);
// 切到目标所在的buffer
set_node(node + node_offset);
cur = first + (offset - node_offset * difference_type(buffer_size()));
}
retrun *this;
}
self operator+(differnce_type n) const {
self tmp = *this;
return tmp += n; // 调用+=
}
self& operator-=(differnce_type n)
{return *this += n;}queue
:- 只有
push_back
和pop_front
- 不允许遍历,不提供
iterator
- 也可以选择
list
作为底层容器,不能选择vector
,set
,map
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18template<class T, class Sequence=deque<T>>
class queue {
...
public:
typedef typename Sequence::value_type value_type;
...size_type, reference, const_reference
protected:
Sequence c; // 底层容器,默认为deque
public:
bool empty() const {return c.empty();}
size_type size() const { return c.size();}
reference front() {return c.front();}
const_reference front() const {return c.front();}
reference back() {return c.back();}
const_reference back() const {return c.back();}
void push(const value_type& x) {c.push_back(x);}
void pop() {c.pop_front();}
};stack
: - 只有
push_back
和pop_back
- 不允许遍历,不提供
iterator
- 也可以选择
list
orvector
作为底层容器,不能选择set
,map
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16template<class T, class Sequence=deque<T>>
class stack {
...
public:
typedef typename Sequence::value_type value_type;
...size_type, reference, const_reference
protected:
Sequence c; // 底层容器,默认为deque
public:
bool empty() const {return c.empty();}
size_type size() const { return c.size();}
reference top() {return c.top();}
const_reference top() const {return c.top();}
void push(const value_type& x) {c.push_back(x);}
void pop() {c.pop_back();}
};
- 只有