STL源码之deque容器深入学习

vector和deque都是连续线性空间，这往往给我们造成一种假设，认为vector和deque的区别仅仅在于一个单向一个双向。但是剖开它们的源码分析，会发现deque和vector的内部实现机制迥然不同，并且deque要复杂的多。

1. deque和vector的区别
   （1）vector是单向开头的连续线性空间，deque则是一种双向开口的连续线性空间。
   （2）deque允许在常数时间内对头部进行元素的插入或删除操作。
   （3）deque没有所谓容量(capacity)观念，因为它是动态地以分段连续空间组合而成随时可以增加一段新的空间并链接起来。
   （4）也因此，deque没有必要提供所谓的空间保留(reserve)功能。
   （5）虽然deque也提供Ramdon Access Iterator,但它的迭代器并不是普通的指针。
   （6）对deque进行排序，为了最高效率，可将deque先完整复制到一个vector内，对vector排序后，在复制回deque。现在我们知道了，deque是动态地以分段连续空间组合而成的。它不像vector那样是严格的连续线性空间，但却能实现vector连续线性空间的特性操作。那么问题来了，它究竟是怎么实现的呢？
2. deque的中控器
   （1）在前面有关vector部分内容中我们已经知道，vector虽然可以增长，却只能向尾端增长，并且其所谓增长实际上是做了三个方面的工作：
   寻找更大空间—>将原数据复制过去—>释放原空间。
   （2）而deque的增长机制是：在头部或尾部增加新空间，deque的最大任务就是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。
   （3）deque采用一块所谓的map(注意，不是STL的map容器)作为主控。
   （4）这里指的map是一小块连续空间，其中每个元素(称为节点node)都是一个指针，指向另一端(较大的)连续线性空间，称为缓冲区。缓冲区才是deque的存储空间主体。
   （5）SGI STL允许我们指定缓冲区大小，默认值0表示将使用512bytes缓冲区。
   
   C++

   template <class T, calss Alloc = alloc, size_t BufSiz = 0> class deque { public: //Basic types typedef T value_type; typedef value_type* pointer; ... protected: //元素的指针的指针(pointer of pointer of T) typedef pointer* map_pointer; protected: //Data members 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

   template <class T, calss Alloc = alloc, size_t BufSiz = 0> class deque { public: //Basic types typedef T value_type; typedef value_type* pointer; ... protected: //元素的指针的指针(pointer of pointer of T) typedef pointer* map_pointer; protected: //Data members map_pointer map; //指向map，map是块连续空间，其内的每个元素都是一个指针(称为节点)，指向一块缓冲区 size_type map_size; //map内可容纳多少指针 ... };

   
   如下图，map和node-buffer(节点-缓冲区)的关系：
3. deque的迭代器
   （1）deque是分段连续空间，维持其“整体连续”的假象的任务，落在了迭代器的operator++和operator–两个运算符上。
   （2）deque迭代器应该具备什么结构？
   （a）它必须能够指出分段连续空间(即缓冲区)在哪里。
   （b）它必须能够判断自己是否已经处于其所在缓冲区的边缘。
   （c）如果是，一旦前进或后退时就必须跳跃至下一个缓冲区。
   （d）为了能够正确跳跃，deque必须随时掌握管控中心(map)。
   基于上述四条，我们实现迭代器如下：
   
   C++

   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 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; //此迭代器所指缓冲区中的现行(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

   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 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; //此迭代器所指缓冲区中的现行(current)元素值 T* first; //此迭代器所指的缓冲区的头 T* last; //此迭代器所指缓冲区的尾(含备用空间,被保留不用于存储) map_pointer node; //指向管控中心 ... };

   
   （3）其中用来决定缓冲区大小的函数buffer_size()，调用__deque_buf_size()， 后者是一个全局函数，定义如下：
   
   C++

   //如果n不为0,传回n,表示buffer size由用户定义 //如果n为0，表示buffer size使用默认值，那么 // 如果sz(元素大小，sizeof(value_type))小于512，传回512/sz， // 如果sz不小于512，传回1 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)); }

   1 2 3 4 5 6 7 8

   //如果n不为0,传回n,表示buffer size由用户定义 //如果n为0，表示buffer size使用默认值，那么 // 如果sz(元素大小，sizeof(value_type))小于512，传回512/sz， // 如果sz不小于512，传回1 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，缓冲区大小为8(个元素)的deque(语法形式为deque<int, alloc, 8>)。经过某些操作之后，deque拥有20个元素，那么气begin()和end()所传回的两个迭代器应该如下图所示。这两个迭代器事实上一直保持在deque内，名为start和finish。20个元素需要20/8=3个缓冲区，所以map之内运用了三个节点。迭代器start内的cur指向缓冲区的第一个元素，迭代器finish内的cur指向缓冲区的最后元素(的下一位置)。

   （4）下面是deque迭代器的几个关键行为，其中最关键的就是：一旦行进时遇到缓冲区边缘，要特别当心，视前进或后退而定，可能需要调用set_node()跳一个缓冲区：

   C++

   void set_node(map_pointer new_node) { node = new_node; first = *new_node; last = first + difference_type(buffer_size()); //每个节点有四个字段，其中cur在这里并没有处理，因为上诉三个节点对节点跳跃来说是固定的 //处理方式，而往往cur并不固定。详情可见下面的前置++和前置--的重载函数 } //以下各个重载运算符是__deque_iterator<>成功运作的关键 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); //对上述计算有些疑惑，第三项不应该是(cur - first + 1)吗？ //按他的方法针对上一个例子：8*(3-1-1)+(3-0)+(8-0)=19？不应该是20吗？ //oh,yes，豁然开朗。求的是两者之间的距离，是19！ //20161021再次更正，距离应该是20：8*(3-1-1)+(4-0)+(8-0)=20。记住一点： //迭代器中指向最后一个元素一般都是指向尾后元素。上诉cur和x.last都是尾后元素。 } //参考More Effective C++，item6：Distingush between preifx and postfix self& operator++() { ++cur; //切换至下一个元素。因为last是尾后元素，需要先自增判断是否需要越界处理 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 = last -1;这样处理恰到好处，棒。 } --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; } self operator+(difference_type n) const { self tmp = *this; return tmp += n; //调用operator+= } self& operator-=(difference_type n) { return *this += -n; } //以上调用operator+=来完成operator-= self operator-(difference_type n) const { self tmp = *this; return tmp -= n; //调用operator-= } //以下实现随机存取，迭代器可以直接跳跃n个距离 reference operator[](difference_type n) const (return *(*this + n)); //以上调用operator*,operator+ 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 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

   void set_node(map_pointer new_node) { node = new_node; first = *new_node; last = first + difference_type(buffer_size()); //每个节点有四个字段，其中cur在这里并没有处理，因为上诉三个节点对节点跳跃来说是固定的 //处理方式，而往往cur并不固定。详情可见下面的前置++和前置--的重载函数 }   //以下各个重载运算符是__deque_iterator<>成功运作的关键   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); //对上述计算有些疑惑，第三项不应该是(cur - first + 1)吗？ //按他的方法针对上一个例子：8*(3-1-1)+(3-0)+(8-0)=19？不应该是20吗？ //oh,yes，豁然开朗。求的是两者之间的距离，是19！   //20161021再次更正，距离应该是20：8*(3-1-1)+(4-0)+(8-0)=20。记住一点： //迭代器中指向最后一个元素一般都是指向尾后元素。上诉cur和x.last都是尾后元素。 }   //参考More Effective C++，item6：Distingush between preifx and postfix self& operator++() { ++cur; //切换至下一个元素。因为last是尾后元素，需要先自增判断是否需要越界处理 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 = last -1;这样处理恰到好处，棒。 } --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; }   self operator+(difference_type n) const { self tmp = *this; return tmp += n; //调用operator+= }   self& operator-=(difference_type n) { return *this += -n; } //以上调用operator+=来完成operator-=   self operator-(difference_type n) const { self tmp = *this; return tmp -= n; //调用operator-= }   //以下实现随机存取，迭代器可以直接跳跃n个距离 reference operator[](difference_type n) const (return *(*this + n)); //以上调用operator*,operator+   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); } }

    

4. deque的数据结构
   deque除了维护指向map的指针外，也维护start, finish两个迭代器，分别指向第一缓冲区的第一个元素和最后缓冲区的最后一个元素(的下一个位置)。
   deque数据结构源码：
   C++

   //见__deque_buf_size().BufSiz默认值为0的唯一理由是为了闪避某些 //编译器在处理常数算式(const expression)时的bug //缺省使用alloc为配置器 template <class T, class Alloc, size_t BufSiz = 0> class deque { public: //Basic types typedef T value_type; typedef value_type* pointer; typedef size_t size_type; public: typedef __deque_iterator<T, T&, T*, BufSiz> iterator; protected: //元素的指针的指针 typedef pointer* map_pointer; protected: //Data members iterator start; //表示第一个节点 iterator finish; //表示最后一个节点 map_pointer map; //指向map, map是块连续空间，其中每个元素都是个指针，指向一个节点(缓冲区) size_type map_size; //map内有多少指针 ... } //有了上述结构，一下数个机能便可轻易完成： public: 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 *(finish-1); //因为__deque_iterator<>没有为(finish-1)定义运算符 } //下行最后有两个;，虽然奇怪但合乎语法 size_type size() const { return finish - start;; } //以上调用iterator::operator- 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

   //见__deque_buf_size().BufSiz默认值为0的唯一理由是为了闪避某些 //编译器在处理常数算式(const expression)时的bug //缺省使用alloc为配置器 template <class T, class Alloc, size_t BufSiz = 0> class deque { public: //Basic types typedef T value_type; typedef value_type* pointer; typedef size_t size_type; public: typedef __deque_iterator<T, T&, T*, BufSiz> iterator; protected: //元素的指针的指针 typedef pointer* map_pointer; protected: //Data members iterator start; //表示第一个节点 iterator finish; //表示最后一个节点 map_pointer map; //指向map, map是块连续空间，其中每个元素都是个指针，指向一个节点(缓冲区) size_type map_size; //map内有多少指针 ... }   //有了上述结构，一下数个机能便可轻易完成： public: 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 *(finish-1); //因为__deque_iterator<>没有为(finish-1)定义运算符 } //下行最后有两个;，虽然奇怪但合乎语法 size_type size() const { return finish - start;; } //以上调用iterator::operator- size_type max_size() const { return size_type(-1); } bool empty() const { return finish == start; }

5. deque的构造与内存管理：ctor, push_back, push_front
   deque的缓冲区扩充操作相当复杂。下面一步一步说明：
   （1）deque自行定义了两个专属的空间配置器：
   C++

   protected: //专属空间配置器，每次配置一个元素大小 typedef simple_alloc<value_type, Alloc> data_allocator; //专属空间配置器，每次配置一个指针大小 typedef simple_alloc<pointer, Alloc> map_allocator; //并提供有一个constructor如下： deque(int n, const value_type& value) : start(), finish(), map(0), map_size(0) { fill_initialize(n, value) ; } //其内所调用的fill_initialize()负责产生并安排好deque的结构 //并将元素的初值设定妥当： template <class T, class Alloc, sizze_t BufSiz> void deque<T, Alloc, BufSiz>::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()负责产生并安排好deque的结构： template <class T, class Alloc, size_t BufSiz> void deque<T, Alloc, BufSiz>::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指向这多配的一个节点（所对应的缓冲区）的起始处 }

   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

   protected: //专属空间配置器，每次配置一个元素大小 typedef simple_alloc<value_type, Alloc> data_allocator; //专属空间配置器，每次配置一个指针大小 typedef simple_alloc<pointer, Alloc> map_allocator; //并提供有一个constructor如下： deque(int n, const value_type& value) : start(), finish(), map(0), map_size(0) { fill_initialize(n, value) ; } //其内所调用的fill_initialize()负责产生并安排好deque的结构 //并将元素的初值设定妥当： template <class T, class Alloc, sizze_t BufSiz> void deque<T, Alloc, BufSiz>::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()负责产生并安排好deque的结构： template <class T, class Alloc, size_t BufSiz> void deque<T, Alloc, BufSiz>::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指向这多配的一个节点（所对应的缓冲区）的起始处 }

   （2）以下是push_back()函数内容：

   C++

   public: 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()调用push_back_aux() //先配置一整块新的缓冲区，在设妥新元素内容然后更改迭代器finish的状态： //只有当finish.cur == finish.last-1时才会被调用 //也就是说，只有当最后一个缓冲区只剩一个备用元素空间时才会被调用 template <class T, class Alloc, size_t BufSiz> void deque<T, Alloc, BufSiz>::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))); }

   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

   public: 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()调用push_back_aux() //先配置一整块新的缓冲区，在设妥新元素内容然后更改迭代器finish的状态： //只有当finish.cur == finish.last-1时才会被调用 //也就是说，只有当最后一个缓冲区只剩一个备用元素空间时才会被调用 template <class T, class Alloc, size_t BufSiz> void deque<T, Alloc, BufSiz>::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))); }

   （3）接着是push_front()函数源码：

   C++

   public: 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(); //只有的那个start.cur == start.first时才会被调用 //也就是说，只有当第一个缓冲区没有任何备用元素时才会被调用 template <class T, class Alloc, size_t BufSiz> void deque<T, Alloc, BufSiz>::push_back_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.cut, t_copy); //针对标的元素设值 } catch(...) { //“commit or rollback” start.set_node(start.node + 1); start.cur = start.first; deallocate_node(*(start.node - 1)); } }

   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

   public: 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(); //只有的那个start.cur == start.first时才会被调用 //也就是说，只有当第一个缓冲区没有任何备用元素时才会被调用 template <class T, class Alloc, size_t BufSiz> void deque<T, Alloc, BufSiz>::push_back_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.cut, t_copy); //针对标的元素设值 } catch(...) { //“commit or rollback” start.set_node(start.node + 1); start.cur = start.first; deallocate_node(*(start.node - 1)); } }

   （4）还有一个问题：什么时候map需要重新整治呢？这个问题的判断由reserve_map_at_back()和reserve_map_at_front()进行，实际操作则由reallocate_map()执行：

   C++

   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 <class T, class Alloc, size_t BufSiz> void deque<T, Alloc, BufSiz>::reallocate_map(size_type nodes_to_add, bool add_at_front) { size_type old_num_nodes = finish.nodes - 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 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

   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 <class T, class Alloc, size_t BufSiz> void deque<T, Alloc, BufSiz>::reallocate_map(size_type nodes_to_add, bool add_at_front) { size_type old_num_nodes = finish.nodes - 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); }

    （5）实例
   （a）假设我们对ideq进行了ideq.push_back()等一系列操作之后得到下图的情形：

   （b）现在如果在新增加一个元素于尾端：ideq.push_back(3);由于尾端只剩一个元素备用空间，于是push_back()调用push_back_aux()，先配置一整块新的缓冲区，在设妥新元素内容，然后更改迭代器finish的状态。如下图：（c）随后，我们再在ideq的前端插入一个新元素：iqed.push_front(99);由于目前状态下，第一缓冲区并无备用空间，所以调用push_front_aux()，如下图：
   参考：STL源码剖析