STL 源码剖析读书笔记四：序列式容器之 deque、stack、queue
程序员文章站
2022-03-19 22:40:51
1. 序列式容器 deque
1.1 deque 概述
vector是单向开口的连续线性空间，用户只能在vector尾部进行插入删除操作，而 deque 是一种双向开口的连续线性空间，允许我们在头尾...
1. 序列式容器 deque
1.1 deque 概述
vector是单向开口的连续线性空间，用户只能在vector尾部进行插入删除操作，而 deque 是一种双向开口的连续线性空间，允许我们在头尾两端操作。
deque 和 vector 的最大差异在于：
deque 允许常数时间对头端元素进行插入和移除操作 deque 没有所谓容量（capacity）概念，因为它是动态地以分段连续的空间组合而成，随时可以增加一段新的空间并链接起来deque提供的迭代器也是 randomaccess iterator，但它的迭代器并不是普通指针，其复杂度远远大于 vector 的迭代器，从而影响了各个运算层面。因此，除非必要，我们应尽可能选择使用 vector 而非 deque。对 deque 进行排序操作，为了最高效率，可将 deque 先完整的复制到一个 vector 身上，将 vector 排序后(利用 stl 的 sort 算法)，在复制回 deque。
1.2 deque 的中控器
deque 是连续空间（逻辑上来看如此），连续线性空间总令我们联想到 array 或 vector。array 空间大小无法增长，vector 虽然可以增长，但只能在尾部扩张，而且这种增长是个假象：
配置更大的空间 复制数据 释放原空间如果不是 vector 每次配置新空间时都有留下一些备用空间，其增长将带来高昂的代价。
deque 是由一段一段的定量连续空间构成。一旦有必要在 deque 的前端或尾端增加新空间，便配置一段定量的连续空间，串接在 整个 deque 的头端或尾端。deque 的最大的任务便是在这些分段连续的空间上维护其整体连续的假象，并提供随机存取接口，避开了“重新配置、复制、释放”的轮回，代价则是复杂的迭代器架构。
deque 采用一块所谓的 map 作为主控，即中控器，这个所谓的 map 是一小块连续空间，其中每个元素都是一个指向另一段较大的连续空间的指针（也称节点），这段线性空间称为缓冲区。缓冲区是 deque 的存储空间主体。sgi stl 允许我们指定缓冲区大小，默认值 0 表示将使用 512 bytes 缓冲区。
template
class deque {
public: // basic types
typedef t value_type;
typedef value_type* pointer;
...
protected: // internal typedefs
typedef pointer* map_pointer;
protected: // data members
...
map_pointer map; // 指向中控器 map，map 是块连续空间，其中每一个指针，指向一块缓冲区
size_type map_size; // map 可容纳的指针数
...
};
根据上述定义，可以发现 map 其实是一个 t**，即一个指针，所指之物也是一个指针，该指针指向型别为 t 的一块空间。
1.3 deque 的迭代器
deque 是分段连续空间。维持其“整体连续”假象的任务，落在了迭代器的 operator++ 和 operator– 两个运算子身上。
deque 迭代器首先需要能够指出分段连续空间的位置，其次它必须能够判断自己是否处于其所在缓冲区边缘，如果是，一旦前进或后退时就必须跳跃至下一个或者上一个缓冲区。为了掌控缓冲区，deque 必须随时掌握中控器。实现如下：
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));
}
template
struct __deque_iterator {
typedef __deque_iterator iterator;
typedef __deque_iterator const_iterator;
static size_t buffer_size() {return __deque_buf_size(bufsiz, sizeof(t)); }
// 迭代器 5 个相应型别
typedef random_access_iterator_tag iterator_category; // 1
typedef t value_type; // 2
typedef ptr pointer; // 3
typedef ref reference; // 4
typedef size_t size_type;
typedef ptrdiff_t difference_type; // 5
typedef t** map_pointer;
typedef __deque_iterator self;
// 保持与容器的联结
t* cur; // 此迭代器所指缓冲区中当前元素
t* first; // 此迭代器所指缓冲区的头
t* last; // 此迭代器所指缓冲区的尾 （含备用空间）
map_pointer node; // 指向中控器
...
};
在 deque 数据结构中，含有两个迭代器：start 和 finish。start 的 cur 指向缓冲区的第一个元素，finish 的 cur 指向缓冲区的最后元素（的下一位置）。
以下是迭代器的几个关键行为。
由于迭代器内对各种指针运算都写进行了重载操作，所以各种指针运算如加、减、前进、后退都不能直观视之。其中最关键的是：一旦行进时遇到缓冲区边缘，要视前进、后退而定，可能需要调用 set_node() 跳一个缓冲区：
void set_node(map_pointer new_node) {
node = new_node;
first = *new_node;
last = first + difference_type(buffer_size());
}
以下是重载各个运算符的实现：
reference operator*() const { return *cur; }
pointer operator->() const { return &(operator*()); }
difference_type operator-(const self& x) const {
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;
}
self& operator--() {
if (cur == first) {
set_node(node - 1);
cur = last;
}
--cur;
return *this;
}
self operator--(int) {
self tmp = *this;
--*this;
return tmp;
}
// 实现随机存取，迭代器可以直接跳跃 n 个距离
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+=
self operator+(difference_type n) const {
self tmp = *this;
return tmp += n;
}
// 调用 operator+=
self& operator-=(difference_type n) { return *this += -n; }
// 调用 operator-=
self operator-(difference_type n) const {
self tmp = *this;
return tmp -= n;
}
// 调用 operator*、operator+
reference operator[](difference_type n) const { return *(*this + n); }
bool operator==(const self& x) const { return cur == x.cur; }
bool operator!=(const self& x) const { return !(*this == x); }
bool operator<(const self& x) const {
return (node == x.node) ? (cur < x.cur) : (node < x.node);
}
1.4 deque 的数据结构
前面提到 deque 除了维护一个指向 map 的指针外，还维护 start、finish 两个迭代器，分别指向第一个缓冲区的第一个元素和最后缓冲区的最后一个元素（的下一位置）。此外，它必须记住当前 map 大小，因为一旦 map 所提供的节点不足，就必须重新配置一块更大的 map。
template
class deque {
public: // basic types
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;
public: // iterators
typedef __deque_iterator iterator;
typedef __deque_iterator const_iterator;
protected: // internal typedefs
// 元素的指针的指针
typedef pointer* map_pointer;
// 两个配置器
typedef simple_alloc data_allocator;
typedef simple_alloc map_allocator;
static size_type buffer_size() {
return __deque_buf_size(bufsiz, sizeof(value_type));
}
static size_type initial_map_size() { return 8; }
protected: // data members
iterator start; // 指向第一个缓冲区
iterator finish; // 指向最后一个缓冲区
map_pointer map; // 指向 map，每个元素都指向一个指针
size_type map_size; // map 内的指针个数
...
}; ,>
根据上述定义，可完成下面函数：
public: // basic accessors
iterator begin() { return start; }
iterator end() { return finish; }
const_iterator begin() const { return start; }
const_iterator end() const { return finish; }
// 调用__deque_iterator<>::operator[]
reference operator[](size_type n) { return start[difference_type(n)]; }
const_reference operator[](size_type n) const {
return start[difference_type(n)];
}
// 调用__deque_iterator<>::operator*
reference front() { return *start; }
reference back() {
iterator tmp = finish;
--tmp; // 调用 __deque_iterator<>::operator--
return *tmp; // 调用__deque_iterator<>::operator*
}
const_reference front() const { return *start; }
const_reference back() const {
const_iterator tmp = finish;
--tmp;
return *tmp;
}
size_type size() const { return finish - start;; }
size_type max_size() const { return size_type(-1); }
bool empty() const { return finish == start; }
1.5 deque 的构造
deque 定义了两个专属的空间配置器：
protected: // internal typedefs typedef simple_alloc data_allocator; typedef simple_allocmap_allocator; ,>
还提供了各种构造函数，其中一个定义如下：
deque(size_type n, const value_type& value)
: start(), finish(), map(0), map_size(0)
{
fill_initialize(n, value);
}
其内调用的 fill_initialize() 负责产生并安排好 deque 的结构，并将元素的初值设定妥当：
template
void deque::fill_initialize(size_type n,
const value_type& value) {
create_map_and_nodes(n); // 把 deque 的结构都产生并安排好
map_pointer cur;
__stl_try {
// 为每个节点（缓冲区）设置初值
for (cur = start.node; cur < finish.node; ++cur)
uninitialized_fill(*cur, *cur + buffer_size(), value);
// 最后一个节点的设定稍有不同（尾端可能有备用空间，不必设定初值）
uninitialized_fill(finish.first, finish.cur, value);
}
# ifdef __stl_use_exceptions
catch(...) { // commit or rollback
for (map_pointer n = start.node; n < cur; ++n)
destroy(*n, *n + buffer_size());
destroy_map_and_nodes();
throw;
}
# endif /* __stl_use_exceptions */
}
其中，create_map_and_nodes 负责产生并安排好deque 的结构：
template
void deque::create_map_and_nodes(size_type num_elements) {
// 需要缓冲区数 = （元素个数/每个缓冲区可容纳元素个数）+ 1
// 若刚好整除，会多分配一个缓冲区
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);
// 以下令 nstart 和 nfinish 指向 map 所拥有之全部节点的最*区段
// 保持在最*，可使头尾两端的扩充能量一样大。每个节点可对应一个缓冲区
map_pointer nstart = map + (map_size - num_nodes) / 2;
map_pointer nfinish = nstart + num_nodes - 1;
map_pointer cur;
__stl_try {
// 为 map 内的每个现用节点配置缓冲区。
// 所有缓冲区加起来就是 deque 的可用空间（最后一个缓冲区可能留有一些备用空间）
for (cur = nstart; cur <= nfinish; ++cur)
*cur = allocate_node();
}
# ifdef __stl_use_exceptions
catch(...) { // commit or rollback
for (map_pointer n = nstart; n < cur; ++n)
deallocate_node(*n);
map_allocator::deallocate(map, map_size);
throw;
}
# endif /* __stl_use_exceptions */
// 为 deque 内的两个迭代器 start 和 finish 设定正确的值
start.set_node(nstart);
finish.set_node(nfinish);
start.cur = start.first;
finish.cur = finish.first + num_elements % buffer_size();
}
前面提到当 map 的备用空间不足，需要重新配置一块更大的 map，有两个函数来判断 map 什么时候需要重新配置：
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)
// 如果 map 头端的节点备用空间不足
// 符合上述条件则必须重新配置 map
reallocate_map(nodes_to_add, true);
}
template
void deque::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 {
size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2;
// 配置一块空间，准备给新 map 使用
map_pointer new_map = map_allocator::allocate(new_map_size);
new_nstart = new_map + (new_map_size - new_num_nodes) / 2
+ (add_at_front ? nodes_to_add : 0);
// 把原 map 内容拷贝过来
copy(start.node, finish.node + 1, new_nstart);
// 释放原 map
map_allocator::deallocate(map, map_size);
// 设定新 map 的起始地址与大小
map = new_map;
map_size = new_map_size;
}
// 重新设定迭代器 start 和 finish
start.set_node(new_nstart);
finish.set_node(new_nstart + old_num_nodes - 1);
}
1.6 deque 的元素操作
push_*、pop_*：
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);
--start.cur;
}
// 第一个缓冲区已无备用空间
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();
}
在上述操作中，当操作发生在缓冲区边缘时，可能需要调用相应的函数：
// 当 finish.cur == finish.last - 1 时调用
// 最后缓冲区只有一个备用空间
template
void deque::push_back_aux(const value_type& t) {
value_type t_copy = t;
reserve_map_at_back(); // 符合某种条件则必须重换一个 map
*(finish.node + 1) = allocate_node(); // 配置一个新缓冲区
__stl_try {
construct(finish.cur, t_copy); // 在 finish.cur 处构造 t
finish.set_node(finish.node + 1); // 改变 finish，使其指向新缓冲区
finish.cur = finish.first; // 设定 finish 状态
}
__stl_unwind(deallocate_node(*(finish.node + 1)));
}
// 当 start.cur == start.first 时调用
// 第一个缓冲区没有备用空间
template
void deque::push_front_aux(const value_type& t) {
value_type t_copy = t;
reserve_map_at_front(); // 符合某种条件则必须重换一个 map
*(start.node - 1) = allocate_node(); // 配置一个新缓冲区
__stl_try {
start.set_node(start.node - 1); // 改变 start，使其指向新缓冲区
start.cur = start.last - 1; // 设定 start状态
construct(start.cur, t_copy); // 在 start.cur 处构造 t
}
# ifdef __stl_use_exceptions
catch(...) { // commit or rollback
start.set_node(start.node + 1);
start.cur = start.first;
deallocate_node(*(start.node - 1));
throw;
}
# endif /* __stl_use_exceptions */
}
// 当 finish.cur == finish.first 时调用
// 最后一个缓冲区没有任何元素
template
void deque:: pop_back_aux() {
deallocate_node(finish.first);
finish.set_node(finish.node - 1);
finish.cur = finish.last - 1;
destroy(finish.cur);
}
// 当 start.cur == start.last - 1 时调用
// 第一缓冲区只有一个元素
template
void deque::pop_front_aux() {
destroy(start.cur);
deallocate_node(start.first);
start.set_node(start.node + 1);
start.cur = start.first;
}
clear，清空整个 deque，由于 deque 的最初状态（不含任何元素）保有一个缓冲区，因此 clear 完成之后要回到初始状态，即也保留一个缓冲区：
template
void deque::clear() {
// 针对头尾以外的每一个缓冲区（他们一定是满的）
for (map_pointer node = start.node + 1; node < finish.node; ++node) {
// 调用 destroy 第二版本，析构所有元素
destroy(*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; // 调整迭代器 finish
}
erase，用于清除某个元素：
// 清除 pos 所指的元素，pos 为清除点
iterator erase(iterator pos) {
iterator next = pos;
++next;
// 清除点之前的元素个数
difference_type index = pos - start;
// 若清除点之前的元素少，就移动清除点之前的元素
if (index < (size() >> 1)) {
copy_backward(start, pos, next); // 移动元素
pop_front(); // 移动完毕，最前一个元素冗余
}
// 若清除点之后的元素少，就移动清除点之后的元素
else {
copy(next, finish, pos); // 移动元素
pop_back(); // 移动完毕，最后一个元素冗余
}
return start + index;
}
erase 还有一个版本用于清除 [first, last) 区间内的所有元素：
template
deque::iterator
deque::erase(iterator first, iterator last) {
// 若清除的是整个 deque，直接调用 clear
if (first == start && last == finish) {
clear();
return finish;
}
else {
difference_type n = last - first; // 清除区间长度
difference_type elems_before = first - start; // 清除区间之前的元素个数
// 清除区间之前的元素个数较少
if (elems_before < (size() - n) / 2) {
copy_backward(start, first, last); // 移动元素
iterator new_start = start + n; // 新的头端
destroy(start, new_start); // 析构元素
// 释放空间
for (map_pointer cur = start.node; cur < new_start.node; ++cur)
data_allocator::deallocate(*cur, buffer_size());
start = new_start; // 设定新的头端
}
else {
copy(last, finish, first); // 移动元素
iterator new_finish = finish - n; // 新的尾端
destroy(new_finish, finish); // 析构元素
// 释放空间
for (map_pointer cur = new_finish.node + 1; cur <= finish.node; ++cur)
data_allocator::deallocate(*cur, buffer_size());
finish = new_finish; // 设定新的尾
}
return start + elems_before;
}
}
insert，在指定迭代器 pos 处插入值为 x 的节点：
iterator insert(iterator position, const value_type& x) {
// 在 deque 头端插入，调用 push_front
if (position.cur == start.cur) {
push_front(x);
return start;
}
// 在 deque 尾端插入，调用 push_back
else if (position.cur == finish.cur) {
push_back(x);
iterator tmp = finish;
--tmp;
return tmp;
}
// 在其他位置插入
else {
return insert_aux(position, x);
}
}
template
typename deque::iterator
deque::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());
iterator front1 = start;
++front1;
iterator front2 = front1;
++front2;
pos = start + index;
iterator pos1 = pos;
++pos1;
copy(front2, pos1, front1); // 元素移动
}
// 插入点之后元素个数较少，则在尾端插入
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;
}
2. 适配器 stack
stack 是一种先进后出的数据结构，只有一个开口，允许进行：新增元素、移除元素、取顶端元素等操作，不能进行迭代器访问操作。
在 sgi stl 的实现中，stack 内含一个 deque 成员，其完整实现如下：
template >
class stack {
friend bool operator== __stl_null_tmpl_args (const stack&, const stack&);
friend bool operator< __stl_null_tmpl_args (const stack&, const stack&);
public:
typedef typename sequence::value_type value_type;
typedef typename sequence::size_type size_type;
typedef typename sequence::reference reference;
typedef typename sequence::const_reference const_reference;
protected:
sequence c;
public:
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference top() { return c.back(); }
const_reference top() const { return c.back(); }
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_back(); }
};
template
bool operator==(const stack& x, const stack& y) {
return x.c == y.c;
}
template
bool operator<(const stack& x, const stack& y) {
return x.c < y.c;
}
2. 适配器 queue
queue 是一种先进先出的数据结构，只能在一端插入，另一端移除，允许进行：新增元素、移除元素、取首尾元素等操作，不能进行迭代器访问操作。
在 sgi stl 的实现中，queue 内含一个 deque 成员，其完整实现如下：
template >
class queue {
friend bool operator== __stl_null_tmpl_args (const queue& x, const queue& y);
friend bool operator< __stl_null_tmpl_args (const queue& x, const queue& y);
public:
typedef typename sequence::value_type value_type;
typedef typename sequence::size_type size_type;
typedef typename sequence::reference reference;
typedef typename sequence::const_reference const_reference;
protected:
sequence c;
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(); }
};
template
bool operator==(const queue& x, const queue& y) {
return x.c == y.c;
}
template
bool operator<(const queue& x, const queue& y) {
return x.c < y.c;
}