首页 > 代码库 > STL源码分析--deque

STL源码分析--deque

2024-07-19 21:57:39   225人阅读

一、deque的中控器
      deque是连续空间（至少逻辑上看来如此），连续线性空间总令我们联想到array或vector。array无法成长，vector虽可成长，却只能向尾端成长，而且其所谓的成长原是个假象，事实上是（1）另觅更大空间；（2）将原数据复制过去；（3）释放原空间三部曲。如果不是vector每次配置新空间时都有留下一些余裕，其成长假象所带来的代价将是相当高昂。
      deque系由一段一段的定量连续空间构成。一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或尾端。deque的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的借口。避开了“重新配置、复制、释放”的轮回，代价则是复杂的迭代器架构。
      受到分段连续线性空间的字面影响，我们可能以为deque的实现复杂度和vector相比虽不中亦不远矣，其实不然。主要因为，既是分段连续线性空间，就必须有中央控制，而为了维持整体连续的假象，数据结构的设计及迭代器前进后退等操作都颇为繁琐。deque的实现代码分量远比vector或list都多得多。
      deque采用一块所谓的map（注意，不是STL的map容器）作为主控。这里所谓map是一小块连续空间，其中每个元素（此处称为一个节点，node）都是指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是deque的储存空间主体。SGI STL 允许我们指定缓冲区大小，默认值0表示将使用512 bytes 缓冲区。
二、deque的迭代器
      让我们思考一下，deque的迭代器应该具备什么结构，首先，它必须能够指出分段连续空间（亦即缓冲区）在哪里，其次它必须能够判断自己是否已经处于其所在缓冲区的边缘，如果是，一旦前进或后退就必须跳跃至下一个或上一个缓冲区。为了能够正确跳跃，deque必须随时掌握管控中心（map）。所以在迭代器中需要定义：当前元素的指针，当前元素所在缓冲区的起始指针，当前元素所在缓冲区的尾指针，指向map中指向所在缓区地址的指针。
在进行迭代器的移动时，需要考虑跨缓冲区的情况。
重载前加(减)，在实现后加(减)时，调用重载的前加(减)。
重载+=,实现+时，直接调用+=,实现-=时，调用+=负数，实现-时，调用-=.
//当需要实现新的功能时，最好使用已经重载好的操作，即方便有安全。。。。
另外，deque在效率上来说是不够vector好的，因此有时候在对deque进行sort的时候，需要先将元素移到vector再进行sort，然后移回来。

构造函数：根据缓冲区设置大小和元素个数，决定map的大小；给map分配空间，根据缓冲区的个数，分配缓冲区，默认指定一个缓冲区；
 设置start和finish迭代器，满足左闭右开的原则。
 push_back:如果空间满足，直接插入；不满足，调用push_back_aux。
 push_back_aux:先调用reverse_map_at_back,若符合某种条件，重换一个map；分配空间。
 reserve_map_at_back:看看map有没有满，满的话，调用reallocate_map。
 reallocate_map:如果前端或后端pop过多，就会导致大量的空闲空间，如果是这种情况，则不用新分配空间，调整一下start的位置即可；
 如果不够，则需要重新申请空间。
 pop：析构元素，如果是最后一块还需要删除空间。
 erase：需要判断，前面的元素少还是后面的元素少，移动较少的部分。
 insert：判断位置，如果为前端或后端直接调用push操作，否则，移动较少的一端。
