1 G++ 2.91.57，cygnus\cygwin-b20\include\g++\stl_deque.h 完整列表   2 /*   3  *   4  * Copyright (c) 1994   5  * Hewlett-Packard Company   6  *   7  * Permission to use, copy, modify, distribute and sell this software   8  * and its documentation for any purpose is hereby granted without fee,   9  * provided that the above copyright notice appear in all copies and  10  * that both that copyright notice and this permission notice appear  11  * in supporting documentation.  Hewlett-Packard Company makes no  12  * representations about the suitability of this software for any  13  * purpose.  It is provided "as is" without express or implied warranty.  14  *  15  *  16  * Copyright (c) 1997  17  * Silicon Graphics Computer Systems, Inc.  18  *  19  * Permission to use, copy, modify, distribute and sell this software  20  * and its documentation for any purpose is hereby granted without fee,  21  * provided that the above copyright notice appear in all copies and  22  * that both that copyright notice and this permission notice appear  23  * in supporting documentation.  Silicon Graphics makes no  24  * representations about the suitability of this software for any  25  * purpose.  It is provided "as is" without express or implied warranty.  26  */  27   28 /* NOTE: This is an internal header file, included by other STL headers.  29  *   You should not attempt to use it directly.  30  */  31   32 #ifndef __SGI_STL_INTERNAL_DEQUE_H  33 #define __SGI_STL_INTERNAL_DEQUE_H  34   35 /* Class 的恆長特性（invariants）:  36  *  對於任何 nonsingular iterator I：  37  *    i.node 是 map array 中的某個元素的位址。  38  *      i.node 所指內容則是一個指標，指向某個節點（緩衝區）的頭。  39  *    i.first == *(i.node)   40  *    i.last  == i.first + node_size（也就是 buffer_size()）  41  *    i.cur 是一個指標，指向範圍 [i.first, i.last) 之間。注意：  42  *      這意味 i.cur 永遠是一個 dereferenceable pointer,  43  *      縱使 i 是一個 past-the-end iterator.  44  *  Start 和 Finish 總是 nonsingular iterators。注意：這意味  45  *    empty deque 一定會有一個node，而一個具有N個元素的deque，  46  *    （N 表示緩衝區大小），一定會有兩個nodes。  47  *  對於start.node 和finish.node 以外的每一個node，其中的每一個元素  48  *    都是一個經過初始化的物件。如果 start.node == finish.node，  49  *    那麼 [start.cur, finish.cur) 都是經過初始化的物件，而該範圍以外  50  *    元素則是未經初始化的空間。否則，[start.cur, start.last) 和  51  *    [finish.first, finish.cur) 是經過初始化的物件，而  52  *    [start.first, start.cur) 和 [finish.cur, finish.last)  53  *    則是未經初始化的空間  54  *  [map, map + map_size) 是一個有效的，non-empty 的範圍。    55  *  [start.node, finish.node] 是一個有效的範圍，內含於   56  *    [map, map + map_size) 之內。    57  *  範圍 [map, map + map_size) 內的任何一個指標會指向一個經過配置的  58  *    node — 若且唯若該指標在範圍 [start.node, finish.node] 之內。  59  */  60   61 /*  62  * 在前一版的deque中，node_size 由編譯器定死。這個版本允許使用者選擇節點   63  * （node）的大小。Deque 有三個 template 參數，其中第三個是一個型別為 size_t   64  * 的數值，代表每個節點（node）內含的元素個數。如果第三個 template 參數為0  65  * （那是預設值），deque 就使用預設的節點大小。  66  *  67  * 使用不同的節點大小的唯一理由是，或許你的程式需要不同的效率並願意付出其他方  68  * 面的代價。例如，假設你的程式內含許多deques，每一個都只內含一些元素，那麼  69  * 你可以使用較小的 nodes 來節省記憶體（或許會因此犧牲速度）。  70  *  71  * 不幸的是，某些編譯器面對 non-type template 參數會有問題。stl_config.h 之  72  * 中為此定義了一個 __STL_NON_TYPE_TMPL_PARAM_BUG。如果你的編譯器正是如  73  * 此，你就無法使用不同的節點大小，你必須使用預設大小。  74 */  75   76 __STL_BEGIN_NAMESPACE   77   78 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)  79 #pragma set woff 1174  80 #endif  81   82 // 注意：下面這個函式是七拼八湊的產品，只是為了閃避數家編譯器在處理常數算式  83 // （constant expressions）時的臭蟲。  84 // 如果 n 不為 0，傳回 n，表示 buffer size 由使用者自定。  85 // 如果 n 為 0，表示buffer size 使用預設值，那麼  86 //   如果 sz（元素大小，sizeof(value_type)）小於 512，傳回 512/sz，  87 //   如果 sz 不小於 512，傳回 1。  88 inline size_t __deque_buf_size(size_t n, size_t sz)  89 {  90   return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));  91 }  92   93 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG  94 template <class T, class Ref, class Ptr, size_t BufSiz>  95 struct __deque_iterator {     // 未繼承 std::iterator  96   typedef __deque_iterator<T, T&, T*, BufSiz>      iterator;  97   typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iterator;  98   static size_t buffer_size() {return __deque_buf_size(BufSiz, sizeof(T)); }  99 #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */ 100 template <class T, class Ref, class Ptr> 101 struct __deque_iterator {     // 未繼承 std::iterator 102   typedef __deque_iterator<T, T&, T*>             iterator; 103   typedef __deque_iterator<T, const T&, const T*> const_iterator; 104   static size_t buffer_size() {return __deque_buf_size(0, sizeof(T)); } 105 #endif 106  107   // 未繼承 std::iterator，所以必須自行撰寫五個必要的迭代器相應型別 108   typedef random_access_iterator_tag iterator_category; // (1) 109   typedef T value_type;                 // (2) 110   typedef Ptr pointer;                 // (3) 111   typedef Ref reference;                 // (4) 112   typedef size_t size_type; 113   typedef ptrdiff_t difference_type;     // (5) 114   typedef T** map_pointer; 115  116   typedef __deque_iterator self; 117  118   // 保持與容器的聯結 119   T* cur;    // 此迭代器所指之緩衝區中的現行（current）元素 120   T* first;    // 此迭代器所指之緩衝區的頭 121   T* last;    // 此迭代器所指之緩衝區的尾（含備用空間） 122   map_pointer node; 123  124   __deque_iterator(T* x, map_pointer y)  125     : cur(x), first(*y), last(*y + buffer_size()), node(y) {} 126   __deque_iterator() : cur(0), first(0), last(0), node(0) {} 127   __deque_iterator(const iterator& x) 128     : cur(x.cur), first(x.first), last(x.last), node(x.node) {} 129  130  131 // 以下各個多載化運算子是 __deque_iterator<> 成功運作的關鍵。 132  133   reference operator*() const { return *cur; } 134 #ifndef __SGI_STL_NO_ARROW_OPERATOR 135   pointer operator->() const { return &(operator*()); } 136 #endif /* __SGI_STL_NO_ARROW_OPERATOR */ 137  138   difference_type operator-(const self& x) const { 139     return difference_type(buffer_size()) * (node - x.node - 1) + 140       (cur - first) + (x.last - x.cur); 141   } 142    143   // 參考 More Effective C++, item6: Distinguish between prefix and 144   // postfix forms of increment and decrement operators. 145   self& operator++() { 146     ++cur;                // 切換至下一個元素。 147     if (cur == last) {        // 如果已達所在緩衝區的尾端， 148       set_node(node + 1);    // 就切換至下一個節點（亦即緩衝區） 149       cur = first;            //   的第一個元素。 150     } 151     return *this;  152   } 153   self operator++(int)  { 154     self tmp = *this; 155     ++*this; 156     return tmp; 157   } 158   self& operator--() { 159     if (cur == first) {    // 如果已達所在緩衝區的頭端， 160       set_node(node - 1);    // 就切換至前一個節點（亦即緩衝區） 161       cur = last;            //   的最後一個元素。 162     } 163     --cur;                // 切換至前一個元素。 164     return *this; 165   } 166   self operator--(int) { 167     self tmp = *this; 168     --*this; 169     return tmp; 170   } 171  172   self& operator+=(difference_type n) { 173     difference_type offset = n + (cur - first); 174     if (offset >= 0 && offset < difference_type(buffer_size())) 175       // 目標位置在同一緩衝區內 176       cur += n; 177     else { 178       // 目標位置不在同一緩衝區內 179       difference_type node_offset = 180         offset > 0 ? offset / difference_type(buffer_size()) 181                    : -difference_type((-offset - 1) / buffer_size()) - 1; 182       // 切換至正確的節點（亦即緩衝區） 183       set_node(node + node_offset); 184       // 切換至正確的元素 185       cur = first + (offset - node_offset * difference_type(buffer_size())); 186     } 187     return *this; 188   } 189  190   // 參考 More Effective C++, item22: Consider using op= instead of   191   // stand-alone op. 192   self operator+(difference_type n) const { 193     self tmp = *this; 194     return tmp += n; // 喚起operator+= 195   } 196  197   self& operator-=(difference_type n) { return *this += -n; } 198   // 以上利用operator+= 來完成 operator-= 199  200   // 參考 More Effective C++, item22: Consider using op= instead of   201   // stand-alone op. 202   self operator-(difference_type n) const { 203     self tmp = *this; 204     return tmp -= n; // 喚起operator-= 205   } 206  207   reference operator[](difference_type n) const { return *(*this + n); } 208   // 以上喚起operator*, operator+ 209  210   bool operator==(const self& x) const { return cur == x.cur; } 211   bool operator!=(const self& x) const { return !(*this == x); } 212   bool operator<(const self& x) const { 213     return (node == x.node) ? (cur < x.cur) : (node < x.node); 214   } 215  216   void set_node(map_pointer new_node) { 217     node = new_node; 218     first = *new_node; 219     last = first + difference_type(buffer_size()); 220   } 221 }; 222  223 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION 224 // 編譯器不支援 partial specialization 時，才需以下定義 225 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG 226  227 template <class T, class Ref, class Ptr, size_t BufSiz> 228 inline random_access_iterator_tag 229 iterator_category(const __deque_iterator<T, Ref, Ptr, BufSiz>&) { 230   return random_access_iterator_tag(); 231 } 232  233 template <class T, class Ref, class Ptr, size_t BufSiz> 234 inline T* value_type(const __deque_iterator<T, Ref, Ptr, BufSiz>&) { 235   return 0; 236 } 237  238 template <class T, class Ref, class Ptr, size_t BufSiz> 239 inline ptrdiff_t* distance_type(const __deque_iterator<T, Ref, Ptr, BufSiz>&) { 240   return 0; 241 } 242  243 #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */ 244  245 template <class T, class Ref, class Ptr> 246 inline random_access_iterator_tag 247 iterator_category(const __deque_iterator<T, Ref, Ptr>&) { 248   return random_access_iterator_tag(); 249 } 250  251 template <class T, class Ref, class Ptr> 252 inline T* value_type(const __deque_iterator<T, Ref, Ptr>&) { return 0; } 253  254 template <class T, class Ref, class Ptr> 255 inline ptrdiff_t* distance_type(const __deque_iterator<T, Ref, Ptr>&) { 256   return 0; 257 } 258  259 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ 260 // 編譯器不支援 partial specialization 時，才需以上定義 261 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 262  263 // 見 __deque_buf_size()。BufSize 預設值為 0 的唯一理由是為了閃避某些 264 //  編譯器在處理常數算式（constant expressions）時的臭蟲。 265 // 預設使用 alloc 為配置器 266 template <class T, class Alloc = alloc, size_t BufSiz = 0>  267 class deque { 268 public:                         // Basic types 269   typedef T value_type; 270   typedef value_type* pointer; 271   typedef const value_type* const_pointer; 272   typedef value_type& reference; 273   typedef const value_type& const_reference; 274   typedef size_t size_type; 275   typedef ptrdiff_t difference_type; 276  277 public:                         // Iterators 278 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG 279   typedef __deque_iterator<T, T&, T*, BufSiz>              iterator; 280   typedef __deque_iterator<T, const T&, const T&, BufSiz>  const_iterator; 281 #else /* __STL_NON_TYPE_TMPL_PARAM_BUG */ 282   typedef __deque_iterator<T, T&, T*>                      iterator; 283   typedef __deque_iterator<T, const T&, const T*>          const_iterator; 284 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ 285  286 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 287   typedef reverse_iterator<const_iterator> const_reverse_iterator; 288   typedef reverse_iterator<iterator> reverse_iterator; 289 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 290   typedef reverse_iterator<const_iterator, value_type, const_reference,  291                            difference_type>   292           const_reverse_iterator; 293   typedef reverse_iterator<iterator, value_type, reference, difference_type> 294           reverse_iterator;  295 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 296  297 protected:                      // Internal typedefs 298   // 元素的指標的指標（pointer of pointer of T） 299   typedef pointer* map_pointer;     300   // 專屬之空間配置器，每次配置一個元素大小 301   typedef simple_alloc<value_type, Alloc> data_allocator; 302   // 專屬之空間配置器，每次配置一個指標大小 303   typedef simple_alloc<pointer, Alloc> map_allocator; 304  305   static size_type buffer_size() { 306     return __deque_buf_size(BufSiz, sizeof(value_type)); 307   } 308   static size_type initial_map_size() { return 8; } 309  310 protected:                      // Data members 311   iterator start;        // 表現第一個節點。 312   iterator finish;    // 表現最後一個節點。 313  314   map_pointer map;    // 指向map，map是塊連續空間， 315                           // 其內的每個元素都是一個指標（稱為節點），指向一塊緩衝區。 316   size_type map_size;    // map內可容納多少指標。 317  318 public:                         // Basic accessors 319   iterator begin() { return start; } 320   iterator end() { return finish; } 321   const_iterator begin() const { return start; } 322   const_iterator end() const { return finish; } 323  324   reverse_iterator rbegin() { return reverse_iterator(finish); } 325   reverse_iterator rend() { return reverse_iterator(start); } 326   const_reverse_iterator rbegin() const { 327     return const_reverse_iterator(finish); 328   } 329   const_reverse_iterator rend() const { 330     return const_reverse_iterator(start); 331   } 332  333   reference operator[](size_type n) { 334     return start[difference_type(n)]; // 喚起 __deque_iterator<>::operator[] 335   } 336   const_reference operator[](size_type n) const { 337     return start[difference_type(n)]; 338   } 339  340   reference front() { return *start; } // 喚起 __deque_iterator<>::operator* 341   reference back() { 342     iterator tmp = finish;     343     --tmp;    // 喚起 __deque_iterator<>::operator-- 344     return *tmp;     // 喚起 __deque_iterator<>::operator* 345     // 以上三行何不改為：return *(finish-1); 346     // 因為 __deque_iterator<> 沒有為 (finish-1) 定義運算子。待查! 347   } 348   const_reference front() const { return *start; } 349   const_reference back() const { 350     const_iterator tmp = finish; 351     --tmp; 352     return *tmp; 353   } 354  355   // 下行最後有兩個 ‘;’，雖奇怪但合乎語法。 356   size_type size() const { return finish - start;; }  357   // 以上喚起iterator::operator- 358   size_type max_size() const { return size_type(-1); } 359   bool empty() const { return finish == start; } 360  361 public:                         // Constructor, destructor. 362   deque() 363     : start(), finish(), map(0), map_size(0) 364     // 以上 start() 和 finish() 喚起 iterator（亦即 __deque_iterator） 365     // 的 default ctor，於是令其 cur, first, last, node 皆為0。 366   { 367     create_map_and_nodes(0); 368   } 369  370   deque(const deque& x) 371     : start(), finish(), map(0), map_size(0) 372   { 373     create_map_and_nodes(x.size()); 374     __STL_TRY { 375       uninitialized_copy(x.begin(), x.end(), start); 376     } 377     __STL_UNWIND(destroy_map_and_nodes()); 378   } 379  380   deque(size_type n, const value_type& value) 381     : start(), finish(), map(0), map_size(0) 382   { 383     fill_initialize(n, value); 384   } 385  386   deque(int n, const value_type& value) 387     : start(), finish(), map(0), map_size(0) 388   { 389     fill_initialize(n, value); 390   } 391   392   deque(long n, const value_type& value) 393     : start(), finish(), map(0), map_size(0) 394   { 395     fill_initialize(n, value); 396   } 397  398   explicit deque(size_type n) 399     : start(), finish(), map(0), map_size(0) 400   { 401     fill_initialize(n, value_type()); 402   } 403  404 #ifdef __STL_MEMBER_TEMPLATES 405  406   template <class InputIterator> 407   deque(InputIterator first, InputIterator last) 408     : start(), finish(), map(0), map_size(0) 409   { 410     range_initialize(first, last, iterator_category(first)); 411   } 412  413 #else /* __STL_MEMBER_TEMPLATES */ 414  415   deque(const value_type* first, const value_type* last) 416     : start(), finish(), map(0), map_size(0) 417   { 418     create_map_and_nodes(last - first); 419     __STL_TRY { 420       uninitialized_copy(first, last, start); 421     } 422     __STL_UNWIND(destroy_map_and_nodes()); 423   } 424  425   deque(const_iterator first, const_iterator last) 426     : start(), finish(), map(0), map_size(0) 427   { 428     create_map_and_nodes(last - first); 429     __STL_TRY { 430       uninitialized_copy(first, last, start); 431     } 432     __STL_UNWIND(destroy_map_and_nodes()); 433   } 434  435 #endif /* __STL_MEMBER_TEMPLATES */ 436  437   ~deque() { 438     destroy(start, finish); 439     destroy_map_and_nodes(); 440   } 441  442   deque& operator= (const deque& x) { 443     const size_type len = size(); 444     if (&x != this) { 445       if (len >= x.size()) 446         erase(copy(x.begin(), x.end(), start), finish); 447       else { 448         const_iterator mid = x.begin() + difference_type(len); 449         copy(x.begin(), mid, start); 450         insert(finish, mid, x.end()); 451       } 452     } 453     return *this; 454   }         455  456   void swap(deque& x) { 457     __STD::swap(start, x.start); 458     __STD::swap(finish, x.finish); 459     __STD::swap(map, x.map); 460     __STD::swap(map_size, x.map_size); 461   } 462  463 public:                         // push_* and pop_* 464    465   void push_back(const value_type& t) { 466     if (finish.cur != finish.last - 1) {  467       // 最後緩衝區尚有一個以上的備用空間 468       construct(finish.cur, t);    // 直接在備用空間上建構元素 469       ++finish.cur;    // 調整最後緩衝區的使用狀態 470     } 471     else  // 最後緩衝區已無（或只剩一個）元素備用空間。 472       push_back_aux(t); 473   } 474  475   void push_front(const value_type& t) { 476     if (start.cur != start.first) {     // 第一緩衝區尚有備用空間 477       construct(start.cur - 1, t);     // 直接在備用空間上建構元素 478       --start.cur;        // 調整第一緩衝區的使用狀態 479     } 480     else // 第一緩衝區已無備用空間 481       push_front_aux(t); 482   } 483  484   void pop_back() { 485     if (finish.cur != finish.first) { 486       // 最後緩衝區有一個（或更多）元素 487  488       --finish.cur;        // 調整指標，相當於排除了最後元素 489       destroy(finish.cur);    // 將最後元素解構 490     } 491     else 492       // 最後緩衝區沒有任何元素 493       pop_back_aux();        // 這裡將進行緩衝區的釋放工作 494   } 495  496   void pop_front() { 497     if (start.cur != start.last - 1) { 498       // 第一緩衝區有一個（或更多）元素 499       destroy(start.cur);    // 將第一元素解構 500       ++start.cur;            // 調整指標，相當於排除了第一元素 501     } 502     else  503       // 第一緩衝區僅有一個元素 504       pop_front_aux();        // 這裡將進行緩衝區的釋放工作 505   } 506  507 public:                         // Insert 508  509   // 在position 處安插一個元素，其值為 x 510   iterator insert(iterator position, const value_type& x) { 511     if (position.cur == start.cur) {    // 如果安插點是deque 最前端 512       push_front(x);                // 交給push_front 去做 513       return start; 514     } 515     else if (position.cur == finish.cur) { // 如果安插點是deque 最尾端 516       push_back(x);                      // 交給push_back 去做 517       iterator tmp = finish; 518       --tmp; 519       return tmp; 520     } 521     else { 522       return insert_aux(position, x);         // 交給 insert_aux 去做 523     } 524   } 525  526   iterator insert(iterator position) { return insert(position, value_type()); } 527  528   void insert(iterator pos, size_type n, const value_type& x);  529  530   void insert(iterator pos, int n, const value_type& x) { 531     insert(pos, (size_type) n, x); 532   } 533   void insert(iterator pos, long n, const value_type& x) { 534     insert(pos, (size_type) n, x); 535   } 536  537 #ifdef __STL_MEMBER_TEMPLATES   538  539   template <class InputIterator> 540   void insert(iterator pos, InputIterator first, InputIterator last) { 541     insert(pos, first, last, iterator_category(first)); 542   } 543  544 #else /* __STL_MEMBER_TEMPLATES */ 545  546   void insert(iterator pos, const value_type* first, const value_type* last); 547   void insert(iterator pos, const_iterator first, const_iterator last); 548  549 #endif /* __STL_MEMBER_TEMPLATES */ 550  551   void resize(size_type new_size, const value_type& x) { 552     const size_type len = size(); 553     if (new_size < len)  554       erase(start + new_size, finish); 555     else 556       insert(finish, new_size - len, x); 557   } 558  559   void resize(size_type new_size) { resize(new_size, value_type()); } 560  561 public:                         // Erase 562   // 清除 pos 所指的元素。pos 為清除點。 563   iterator erase(iterator pos) { 564     iterator next = pos; 565     ++next; 566     difference_type index = pos - start;    // 清除點之前的元素個數 567     if (index < (size() >> 1)) {            // 如果清除點之前的元素比較少， 568       copy_backward(start, pos, next);    // 就搬移清除點之前的元素 569       pop_front();                // 搬移完畢，最前一個元素贅餘，去除之 570     } 571     else {                    // 清除點之後的元素比較少， 572       copy(next, finish, pos);    // 就搬移清除點之後的元素 573       pop_back();                // 搬移完畢，最後一個元素贅餘，去除之 574     } 575     return start + index; 576   } 577  578   iterator erase(iterator first, iterator last); 579   void clear();  580  581 protected:                        // Internal construction/destruction 582  583   void create_map_and_nodes(size_type num_elements); 584   void destroy_map_and_nodes(); 585   void fill_initialize(size_type n, const value_type& value); 586  587 #ifdef __STL_MEMBER_TEMPLATES   588  589   template <class InputIterator> 590   void range_initialize(InputIterator first, InputIterator last, 591                         input_iterator_tag); 592  593   template <class ForwardIterator> 594   void range_initialize(ForwardIterator first, ForwardIterator last, 595                         forward_iterator_tag); 596  597 #endif /* __STL_MEMBER_TEMPLATES */ 598  599 protected:                        // Internal push_* and pop_* 600  601   void push_back_aux(const value_type& t); 602   void push_front_aux(const value_type& t); 603   void pop_back_aux(); 604   void pop_front_aux(); 605  606 protected:                        // Internal insert functions 607  608 #ifdef __STL_MEMBER_TEMPLATES   609  610   template <class InputIterator> 611   void insert(iterator pos, InputIterator first, InputIterator last, 612               input_iterator_tag); 613  614   template <class ForwardIterator> 615   void insert(iterator pos, ForwardIterator first, ForwardIterator last, 616               forward_iterator_tag); 617  618 #endif /* __STL_MEMBER_TEMPLATES */ 619  620   iterator insert_aux(iterator pos, const value_type& x); 621   void insert_aux(iterator pos, size_type n, const value_type& x); 622  623 #ifdef __STL_MEMBER_TEMPLATES   624  625   template <class ForwardIterator> 626   void insert_aux(iterator pos, ForwardIterator first, ForwardIterator last, 627                   size_type n); 628  629 #else /* __STL_MEMBER_TEMPLATES */ 630    631   void insert_aux(iterator pos, 632                   const value_type* first, const value_type* last, 633                   size_type n); 634  635   void insert_aux(iterator pos, const_iterator first, const_iterator last, 636                   size_type n); 637   638 #endif /* __STL_MEMBER_TEMPLATES */ 639  640   iterator reserve_elements_at_front(size_type n) { 641     size_type vacancies = start.cur - start.first; 642     if (n > vacancies)  643       new_elements_at_front(n - vacancies); 644     return start - difference_type(n); 645   } 646  647   iterator reserve_elements_at_back(size_type n) { 648     size_type vacancies = (finish.last - finish.cur) - 1; 649     if (n > vacancies) 650       new_elements_at_back(n - vacancies); 651     return finish + difference_type(n); 652   } 653  654   void new_elements_at_front(size_type new_elements); 655   void new_elements_at_back(size_type new_elements); 656  657   void destroy_nodes_at_front(iterator before_start); 658   void destroy_nodes_at_back(iterator after_finish); 659  660 protected:                      // Allocation of map and nodes 661  662   // Makes sure the map has space for new nodes.  Does not actually 663   //  add the nodes.  Can invalidate map pointers.  (And consequently,  664   //  deque iterators.) 665  666   void reserve_map_at_back (size_type nodes_to_add = 1) { 667     if (nodes_to_add + 1 > map_size - (finish.node - map)) 668       // 如果 map 尾端的節點備用空間不足 669       // 符合以上條件則必須重換一個map（配置更大的，拷貝原來的，釋放原來的） 670       reallocate_map(nodes_to_add, false);  671   } 672  673   void reserve_map_at_front (size_type nodes_to_add = 1) { 674     if (nodes_to_add > start.node - map) 675       // 如果 map 前端的節點備用空間不足 676       // 符合以上條件則必須重換一個map（配置更大的，拷貝原來的，釋放原來的） 677       reallocate_map(nodes_to_add, true);     678   } 679  680   void reallocate_map(size_type nodes_to_add, bool add_at_front); 681  682   pointer allocate_node() { return data_allocator::allocate(buffer_size()); } 683   void deallocate_node(pointer n) { 684     data_allocator::deallocate(n, buffer_size()); 685   } 686  687 #ifdef __STL_NON_TYPE_TMPL_PARAM_BUG 688 public: 689   bool operator==(const deque<T, Alloc, 0>& x) const { 690     return size() == x.size() && equal(begin(), end(), x.begin()); 691   } 692   bool operator!=(const deque<T, Alloc, 0>& x) const { 693     return size() != x.size() || !equal(begin(), end(), x.begin()); 694   } 695   bool operator<(const deque<T, Alloc, 0>& x) const { 696     return lexicographical_compare(begin(), end(), x.begin(), x.end()); 697   } 698 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ 699 }; 700  701 // Non-inline member functions 702  703 template <class T, class Alloc, size_t BufSize> 704 void deque<T, Alloc, BufSize>::insert(iterator pos, 705                                       size_type n, const value_type& x) { 706   if (pos.cur == start.cur) { 707     iterator new_start = reserve_elements_at_front(n); 708     uninitialized_fill(new_start, start, x); 709     start = new_start; 710   } 711   else if (pos.cur == finish.cur) { 712     iterator new_finish = reserve_elements_at_back(n); 713     uninitialized_fill(finish, new_finish, x); 714     finish = new_finish; 715   } 716   else  717     insert_aux(pos, n, x); 718 } 719  720 #ifndef __STL_MEMBER_TEMPLATES   721  722 template <class T, class Alloc, size_t BufSize> 723 void deque<T, Alloc, BufSize>::insert(iterator pos, 724                                       const value_type* first, 725                                       const value_type* last) { 726   size_type n = last - first; 727   if (pos.cur == start.cur) { 728     iterator new_start = reserve_elements_at_front(n); 729     __STL_TRY { 730       uninitialized_copy(first, last, new_start); 731       start = new_start; 732     } 733     __STL_UNWIND(destroy_nodes_at_front(new_start)); 734   } 735   else if (pos.cur == finish.cur) { 736     iterator new_finish = reserve_elements_at_back(n); 737     __STL_TRY { 738       uninitialized_copy(first, last, finish); 739       finish = new_finish; 740     } 741     __STL_UNWIND(destroy_nodes_at_back(new_finish)); 742   } 743   else 744     insert_aux(pos, first, last, n); 745 } 746  747 template <class T, class Alloc, size_t BufSize> 748 void deque<T, Alloc, BufSize>::insert(iterator pos, 749                                       const_iterator first, 750                                       const_iterator last) 751 { 752   size_type n = last - first; 753   if (pos.cur == start.cur) { 754     iterator new_start = reserve_elements_at_front(n); 755     __STL_TRY { 756       uninitialized_copy(first, last, new_start); 757       start = new_start; 758     } 759     __STL_UNWIND(destroy_nodes_at_front(new_start)); 760   } 761   else if (pos.cur == finish.cur) { 762     iterator new_finish = reserve_elements_at_back(n); 763     __STL_TRY { 764       uninitialized_copy(first, last, finish); 765       finish = new_finish; 766     } 767     __STL_UNWIND(destroy_nodes_at_back(new_finish)); 768   } 769   else 770     insert_aux(pos, first, last, n); 771 } 772  773 #endif /* __STL_MEMBER_TEMPLATES */ 774  775 template <class T, class Alloc, size_t BufSize> 776 deque<T, Alloc, BufSize>::iterator  777 deque<T, Alloc, BufSize>::erase(iterator first, iterator last) { 778   if (first == start && last == finish) { // 如果清除區間就是整個 deque 779     clear();                            // 直接呼叫 clear() 即可 780     return finish; 781   } 782   else { 783     difference_type n = last - first;            // 清除區間的長度 784     difference_type elems_before = first - start;    // 清除區間前方的元素個數 785     if (elems_before < (size() - n) / 2) {        // 如果前方的元素比較少， 786       copy_backward(start, first, last);        // 向後搬移前方元素（覆蓋清除區間） 787       iterator new_start = start + n;            // 標記 deque 的新起點 788       destroy(start, new_start);                // 搬移完畢，將贅餘的元素解構 789       // 以下將贅餘的緩衝區釋放 790       for (map_pointer cur = start.node; cur < new_start.node; ++cur) 791         data_allocator::deallocate(*cur, buffer_size()); 792       start = new_start;    // 設定 deque 的新起點 793     } 794     else {    // 如果清除區間後方的元素比較少 795       copy(last, finish, first);            // 向前搬移後方元素（覆蓋清除區間） 796       iterator new_finish = finish - n;    // 標記 deque 的新尾點 797       destroy(new_finish, finish);        // 搬移完畢，將贅餘的元素解構 798       // 以下將贅餘的緩衝區釋放 799       for (map_pointer cur = new_finish.node + 1; cur <= finish.node; ++cur) 800         data_allocator::deallocate(*cur, buffer_size()); 801       finish = new_finish;    // 設定 deque 的新尾點 802     } 803     return start + elems_before; 804   } 805 } 806  807 // 注意，最終需要保留一個緩衝區。這是deque 的策略，也是deque 的初始狀態。 808 template <class T, class Alloc, size_t BufSize> 809 void deque<T, Alloc, BufSize>::clear() { 810   // 以下針對頭尾以外的每一個緩衝區（它們一定都是飽滿的） 811   for (map_pointer node = start.node + 1; node < finish.node; ++node) { 812     // 將緩衝區內的所有元素解構。注意，呼叫的是destroy() 第二版本，見2.2.3節 813     destroy(*node, *node + buffer_size()); 814     // 釋放緩衝區記憶體 815     data_allocator::deallocate(*node, buffer_size()); 816   } 817  818   if (start.node != finish.node) {    // 至少有頭尾兩個緩衝區 819     destroy(start.cur, start.last);    // 將頭緩衝區的目前所有元素解構 820     destroy(finish.first, finish.cur); // 將尾緩衝區的目前所有元素解構 821     // 以下釋放尾緩衝區。注意，頭緩衝區保留。 822     data_allocator::deallocate(finish.first, buffer_size()); 823   } 824   else    // 只有一個緩衝區 825     destroy(start.cur, finish.cur);    // 將此唯一緩衝區內的所有元素解構 826     // 注意，並不釋放緩衝區空間。這唯一的緩衝區將保留。 827  828   finish = start;    // 調整狀態 829 } 830  831 template <class T, class Alloc, size_t BufSize> 832 void deque<T, Alloc, BufSize>::create_map_and_nodes(size_type num_elements) { 833   // 需要節點數=(元素個數/每個緩衝區可容納的元素個數)+1 834   // 如果剛好整除，會多配一個節點。 835   size_type num_nodes = num_elements / buffer_size() + 1; 836  837   // 一個 map 要管理幾個節點。最少8個，最多是 “所需節點數加2” 838   // （前後各預留一個，擴充時可用）。 839   map_size = max(initial_map_size(), num_nodes + 2); 840   map = map_allocator::allocate(map_size); 841   // 以上配置出一個 “具有 map_size個節點” 的map。 842  843   // 以下令nstart和nfinish指向map所擁有之全部節點的最中央區段。 844   // 保持在最中央，可使頭尾兩端的擴充能量一樣大。每個節點可對應一個緩衝區。 845   map_pointer nstart = map + (map_size - num_nodes) / 2; 846   map_pointer nfinish = nstart + num_nodes - 1; 847      848   map_pointer cur; 849   __STL_TRY { 850     // 為map內的每個現用節點配置緩衝區。所有緩衝區加起來就是deque的空間 851    // （最後一個緩衝區可能留有一些餘裕）。 852     for (cur = nstart; cur <= nfinish; ++cur) 853       *cur = allocate_node(); 854   } 855 #     ifdef  __STL_USE_EXCEPTIONS  856   catch(...) { 857     // "commit or rollback" 語意：若非全部成功，就一個不留。 858     for (map_pointer n = nstart; n < cur; ++n) 859       deallocate_node(*n); 860     map_allocator::deallocate(map, map_size); 861     throw; 862   } 863 #     endif /* __STL_USE_EXCEPTIONS */ 864  865   // 為deque內的兩個迭代器start和end 設定正確的內容。 866   start.set_node(nstart); 867   finish.set_node(nfinish); 868   start.cur = start.first;        // first, cur都是public 869   finish.cur = finish.first + num_elements % buffer_size(); 870   // 前面說過，如果剛好整除，會多配一個節點。 871   // 此時即令cur指向這多配的一個節點（所對映之緩衝區）的起頭處。 872 } 873  874 // This is only used as a cleanup function in catch clauses. 875 template <class T, class Alloc, size_t BufSize> 876 void deque<T, Alloc, BufSize>::destroy_map_and_nodes() { 877   for (map_pointer cur = start.node; cur <= finish.node; ++cur) 878     deallocate_node(*cur); 879   map_allocator::deallocate(map, map_size); 880 } 881    882  883 template <class T, class Alloc, size_t BufSize> 884 void deque<T, Alloc, BufSize>::fill_initialize(size_type n, 885                                                const value_type& value) { 886   create_map_and_nodes(n);     // 把deque的結構都產生並安排好 887   map_pointer cur; 888   __STL_TRY { 889     // 為每個節點的緩衝區設定初值 890     for (cur = start.node; cur < finish.node; ++cur) 891       uninitialized_fill(*cur, *cur + buffer_size(), value); 892     // 最後一個節點的設定稍有不同（因為尾端可能有備用空間，不必設初值） 893     uninitialized_fill(finish.first, finish.cur, value); 894   } 895 #       ifdef __STL_USE_EXCEPTIONS 896   catch(...) { 897     // "commit or rollback" 語意：若非全部成功，就一個不留。 898     for (map_pointer n = start.node; n < cur; ++n) 899       destroy(*n, *n + buffer_size()); 900     destroy_map_and_nodes(); 901     throw; 902   } 903 #       endif /* __STL_USE_EXCEPTIONS */ 904 } 905  906 #ifdef __STL_MEMBER_TEMPLATES   907  908 template <class T, class Alloc, size_t BufSize> 909 template <class InputIterator> 910 void deque<T, Alloc, BufSize>::range_initialize(InputIterator first, 911                                                 InputIterator last, 912                                                 input_iterator_tag) { 913   create_map_and_nodes(0); 914   for ( ; first != last; ++first) 915     push_back(*first); 916 } 917  918 template <class T, class Alloc, size_t BufSize> 919 template <class ForwardIterator> 920 void deque<T, Alloc, BufSize>::range_initialize(ForwardIterator first, 921                                                 ForwardIterator last, 922                                                 forward_iterator_tag) { 923   size_type n = 0; 924   distance(first, last, n); 925   create_map_and_nodes(n); 926   __STL_TRY { 927     uninitialized_copy(first, last, start); 928   } 929   __STL_UNWIND(destroy_map_and_nodes()); 930 } 931  932 #endif /* __STL_MEMBER_TEMPLATES */ 933  934 // 只有當 finish.cur == finish.last – 1 時才會被呼叫。 935 // 也就是說只有當最後一個緩衝區只剩一個備用元素空間時才會被呼叫。 936 template <class T, class Alloc, size_t BufSize> 937 void deque<T, Alloc, BufSize>::push_back_aux(const value_type& t) { 938   value_type t_copy = t; 939   reserve_map_at_back();        //  若符合某種條件則必須重換一個map 940   *(finish.node + 1) = allocate_node();    // 配置一個新節點（緩衝區） 941   __STL_TRY { 942     construct(finish.cur, t_copy);        // 針對標的元素設值 943     finish.set_node(finish.node + 1);    // 改變finish，令其指向新節點 944     finish.cur = finish.first;            // 設定 finish 的狀態 945   } 946   __STL_UNWIND(deallocate_node(*(finish.node + 1))); 947 } 948  949 // 只有當start.cur == start.first時才會被呼叫。 950 // 也就是說只有當第一個緩衝區沒有任何備用元素時才會被呼叫。 951 template <class T, class Alloc, size_t BufSize> 952 void deque<T, Alloc, BufSize>::push_front_aux(const value_type& t) { 953   value_type t_copy = t; 954   reserve_map_at_front();        //  若符合某種條件則必須重換一個map 955   *(start.node - 1) = allocate_node();    // 配置一個新節點（緩衝區） 956   __STL_TRY { 957     start.set_node(start.node - 1);        // 改變start，令其指向新節點 958     start.cur = start.last - 1;            // 設定 start的狀態 959     construct(start.cur, t_copy);        // 針對標的元素設值 960   } 961 #     ifdef __STL_USE_EXCEPTIONS 962   catch(...) { 963     // "commit or rollback" 語意：若非全部成功，就一個不留。 964     start.set_node(start.node + 1); 965     start.cur = start.first; 966     deallocate_node(*(start.node - 1)); 967     throw; 968   } 969 #     endif /* __STL_USE_EXCEPTIONS */ 970 }  971  972 // 只有當finish.cur == finish.first時才會被呼叫。 973 template <class T, class Alloc, size_t BufSize> 974 void deque<T, Alloc, BufSize>::pop_back_aux() { 975   deallocate_node(finish.first);    // 釋放最後一個緩衝區 976   finish.set_node(finish.node - 1);    // 調整 finish 的狀態，使指向 977   finish.cur = finish.last - 1;        //  上一個緩衝區的最後一個元素 978   destroy(finish.cur);                // 將該元素解構。 979 } 980  981 // 只有當start.cur == start.last - 1時才會被呼叫。 982 template <class T, class Alloc, size_t BufSize> 983 void deque<T, Alloc, BufSize>::pop_front_aux() { 984   destroy(start.cur);                // 將第一緩衝區的第一個元素解構。 985   deallocate_node(start.first);        // 釋放第一緩衝區。 986   start.set_node(start.node + 1);    // 調整 start 的狀態，使指向 987   start.cur = start.first;            //  下一個緩衝區的第一個元素。 988 }       989  990 #ifdef __STL_MEMBER_TEMPLATES   991  992 template <class T, class Alloc, size_t BufSize> 993 template <class InputIterator> 994 void deque<T, Alloc, BufSize>::insert(iterator pos, 995                                       InputIterator first, InputIterator last, 996                                       input_iterator_tag) { 997   copy(first, last, inserter(*this, pos)); 998 } 999 1000 template <class T, class Alloc, size_t BufSize>1001 template <class ForwardIterator>1002 void deque<T, Alloc, BufSize>::insert(iterator pos,1003                                       ForwardIterator first,1004                                       ForwardIterator last,1005                                       forward_iterator_tag) {1006   size_type n = 0;1007   distance(first, last, n);1008   if (pos.cur == start.cur) {1009     iterator new_start = reserve_elements_at_front(n);1010     __STL_TRY {1011       uninitialized_copy(first, last, new_start);1012       start = new_start;1013     }1014     __STL_UNWIND(destroy_nodes_at_front(new_start));1015   }1016   else if (pos.cur == finish.cur) {1017     iterator new_finish = reserve_elements_at_back(n);1018     __STL_TRY {1019       uninitialized_copy(first, last, finish);1020       finish = new_finish;1021     }1022     __STL_UNWIND(destroy_nodes_at_back(new_finish));1023   }1024   else1025     insert_aux(pos, first, last, n);1026 }1027 1028 #endif /* __STL_MEMBER_TEMPLATES */1029 1030 template <class T, class Alloc, size_t BufSize>1031 typename deque<T, Alloc, BufSize>::iterator1032 deque<T, Alloc, BufSize>::insert_aux(iterator pos, const value_type& x) {1033   difference_type index = pos - start;    // 安插點之前的元素個數1034   value_type x_copy = x;1035   if (index < size() / 2) {            // 如果安插點之前的元素個數比較少1036     push_front(front());            // 在最前端加入與第一元素同值的元素。1037     iterator front1 = start;        // 以下標示記號，然後進行元素搬移...1038     ++front1;1039     iterator front2 = front1;1040     ++front2;1041     pos = start + index;1042     iterator pos1 = pos;1043     ++pos1;1044     copy(front2, pos1, front1);        // 元素搬移1045   }1046   else {                        // 安插點之後的元素個數比較少1047     push_back(back());            // 在最尾端加入與最後元素同值的元素。1048     iterator back1 = finish;    // 以下標示記號，然後進行元素搬移...1049     --back1;1050     iterator back2 = back1;1051     --back2;1052     pos = start + index;1053     copy_backward(pos, back2, back1);    // 元素搬移1054   }1055   *pos = x_copy;    // 在安插點上設定新值1056   return pos;1057 }1058 1059 template <class T, class Alloc, size_t BufSize>1060 void deque<T, Alloc, BufSize>::insert_aux(iterator pos,1061                                           size_type n, const value_type& x) {1062   const difference_type elems_before = pos - start;1063   size_type length = size();1064   value_type x_copy = x;1065   if (elems_before < length / 2) {1066     iterator new_start = reserve_elements_at_front(n);1067     iterator old_start = start;1068     pos = start + elems_before;1069     __STL_TRY {1070       if (elems_before >= difference_type(n)) {1071         iterator start_n = start + difference_type(n);1072         uninitialized_copy(start, start_n, new_start);1073         start = new_start;1074         copy(start_n, pos, old_start);1075         fill(pos - difference_type(n), pos, x_copy);1076       }1077       else {1078         __uninitialized_copy_fill(start, pos, new_start, start, x_copy);1079         start = new_start;1080         fill(old_start, pos, x_copy);1081       }1082     }1083     __STL_UNWIND(destroy_nodes_at_front(new_start));1084   }1085   else {1086     iterator new_finish = reserve_elements_at_back(n);1087     iterator old_finish = finish;1088     const difference_type elems_after = difference_type(length) - elems_before;1089     pos = finish - elems_after;1090     __STL_TRY {1091       if (elems_after > difference_type(n)) {1092         iterator finish_n = finish - difference_type(n);1093         uninitialized_copy(finish_n, finish, finish);1094         finish = new_finish;1095         copy_backward(pos, finish_n, old_finish);1096         fill(pos, pos + difference_type(n), x_copy);1097       }1098       else {1099         __uninitialized_fill_copy(finish, pos + difference_type(n),1100                                   x_copy,1101                                   pos, finish);1102         finish = new_finish;1103         fill(pos, old_finish, x_copy);1104       }1105     }1106     __STL_UNWIND(destroy_nodes_at_back(new_finish));1107   }1108 }1109 1110 #ifdef __STL_MEMBER_TEMPLATES  1111 1112 template <class T, class Alloc, size_t BufSize>1113 template <class ForwardIterator>1114 void deque<T, Alloc, BufSize>::insert_aux(iterator pos,1115                                           ForwardIterator first,1116                                           ForwardIterator last,1117                                           size_type n)1118 {1119   const difference_type elems_before = pos - start;1120   size_type length = size();1121   if (elems_before < length / 2) {1122     iterator new_start = reserve_elements_at_front(n);1123     iterator old_start = start;1124     pos = start + elems_before;1125     __STL_TRY {1126       if (elems_before >= difference_type(n)) {1127         iterator start_n = start + difference_type(n); 1128         uninitialized_copy(start, start_n, new_start);1129         start = new_start;1130         copy(start_n, pos, old_start);1131         copy(first, last, pos - difference_type(n));1132       }1133       else {1134         ForwardIterator mid = first;1135         advance(mid, difference_type(n) - elems_before);1136         __uninitialized_copy_copy(start, pos, first, mid, new_start);1137         start = new_start;1138         copy(mid, last, old_start);1139       }1140     }1141     __STL_UNWIND(destroy_nodes_at_front(new_start));1142   }1143   else {1144     iterator new_finish = reserve_elements_at_back(n);1145     iterator old_finish = finish;1146     const difference_type elems_after = difference_type(length) - elems_before;1147     pos = finish - elems_after;1148     __STL_TRY {1149       if (elems_after > difference_type(n)) {1150         iterator finish_n = finish - difference_type(n);1151         uninitialized_copy(finish_n, finish, finish);1152         finish = new_finish;1153         copy_backward(pos, finish_n, old_finish);1154         copy(first, last, pos);1155       }1156       else {1157         ForwardIterator mid = first;1158         advance(mid, elems_after);1159         __uninitialized_copy_copy(mid, last, pos, finish, finish);1160         finish = new_finish;1161         copy(first, mid, pos);1162       }1163     }1164     __STL_UNWIND(destroy_nodes_at_back(new_finish));1165   }1166 }1167 1168 #else /* __STL_MEMBER_TEMPLATES */1169 1170 template <class T, class Alloc, size_t BufSize>1171 void deque<T, Alloc, BufSize>::insert_aux(iterator pos,1172                                           const value_type* first,1173                                           const value_type* last,1174                                           size_type n)1175 {1176   const difference_type elems_before = pos - start;1177   size_type length = size();1178   if (elems_before < length / 2) {1179     iterator new_start = reserve_elements_at_front(n);1180     iterator old_start = start;1181     pos = start + elems_before;1182     __STL_TRY {1183       if (elems_before >= difference_type(n)) {1184         iterator start_n = start + difference_type(n);1185         uninitialized_copy(start, start_n, new_start);1186         start = new_start;1187         copy(start_n, pos, old_start);1188         copy(first, last, pos - difference_type(n));1189       }1190       else {1191         const value_type* mid = first + (difference_type(n) - elems_before);1192         __uninitialized_copy_copy(start, pos, first, mid, new_start);1193         start = new_start;1194         copy(mid, last, old_start);1195       }1196     }1197     __STL_UNWIND(destroy_nodes_at_front(new_start));1198   }1199   else {1200     iterator new_finish = reserve_elements_at_back(n);1201     iterator old_finish = finish;1202     const difference_type elems_after = difference_type(length) - elems_before;1203     pos = finish - elems_after;1204     __STL_TRY {1205       if (elems_after > difference_type(n)) {1206         iterator finish_n = finish - difference_type(n);1207         uninitialized_copy(finish_n, finish, finish);1208         finish = new_finish;1209         copy_backward(pos, finish_n, old_finish);1210         copy(first, last, pos);1211       }1212       else {1213         const value_type* mid = first + elems_after;1214         __uninitialized_copy_copy(mid, last, pos, finish, finish);1215         finish = new_finish;1216         copy(first, mid, pos);1217       }1218     }1219     __STL_UNWIND(destroy_nodes_at_back(new_finish));1220   }1221 }1222 1223 template <class T, class Alloc, size_t BufSize>1224 void deque<T, Alloc, BufSize>::insert_aux(iterator pos,1225                                           const_iterator first,1226                                           const_iterator last,1227                                           size_type n)1228 {1229   const difference_type elems_before = pos - start;1230   size_type length = size();1231   if (elems_before < length / 2) {1232     iterator new_start = reserve_elements_at_front(n);1233     iterator old_start = start;1234     pos = start + elems_before;1235     __STL_TRY {1236       if (elems_before >= n) {1237         iterator start_n = start + n;1238         uninitialized_copy(start, start_n, new_start);1239         start = new_start;1240         copy(start_n, pos, old_start);1241         copy(first, last, pos - difference_type(n));1242       }1243       else {1244         const_iterator mid = first + (n - elems_before);1245         __uninitialized_copy_copy(start, pos, first, mid, new_start);1246         start = new_start;1247         copy(mid, last, old_start);1248       }1249     }1250     __STL_UNWIND(destroy_nodes_at_front(new_start));1251   }1252   else {1253     iterator new_finish = reserve_elements_at_back(n);1254     iterator old_finish = finish;1255     const difference_type elems_after = length - elems_before;1256     pos = finish - elems_after;1257     __STL_TRY {1258       if (elems_after > n) {1259         iterator finish_n = finish - difference_type(n);1260         uninitialized_copy(finish_n, finish, finish);1261         finish = new_finish;1262         copy_backward(pos, finish_n, old_finish);1263         copy(first, last, pos);1264       }1265       else {1266         const_iterator mid = first + elems_after;1267         __uninitialized_copy_copy(mid, last, pos, finish, finish);1268         finish = new_finish;1269         copy(first, mid, pos);1270       }1271     }1272     __STL_UNWIND(destroy_nodes_at_back(new_finish));1273   }1274 }1275 1276 #endif /* __STL_MEMBER_TEMPLATES */1277 1278 template <class T, class Alloc, size_t BufSize>1279 void deque<T, Alloc, BufSize>::new_elements_at_front(size_type new_elements) {1280   size_type new_nodes = (new_elements + buffer_size() - 1) / buffer_size();1281   reserve_map_at_front(new_nodes);1282   size_type i;1283   __STL_TRY {1284     for (i = 1; i <= new_nodes; ++i)1285       *(start.node - i) = allocate_node();1286   }1287 #       ifdef __STL_USE_EXCEPTIONS1288   catch(...) {1289     for (size_type j = 1; j < i; ++j)1290       deallocate_node(*(start.node - j));      1291     throw;1292   }1293 #       endif /* __STL_USE_EXCEPTIONS */1294 }1295 1296 template <class T, class Alloc, size_t BufSize>1297 void deque<T, Alloc, BufSize>::new_elements_at_back(size_type new_elements) {1298   size_type new_nodes = (new_elements + buffer_size() - 1) / buffer_size();1299   reserve_map_at_back(new_nodes);1300   size_type i;1301   __STL_TRY {1302     for (i = 1; i <= new_nodes; ++i)1303       *(finish.node + i) = allocate_node();1304   }1305 #       ifdef __STL_USE_EXCEPTIONS1306   catch(...) {1307     for (size_type j = 1; j < i; ++j)1308       deallocate_node(*(finish.node + j));      1309     throw;1310   }1311 #       endif /* __STL_USE_EXCEPTIONS */1312 }1313 1314 template <class T, class Alloc, size_t BufSize>1315 void deque<T, Alloc, BufSize>::destroy_nodes_at_front(iterator before_start) {1316   for (map_pointer n = before_start.node; n < start.node; ++n)1317     deallocate_node(*n);1318 }1319 1320 template <class T, class Alloc, size_t BufSize>1321 void deque<T, Alloc, BufSize>::destroy_nodes_at_back(iterator after_finish) {1322   for (map_pointer n = after_finish.node; n > finish.node; --n)1323     deallocate_node(*n);1324 }1325 1326 template <class T, class Alloc, size_t BufSize>1327 void deque<T, Alloc, BufSize>::reallocate_map(size_type nodes_to_add,1328                                               bool add_at_front) {1329   size_type old_num_nodes = finish.node - start.node + 1;1330   size_type new_num_nodes = old_num_nodes + nodes_to_add;1331 1332   map_pointer new_nstart;1333   if (map_size > 2 * new_num_nodes) {1334     new_nstart = map + (map_size - new_num_nodes) / 2 1335                      + (add_at_front ? nodes_to_add : 0);1336     if (new_nstart < start.node)1337       copy(start.node, finish.node + 1, new_nstart);1338     else1339       copy_backward(start.node, finish.node + 1, new_nstart + old_num_nodes);1340   }1341   else {1342     size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2;1343     // 配置一塊空間，準備給新map使用。1344     map_pointer new_map = map_allocator::allocate(new_map_size);1345     new_nstart = new_map + (new_map_size - new_num_nodes) / 21346                          + (add_at_front ? nodes_to_add : 0);1347     // 把原map 內容拷貝過來。1348     copy(start.node, finish.node + 1, new_nstart);1349     // 釋放原map1350     map_allocator::deallocate(map, map_size);1351     // 設定新map的起始位址與大小1352     map = new_map;1353     map_size = new_map_size;1354   }1355 1356   // 重新設定迭代器 start 和 finish1357   start.set_node(new_nstart);1358   finish.set_node(new_nstart + old_num_nodes - 1);1359 }1360 1361 1362 // Nonmember functions.1363 1364 #ifndef __STL_NON_TYPE_TMPL_PARAM_BUG1365 1366 template <class T, class Alloc, size_t BufSiz>1367 bool operator==(const deque<T, Alloc, BufSiz>& x,1368                 const deque<T, Alloc, BufSiz>& y) {1369   return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());1370 }1371 1372 template <class T, class Alloc, size_t BufSiz>1373 bool operator<(const deque<T, Alloc, BufSiz>& x,1374                const deque<T, Alloc, BufSiz>& y) {1375   return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());1376 }1377 1378 #endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */1379 1380 #if defined(__STL_FUNCTION_TMPL_PARTIAL_ORDER) && 1381     !defined(__STL_NON_TYPE_TMPL_PARAM_BUG)1382 1383 template <class T, class Alloc, size_t BufSiz>1384 inline void swap(deque<T, Alloc, BufSiz>& x, deque<T, Alloc, BufSiz>& y) {1385   x.swap(y);1386 }1387 1388 #endif1389 1390 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)1391 #pragma reset woff 11741392 #endif1393           1394 __STL_END_NAMESPACE 1395   1396 #endif /* __SGI_STL_INTERNAL_DEQUE_H */1397 1398 // Local Variables:1399 // mode:C++1400 // End: