1 G++ 2.91.57，cygnus\cygwin-b20\include\g++\stl_vector.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) 1996 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_VECTOR_H 33 #define __SGI_STL_INTERNAL_VECTOR_H 34  35 __STL_BEGIN_NAMESPACE  36  37 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 38 #pragma set woff 1174 39 #endif 40  41 template <class T, class Alloc = alloc>  // 預設使用 alloc 為配置器 42 class vector { 43 public: 44   // 以下標示 (1),(2),(3),(4),(5)，代表 iterator_traits<I> 所服務的5個型別。 45   typedef T value_type;                // (1) 46   typedef value_type* pointer;             // (2) 47   typedef const value_type* const_pointer; 48   typedef const value_type* const_iterator; 49   typedef value_type& reference;         // (3) 50   typedef const value_type& const_reference; 51   typedef size_t size_type; 52   typedef ptrdiff_t difference_type;     // (4) 53   // 以下，由於vector 所維護的是一個連續線性空間，所以不論其元素型別為何， 54   // 原生指標都可以做為其迭代器而滿足所有需求。 55   typedef value_type* iterator; 56   /* 根據上述寫法，如果客端寫出這樣的碼： 57       vector<Shape>::iterator is; 58       is 的型別其實就是Shape* 59       而STL 內部運用 iterator_traits<is>::reference 時，獲得 Shape& 60                  運用iterator_traits<is>::iterator_category 時，獲得  61                       random_access_iterator_tag        (5) 62       （此乃iterator_traits 針對原生指標的特化結果） 63   */ 64  65 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 66   typedef reverse_iterator<const_iterator> const_reverse_iterator; 67   typedef reverse_iterator<iterator> reverse_iterator; 68 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 69   typedef reverse_iterator<const_iterator, value_type, const_reference,  70                            difference_type>  const_reverse_iterator; 71   typedef reverse_iterator<iterator, value_type, reference, difference_type> 72           reverse_iterator; 73 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 74 protected: 75   // 專屬之空間配置器，每次配置一個元素大小 76   typedef simple_alloc<value_type, Alloc> data_allocator; 77  78   // vector採用簡單的線性連續空間。以兩個迭代器start和end分別指向頭尾， 79   // 並以迭代器end_of_storage指向容量尾端。容量可能比(尾-頭)還大， 80   // 多餘即備用空間。 81   iterator start; 82   iterator finish; 83   iterator end_of_storage; 84  85   void insert_aux(iterator position, const T& x); 86   void deallocate() { 87     if (start) 88          data_allocator::deallocate(start, end_of_storage - start); 89   } 90  91   void fill_initialize(size_type n, const T& value) { 92     start = allocate_and_fill(n, value);  // 配置空間並設初值 93     finish = start + n;                // 調整水位 94     end_of_storage = finish;             // 調整水位 95   } 96 public: 97   iterator begin() { return start; } 98   const_iterator begin() const { return start; } 99   iterator end() { return finish; }100   const_iterator end() const { return finish; }101   reverse_iterator rbegin() { return reverse_iterator(end()); }102   const_reverse_iterator rbegin() const { 103     return const_reverse_iterator(end()); 104   }105   reverse_iterator rend() { return reverse_iterator(begin()); }106   const_reverse_iterator rend() const { 107     return const_reverse_iterator(begin()); 108   }109   size_type size() const { return size_type(end() - begin()); }110   size_type max_size() const { return size_type(-1) / sizeof(T); }111   size_type capacity() const { return size_type(end_of_storage - begin()); }112   bool empty() const { return begin() == end(); }113   reference operator[](size_type n) { return *(begin() + n); }114   const_reference operator[](size_type n) const { return *(begin() + n); }115 116   vector() : start(0), finish(0), end_of_storage(0) {}117   // 以下建構式，允許指定大小 n 和初值 value118   vector(size_type n, const T& value) { fill_initialize(n, value); }119   vector(int n, const T& value) { fill_initialize(n, value); }120   vector(long n, const T& value) { fill_initialize(n, value); }121   explicit vector(size_type n) { fill_initialize(n, T()); }122 123   vector(const vector<T, Alloc>& x) {124     start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());125     finish = start + (x.end() - x.begin());126     end_of_storage = finish;127   }128 #ifdef __STL_MEMBER_TEMPLATES129   template <class InputIterator>130   vector(InputIterator first, InputIterator last) :131     start(0), finish(0), end_of_storage(0)132   {133     range_initialize(first, last, iterator_category(first));134   }135 #else /* __STL_MEMBER_TEMPLATES */136   vector(const_iterator first, const_iterator last) {137     size_type n = 0;138     distance(first, last, n);139     start = allocate_and_copy(n, first, last);140     finish = start + n;141     end_of_storage = finish;142   }143 #endif /* __STL_MEMBER_TEMPLATES */144   ~vector() { 145     destroy(start, finish);  // 全域函式，建構/解構基本工具。146     deallocate();   // 先前定義好的成員函式147   }148   vector<T, Alloc>& operator=(const vector<T, Alloc>& x);149   void reserve(size_type n) {150     if (capacity() < n) {151       const size_type old_size = size();152       iterator tmp = allocate_and_copy(n, start, finish);153       destroy(start, finish);154       deallocate();155       start = tmp;156       finish = tmp + old_size;157       end_of_storage = start + n;158     }159   }160 161   // 取出第一個元素內容162   reference front() { return *begin(); }163   const_reference front() const { return *begin(); }164   // 取出最後一個元素內容165   reference back() { return *(end() - 1); }166   const_reference back() const { return *(end() - 1); }167   // 增加一個元素，做為最後元素168   void push_back(const T& x) {169     if (finish != end_of_storage) {  // 還有備用空間170       construct(finish, x);           // 直接在備用空間中建構元素。171       ++finish;                              // 調整水位高度172     }173     else                                  // 已無備用空間174       insert_aux(end(), x);            175   }176   void swap(vector<T, Alloc>& x) {177     __STD::swap(start, x.start);178     __STD::swap(finish, x.finish);179     __STD::swap(end_of_storage, x.end_of_storage);180   }181   iterator insert(iterator position, const T& x) {182     size_type n = position - begin();183     if (finish != end_of_storage && position == end()) {184       construct(finish, x);        // 全域函式，建構/解構基本工具。185       ++finish;186     }187     else188       insert_aux(position, x);189     return begin() + n;190   }191   iterator insert(iterator position) { return insert(position, T()); }192 #ifdef __STL_MEMBER_TEMPLATES193   template <class InputIterator>194   void insert(iterator position, InputIterator first, InputIterator last){195     range_insert(position, first, last, iterator_category(first));196   }197 #else /* __STL_MEMBER_TEMPLATES */198   void insert(iterator position,199               const_iterator first, const_iterator last);200 #endif /* __STL_MEMBER_TEMPLATES */201 202   void insert (iterator pos, size_type n, const T& x);203   void insert (iterator pos, int n, const T& x) {204     insert(pos, (size_type) n, x);205   }206   void insert (iterator pos, long n, const T& x) {207     insert(pos, (size_type) n, x);208   }209 210   void pop_back() {211     --finish;212     destroy(finish);    // 全域函式，建構/解構基本工具。213   }214   // 將迭代器 position 所指之元素移除215   iterator erase(iterator position) {216     if (position + 1 != end()) // 如果 p 不是指向最後一個元素217       // 將 p 之後的元素一一向前遞移218       copy(position + 1, finish, position); 219 220     --finish;  // 調整水位221     destroy(finish);    // 全域函式，建構/解構基本工具。222     return position;223   }224   iterator erase(iterator first, iterator last) {225     iterator i = copy(last, finish, first);226     destroy(i, finish);    // 全域函式，建構/解構基本工具。227     finish = finish - (last - first);228     return first;229   }230   void resize(size_type new_size, const T& x) {231     if (new_size < size()) 232       erase(begin() + new_size, end());233     else234       insert(end(), new_size - size(), x);235   }236   void resize(size_type new_size) { resize(new_size, T()); }237   // 清除全部元素。注意，並未釋放空間，以備可能未來還會新加入元素。238   void clear() { erase(begin(), end()); }239 240 protected:241   iterator allocate_and_fill(size_type n, const T& x) {242     iterator result = data_allocator::allocate(n); // 配置n個元素空間243     __STL_TRY {244       // 全域函式，記憶體低階工具，將result所指之未初始化空間設定初值為 x，n個245       // 定義於 <stl_uninitialized.h>。246       uninitialized_fill_n(result, n, x);  247       return result;248     }249      // "commit or rollback" 語意：若非全部成功，就一個不留。250     __STL_UNWIND(data_allocator::deallocate(result, n));251   }252 253 #ifdef __STL_MEMBER_TEMPLATES254   template <class ForwardIterator>255   iterator allocate_and_copy(size_type n,256                              ForwardIterator first, ForwardIterator last) {257     iterator result = data_allocator::allocate(n);258     __STL_TRY {259       uninitialized_copy(first, last, result);260       return result;261     }262     __STL_UNWIND(data_allocator::deallocate(result, n));263   }264 #else /* __STL_MEMBER_TEMPLATES */265   iterator allocate_and_copy(size_type n,266                              const_iterator first, const_iterator last) {267     iterator result = data_allocator::allocate(n);268     __STL_TRY {269       uninitialized_copy(first, last, result);270       return result;271     }272     __STL_UNWIND(data_allocator::deallocate(result, n));273   }274 #endif /* __STL_MEMBER_TEMPLATES */275 276 277 #ifdef __STL_MEMBER_TEMPLATES278   template <class InputIterator>279   void range_initialize(InputIterator first, InputIterator last,280                         input_iterator_tag) {281     for ( ; first != last; ++first)282       push_back(*first);283   }284 285   // This function is only called by the constructor.  We have to worry286   //  about resource leaks, but not about maintaining invariants.287   template <class ForwardIterator>288   void range_initialize(ForwardIterator first, ForwardIterator last,289                         forward_iterator_tag) {290     size_type n = 0;291     distance(first, last, n);292     start = allocate_and_copy(n, first, last);293     finish = start + n;294     end_of_storage = finish;295   }296 297   template <class InputIterator>298   void range_insert(iterator pos,299                     InputIterator first, InputIterator last,300                     input_iterator_tag);301 302   template <class ForwardIterator>303   void range_insert(iterator pos,304                     ForwardIterator first, ForwardIterator last,305                     forward_iterator_tag);306 307 #endif /* __STL_MEMBER_TEMPLATES */308 };309 310 template <class T, class Alloc>311 inline bool operator==(const vector<T, Alloc>& x, const vector<T, Alloc>& y) {312   return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());313 }314 315 template <class T, class Alloc>316 inline bool operator<(const vector<T, Alloc>& x, const vector<T, Alloc>& y) {317   return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());318 }319 320 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER321 322 template <class T, class Alloc>323 inline void swap(vector<T, Alloc>& x, vector<T, Alloc>& y) {324   x.swap(y);325 }326 327 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */328 329 template <class T, class Alloc>330 vector<T, Alloc>& vector<T, Alloc>::operator=(const vector<T, Alloc>& x) {331   if (&x != this) {    // 判斷是否 self-assignment332     if (x.size() > capacity()) {        // 如果標的物比我本身的容量還大333       iterator tmp = allocate_and_copy(x.end() - x.begin(),334                                        x.begin(), x.end());335       destroy(start, finish);    // 把整個舊的vector 摧毀336       deallocate();            // 釋放舊空間337       start = tmp;                // 設定指向新空間338       end_of_storage = start + (x.end() - x.begin());339     }340     else if (size() >= x.size()) {    // 如果標的物大小 <= 我的大小341       iterator i = copy(x.begin(), x.end(), begin());342       destroy(i, finish);343     }344     else {345       copy(x.begin(), x.begin() + size(), start);346       uninitialized_copy(x.begin() + size(), x.end(), finish);347     }348     finish = start + x.size();349   }350   return *this;351 }352 353 template <class T, class Alloc>354 void vector<T, Alloc>::insert_aux(iterator position, const T& x) {355   if (finish != end_of_storage) {  // 還有備用空間356     // 在備用空間起始處建構一個元素，並以vector 最後一個元素值為其初值。    357     construct(finish, *(finish - 1));358     // 調整水位。359     ++finish;360     // 以下做啥用？361     T x_copy = x;362     copy_backward(position, finish - 2, finish - 1);363     *position = x_copy;364   }365   else {        // 已無備用空間366     const size_type old_size = size();367     const size_type len = old_size != 0 ? 2 * old_size : 1;368     // 以上配置原則：如果原大小為0，則配置 1（個元素大小）；369     // 如果原大小不為0，則配置原大小的兩倍，370     // 前半段用來放置原資料，後半段準備用來放置新資料。371 372     iterator new_start = data_allocator::allocate(len); // 實際配置373     iterator new_finish = new_start;374     __STL_TRY {375       // 將原vector 的內容拷貝到新 vector。376       new_finish = uninitialized_copy(start, position, new_start);377       // 為新元素設定初值x378       construct(new_finish, x);379       // 調整水位。380       ++new_finish;381       // 將原vector 的備用空間中的內容也忠實拷貝過來（啥用途？）382       new_finish = uninitialized_copy(position, finish, new_finish);383     }384 385 #       ifdef  __STL_USE_EXCEPTIONS 386     catch(...) {387       // "commit or rollback" 語意：若非全部成功，就一個不留。388       destroy(new_start, new_finish); 389       data_allocator::deallocate(new_start, len);390       throw;391     }392 #       endif /* __STL_USE_EXCEPTIONS */393 394     // 解構並釋放原 vector395     destroy(begin(), end());396     deallocate();397 398     // 調整迭代器，指向新vector399     start = new_start;400     finish = new_finish;401     end_of_storage = new_start + len;402   }403 }404 405 // 從 position 開始，安插 n 個元素，元素初值為 x406 template <class T, class Alloc>407 void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {408   if (n != 0) { // 當 n != 0  才進行以下所有動作409     if (size_type(end_of_storage - finish) >= n) { 410       // 備用空間大於等於「新增元素個數」411       T x_copy = x;412       // 以下計算安插點之後的現有元素個數413       const size_type elems_after = finish - position;    414       iterator old_finish = finish;415       if (elems_after > n) { 416         // 「安插點之後的現有元素個數」大於「新增元素個數」417         uninitialized_copy(finish - n, finish, finish);418         finish += n;    // 將vector 尾端標記後移419         copy_backward(position, old_finish - n, old_finish);420         fill(position, position + n, x_copy);    // 從安插點開始填入新值421       }422       else {    423         // 「安插點之後的現有元素個數」小於等於「新增元素個數」424         uninitialized_fill_n(finish, n - elems_after, x_copy);425         finish += n - elems_after;426         uninitialized_copy(position, old_finish, finish);427         finish += elems_after;428         fill(position, old_finish, x_copy);429       }430     }431     else {432       // 備用空間小於「新增元素個數」（那就必須配置額外的記憶體）433       // 首先決定新長度：舊長度的兩倍，或舊長度+新增元素個數。434       const size_type old_size = size();        435       const size_type len = old_size + max(old_size, n);436       // 以下配置新的vector 空間437       iterator new_start = data_allocator::allocate(len);438       iterator new_finish = new_start;439       __STL_TRY {440         // 以下首先將舊vector 的安插點之前的元素複製到新空間。441         new_finish = uninitialized_copy(start, position, new_start);442         // 以下再將新增元素（初值皆為 n）填入新空間。443         new_finish = uninitialized_fill_n(new_finish, n, x);444         // 以下再將舊vector 的安插點之後的元素複製到新空間。445         new_finish = uninitialized_copy(position, finish, new_finish);446       }447 #         ifdef  __STL_USE_EXCEPTIONS 448       catch(...) {449         // 如有異常發生，實現 "commit or rollback" semantics.450         destroy(new_start, new_finish);451         data_allocator::deallocate(new_start, len);452         throw;453       }454 #         endif /* __STL_USE_EXCEPTIONS */455       // 以下清除並釋放舊的 vector 456       destroy(start, finish);457       deallocate();458       // 以下調整水位標記459       start = new_start;460       finish = new_finish;461       end_of_storage = new_start + len;462     }463   }464 }465 466 #ifdef __STL_MEMBER_TEMPLATES467 468 template <class T, class Alloc> template <class InputIterator>469 void vector<T, Alloc>::range_insert(iterator pos,470                                     InputIterator first, InputIterator last,471                                     input_iterator_tag) {472   for ( ; first != last; ++first) {473     pos = insert(pos, *first);474     ++pos;475   }476 }477 478 template <class T, class Alloc> template <class ForwardIterator>479 void vector<T, Alloc>::range_insert(iterator position,480                                     ForwardIterator first,481                                     ForwardIterator last,482                                     forward_iterator_tag) {483   if (first != last) {484     size_type n = 0;485     distance(first, last, n);486     if (size_type(end_of_storage - finish) >= n) {487       const size_type elems_after = finish - position;488       iterator old_finish = finish;489       if (elems_after > n) {490         uninitialized_copy(finish - n, finish, finish);491         finish += n;492         copy_backward(position, old_finish - n, old_finish);493         copy(first, last, position);494       }495       else {496         ForwardIterator mid = first;497         advance(mid, elems_after);498         uninitialized_copy(mid, last, finish);499         finish += n - elems_after;500         uninitialized_copy(position, old_finish, finish);501         finish += elems_after;502         copy(first, mid, position);503       }504     }505     else {506       const size_type old_size = size();507       const size_type len = old_size + max(old_size, n);508       iterator new_start = data_allocator::allocate(len);509       iterator new_finish = new_start;510       __STL_TRY {511         new_finish = uninitialized_copy(start, position, new_start);512         new_finish = uninitialized_copy(first, last, new_finish);513         new_finish = uninitialized_copy(position, finish, new_finish);514       }515 #         ifdef __STL_USE_EXCEPTIONS516       catch(...) {517         destroy(new_start, new_finish);518         data_allocator::deallocate(new_start, len);519         throw;520       }521 #         endif /* __STL_USE_EXCEPTIONS */522       destroy(start, finish);523       deallocate();524       start = new_start;525       finish = new_finish;526       end_of_storage = new_start + len;527     }528   }529 }530 531 #else /* __STL_MEMBER_TEMPLATES */532 533 template <class T, class Alloc>534 void vector<T, Alloc>::insert(iterator position, 535                               const_iterator first, 536                               const_iterator last) {537   if (first != last) {538     size_type n = 0;539     distance(first, last, n);540     if (size_type(end_of_storage - finish) >= n) {541       const size_type elems_after = finish - position;542       iterator old_finish = finish;543       if (elems_after > n) {544         uninitialized_copy(finish - n, finish, finish);545         finish += n;546         copy_backward(position, old_finish - n, old_finish);547         copy(first, last, position);548       }549       else {550         uninitialized_copy(first + elems_after, last, finish);551         finish += n - elems_after;552         uninitialized_copy(position, old_finish, finish);553         finish += elems_after;554         copy(first, first + elems_after, position);555       }556     }557     else {558       const size_type old_size = size();559       const size_type len = old_size + max(old_size, n);560       iterator new_start = data_allocator::allocate(len);561       iterator new_finish = new_start;562       __STL_TRY {563         new_finish = uninitialized_copy(start, position, new_start);564         new_finish = uninitialized_copy(first, last, new_finish);565         new_finish = uninitialized_copy(position, finish, new_finish);566       }567 #         ifdef __STL_USE_EXCEPTIONS568       catch(...) {569         destroy(new_start, new_finish);570         data_allocator::deallocate(new_start, len);571         throw;572       }573 #         endif /* __STL_USE_EXCEPTIONS */574       destroy(start, finish);575       deallocate();576       start = new_start;577       finish = new_finish;578       end_of_storage = new_start + len;579     }580   }581 }582 583 #endif /* __STL_MEMBER_TEMPLATES */584 585 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)586 #pragma reset woff 1174587 #endif588 589 __STL_END_NAMESPACE 590 591 #endif /* __SGI_STL_INTERNAL_VECTOR_H */592 593 // Local Variables:594 // mode:C++595 // End: