C++(STL):21---deque之源码剖析

一、deque概述

deque的使用语法：
总的来说：是一个双端队列
特点：

支持快速随机访问（支持索引取值）
在头尾插入/删除速度很快
deque是非常复杂的数据结构，由多个vector组成，迭代器使用时会在不同的区间跳转
存取元素的时候，deque的内部结构会多出一个间接过程，相比vector操作会慢一些
对内存有限制的系统中，deque比vector可以包含更多元素，因为它不止使用一块内存

设计目的：在头尾两端分别做元素的插入和删除操作。相比于vector，vector在头部操作效率太低

何时使用：需要在两端进行插入删除操作
与vector最大的差异：

一在于deque允许于常数时间内对起头端进行元素的插入或移除动作
二在于deque没有所谓容量（capacity）观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。换句话说，像vector那样“因旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在deque 是不会发生的。也因此，deque没有必要提供所谓的空间保留（reserve）功能

deque的迭代器：虽然deque也提供 Ramdon Access Iterator，但它的迭代器并不是原生指标，其复杂度和 vector不可以相对比（稍后看到源码，你便知道），这当然在在影响了各个运算层面。因此，除非必要，我们应尽可能选择使用vector而非deque。对deque进行的排序动作，为了最高效率，可将deque先完整复制到一个vector中，将vector排序后（利用STL sort 算法），再复制回deque
与其他容器的比较：

vector	可变大小数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢
deque	双端队列。支持快速随机访问。在头尾插入/删除速度很快
list	双向链表。支持双向顺序访问。在list中任何位置进行插入和删除的速度都很快
forward_list	单向链表。只支持单向顺序访问。在链表任何位置进行插入和删除操作速度都很快
array	固定大小数组。支持快速随机访问。不能添加或删除元素
string	与vector相似的容器，但专门用于保存字符。随机访问快。在尾部插入或删除速度快

二、deque的中控器（map）与缓冲区

deque是由一段一段的定量连续空间构成：

一旦有必要在deque 的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个 deque的头端或尾端。
deque的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。避开了“重新配置、复制、释放”的轮回，代价则是复杂的迭代器架构

受到分段连续线性空间的字面影响，我们可能以为deque的实现复杂度和vector相比虽不中亦不远矣，其实不然。主要因为，既要分段连续线性空间，就必须有中央控制，而为了维护整体连续的假象，数据结构的设计及迭代器前进后退等动作都颇为繁琐。deque的实现代码量远比vector或 list都多得多

map、map_size

deque采用一块所谓的map（注意，不是STL的map容器）做为主控
这里所谓map是一小块连续空间，其中每个元素（此处称为㆒个节点，node）都是指针，指向另一段（较大的）连续线性空间，称为缓冲区
缓冲区才是deque 的储存空间主体。SGI STL允许我们指定缓冲区大小，默认值0表示将使用512 bytes缓冲区

template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque {
public: //Basic types
typedef T value_type;
typedef value_type* pointer;
...




protected: //Internal typedefs
//元素的指针的指针（pointer of pointer of T）
typedef pointer* map_pointer;




protected: // Data members
map_pointer map;    //指向 map，map是块连续空间，其内的每个元素
//都是一个指标（称为节点），指向一块缓冲区
size_type map_size; //map内可容纳多少指针
...
};

把令人头皮发麻的各种型别定义（为了型别安全，那其实是有必要的）整理一下，我们便可发现，map其实是一个T**，也就是说它是一个指针，所指之物又是一个指标，指向型别为T的一块空间，如下图所示

稍后在deque的建构过程中，我会详细解释map的配置及维护
备注：deque的最初状态（无任何元素）时保有一个缓冲区（下面介绍clear时会提到）

三、deque的迭代器

deque是分段连续空间。维护其“整体连续”假象的任务，着落在迭代器的operator++ 和 operator-- 两个运算符身上
让我们思考一下，deque迭代器应该具备什么结构：

首先，它必须能够指出分段连续空间（亦即缓冲区）在哪里
其次它必须能够判断自己是否已经处于其所在缓冲区的边缘，如果是，一旦前进或后退时就必须跳跃至下一个或上一个缓冲区
为了能够正确跳跃，deque必须随时掌握管控中心（map）
下面的源码符合这些需求

cur、first、last、node、buffer_size()函数

cur：当前迭代器所指的元素
first：迭代器当前所指的缓冲区区间的头
last：迭代器当前所指的缓冲区区间的尾
node：指向deque管控器中的一个指针。用来指针当前迭代器所指的缓冲区归管控器中的哪一个指针所管理
buffer_size()函数：绝对缓冲区大小的函数，调用__deque_buf_size()全局函数（见下面介绍）

template <class T, class Ref, class Ptr, size_t BufSiz>
struct deque_iterator { // 未继承 std::iterator




typedef deque_iterator<T, T&, T*, BufSiz> iterator;
typedef deque_iterator<T, const T&, const T*, BufSiz> const_iterator;
static size_t buffer_size(){return deque_buf_size(BufSiz,sizeof(T));}




// 未继承 std::iterator，所以必须自行撰写五个必要的迭代器相应型别
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; // 此迭代器所指之缓冲区中的现行（current）元素
T* first; // 此迭代器所指之缓冲区的头
T* last; // 此迭代器所指之缓冲区的尾（含备用空间）
map_pointer node; // 指向管控中心
...
};

deque_buf_size()全局函数

迭代器中用来决定缓冲区大小的函数buffer_size()，直接调用deque_buf_size()，这是个全局函数，定义如下：

如果sz（元素大小，sizeof(value_type)）小于512，传回512/sz
如果sz不小于 512，返回1
如果n不为0，传回n，表示buffer size由使用者自定
如果n为0，表示buffer size使用默认值，那么：

备注：n是指缓冲区可以存放多少个数据类型为T的元素，而不是缓冲区的字节大小。例如一个deque存放的数据，其类型为intn，n=8，代表缓冲区可以存放8个int值（缓冲区大小为8），而缓冲区的字节大小为4*8=32bytes

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

演示说明

假设我们声明一个deque<int,alloc,8>，那么这个deque的缓冲区大小为8（是指缓冲区可以存放8个int类型的元素），缓冲区的字节数为4*8=32bytes
再假设经过某些操作之后，deque拥有20个元素，那么其begin() 和 end()所传回的两个迭代器应该如下图所示。这两个迭代器事实上一直保持在deque内，名为start 和 finish，稍后在deque数据结构中便可看到
20个元素需要20/8=3个缓冲区，所以map之内运用了三个节点

迭代器start内的cur指标当然指向缓冲区的第一个元素
迭代器finish内的cur指标当然指向缓冲区的最后元素（的下一位置）
注意，最后一个缓冲区尚有备用空间。如果有新元素要插入于尾端，可直接拿此备用空间来使用

迭代器其他函数（附set_node函数）

下面是deque迭代器的几个关键行为。由于迭代器内对各种指标运算都做了重载操作，所以各种指标运算如加、减、前进、后退都不能直观视之
其中最重点的关键就是：一旦行进时遇到缓冲区边缘，要特别当心，视前进或后退而定，可能需要调用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);
}




// 参考 More Effective C++, item6: Distinguish between prefix and
// postfix forms of increment and decrement operators.
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;
}

四、deque的数据结构（start迭代器、finish迭代器）

deque除了维护一个先前说过的指向map的指标外，也维护start, finish两个迭代器：

分别指向第一缓冲区的第一个元素和最后缓冲区的最后一个元素的下一位置（可以参见上图）
此外它也记住目前的map大小。因为一旦map所提供的节点不足，就必须重新配置更大的以块map

// 见 deque_buf_size()。BufSize 默认值为 0 的唯一理由是为了闪避某些
// 编译程序在处理常数算式（constant expressions）时的臭虫。
// 默认使用alloc为配置器
template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque {
public: // Basic types
typedef T value_type;
typedef value_type* pointer;
typedef size_t size_type;




public: // Iterators
typedef deque_iterator<T, T&, T*, BufSiz> iterator;




protected: // Internal typedefs
// 元素的指针的指针（pointer of pointer of T）
typedef pointer* map_pointer;




protected: // Data members
iterator start;  // 表现第一个节点。
iterator finish; // 表现最后一个节点。
map_pointer map; // 指向 map，map是块连续空间，
// 其每个元素都是个指针，指向一个节点（缓冲区）
size_type map_size; // map内有多少指标
...
};

有了上述结构，以下几个机能便可轻易完成：

public: // Basic accessors
iterator begin() { return start; }
iterator end() { return finish; }




reference operator[](size_type n) {
return start[difference_type(n)]; //调用__deque_iterator<>::operator[]
}




reference front() { return *start; } //调用__deque_iterator<>::operator*
reference back() {
iterator tmp = finish;
--tmp;       //调用__deque_iterator<>::operator--
return *tmp; //调用__deque_iterator<>::operator*
// 以上三行何不改为：return *(finish-1);
// 因为__deque_iterator<> 没有为 (finish-1) 定义运算符?!
}




//下行最后有两个 ‘;’，虽奇怪但合乎语法
size_type size() const { return finish - start;; }




// 以上唤起 iterator::operatorsize_type
max_size() const { return size_type(-1); }
bool empty() const { return finish == start; }

五、deque的构造于内存管理（constructor、push_back、push_front）

deque的内存分配

deque的缓冲区扩充动作相当琐碎繁杂，以下将以分解动作的方式一步一步说明
程序一开始声明了一个deque：

deque<int,alloc,8> ideq(20,9);

其缓冲区大小为8（保存8个int类型的元素），并令其保留20个元素空间，每个元素初值为9。为了指定 deque的第3个 template 参数（缓冲区大小），我们必须将前两个参数都指明出来（C++语法规则），因此必须明确指定alloc为空间配置器
现在，deque的情况如下图所示（该图并未显示每个元素的初值为 9）

data_allocator、map_allocator

deque自行定义了两个专属的空间配置器

protected: // Internal typedefs
//专属之空间配置器，每次配置一个元素大小
typedef simple_alloc<value_type, Alloc> data_allocator;
// 专属之空间配置器，每次配置一个指针大小
typedef simple_alloc<pointer, Alloc> map_allocator;

构造函数

其中一个构造函数的版本如下

deque(int n, const value_type& value): start(), finish(), map(0), map_size(0)
{
fill_initialize(n, value);
}

fill_initialize()

其内所调用的fill_initialize() 负责产生并安排好deque的结构，并将元素的初值设定妥当：

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::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);
}
catch(...) {
...
}
}

create_map_and_nodes()

其中create_map_and_nodes()负责产生并安排好deque的结构：

template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::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);
// 以上配置出一个 “具有 map_size个节点” 的 map




// 以下令 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();
}




catch(...) {
// "commit or rollback" 语意：若非全部成功，就一个不留
...
}




// 为 deque内的两个迭代器start和end设定正确内容
start.set_node(nstart);
finish.set_node(nfinish);
start.cur = start.first; // first, cur都是 public
finish.cur = finish.first + num_elements % buffer_size();
// 前面说过，如果刚好整除，会多配一个节点
// 此时即令 cur指向这多配的一个节点（所对映之缓冲区）的起头处
}

图示说明

在上面的演示案例中，我们的第3个缓冲区还有4个空间使用，现在我们执行下面的代码在尾部增加3个元素：

for(int i=0;i<3;i++)
ideq.push_back(i);

由于此时最后一个缓冲区仍有4个备用元素空间，所以不会引起缓冲区的再配置。此时的deque状态如下图所示

push_front()

以下是 push_back()函数的内容：

public: // push_* and 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);
}

push_back_aux()

当尾端没有剩余空间或者只剩一个元素备用空间，push_back()就会调用push_back_aux()，先配置一整块新的缓冲区，再设妥新元素内容，然后更改迭代器finish的状态：

// 只有当 finish.cur == finish.last – 1 时才会被呼叫。
// 也就是说只有当最后一个缓冲区只剩一个备用元素空间时才会被调用
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(); //若符合某种条件则必须重换一个map
*(finish.node + 1) = allocate_node(); //配置一个新节点（缓冲区）
__STL_TRY {
construct(finish.cur, t_copy); //针对标的元素设值
finish.set_node(finish.node + 1); //改变 finish，令其指向新节点
finish.cur = finish.first; //设定 finish的状态
}
__STL_UNWIND(deallocate_node(*(finish.node + 1)));
}

演示说明

如果当前deque的状态如上图所示。现在，如果再新增加一个新元素于尾端：

ideq.push_back(3);

现在，deque的状态将如下所示，多申请了一个缓冲区

push_front()

push_front()函数的原型如下：

public: // push_* and pop_*
void push_front(const value_type& t) {
if (start.cur != start.first) { //第一缓冲区尚有备用空间
construct(start.cur - 1, t); //直接在备用空间上建构元素
--start.cur; // 调整第㆒缓冲区的使用状态
}
else //第一缓冲区已无备用空间
push_front_aux(t);
}

push_front_aux()

如果第一缓冲区并无备用空间，那么就会调用push_front_aux()

此函式一开始即呼叫 reserve_map_at_front()，后者用来判断是否需要扩充map，如有需要就付诸行动。稍后我会呈现 reserve_map_at_front() 的函式内容

//只有当 start.cur == start.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(); // 若符合某种条件则必须重换一个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); //针对标的元素设值
}
catch(...) {
// "commit or rollback" 语意：若非全部成功，就一个不留
start.set_node(start.node + 1);
start.cur = start.first;
deallocate_node(*(start.node - 1));
throw;
}
}

演示案例

如果deque的状态如上图所示，此时我们执行下面的代码：

ideq.push_front(99);

上图的的状态不需要重新整治map，所以后继流程便配置了一块新缓冲区并直接将节点安置于现有的map上，然后设定新元素，然后改变迭代器start的状态，如下图所示

如果现在我们在头部添加两个元素，则结构会更新如下图所示：

ideq.push_front(98);
ideq.push_front(97);

map重分配

上面介绍的push_back_aux()、push_front_aux()函数，这些函数会首先分别调用reserve_map_at_back()、reserve_map_at_front()对map进行重新整治

reserve_map_at_back()

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

reserve_map_at_front()

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

reallocate_map()

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

六、deque的元素操作

pop_back、pop_front、clear、erase、insert

pop_back()

void pop_back()
{
if (finish.cur != finish.first) {
//最后缓冲区有一个（或更多）元素
--finish.cur; // 调整指针，相当于排除了最后元素
destroy(finish.cur); // 将最后元素析构
}
else
//最后缓冲区没有任何元素
pop_back_aux(); // 这里将进行缓冲区的释放工作
}

pop_back_aux()

// 只有当 finish.cur == finish.first时才会被调用
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 的状态，使指向
finish.cur = finish.last - 1; //上一个缓冲区的最后一个元素
destroy(finish.cur); // 将该元素析构
}

pop_front()

void pop_front()
{
if (start.cur != start.last - 1)
{
//第一缓冲区有一个（或更多）元素
destroy(start.cur); //将第一元素析构
++start.cur; //调整指针，相当于排除了第一元素
}
else
//第一缓冲区仅有一个元素
pop_front_aux(); // 这里将进行缓冲区的释放工作
}

pop_front_aux()

// 只有当 start.cur == start.last - 1时才会被调用
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 的状态，使指向
start.cur = start.first;        //下一个缓冲区的第一个元素
}

clear()

clear()用来清除整个deque
请注意，deque的最初状态（无任何元素时）保有一个缓冲区，因此clear()完成之后回复初始状态，也一样要保留一个缓冲区：

// 注意，最终需要保留一个缓冲区。这是deque的策略，也是deque的初始状态
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::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; //调整状态
}

erase()

下面的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 <class T, class Alloc, size_t BufSize>
deque<T, Alloc, BufSize>::iterator
deque<T, Alloc, BufSize>::erase(iterator first, iterator last) {
if (first == start && last == finish) { // 如果清除区间就是整个deque
clear();                            // 直接调用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;           // 标记 deque 的新起点
destroy(start, new_start);                // 移动完毕，将冗余的元素析构
// 以下将冗余的缓冲区释放
for (map_pointer cur = start.node; cur < new_start.node; ++cur)
data_allocator::deallocate(*cur, buffer_size());
start = new_start; // 设定 deque 的新起点
}




else { // 如果清除区间后方的元素比较少
copy(last, finish, first);        // 向前搬移后方元素（覆盖清除区间）
iterator new_finish = finish - n; // 标记 deque 的新尾点
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; // 设定 deque 的新尾点
}
return start + elems_before;
}
}

insert()函数

insert提供了许多版本，最基础最重要的是以下的版本，允许在某个点（之前）插入一个元素，并设定其值

// 在 position 处插入一个元素，其值为 x
iterator insert(iterator position, const value_type& x) {
if (position.cur == start.cur) { // 如果插入点是 deque 最前端
push_front(x);               //交给push_front去做
return start;
}
else if (position.cur == finish.cur) { //如果插入点是 deque 最尾端
push_back(x);                      // 交给 push_back 去做
iterator tmp = finish;
--tmp;
}
else {
return insert_aux(position, x); // 交给 insert_aux 去做
}
}

insert_aux()函数

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;




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

C++(STL):21---deque之源码剖析

一、deque概述

二、deque的中控器（map）与缓冲区

map、map_size

三、deque的迭代器

cur、first、last、node、buffer_size()函数

deque_buf_size()全局函数

演示说明

迭代器其他函数（附set_node函数）

四、deque的数据结构（start迭代器、finish迭代器）

五、deque的构造于内存管理（constructor、push_back、push_front）

deque的内存分配

data_allocator、map_allocator

构造函数

fill_initialize()

create_map_and_nodes()

图示说明

push_front()

push_back_aux()

演示说明

push_front()

push_front_aux()

演示案例

map重分配

reserve_map_at_back()

reserve_map_at_front()

reallocate_map()

六、deque的元素操作

pop_back()

pop_back_aux()

pop_front()

pop_front_aux()

clear()

erase()

insert()函数

insert_aux()函数

继续阅读