deque的构造与内存管理：
由于deque的设计思想就是由一块块的缓存区连接起来的，因此它的内存管理会比较复杂。插入的时候要考虑是否要跳转缓存区、是否要新建map节点（和vector一样，其实是重新分配一块空间给map，删除原来空间）、插入后元素是前面元素向前移动还是后面元素向后面移动（谁小移动谁）。而在删除元素的时候，考虑是将前面元素后移覆盖需要移除元素的地方还是后面元素前移覆盖（谁小移动谁）。移动完以后要析构冗余的元素，释放冗余的缓存区。
三、deque的源码剖析
[cpp] view plaincopy
  1. //   deque的特性:  
  2. //   对于任何一个迭代器i  
  3. //     i.node是map array中的某元素的地址. i.node的内容是一个指向某个结点的头的指针  
  4. //     i.first == *(i.node)  
  5. //     i.last  == i.first + node_size  
  6. //     i.cur是一个指向[i.first, i.last)之间的指针  
  7. //       注意: 这意味着i.cur永远是一个可以解引用的指针,  
  8. //            即使其是一个指向结尾后元素的迭代器  
  9. //  
  10. //   起点和终点总是非奇异(nonsingular)的迭代器.  
  11. //     注意: 这意味着空deque一定有一个node, 而一个具有N个元素的deque  
  12. //          (N是Buffer Size)一定有有两个nodes  
  13. //  
  14. //   对于除了start.node和finish.node之外的每一个node, 每一个node中的元素  
  15. //   都是一个初始化过的对象. 如果start.node == finish.node,  
  16. //   那么[start.cur, finish.cur)都是未初始化的空间.  
  17. //   否则, [start.cur, start.last)和[finish.first, finish.cur)都是初始化的对象,  
  18. //   而[start.first, start.cur)和[finish.cur, finish.last)是未初始化的空间  
  19. //  
  20. //   [map, map + map_size)是一个合法的非空区间  
  21. //   [start.node, finish.node]是内含在[map, map + map_size)区间的合法区间  
  22. //   一个在[map, map + map_size)区间内的指针指向一个分配过的node,  
  23. //   当且仅当此指针在[start.node, finish.node]区间内  
  24.   
  25. inline size_t __deque_buf_size(size_t n, size_t sz)    
  26. {    
  27.   return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));    
  28. }  
  29.   
  30. // __deque_iterator的数据结构  
  31. template <class T, class Ref, class Ptr, size_t BufSiz>  
  32. struct __deque_iterator  
  33. {  
  34.     typedef __deque_iterator<T, T&, T*>             iterator;  
  35.     typedef __deque_iterator<T, const T&, const T*> const_iterator;  
  36.     static size_t buffer_size() {return __deque_buf_size(0, sizeof(T)); }  
  37.   
  38.     typedef random_access_iterator_tag iterator_category;  
  39.     typedef T value_type;  
  40.     typedef Ptr pointer;  
  41.     typedef Ref reference;  
  42.     typedef size_t size_type;  
  43.     typedef ptrdiff_t difference_type;  
  44.     typedef T** map_pointer;  
  45.   
  46.     typedef __deque_iterator self;  
  47.   
  48.     // 保持与容器的联结  
  49.     T* cur;       // 此迭代器所指之缓冲区中的现行元素  
  50.     T* first;     // 此迭代器所指之缓冲区的头  
  51.     T* last;      // 此迭代器所指之缓冲区的尾（含备用空间）  
  52.     map_pointer node;    // 指向管控中心  
  53.   
  54. ////////////////////////////////////////////////////////////////////////////////  
  55. // 这个是deque内存管理的关键, 其模型如下  
  56. ////////////////////////////////////////////////////////////////////////////////  
  57. //  
  58. //       ---------------------------------------------  
  59. // map-->|   |   |   |   |   |   | ..... |   |   |   |<------------------  
  60. //       ---------------------------------------------                  |  
  61. //             |                                                        |  
  62. //             |                                                        |  
  63. //             |   node                                                 |  
  64. //             |   缓冲区buffer, 这里实际存储元素                          |  
  65. //             |   ---------------------------------------------        |  
  66. //             --->|   |   |   |   |   |   | ..... |   |   | X |        |  
  67. //                 ---------------------------------------------        |  
  68. //                   ↑       ↑                             ↑            |  
  69. //             ------        |                             |            |  
  70. //             |             |                             |            |  
  71. //             |   -----------   ---------------------------            |  
  72. //             ----|-----        |                                      |  
  73. //                 |    |        |                                      |  
  74. //                 |    |        |                                      |  
  75. //                 |    |        |                                      |  
  76. //              ---------------------------                             |  
  77. //              | cur | first | end | map |------------------------------  
  78. //              ---------------------------  
  79. //              迭代器, 其内部维护着一个缓冲区状态  
  80. ////////////////////////////////////////////////////////////////////////////////  
  81.     __deque_iterator(T* x, map_pointer y)  
  82.         : cur(x), first(*y), last(*y + buffer_size()), node(y) {}  
  83.     __deque_iterator() : cur(0), first(0), last(0), node(0) {}  
  84.     __deque_iterator(const iterator& x)  
  85.         : cur(x.cur), first(x.first), last(x.last), node(x.node) {}  
  86.   
  87.     reference operator*() const { return *cur; }  
  88.   
  89.     // 判断两个迭代器间的距离  
  90.     difference_type operator-(const self& x) const  
  91.     {  
  92.         return difference_type(buffer_size()) * (node - x.node - 1) +  
  93.             (cur - first) + (x.last - x.cur);  
  94.     }  
  95.   
  96. ////////////////////////////////////////////////////////////////////////////////  
  97. // 下面重载的这些运算符是让deque从外界看上去维护的是一段连续空间的关键!!!  
  98.   
  99. // 前缀自增  
  100. ////////////////////////////////////////////////////////////////////////////////  
  101. // 如果当前迭代器指向元素是当前缓冲区的最后一个元素,  
  102. // 则将迭代器状态调整为下一个缓冲区的第一个元素  
  103. ////////////////////////////////////////////////////////////////////////////////  
  104. // 不是当前缓冲区最后一个元素  
  105. //  
  106. // 执行前缀自增前的状态  
  107. // first          cur                     end  
  108. // ↓               ↓                       ↓  
  109. // ---------------------------------------------  
  110. // |   |   |   |   |   |   | ..... |   |   | X | <----- 当前缓冲区  
  111. // ---------------------------------------------  
  112. //  
  113. // 执行完成后的状态  
  114. // first              cur                 end  
  115. // ↓                   ↓                   ↓  
  116. // ---------------------------------------------  
  117. // |   |   |   |   |   |   | ..... |   |   | X | <----- 当前缓冲区  
  118. // ---------------------------------------------  
  119. //  
  120. ////////////////////////////////////////////////////////////////////////////////  
  121. // 当前元素为当前缓冲区的最后一个元素  
  122. //  
  123. // 执行前缀自增前的状态  
  124. // first                              cur end  
  125. // ↓                                   ↓   ↓  
  126. // ---------------------------------------------  
  127. // |   |   |   |   |   |   | ..... |   |   | X | <----- 当前缓冲区  
  128. // ---------------------------------------------  
  129. //  
  130. // 执行完成后的状态  
  131. // first                                  end  
  132. // ↓                                       ↓  
  133. // ---------------------------------------------  
  134. // |   |   |   |   |   |   | ..... |   |   | X | <----- 下一缓冲区  
  135. // ---------------------------------------------  
  136. // ↑  
  137. // cur  
  138. //  
  139. ////////////////////////////////////////////////////////////////////////////////  
  140.     self& operator++()  
  141.     {  
  142.         ++cur;    // 切换至下一个元素  
  143.         if (cur == last)    // 如果已达到缓冲区的尾端  
  144.         {  
  145.             set_node(node + 1);    // 就切换至下一节点（亦即缓冲区）  
  146.             cur = first;           // 的第一个元素  
  147.         }  
  148.         return *this;  
  149.     }  
  150.   
  151.     // 后缀自增  
  152.     // 返回当前迭代器的一个副本, 并调用前缀自增运算符实现迭代器自身的自增  
  153.     self operator++(int)  
  154.     {  
  155.         self tmp = *this;  
  156.         ++*this;  
  157.         return tmp;  
  158.     }  
  159.   
  160.     // 前缀自减, 处理方式类似于前缀自增  
  161.     // 如果当前迭代器指向元素是当前缓冲区的第一个元素  
  162.     // 则将迭代器状态调整为前一个缓冲区的最后一个元素  
  163.     self& operator--()  
  164.     {  
  165.         if (cur == first)    // 如果已达到缓冲区的头端  
  166.         {  
  167.             set_node(node - 1);    // 就切换至前一节点（亦即缓冲区）  
  168.             cur = last;            // 的最后一个元素  
  169.         }  
  170.         --cur;  
  171.         return *this;  
  172.     }  
  173.   
  174.     self operator--(int)  
  175.     {  
  176.         self tmp = *this;  
  177.         --*this;  
  178.         return tmp;  
  179.     }  
  180.   
  181. ////////////////////////////////////////////////////////////////////////////////  
  182. // 将迭代器向前移动n个元素, n可以为负  
  183. ////////////////////////////////////////////////////////////////////////////////  
  184. //                     operator+=(difference_type n)  
  185. //                                   ↓  
  186. //                      offset = n + (cur - first)  
  187. //                                   |  
  188. //                                   |---------- offset > 0 ? &&  
  189. //                                   |           移动后是否超出当前缓冲区?  
  190. //               ----------------------------  
  191. //           No  |                          |  Yes  
  192. //               |                          |  
  193. //               ↓                          |---------- offset > 0?  
  194. //           cur += n;                      |  
  195. //                              ----------------------------  
  196. //                          Yes |                          | No  
  197. //                              |                          |  
  198. //                              ↓                          |  
  199. //                   计算要向后移动多少个缓冲区                |  
  200. //                   node_offset =                         |  
  201. //                   offset / difference_type              |  
  202. //                   (buffer_size());                      ↓  
  203. //                              |           计算要向前移动多少个缓冲区  
  204. //                              |           node_offset = -difference_type  
  205. //                              |           ((-offset - 1) / buffer_size()) - 1;  
  206. //                              |                          |  
  207. //                              ----------------------------  
  208. //                                           |  
  209. //                                           |  
  210. //                                           ↓  
  211. //                                       调整缓冲区  
  212. //                              set_node(node + node_offset);  
  213. //                                    计算并调整cur指针  
  214. ////////////////////////////////////////////////////////////////////////////////  
  215.     // 以下实现随机存取。迭代器可以直接跳跃n个距离  
  216.     self& operator+=(difference_type n)  
  217.     {  
  218.         difference_type offset = n + (cur - first);  
  219.         if (offset >= 0 && offset < difference_type(buffer_size()))  
  220.             cur += n;        // 目标位置在同一缓冲区内  
  221.         else  
  222.         {           // 目标位置不在同一缓冲区内  
  223.             difference_type node_offset =  
  224.                 offset > 0 ? offset / difference_type(buffer_size())  
  225.                 : -difference_type((-offset - 1) / buffer_size()) - 1;  
  226.             // 切换至正确的节点（亦即缓冲区）  
  227.             set_node(node + node_offset);  
  228.             // 切换至正确的元素  
  229.             cur = first + (offset - node_offset * difference_type(buffer_size()));  
  230.         }  
  231.         return *this;  
  232.     }  
  233.   
  234.     self operator+(difference_type n) const  
  235.     {  
  236.         self tmp = *this;  
  237.   
  238.         // 这里调用了operator +=()可以自动调整指针状态  
  239.         return tmp += n;  
  240.     }  
  241.   
  242.     // 将n变为-n就可以使用operator +=()了,  
  243.     self& operator-=(difference_type n) { return *this += -n; }  
  244.   
  245.     self operator-(difference_type n) const  
  246.     {  
  247.         self tmp = *this;  
  248.         return tmp -= n;  
  249.     }  
  250.   
  251.     reference operator[](difference_type n) const { return *(*this + n); }  
  252.   
  253.     bool operator==(const self& x) const { return cur == x.cur; }  
  254.     bool operator!=(const self& x) const { return !(*this == x); }  
  255.     bool operator<(const self& x) const  
  256.     {  
  257.         return (node == x.node) ? (cur < x.cur) : (node < x.node);  
  258.     }  
  259.   
  260.     void set_node(map_pointer new_node)  
  261.     {  
  262.         node = new_node;  
  263.         first = *new_node;  
  264.         last = first + difference_type(buffer_size());  
  265.     }  
  266. };  
  267.   
  268.   
  269. // deque的数据结构  
  270. template <class T, class Alloc = alloc, size_t BufSiz = 0>  
  271. class deque  
  272. {  
  273. public:                         // Basic types  
  274.     typedef T value_type;  
  275.     typedef value_type* pointer;  
  276.     typedef value_type& reference;  
  277.     typedef size_t size_type;  
  278.     typedef ptrdiff_t difference_type;  
  279.   
  280. public:                         // Iterators  
  281.     typedef __deque_iterator<T, T&, T*, BufSiz>       iterator;  
  282.   
  283. protected:                      // Internal typedefs  
  284.   
  285.     typedef pointer* map_pointer;  
  286.   
  287.     // 这个提供STL标准的allocator接口, 见<stl_alloc.h>  
  288.     typedef simple_alloc<value_type, Alloc> data_allocator;  
  289.     typedef simple_alloc<pointer, Alloc> map_allocator;  
  290.   
  291.     // 获取缓冲区最大存储元素数量  
  292.     static size_type buffer_size()  
  293.     {  
  294.         return __deque_buf_size(BufSiz, sizeof(value_type));  
  295.     }  
  296.   
  297.     static size_type initial_map_size() { return 8; }  
  298.   
  299. protected:                      // Data members  
  300.     iterator start;               // 起始缓冲区  
  301.     iterator finish;              // 最后一个缓冲区  
  302.   
  303.     // 指向map, map是一个连续的空间, 其每个元素都是一个指针，指向一个节点（缓冲区）  
  304.     map_pointer map;  
  305.     size_type map_size;   // map容量  
  306.   
  307. public:  
  308.     iterator begin() { return start; }  
  309.     iterator end() { return finish; }  
  310.   
  311.     // 提供随机访问能力, 其调用的是迭代器重载的operator []  
  312.     // 其实际地址需要进行一些列的计算, 效率有损失  
  313.     reference operator[](size_type n) { return start[difference_type(n)]; }  
  314.   
  315.     reference front() { return *start; }  
  316.     reference back()  
  317.     {  
  318.         iterator tmp = finish;  
  319.         --tmp;  
  320.         return *tmp;  
  321.     }  
  322.   
  323.     // 当前容器拥有的元素个数, 调用迭代器重载的operator -  
  324.     size_type size() const { return finish - start;; }  
  325.     size_type max_size() const { return size_type(-1); }  
  326.   
  327.     // deque为空的时, 只有一个缓冲区  
  328.     bool empty() const { return finish == start; }  
  329.   
  330. public:                         // Constructor, destructor.  
  331.     deque() : start(), finish(), map(0), map_size(0)  
  332.     {  
  333.         create_map_and_nodes(0);  
  334.     }  
  335.   
  336.     deque(size_type n, const value_type& value)  
  337.         : start(), finish(), map(0), map_size(0)  
  338.     {  
  339.         fill_initialize(n, value);  
  340.     }  
  341.   
  342.     deque(int n, const value_type& value)  
  343.         : start(), finish(), map(0), map_size(0)  
  344.     {  
  345.         fill_initialize(n, value);  
  346.     }  
  347.   
  348.   
  349.     ~deque()  
  350.     {  
  351.         destroy(start, finish);     // <stl_construct.h>  
  352.         destroy_map_and_nodes();  
  353.     }  
  354.   
  355.     deque& operator= (const deque& x)  
  356.     {  
  357.         // 其实我觉得把这个操作放在if内效率更高  
  358.         const size_type len = size();  
  359.         if (&x != this)  
  360.         {  
  361.             // 当前容器比x容器拥有元素多, 析构多余元素  
  362.             if (len >= x.size())  
  363.                 erase(copy(x.begin(), x.end(), start), finish);  
  364.             // 将x所有超出部分的元素使用insert()追加进去  
  365.             else {  
  366.                 const_iterator mid = x.begin() + difference_type(len);  
  367.                 copy(x.begin(), mid, start);  
  368.                 insert(finish, mid, x.end());  
  369.             }  
  370.         }  
  371.         return *this;  
  372.     }  
  373.   
  374. public:  
  375.     void push_back(const value_type& t)  
  376.     {  
  377.         // 最后缓冲区尚有两个（含）以上的元素备用空间  
  378.         if (finish.cur != finish.last - 1)  
  379.         {  
  380.             construct(finish.cur, t);     // 直接在备用空间上构造元素  
  381.             ++finish.cur;     // 调整最后缓冲区的使用状态  
  382.         }  
  383.         // 容量已满就要新申请内存了  
  384.         else  
  385.             push_back_aux(t);  
  386.     }  
  387.   
  388.     void push_front(const value_type& t)  
  389.     {  
  390.         if (start.cur != start.first)      // 第一缓冲区尚有备用空间  
  391.         {  
  392.             construct(start.cur - 1, t);   // 直接在备用空间上构造元素  
  393.             --start.cur;     // 调整第一缓冲区的使用状态  
  394.         }  
  395.         else    // 第一缓冲区已无备用空间  
  396.             push_front_aux(t);  
  397.     }  
  398.   
  399.     void pop_back()  
  400.     {  
  401.         if (finish.cur != finish.first)    // 最后缓冲区有一个（或更多）元素  
  402.         {  
  403.             --finish.cur;    // 调整指针，相当于排除了最后元素  
  404.             destroy(finish.cur);    // 将最后元素析构  
  405.         }  
  406.         else  
  407.             // 最后缓冲区没有任何元素  
  408.             pop_back_aux();    // 这里将进行缓冲区的释放工作  
  409.     }  
  410.   
  411.     void pop_front()  
  412.     {  
  413.         if (start.cur != start.last - 1)    // 第一缓冲区有两个（或更多）元素  
  414.         {  
  415.             destroy(start.cur);    // 将第一元素析构  
  416.             ++start.cur;           //调整指针，相当于排除了第一元素  
  417.         }  
  418.         else  
  419.             // 第一缓冲区仅有一个元素  
  420.             pop_front_aux();    // 这里将进行缓冲区的释放工作  
  421.     }  
  422.   
  423. public:                         // Insert  
  424.   
  425. ////////////////////////////////////////////////////////////////////////////////  
  426. // 在指定位置前插入元素  
  427. ////////////////////////////////////////////////////////////////////////////////  
  428. //             insert(iterator position, const value_type& x)  
  429. //                                   |  
  430. //                                   |---------------- 判断插入位置  
  431. //                                   |  
  432. //               -----------------------------------------------  
  433. // deque.begin() |          deque.emd() |                      |  
  434. //               |                      |                      |  
  435. //               ↓                      ↓                      |  
  436. //         push_front(x);         push_back(x);                |  
  437. //                                                             ↓  
  438. //                                                 insert_aux(position, x);  
  439. //                                                 具体剖析见后面实现  
  440. ////////////////////////////////////////////////////////////////////////////////  
  441.   
  442.     iterator insert(iterator position, const value_type& x)  
  443.     {  
  444.         // 如果是在deque的最前端插入, 那么直接push_front()即可  
  445.         if (position.cur == start.cur)  
  446.         {  
  447.             push_front(x);  
  448.             return start;  
  449.         }  
  450.         // 如果是在deque的末尾插入, 直接调用push_back()  
  451.         else if (position.cur == finish.cur)  
  452.         {  
  453.             push_back(x);  
  454.             iterator tmp = finish;  
  455.             --tmp;  
  456.             return tmp;  
  457.         }  
  458.         else  
  459.         {  
  460.             return insert_aux(position, x);  
  461.         }  
  462.     }  
  463.   
  464.     iterator insert(iterator position) { return insert(position, value_type()); }  
  465.   
  466.     // 详解见实现部分  
  467.     void insert(iterator pos, size_type n, const value_type& x);  
  468.   
  469.     void insert(iterator pos, int n, const value_type& x)  
  470.     {  
  471.         insert(pos, (size_type) n, x);  
  472.     }  
  473.     void insert(iterator pos, long n, const value_type& x)  
  474.     {  
  475.         insert(pos, (size_type) n, x);  
  476.     }  
  477.   
  478.     void resize(size_type new_size) { resize(new_size, value_type()); }  
  479.   
  480. public:                         // Erase  
  481.   
  482.     iterator erase(iterator pos)  
  483.     {  
  484.         iterator next = pos;  
  485.         ++next;  
  486.   
  487.         // 清除点之前的元素个数  
  488.         difference_type index = pos - start;  
  489.   
  490.         // 如果清除点之前的元素个数比较少, 哪部分少就移动哪部分  
  491.         if (index < (size() >> 1))  
  492.         {  
  493.             // 就移动清除点之前的元素  
  494.             copy_backward(start, pos, next);  
  495.             pop_front();   // 移动完毕，最前一个元素冗余，去除之  
  496.         }  
  497.         else   // 如果清除点之后的元素个数比较少  
  498.         {  
  499.             copy(next, finish, pos);  // 就移动清除点之后的元素  
  500.             pop_back();   // 移动完毕，最后一个元素冗余，去除之  
  501.         }  
  502.         return start + index;  
  503.     }  
  504.   
  505.     iterator erase(iterator first, iterator last);  
  506.     void clear();  
  507.   
  508. protected:  
  509.   
  510.     // 详解见实现部分  
  511.     void push_back_aux(const value_type& t);  
  512.     void push_front_aux(const value_type& t);  
  513.     void pop_back_aux();  
  514.     void pop_front_aux();  
  515.   
  516.     iterator insert_aux(iterator pos, const value_type& x);  
  517.     void insert_aux(iterator pos, size_type n, const value_type& x);  
  518.   
  519.     // 分配内存, 不进行构造  
  520.     pointer allocate_node() { return data_allocator::allocate(buffer_size()); }  
  521.   
  522.     // 释放内存, 不进行析构  
  523.     void deallocate_node(pointer n)  
  524.     {  
  525.         data_allocator::deallocate(n, buffer_size());  
  526.     }  
  527.   
  528. };  
  529.   
  530.   
  531. ////////////////////////////////////////////////////////////////////////////////  
  532. // 清除[first, last)区间的所有元素  
  533. ////////////////////////////////////////////////////////////////////////////////  
  534. //                  erase(iterator first, iterator last)  
  535. //                                   |  
  536. //                                   |---------------- 是否要删除整个区间?  
  537. //                                   |  
  538. //               ------------------------------------------  
  539. //           Yes |                                        | No  
  540. //               |                                        |  
  541. //               ↓                                        | --- 判断哪侧元素少  
  542. //            clear();                                    ↓  
  543. //       -----------------------------------------------------------------  
  544. // 左侧少 |                                                         右侧少 |  
  545. //       |                                                               |  
  546. //       ↓                                                               ↓  
  547. //   copy_backward(start, first, last);            copy(last, finish, first);  
  548. //   new_start = start + n;                        new_finish = finish - n;  
  549. //   析构多余的元素                                  析构多余的元素  
  550. //   destroy(start, new_start);                    destroy(new_finish, finish);  
  551. //   释放多余内存空间                                释放多余内存空间  
  552. //   for (...)                                     for (...)  
  553. //      ...                                             ...  
  554. //   更新map状态                                    更新map状态  
  555. ////////////////////////////////////////////////////////////////////////////////  
  556. template <class T, class Alloc, size_t BufSize>  
  557. deque<T, Alloc, BufSize>::iterator  
  558. deque<T, Alloc, BufSize>::erase(iterator first, iterator last)  
  559. {  
  560.     if (first == start && last == finish)   // 如果清除区间是整个deque  
  561.     {  
  562.         clear();              // 直接调用clear()即可  
  563.         return finish;  
  564.     }  
  565.     else  
  566.     {  
  567.         difference_type n = last - first;   // 清除区间的长度  
  568.         difference_type elems_before = first - start;   // 清除区间前方的元素个数  
  569.         if (elems_before < (size() - n) / 2)   // 如果前方的元素个数比较少  
  570.         {  
  571.             copy_backward(start, first, last);  // 向后移动前方元素（覆盖清除区间）  
  572.             iterator new_start = start + n;     // 标记deque的新起点  
  573.             destroy(start, new_start);          // 移动完毕，将冗余的元素析构  
  574.             // 以下将冗余的缓冲区释放  
  575.             for (map_pointer cur = start.node; cur < new_start.node; ++cur)  
  576.                 data_allocator::deallocate(*cur, buffer_size());  
  577.             start = new_start;   // 设定deque的新起点  
  578.         }  
  579.         else    // 如果清除区间后方的元素个数比较少  
  580.         {  
  581.             copy(last, finish, first);  // 向前移动后方元素（覆盖清除区间）  
  582.             iterator new_finish = finish - n;     // 标记deque的新尾点  
  583.             destroy(new_finish, finish);          // 移动完毕，将冗余的元素析构  
  584.             // 以下将冗余的缓冲区释放  
  585.             for (map_pointer cur = new_finish.node + 1; cur <= finish.node; ++cur)  
  586.                 data_allocator::deallocate(*cur, buffer_size());  
  587.             finish = new_finish;   // 设定deque的新尾点  
  588.         }  
  589.         return start + elems_before;  
  590.     }  
  591. }  
  592.   
  593. template <class T, class Alloc, size_t BufSize>  
  594. void deque<T, Alloc, BufSize>::clear()  
  595. {  
  596.     // 以下针对头尾以外的每一个缓冲区  
  597.     for (map_pointer node = start.node + 1; node < finish.node; ++node)  
  598.     {  
  599.         // 将缓冲区内的所有元素析构  
  600.         destroy(*node, *node + buffer_size());  
  601.         // 释放缓冲区内存  
  602.         data_allocator::deallocate(*node, buffer_size());  
  603.     }  
  604.   
  605.     if (start.node != finish.node)   // 至少有头尾两个缓冲区  
  606.     {  
  607.         destroy(start.cur, start.last);  // 将头缓冲区的目前所有元素析构  
  608.         destroy(finish.first, finish.cur);  // 将尾缓冲区的目前所有元素析构  
  609.         // 以下释放尾缓冲区。注意：头缓冲区保留  
  610.         data_allocator::deallocate(finish.first, buffer_size());  
  611.     }  
  612.     else   // 只有一个缓冲区  
  613.         destroy(start.cur, finish.cur);   // 将此唯一缓冲区内的所有元素析构  
  614.         // 注意：并不释放缓冲区空间，这唯一的缓冲区将保留  
  615.   
  616.     finish = start;   // 调整状态  
  617. }  
  618.   
  619.   
  620. // 只有当finish.cur == finish.last - 1 时才会被调用  
  621. // 也就是说，只有当最后一个缓冲区只剩下一个备用元素空间时才会被调用  
  622. template <class T, class Alloc, size_t BufSize>  
  623. void deque<T, Alloc, BufSize>::push_back_aux(const value_type& t)  
  624. {  
  625.     value_type t_copy = t;  
  626.     reserve_map_at_back();  
  627.     *(finish.node + 1) = allocate_node();    // 配置一个新节点（缓冲区）  
  628.     __STL_TRY  
  629.     {  
  630.         construct(finish.cur, t_copy);         // 针对标的元素设值  
  631.         finish.set_node(finish.node + 1);      // 改变finish，令其指向新节点  
  632.         finish.cur = finish.first;             // 设定finish的状态  
  633.     }  
  634.     __STL_UNWIND(deallocate_node(*(finish.node + 1)));  
  635. }  
  636.   
  637. // Called only if start.cur == start.first.  
  638. template <class T, class Alloc, size_t BufSize>  
  639. void deque<T, Alloc, BufSize>::push_front_aux(const value_type& t)  
  640. {  
  641.     value_type t_copy = t;  
  642.     reserve_map_at_front();  
  643.     *(start.node - 1) = allocate_node();  
  644.     __STL_TRY  
  645.     {  
  646.         start.set_node(start.node - 1);        // 改变start，令其指向新节点  
  647.         start.cur = start.last - 1;            // 设定start的状态  
  648.         construct(start.cur, t_copy);          // 针对标的元素设值  
  649.     }  
  650.     catch(...)  
  651.     {  
  652.         start.set_node(start.node + 1);  
  653.         start.cur = start.first;  
  654.         deallocate_node(*(start.node - 1));  
  655.         throw;  
  656.     }  
  657. }  
  658.   
  659. // 只有当 finish.cur == finish.first 时才会被调用  
  660. template <class T, class Alloc, size_t BufSize>  
  661. void deque<T, Alloc, BufSize>:: pop_back_aux()  
  662. {  
  663.     deallocate_node(finish.first);      // 释放最后一个缓冲区  
  664.     finish.set_node(finish.node - 1);   // 调整finish状态，使指向  
  665.     finish.cur = finish.last - 1;       // 上一个缓冲区的最后一个元素  
  666.     destroy(finish.cur);                // 将该元素析构  
  667. }  
  668.   
  669. // 只有当 start.cur == start.last - 1 时才会被调用  
  670. template <class T, class Alloc, size_t BufSize>  
  671. void deque<T, Alloc, BufSize>::pop_front_aux()  
  672. {  
  673.     destroy(start.cur);    // 将第一个缓冲区的第一个（也是最后一个、唯一一个）元素析构  
  674.     deallocate_node(start.first);    // 释放第一缓冲区  
  675.     start.set_node(start.node + 1);  // 调整start状态，使指向  
  676.     start.cur = start.first;         // 下一个缓冲区的第一个元素  
  677. }  
  678.   
  679.   
  680. ////////////////////////////////////////////////////////////////////////////////  
  681. // 在指定位置前插入元素  
  682. ////////////////////////////////////////////////////////////////////////////////  
  683. //              insert_aux(iterator pos, const value_type& x)  
  684. //                                   |  
  685. //                                   |----------- 判断pos前端元素少还是后端元素少  
  686. //                                   |  
  687. //               -----------------------------------------------  
  688. //         前端少 |                                       后端少 |  
  689. //               |                                             |  
  690. //               ↓                                             |  
  691. //           进行相关操作                                   进行相关操作  
  692. ////////////////////////////////////////////////////////////////////////////////  
  693. // 下面以pos前面元素少的情形进行说明, 为了简化, 假设操作不会超过一个缓冲区区间  
  694. //  
  695. // 插入前状态  
  696. //           start            pos                                 end  
  697. //             ↓               ↓                                   ↓  
  698. // ---------------------------------------------------------------------  
  699. // |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   | X |  
  700. // ---------------------------------------------------------------------  
  701. //  
  702. // 需要进行操作的区间  
  703. //                需要拷贝的区间  
  704. //                 -------------  
  705. //       start     |           |                                  end  
  706. //         ↓       ↓           ↓                                   ↓  
  707. // ---------------------------------------------------------------------  
  708. // |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   | X |  
  709. // ---------------------------------------------------------------------  
  710. //             ↑   ↑       ↑   ↑  
  711. //        front1   |       |   |  
  712. //                 |       |   |  
  713. //            front2       |   |  
  714. //                         |   |  
  715. //                       pos   |  
  716. //                             |  
  717. //                          pos1  
  718. // 拷贝操作完成后  
  719. //  
  720. //         这是[front2, pos1)  
  721. //             ------------- --------- 这里是给待插入元素预留的空间  
  722. //       start |           | |                                    end  
  723. //         ↓   ↓           ↓ ↓                                     ↓  
  724. // ---------------------------------------------------------------------  
  725. // |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   | X |  
  726. // ---------------------------------------------------------------------  
  727. //         ↑  
  728. //   这里存储的是原来的front()  
  729. //  
  730. ////////////////////////////////////////////////////////////////////////////////  
  731.   
  732. template <class T, class Alloc, size_t BufSize>  
  733. typename deque<T, Alloc, BufSize>::iterator  
  734. deque<T, Alloc, BufSize>::insert_aux(iterator pos, const value_type& x)  
  735. {  
  736.     difference_type index = pos - start;   // 插入点之前的元素个数  
  737.     value_type x_copy = x;  
  738.   
  739.     // 前面的时候用的移位操作, 这里怎么不用了呢^_^?  
  740.     if (index < size() / 2)    // 如果插入点之前的元素个数比较少  
  741.     {  
  742.         push_front(front());       // 在最前端加入与第一元素同值的元素  
  743.         iterator front1 = start;   // 以下标示记号，然后进行元素移动  
  744.         ++front1;  
  745.         iterator front2 = front1;  
  746.         ++front2;  
  747.         pos = start + index;  
  748.         iterator pos1 = pos;  
  749.         ++pos1;  
  750.         copy(front2, pos1, front1);    // 元素移动  
  751.     }  
  752.     else    // 插入点之后的元素个数比较少  
  753.     {  
  754.         push_back(back());         // 在最尾端加入与最后元素同值的元素  
  755.         iterator back1 = finish;   // 以下标示记号，然后进行元素移动  
  756.         --back1;  
  757.         iterator back2 = back1;  
  758.         --back2;  
  759.         pos = start + index;  
  760.         copy_backward(pos, back2, back1);    // 元素移动  
  761.     }  
  762.     *pos = x_copy;    // 在插入点上设定新值  
  763.     return pos;  
  764. } 

STL源码分析--deque


联系
我们