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

__deque_iterator的数据结构

template <class T, class Ref, class Ptr, size_t BufSiz>
struct _deque_iterator
{
    ...
};

迭代器类型的别名和迭代器常用的属性们：

	typedef __deque_iterator<T, T&, T*>      iterator;typedef __deque_iterator<T, const T&, const T*> const_iterator;static size_t buffer_size() {
    return __deque_buf_size(0, sizeof(T)); }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* cur;       // 此迭代器所指之缓冲区中的现行元素T* first;     // 此迭代器所指之缓冲区的头T* last;      // 此迭代器所指之缓冲区的尾（含备用空间）map_pointer node;    // 指向管控中心

迭代器的构造函数

	__deque_iterator(T* x, map_pointer y): cur(x), first(*y), last(*y + buffer_size()), node(y) {
    }__deque_iterator() : cur(0), first(0), last(0), node(0) {
    }__deque_iterator(const iterator& x): cur(x.cur), first(x.first), last(x.last), node(x.node) {
    }

下面重载的这些运算符是让deque从外界看上去维护的是一段连续空间的关键!!

①前缀自增
如果当前迭代器指向元素是当前缓冲区的最后一个元素则将迭代器状态调，整为下一个缓冲区的第一个元素， 不是当前缓冲区最后一个元素的话执行前缀自增前的状态

	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个元素, n可以为负
先判断会不会超出（往前或往后）当前缓冲区，如果不会的话就直接加cur+n；
如果会超出的话，由于可以是负数，所以要考虑是往前移动多少个缓冲区或者往后移动多少个缓冲区，之后就是调整缓冲区，调整cur指针

// 迭代器可以直接跳跃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指针至正确的元素cur = first + (offset - node_offset * difference_type(buffer_size()));}return *this;}

⑤其他一些运算符重载

	reference operator*() const {
     return *cur; }// 判断两个迭代器间的距离difference_type operator-(const self& x) const{
    return difference_type(buffer_size()) * (node - x.node - 1) +(cur - first) + (x.last - x.cur);}//在+=基础上的const型self operator+(difference_type n) const{
    self tmp = *this;// 这里调用了operator +=()可以自动调整指针状态return tmp += n;}
//-n就是+n，只不过传入-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); }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);}

⑥map新增节点

void set_node(map_pointer new_node){
    node = new_node;first = *new_node;last = first + difference_type(buffer_size());}

deque的数据结构

template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque
{
    
...
};

一系列基础：

公有属性、迭代器别名、指向管理中心map指针、分配器、获取缓冲区最大存储元素数量，初始化map大小

public:                         // Basic typestypedef T value_type;typedef value_type* pointer;typedef value_type& reference;typedef size_t size_type;typedef ptrdiff_t difference_type;public:                         // Iteratorstypedef __deque_iterator<T, T&, T*, BufSiz>       iterator;protected:                      // Internal typedefstypedef pointer* map_pointer;// 这个提供STL标准的allocator接口, 见<stl_alloc.h>typedef simple_alloc<value_type, Alloc> data_allocator;typedef simple_alloc<pointer, Alloc> map_allocator;// 获取缓冲区最大存储元素数量static size_type buffer_size(){
    return __deque_buf_size(BufSiz, sizeof(value_type));}static size_type initial_map_size() {
     return 8; }

重要的四个成员变量四个指针

连接缓冲区与map， map是一个连续的空间，每一个元素都是一个指针，指针指向一个缓冲区

protected:                      // Data membersiterator start;               // 起始缓冲区iterator finish;              // 最后一个缓冲区map_pointer map;size_type map_size;   // map容量

简单的基础函数

	iterator begin() {
     return start; }iterator end() {
     return finish; }// 重载operator [] 提供随机访问能力reference operator[](size_type n) {
     return start[difference_type(n)]; }reference front() {
     return *start; }//返回reference reference back(){
    iterator tmp = finish;--tmp;//前闭后开return *tmp;}// 当前容器拥有的元素个数, 调用迭代器重载的operator -size_type size() const {
     return finish - start;; }size_type max_size() const {
     return size_type(-1); }// deque为空的时, 只有一个缓冲区bool empty() const {
     return finish == start; }//缓冲区中是first和last

构造函数和析构函数，

注意拷贝构造函数，如果当前容器size大，将多出来的erase掉， 用法erase(copy(x.begin(), x.end(), start), finish);先将x的元素先拷贝过去，copy函数返回的是一个迭代器指出已被赋值元素区间的最后一个位置，然后就在原容器中从这个copy函数返回位置到最后元素这个区间删除，即多出来的范围删除用。法就很好
如果当前容器长度不够的话，注意deque容器会将所有x超出的元素用insert追加进去，duque的insert函数后面再看

