stl_vect.h
上传用户:nizebo
上传日期:2022-05-14
资源大小:882k
文件大小:28k
源码类别:

STL

开发平台:

Visual C++

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