home *** CD-ROM | disk | FTP | other *** search
/ Programming Win32 Under the API / ProgrammingWin32UnderTheApiPatVillani.iso / gcc-2.95.2-msvcrt.exe / include / g++-3 / stl_vector.h < prev    next >
C/C++ Source or Header  |  1999-11-07  |  27KB  |  824 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  *
  15.  * Copyright (c) 1996
  16.  * Silicon Graphics Computer Systems, Inc.
  17.  *
  18.  * Permission to use, copy, modify, distribute and sell this software
  19.  * and its documentation for any purpose is hereby granted without fee,
  20.  * provided that the above copyright notice appear in all copies and
  21.  * that both that copyright notice and this permission notice appear
  22.  * in supporting documentation.  Silicon Graphics makes no
  23.  * representations about the suitability of this software for any
  24.  * purpose.  It is provided "as is" without express or implied warranty.
  25.  */
  26.  
  27. /* NOTE: This is an internal header file, included by other STL headers.
  28.  *   You should not attempt to use it directly.
  29.  */
  30.  
  31. #ifndef __SGI_STL_INTERNAL_VECTOR_H
  32. #define __SGI_STL_INTERNAL_VECTOR_H
  33.  
  34. __STL_BEGIN_NAMESPACE 
  35.  
  36. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  37. #pragma set woff 1174
  38. #pragma set woff 1375
  39. #endif
  40.  
  41. // The vector base class serves two purposes.  First, its constructor
  42. // and destructor allocate (but don't initialize) storage.  This makes
  43. // exception safety easier.  Second, the base class encapsulates all of
  44. // the differences between SGI-style allocators and standard-conforming
  45. // allocators.
  46.  
  47. #ifdef __STL_USE_STD_ALLOCATORS
  48.  
  49. // Base class for ordinary allocators.
  50. template <class _Tp, class _Allocator, bool _IsStatic>
  51. class _Vector_alloc_base {
  52. public:
  53.   typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
  54.           allocator_type;
  55.   allocator_type get_allocator() const { return _M_data_allocator; }
  56.  
  57.   _Vector_alloc_base(const allocator_type& __a)
  58.     : _M_data_allocator(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0) 
  59.   {}
  60.   
  61. protected:
  62.   allocator_type _M_data_allocator;
  63.   _Tp* _M_start;
  64.   _Tp* _M_finish;
  65.   _Tp* _M_end_of_storage;
  66.  
  67.   _Tp* _M_allocate(size_t __n)
  68.     { return _M_data_allocator.allocate(__n); }
  69.   void _M_deallocate(_Tp* __p, size_t __n)
  70.     { if (__p) _M_data_allocator.deallocate(__p, __n); }
  71. };
  72.  
  73. // Specialization for allocators that have the property that we don't
  74. // actually have to store an allocator object.  
  75. template <class _Tp, class _Allocator>
  76. class _Vector_alloc_base<_Tp, _Allocator, true> {
  77. public:
  78.   typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
  79.           allocator_type;
  80.   allocator_type get_allocator() const { return allocator_type(); }
  81.  
  82.   _Vector_alloc_base(const allocator_type&)
  83.     : _M_start(0), _M_finish(0), _M_end_of_storage(0) 
  84.   {}
  85.   
  86. protected:
  87.   _Tp* _M_start;
  88.   _Tp* _M_finish;
  89.   _Tp* _M_end_of_storage;
  90.  
  91.   typedef typename _Alloc_traits<_Tp, _Allocator>::_Alloc_type _Alloc_type;
  92.   _Tp* _M_allocate(size_t __n)
  93.     { return _Alloc_type::allocate(__n); }
  94.   void _M_deallocate(_Tp* __p, size_t __n)
  95.     { _Alloc_type::deallocate(__p, __n);}
  96. };
  97.  
  98. template <class _Tp, class _Alloc>
  99. struct _Vector_base
  100.   : public _Vector_alloc_base<_Tp, _Alloc,
  101.                               _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
  102. {
  103.   typedef _Vector_alloc_base<_Tp, _Alloc, 
  104.                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
  105.           _Base;
  106.   typedef typename _Base::allocator_type allocator_type;
  107.  
  108.   _Vector_base(const allocator_type& __a) : _Base(__a) {}
  109.   _Vector_base(size_t __n, const allocator_type& __a) : _Base(__a) {
  110.     _M_start = _M_allocate(__n);
  111.     _M_finish = _M_start;
  112.     _M_end_of_storage = _M_start + __n;
  113.   }
  114.  
  115.   ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
  116. };    
  117.  
  118. #else /* __STL_USE_STD_ALLOCATORS */
  119.  
  120. template <class _Tp, class _Alloc> 
  121. class _Vector_base {
  122. public:
  123.   typedef _Alloc allocator_type;
  124.   allocator_type get_allocator() const { return allocator_type(); }
  125.  
  126.   _Vector_base(const _Alloc&)
  127.     : _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
  128.   _Vector_base(size_t __n, const _Alloc&)
  129.     : _M_start(0), _M_finish(0), _M_end_of_storage(0) 
  130.   {
  131.     _M_start = _M_allocate(__n);
  132.     _M_finish = _M_start;
  133.     _M_end_of_storage = _M_start + __n;
  134.   }
  135.  
  136.   ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
  137.  
  138. protected:
  139.   _Tp* _M_start;
  140.   _Tp* _M_finish;
  141.   _Tp* _M_end_of_storage;
  142.  
  143.   typedef simple_alloc<_Tp, _Alloc> _M_data_allocator;
  144.   _Tp* _M_allocate(size_t __n)
  145.     { return _M_data_allocator::allocate(__n); }
  146.   void _M_deallocate(_Tp* __p, size_t __n) 
  147.     { _M_data_allocator::deallocate(__p, __n); }
  148. };
  149.  
  150. #endif /* __STL_USE_STD_ALLOCATORS */
  151.  
  152. template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
  153. class vector : protected _Vector_base<_Tp, _Alloc> 
  154. {
  155. private:
  156.   typedef _Vector_base<_Tp, _Alloc> _Base;
  157. public:
  158.   typedef _Tp value_type;
  159.   typedef value_type* pointer;
  160.   typedef const value_type* const_pointer;
  161.   typedef value_type* iterator;
  162.   typedef const value_type* const_iterator;
  163.   typedef value_type& reference;
  164.   typedef const value_type& const_reference;
  165.   typedef size_t size_type;
  166.   typedef ptrdiff_t difference_type;
  167.  
  168.   typedef typename _Base::allocator_type allocator_type;
  169.   allocator_type get_allocator() const { return _Base::get_allocator(); }
  170.  
  171. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  172.   typedef reverse_iterator<const_iterator> const_reverse_iterator;
  173.   typedef reverse_iterator<iterator> reverse_iterator;
  174. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  175.   typedef reverse_iterator<const_iterator, value_type, const_reference, 
  176.                            difference_type>  const_reverse_iterator;
  177.   typedef reverse_iterator<iterator, value_type, reference, difference_type>
  178.           reverse_iterator;
  179. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  180.  
  181. protected:
  182. #ifdef __STL_HAS_NAMESPACES
  183.   using _Base::_M_allocate;
  184.   using _Base::_M_deallocate;
  185.   using _Base::_M_start;
  186.   using _Base::_M_finish;
  187.   using _Base::_M_end_of_storage;
  188. #endif /* __STL_HAS_NAMESPACES */
  189.  
  190. protected:
  191.   void _M_insert_aux(iterator __position, const _Tp& __x);
  192.   void _M_insert_aux(iterator __position);
  193.  
  194. public:
  195.   iterator begin() { return _M_start; }
  196.   const_iterator begin() const { return _M_start; }
  197.   iterator end() { return _M_finish; }
  198.   const_iterator end() const { return _M_finish; }
  199.  
  200.   reverse_iterator rbegin()
  201.     { return reverse_iterator(end()); }
  202.   const_reverse_iterator rbegin() const
  203.     { return const_reverse_iterator(end()); }
  204.   reverse_iterator rend()
  205.     { return reverse_iterator(begin()); }
  206.   const_reverse_iterator rend() const
  207.     { return const_reverse_iterator(begin()); }
  208.  
  209.   size_type size() const
  210.     { return size_type(end() - begin()); }
  211.   size_type max_size() const
  212.     { return size_type(-1) / sizeof(_Tp); }
  213.   size_type capacity() const
  214.     { return size_type(_M_end_of_storage - begin()); }
  215.   bool empty() const
  216.     { return begin() == end(); }
  217.  
  218.   reference operator[](size_type __n) { return *(begin() + __n); }
  219.   const_reference operator[](size_type __n) const { return *(begin() + __n); }
  220.  
  221.   explicit vector(const allocator_type& __a = allocator_type())
  222.     : _Base(__a) {}
  223.  
  224.   vector(size_type __n, const _Tp& __value,
  225.          const allocator_type& __a = allocator_type()) 
  226.     : _Base(__n, __a)
  227.     { _M_finish = uninitialized_fill_n(_M_start, __n, __value); }
  228.  
  229.   explicit vector(size_type __n)
  230.     : _Base(__n, allocator_type())
  231.     { _M_finish = uninitialized_fill_n(_M_start, __n, _Tp()); }
  232.  
  233.   vector(const vector<_Tp, _Alloc>& __x) 
  234.     : _Base(__x.size(), __x.get_allocator())
  235.     { _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); }
  236.  
  237. #ifdef __STL_MEMBER_TEMPLATES
  238.   // Check whether it's an integral type.  If so, it's not an iterator.
  239.   template <class _InputIterator>
  240.   vector(_InputIterator __first, _InputIterator __last,
  241.          const allocator_type& __a = allocator_type()) : _Base(__a) {
  242.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  243.     _M_initialize_aux(__first, __last, _Integral());
  244.   }
  245.  
  246.   template <class _Integer>
  247.   void _M_initialize_aux(_Integer __n, _Integer __value, __true_type) {
  248.     _M_start = _M_allocate(__n);
  249.     _M_end_of_storage = _M_start + __n; 
  250.     _M_finish = uninitialized_fill_n(_M_start, __n, __value);
  251.   }
  252.  
  253.   template <class _InputIterator>
  254.   void _M_initialize_aux(_InputIterator __first, _InputIterator __last,
  255.                          __false_type) {
  256.     _M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first));
  257.   }
  258.  
  259. #else
  260.   vector(const _Tp* __first, const _Tp* __last,
  261.          const allocator_type& __a = allocator_type())
  262.     : _Base(__last - __first, __a) 
  263.     { _M_finish = uninitialized_copy(__first, __last, _M_start); }
  264. #endif /* __STL_MEMBER_TEMPLATES */
  265.  
  266.   ~vector() { destroy(_M_start, _M_finish); }
  267.  
  268.   vector<_Tp, _Alloc>& operator=(const vector<_Tp, _Alloc>& __x);
  269.   void reserve(size_type __n) {
  270.     if (capacity() < __n) {
  271.       const size_type __old_size = size();
  272.       iterator __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
  273.       destroy(_M_start, _M_finish);
  274.       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
  275.       _M_start = __tmp;
  276.       _M_finish = __tmp + __old_size;
  277.       _M_end_of_storage = _M_start + __n;
  278.     }
  279.   }
  280.  
  281.   // assign(), a generalized assignment member function.  Two
  282.   // versions: one that takes a count, and one that takes a range.
  283.   // The range version is a member template, so we dispatch on whether
  284.   // or not the type is an integer.
  285.  
  286.   void assign(size_type __n, const _Tp& __val);
  287.  
  288. #ifdef __STL_MEMBER_TEMPLATES
  289.   
  290.   template <class _InputIterator>
  291.   void assign(_InputIterator __first, _InputIterator __last) {
  292.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  293.     _M_assign_dispatch(__first, __last, _Integral());
  294.   }
  295.  
  296.   template <class _Integer>
  297.   void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
  298.     { assign((size_type) __n, (_Tp) __val); }
  299.  
  300.   template <class _InputIter>
  301.   void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
  302.     { _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first)); }
  303.  
  304.   template <class _InputIterator>
  305.   void _M_assign_aux(_InputIterator __first, _InputIterator __last,
  306.                      input_iterator_tag);
  307.  
  308.   template <class _ForwardIterator>
  309.   void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
  310.                      forward_iterator_tag); 
  311.  
  312. #endif /* __STL_MEMBER_TEMPLATES */
  313.  
  314.   reference front() { return *begin(); }
  315.   const_reference front() const { return *begin(); }
  316.   reference back() { return *(end() - 1); }
  317.   const_reference back() const { return *(end() - 1); }
  318.  
  319.   void push_back(const _Tp& __x) {
  320.     if (_M_finish != _M_end_of_storage) {
  321.       construct(_M_finish, __x);
  322.       ++_M_finish;
  323.     }
  324.     else
  325.       _M_insert_aux(end(), __x);
  326.   }
  327.   void push_back() {
  328.     if (_M_finish != _M_end_of_storage) {
  329.       construct(_M_finish);
  330.       ++_M_finish;
  331.     }
  332.     else
  333.       _M_insert_aux(end());
  334.   }
  335.   void swap(vector<_Tp, _Alloc>& __x) {
  336.     __STD::swap(_M_start, __x._M_start);
  337.     __STD::swap(_M_finish, __x._M_finish);
  338.     __STD::swap(_M_end_of_storage, __x._M_end_of_storage);
  339.   }
  340.  
  341.   iterator insert(iterator __position, const _Tp& __x) {
  342.     size_type __n = __position - begin();
  343.     if (_M_finish != _M_end_of_storage && __position == end()) {
  344.       construct(_M_finish, __x);
  345.       ++_M_finish;
  346.     }
  347.     else
  348.       _M_insert_aux(__position, __x);
  349.     return begin() + __n;
  350.   }
  351.   iterator insert(iterator __position) {
  352.     size_type __n = __position - begin();
  353.     if (_M_finish != _M_end_of_storage && __position == end()) {
  354.       construct(_M_finish);
  355.       ++_M_finish;
  356.     }
  357.     else
  358.       _M_insert_aux(__position);
  359.     return begin() + __n;
  360.   }
  361. #ifdef __STL_MEMBER_TEMPLATES
  362.   // Check whether it's an integral type.  If so, it's not an iterator.
  363.   template <class _InputIterator>
  364.   void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
  365.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  366.     _M_insert_dispatch(__pos, __first, __last, _Integral());
  367.   }
  368.  
  369.   template <class _Integer>
  370.   void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
  371.                           __true_type) {
  372.     insert(__pos, (size_type) __n, (_Tp) __val);
  373.   }
  374.  
  375.   template <class _InputIterator>
  376.   void _M_insert_dispatch(iterator __pos,
  377.                           _InputIterator __first, _InputIterator __last,
  378.                           __false_type) {
  379.     _M_range_insert(__pos, __first, __last, __ITERATOR_CATEGORY(__first));
  380.   }
  381. #else /* __STL_MEMBER_TEMPLATES */
  382.   void insert(iterator __position,
  383.               const_iterator __first, const_iterator __last);
  384. #endif /* __STL_MEMBER_TEMPLATES */
  385.  
  386.   void insert (iterator __pos, size_type __n, const _Tp& __x);
  387.  
  388.   void pop_back() {
  389.     --_M_finish;
  390.     destroy(_M_finish);
  391.   }
  392.   iterator erase(iterator __position) {
  393.     if (__position + 1 != end())
  394.       copy(__position + 1, _M_finish, __position);
  395.     --_M_finish;
  396.     destroy(_M_finish);
  397.     return __position;
  398.   }
  399.   iterator erase(iterator __first, iterator __last) {
  400.     iterator __i = copy(__last, _M_finish, __first);
  401.     destroy(__i, _M_finish);
  402.     _M_finish = _M_finish - (__last - __first);
  403.     return __first;
  404.   }
  405.  
  406.   void resize(size_type __new_size, const _Tp& __x) {
  407.     if (__new_size < size()) 
  408.       erase(begin() + __new_size, end());
  409.     else
  410.       insert(end(), __new_size - size(), __x);
  411.   }
  412.   void resize(size_type __new_size) { resize(__new_size, _Tp()); }
  413.   void clear() { erase(begin(), end()); }
  414.  
  415. protected:
  416.  
  417. #ifdef __STL_MEMBER_TEMPLATES
  418.   template <class _ForwardIterator>
  419.   iterator _M_allocate_and_copy(size_type __n, _ForwardIterator __first, 
  420.                                                _ForwardIterator __last)
  421. {
  422.     iterator __result = _M_allocate(__n);
  423.     __STL_TRY {
  424.       uninitialized_copy(__first, __last, __result);
  425.       return __result;
  426.     }
  427.     __STL_UNWIND(_M_deallocate(__result, __n));
  428.   }
  429. #else /* __STL_MEMBER_TEMPLATES */
  430.   iterator _M_allocate_and_copy(size_type __n, const_iterator __first, 
  431.                                                const_iterator __last)
  432.   {
  433.     iterator __result = _M_allocate(__n);
  434.     __STL_TRY {
  435.       uninitialized_copy(__first, __last, __result);
  436.       return __result;
  437.     }
  438.     __STL_UNWIND(_M_deallocate(__result, __n));
  439.   }
  440. #endif /* __STL_MEMBER_TEMPLATES */
  441.  
  442.  
  443. #ifdef __STL_MEMBER_TEMPLATES
  444.   template <class _InputIterator>
  445.   void _M_range_initialize(_InputIterator __first,  
  446.                            _InputIterator __last, input_iterator_tag)
  447.   {
  448.     for ( ; __first != __last; ++__first)
  449.       push_back(*__first);
  450.   }
  451.  
  452.   // This function is only called by the constructor. 
  453.   template <class _ForwardIterator>
  454.   void _M_range_initialize(_ForwardIterator __first,
  455.                            _ForwardIterator __last, forward_iterator_tag)
  456.   {
  457.     size_type __n = 0;
  458.     distance(__first, __last, __n);
  459.     _M_start = _M_allocate(__n);
  460.     _M_end_of_storage = _M_start + __n;
  461.     _M_finish = uninitialized_copy(__first, __last, _M_start);
  462.   }
  463.  
  464.   template <class _InputIterator>
  465.   void _M_range_insert(iterator __pos,
  466.                        _InputIterator __first, _InputIterator __last,
  467.                        input_iterator_tag);
  468.  
  469.   template <class _ForwardIterator>
  470.   void _M_range_insert(iterator __pos,
  471.                        _ForwardIterator __first, _ForwardIterator __last,
  472.                        forward_iterator_tag);
  473.  
  474. #endif /* __STL_MEMBER_TEMPLATES */
  475. };
  476.  
  477. template <class _Tp, class _Alloc>
  478. inline bool 
  479. operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
  480. {
  481.   return __x.size() == __y.size() &&
  482.          equal(__x.begin(), __x.end(), __y.begin());
  483. }
  484.  
  485. template <class _Tp, class _Alloc>
  486. inline bool 
  487. operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
  488. {
  489.   return lexicographical_compare(__x.begin(), __x.end(), 
  490.                                  __y.begin(), __y.end());
  491. }
  492.  
  493. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  494.  
  495. template <class _Tp, class _Alloc>
  496. inline void swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
  497. {
  498.   __x.swap(__y);
  499. }
  500.  
  501. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  502.  
  503. template <class _Tp, class _Alloc>
  504. vector<_Tp,_Alloc>& 
  505. vector<_Tp,_Alloc>::operator=(const vector<_Tp, _Alloc>& __x)
  506. {
  507.   if (&__x != this) {
  508.     const size_type __xlen = __x.size();
  509.     if (__xlen > capacity()) {
  510.       iterator __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end());
  511.       destroy(_M_start, _M_finish);
  512.       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
  513.       _M_start = __tmp;
  514.       _M_end_of_storage = _M_start + __xlen;
  515.     }
  516.     else if (size() >= __xlen) {
  517.       iterator __i = copy(__x.begin(), __x.end(), begin());
  518.       destroy(__i, _M_finish);
  519.     }
  520.     else {
  521.       copy(__x.begin(), __x.begin() + size(), _M_start);
  522.       uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish);
  523.     }
  524.     _M_finish = _M_start + __xlen;
  525.   }
  526.   return *this;
  527. }
  528.  
  529. template <class _Tp, class _Alloc>
  530. void vector<_Tp, _Alloc>::assign(size_t __n, const value_type& __val) {
  531.   if (__n > capacity()) {
  532.     vector<_Tp, _Alloc> __tmp(__n, __val, get_allocator());
  533.     __tmp.swap(*this);
  534.   }
  535.   else if (__n > size()) {
  536.     fill(begin(), end(), __val);
  537.     _M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val);
  538.   }
  539.   else
  540.     erase(fill_n(begin(), __n, __val), end());
  541. }
  542.  
  543. #ifdef __STL_MEMBER_TEMPLATES
  544.  
  545. template <class _Tp, class _Alloc> template <class _InputIter>
  546. void vector<_Tp, _Alloc>::_M_assign_aux(_InputIter __first, _InputIter __last,
  547.                                         input_iterator_tag) {
  548.   iterator __cur = begin();
  549.   for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
  550.     *__cur = *__first;
  551.   if (__first == __last)
  552.     erase(__cur, end());
  553.   else
  554.     insert(end(), __first, __last);
  555. }
  556.  
  557. template <class _Tp, class _Alloc> template <class _ForwardIter>
  558. void
  559. vector<_Tp, _Alloc>::_M_assign_aux(_ForwardIter __first, _ForwardIter __last,
  560.                                    forward_iterator_tag) {
  561.   size_type __len = 0;
  562.   distance(__first, __last, __len);
  563.  
  564.   if (__len > capacity()) {
  565.     iterator __tmp = _M_allocate_and_copy(__len, __first, __last);
  566.     destroy(_M_start, _M_finish);
  567.     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
  568.     _M_start = __tmp;
  569.     _M_end_of_storage = _M_finish = _M_start + __len;
  570.   }
  571.   else if (size() >= __len) {
  572.     iterator __new_finish = copy(__first, __last, _M_start);
  573.     destroy(__new_finish, _M_finish);
  574.     _M_finish = __new_finish;
  575.   }
  576.   else {
  577.     _ForwardIter __mid = __first;
  578.     advance(__mid, size());
  579.     copy(__first, __mid, _M_start);
  580.     _M_finish = uninitialized_copy(__mid, __last, _M_finish);
  581.   }
  582. }
  583.  
  584. #endif /* __STL_MEMBER_TEMPLATES */
  585.  
  586. template <class _Tp, class _Alloc>
  587. void 
  588. vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
  589. {
  590.   if (_M_finish != _M_end_of_storage) {
  591.     construct(_M_finish, *(_M_finish - 1));
  592.     ++_M_finish;
  593.     _Tp __x_copy = __x;
  594.     copy_backward(__position, _M_finish - 2, _M_finish - 1);
  595.     *__position = __x_copy;
  596.   }
  597.   else {
  598.     const size_type __old_size = size();
  599.     const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
  600.     iterator __new_start = _M_allocate(__len);
  601.     iterator __new_finish = __new_start;
  602.     __STL_TRY {
  603.       __new_finish = uninitialized_copy(_M_start, __position, __new_start);
  604.       construct(__new_finish, __x);
  605.       ++__new_finish;
  606.       __new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
  607.     }
  608.     __STL_UNWIND((destroy(__new_start,__new_finish), 
  609.                   _M_deallocate(__new_start,__len)));
  610.     destroy(begin(), end());
  611.     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
  612.     _M_start = __new_start;
  613.     _M_finish = __new_finish;
  614.     _M_end_of_storage = __new_start + __len;
  615.   }
  616. }
  617.  
  618. template <class _Tp, class _Alloc>
  619. void 
  620. vector<_Tp, _Alloc>::_M_insert_aux(iterator __position)
  621. {
  622.   if (_M_finish != _M_end_of_storage) {
  623.     construct(_M_finish, *(_M_finish - 1));
  624.     ++_M_finish;
  625.     copy_backward(__position, _M_finish - 2, _M_finish - 1);
  626.     *__position = _Tp();
  627.   }
  628.   else {
  629.     const size_type __old_size = size();
  630.     const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
  631.     iterator __new_start = _M_allocate(__len);
  632.     iterator __new_finish = __new_start;
  633.     __STL_TRY {
  634.       __new_finish = uninitialized_copy(_M_start, __position, __new_start);
  635.       construct(__new_finish);
  636.       ++__new_finish;
  637.       __new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
  638.     }
  639.     __STL_UNWIND((destroy(__new_start,__new_finish), 
  640.                   _M_deallocate(__new_start,__len)));
  641.     destroy(begin(), end());
  642.     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
  643.     _M_start = __new_start;
  644.     _M_finish = __new_finish;
  645.     _M_end_of_storage = __new_start + __len;
  646.   }
  647. }
  648.  
  649. template <class _Tp, class _Alloc>
  650. void vector<_Tp, _Alloc>::insert(iterator __position, size_type __n, 
  651.                                  const _Tp& __x)
  652. {
  653.   if (__n != 0) {
  654.     if (size_type(_M_end_of_storage - _M_finish) >= __n) {
  655.       _Tp __x_copy = __x;
  656.       const size_type __elems_after = _M_finish - __position;
  657.       iterator __old_finish = _M_finish;
  658.       if (__elems_after > __n) {
  659.         uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
  660.         _M_finish += __n;
  661.         copy_backward(__position, __old_finish - __n, __old_finish);
  662.         fill(__position, __position + __n, __x_copy);
  663.       }
  664.       else {
  665.         uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
  666.         _M_finish += __n - __elems_after;
  667.         uninitialized_copy(__position, __old_finish, _M_finish);
  668.         _M_finish += __elems_after;
  669.         fill(__position, __old_finish, __x_copy);
  670.       }
  671.     }
  672.     else {
  673.       const size_type __old_size = size();        
  674.       const size_type __len = __old_size + max(__old_size, __n);
  675.       iterator __new_start = _M_allocate(__len);
  676.       iterator __new_finish = __new_start;
  677.       __STL_TRY {
  678.         __new_finish = uninitialized_copy(_M_start, __position, __new_start);
  679.         __new_finish = uninitialized_fill_n(__new_finish, __n, __x);
  680.         __new_finish
  681.           = uninitialized_copy(__position, _M_finish, __new_finish);
  682.       }
  683.       __STL_UNWIND((destroy(__new_start,__new_finish), 
  684.                     _M_deallocate(__new_start,__len)));
  685.       destroy(_M_start, _M_finish);
  686.       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
  687.       _M_start = __new_start;
  688.       _M_finish = __new_finish;
  689.       _M_end_of_storage = __new_start + __len;
  690.     }
  691.   }
  692. }
  693.  
  694. #ifdef __STL_MEMBER_TEMPLATES
  695.  
  696. template <class _Tp, class _Alloc> template <class _InputIterator>
  697. void 
  698. vector<_Tp, _Alloc>::_M_range_insert(iterator __pos, 
  699.                                      _InputIterator __first, 
  700.                                      _InputIterator __last,
  701.                                      input_iterator_tag)
  702. {
  703.   for ( ; __first != __last; ++__first) {
  704.     __pos = insert(__pos, *__first);
  705.     ++__pos;
  706.   }
  707. }
  708.  
  709. template <class _Tp, class _Alloc> template <class _ForwardIterator>
  710. void 
  711. vector<_Tp, _Alloc>::_M_range_insert(iterator __position,
  712.                                      _ForwardIterator __first,
  713.                                      _ForwardIterator __last,
  714.                                      forward_iterator_tag)
  715. {
  716.   if (__first != __last) {
  717.     size_type __n = 0;
  718.     distance(__first, __last, __n);
  719.     if (size_type(_M_end_of_storage - _M_finish) >= __n) {
  720.       const size_type __elems_after = _M_finish - __position;
  721.       iterator __old_finish = _M_finish;
  722.       if (__elems_after > __n) {
  723.         uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
  724.         _M_finish += __n;
  725.         copy_backward(__position, __old_finish - __n, __old_finish);
  726.         copy(__first, __last, __position);
  727.       }
  728.       else {
  729.         _ForwardIterator __mid = __first;
  730.         advance(__mid, __elems_after);
  731.         uninitialized_copy(__mid, __last, _M_finish);
  732.         _M_finish += __n - __elems_after;
  733.         uninitialized_copy(__position, __old_finish, _M_finish);
  734.         _M_finish += __elems_after;
  735.         copy(__first, __mid, __position);
  736.       }
  737.     }
  738.     else {
  739.       const size_type __old_size = size();
  740.       const size_type __len = __old_size + max(__old_size, __n);
  741.       iterator __new_start = _M_allocate(__len);
  742.       iterator __new_finish = __new_start;
  743.       __STL_TRY {
  744.         __new_finish = uninitialized_copy(_M_start, __position, __new_start);
  745.         __new_finish = uninitialized_copy(__first, __last, __new_finish);
  746.         __new_finish
  747.           = uninitialized_copy(__position, _M_finish, __new_finish);
  748.       }
  749.       __STL_UNWIND((destroy(__new_start,__new_finish), 
  750.                     _M_deallocate(__new_start,__len)));
  751.       destroy(_M_start, _M_finish);
  752.       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
  753.       _M_start = __new_start;
  754.       _M_finish = __new_finish;
  755.       _M_end_of_storage = __new_start + __len;
  756.     }
  757.   }
  758. }
  759.  
  760. #else /* __STL_MEMBER_TEMPLATES */
  761.  
  762. template <class _Tp, class _Alloc>
  763. void 
  764. vector<_Tp, _Alloc>::insert(iterator __position, 
  765.                             const_iterator __first, 
  766.                             const_iterator __last)
  767. {
  768.   if (__first != __last) {
  769.     size_type __n = 0;
  770.     distance(__first, __last, __n);
  771.     if (size_type(_M_end_of_storage - _M_finish) >= __n) {
  772.       const size_type __elems_after = _M_finish - __position;
  773.       iterator __old_finish = _M_finish;
  774.       if (__elems_after > __n) {
  775.         uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
  776.         _M_finish += __n;
  777.         copy_backward(__position, __old_finish - __n, __old_finish);
  778.         copy(__first, __last, __position);
  779.       }
  780.       else {
  781.         uninitialized_copy(__first + __elems_after, __last, _M_finish);
  782.         _M_finish += __n - __elems_after;
  783.         uninitialized_copy(__position, __old_finish, _M_finish);
  784.         _M_finish += __elems_after;
  785.         copy(__first, __first + __elems_after, __position);
  786.       }
  787.     }
  788.     else {
  789.       const size_type __old_size = size();
  790.       const size_type __len = __old_size + max(__old_size, __n);
  791.       iterator __new_start = _M_allocate(__len);
  792.       iterator __new_finish = __new_start;
  793.       __STL_TRY {
  794.         __new_finish = uninitialized_copy(_M_start, __position, __new_start);
  795.         __new_finish = uninitialized_copy(__first, __last, __new_finish);
  796.         __new_finish
  797.           = uninitialized_copy(__position, _M_finish, __new_finish);
  798.       }
  799.       __STL_UNWIND((destroy(__new_start,__new_finish),
  800.                     _M_deallocate(__new_start,__len)));
  801.       destroy(_M_start, _M_finish);
  802.       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
  803.       _M_start = __new_start;
  804.       _M_finish = __new_finish;
  805.       _M_end_of_storage = __new_start + __len;
  806.     }
  807.   }
  808. }
  809.  
  810. #endif /* __STL_MEMBER_TEMPLATES */
  811.  
  812. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  813. #pragma reset woff 1174
  814. #pragma reset woff 1375
  815. #endif
  816.  
  817. __STL_END_NAMESPACE 
  818.  
  819. #endif /* __SGI_STL_INTERNAL_VECTOR_H */
  820.  
  821. // Local Variables:
  822. // mode:C++
  823. // End:
  824.