public:                         // Constructor, destructor.deque() : start(), finish(), map(0), map_size(0){
    create_map_and_nodes(0);//就是创建map和node}deque(size_type n, const value_type& value): start(), finish(), map(0), map_size(0){
    fill_initialize(n, value);}deque(int n, const value_type& value): start(), finish(), map(0), map_size(0){
    fill_initialize(n, value);}~deque(){
    destroy(start, finish);     // <stl_construct.h>destroy_map_and_nodes();}deque& operator= (const deque& x){
    // 拷贝构造函数，如果当前容器size大，将多出来的erase掉， 用法erase(copy(x.begin(), x.end(), start), finish);先将x的元素先拷贝过去，copy函数返回的是一个迭代器指出已被赋值元素区间的最后一个位置，然后就在原容器中从这个位置到最后元素这个区间的删除，即多出来的范围删除，用法就很好// 如果当前容器长度不够的话，注意deque容器会将所有x超出的元素用insert追加进去，duque的insert函数后面再看const size_type len = size();if (&x != this){
    // 当前容器比x容器拥有元素多, 析构多余元素if (len >= x.size())erase(copy(x.begin(), x.end(), start), finish);// 将x所有超出部分的元素使用insert()追加进去else {
    const_iterator mid = x.begin() + difference_type(len);copy(x.begin(), mid, start);insert(finish, mid, x.end());}}return *this;}

正经的牵扯到map的内存， 跨区块的函数们

push / pop函数， 先不考虑容器满或空的情况

public:void push_back(const value_type& t){
    // 最后缓冲区尚有两个（含）以上的元素备用空间if (finish.cur != finish.last - 1){
    construct(finish.cur, t);     // 直接在备用空间上构造元素++finish.cur;     // 调整最后缓冲区的使用状态}// 容量已满就要新申请内存了elsepush_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();    // 这里将进行缓冲区的释放工作}

insert函数，重点就是insert_aux函数

insert_aux在指定位置pos插入元素，需要判断是pos前端元素少还是后端少前：端少的话首先复制当前front值push到最前端，将元素往前拷贝移动；同理后端元素少的话，先复制一个最后元素push到最尾端，再拷贝后移；最后在位置pos上设定新值即可

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

erase函数、清除某个位置的元素、清除某个区间的元素

删除某个值的元素：删除完元素之后要移动元素，所以依旧要先判断是前端移动的元素少还是后端，代码中右移1位就是除以2
如果是前端的元素少，复制拷贝pos前的元素，最后再将重复的第一个元素删除；如果是后端的元素少，就移动之后的元素，最后将重复的最后一个元素删除；返回删除位置的元素

清除一个区间[ )的元素：如果清除区间是整个deque的话，直接调用clear()即可；否则
首先记录要删除区间的长度，以及前端待移动的元素用于判断是移动前端元素好还是后端元素好：如果是前方元素较少，将前端元素拷贝复制向后移动以覆盖待清除的区间，标记新起点new_start = start + n， 删除前端重复的元素并释放其空间，更新起点start = new_start；如果后端元素较少，则向前拷贝移动元素，标记新finish点，析构并释放重复的元素，最后更新finish为标记的finish

//清除某个位置的元素
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;}//清除某个区间的元素
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;}
}

下面解析push/pop超出当前缓存区时的情况：

    void push_back_aux(const value_type& t);void push_front_aux(const value_type& t);void pop_back_aux();void pop_front_aux();

?
push_back_aux:先调用reverse_map_at_back,若符合某种条件，重换一个map；分配空间。
reserve_map_at_back:看看map有没有满，满的话，调用reallocate_map。
reallocate_map:如果前端或后端pop过多，就会导致大量的空闲空间，如果是这种情况，则不用新分配空间，调整一下start的位置即可
总之，reserve_map_at_back就已经把map给搞定了，

因此

① push_back_aux的情况，给新配置一个缓冲区(node)，记得前闭后开的原则，给当前缓冲区的cur指针赋值，调整finish这个缓冲区的状态，finish.cur = finish.first
②pop_back_aux：释放最后一个缓冲区调，整finish状态，使指向上一个缓冲区的最后一个元素，将该元素析构
③push_front_aux、pop_front_aux同理

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();*(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)));
}// Called only if 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();*(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(...){
    start.set_node(start.node + 1);start.cur = start.first;deallocate_node(*(start.node - 1));throw;}
}// 只有当 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);                // 将该元素析构
}// 只有当 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;         // 下一个缓冲区的第一个元素
}