- Main Page
- Namespaces
- Classes
- Files
- Related Pages

# /Users/fpy/titan-1-5-MBARI/Mers/Executives/DeductiveController/Configs/TI_DSP_BIOS/stl/stl_vector.h

    00001 /*
    00002  *
    00003  * Copyright (c) 1994
    00004  * Hewlett-Packard Company
    00005  *
    00006  * Permission to use, copy, modify, distribute and sell this software
    00007  * and its documentation for any purpose is hereby granted without fee,
    00008  * provided that the above copyright notice appear in all copies and
    00009  * that both that copyright notice and this permission notice appear
    00010  * in supporting documentation.  Hewlett-Packard Company makes no
    00011  * representations about the suitability of this software for any
    00012  * purpose.  It is provided "as is" without express or implied warranty.
    00013  *
    00014  *
    00015  * Copyright (c) 1996
    00016  * Silicon Graphics Computer Systems, Inc.
    00017  *
    00018  * Permission to use, copy, modify, distribute and sell this software
    00019  * and its documentation for any purpose is hereby granted without fee,
    00020  * provided that the above copyright notice appear in all copies and
    00021  * that both that copyright notice and this permission notice appear
    00022  * in supporting documentation.  Silicon Graphics makes no
    00023  * representations about the suitability of this software for any
    00024  * purpose.  It is provided "as is" without express or implied warranty.
    00025  */
    00026
    00027 /* NOTE: This is an internal header file, included by other STL headers.
    00028  *   You should not attempt to use it directly.
    00029  */
    00030
    00031 #ifndef __SGI_STL_INTERNAL_VECTOR_H
    00032 #define __SGI_STL_INTERNAL_VECTOR_H
    00033
    00034 __STL_BEGIN_NAMESPACE
    00035
    00036 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    00037 #pragma set woff 1174
    00038 #pragma set woff 1375
    00039 #endif
    00040
    00041 // The vector base class serves two purposes.  First, its constructor
    00042 // and destructor allocate (but don't initialize) storage.  This makes
    00043 // exception safety easier.  Second, the base class encapsulates all of
    00044 // the differences between SGI-style allocators and standard-conforming
    00045 // allocators.
    00046
    00047 #ifdef __STL_USE_STD_ALLOCATORS
    00048
    00049 // Base class for ordinary allocators.
    00050 template <class _Tp, class _Allocator, bool _IsStatic>
    00051 class _Vector_alloc_base {
    00052 public:
    00053   typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
    00054           allocator_type;
    00055   allocator_type get_allocator() const { return _M_data_allocator; }
    00056
    00057   _Vector_alloc_base(const allocator_type& __a)
    00058     : _M_data_allocator(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
    00059   {}
    00060
    00061 protected:
    00062   allocator_type _M_data_allocator;
    00063   _Tp* _M_start;
    00064   _Tp* _M_finish;
    00065   _Tp* _M_end_of_storage;
    00066
    00067   _Tp* _M_allocate(size_t __n)
    00068     { return _M_data_allocator.allocate(__n); }
    00069   void _M_deallocate(_Tp* __p, size_t __n)
    00070     { if (__p) _M_data_allocator.deallocate(__p, __n); }
    00071 };
    00072
    00073 // Specialization for allocators that have the property that we don't
    00074 // actually have to store an allocator object.
    00075 template <class _Tp, class _Allocator>
    00076 class _Vector_alloc_base<_Tp, _Allocator, true> {
    00077 public:
    00078   typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
    00079           allocator_type;
    00080   allocator_type get_allocator() const { return allocator_type(); }
    00081
    00082   _Vector_alloc_base(const allocator_type&)
    00083     : _M_start(0), _M_finish(0), _M_end_of_storage(0)
    00084   {}
    00085
    00086 protected:
    00087   _Tp* _M_start;
    00088   _Tp* _M_finish;
    00089   _Tp* _M_end_of_storage;
    00090
    00091   typedef typename _Alloc_traits<_Tp, _Allocator>::_Alloc_type _Alloc_type;
    00092   _Tp* _M_allocate(size_t __n)
    00093     { return _Alloc_type::allocate(__n); }
    00094   void _M_deallocate(_Tp* __p, size_t __n)
    00095     { _Alloc_type::deallocate(__p, __n);}
    00096 };
    00097
    00098 template <class _Tp, class _Alloc>
    00099 struct _Vector_base
    00100   : public _Vector_alloc_base<_Tp, _Alloc,
    00101                               _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
    00102 {
    00103   typedef _Vector_alloc_base<_Tp, _Alloc,
    00104                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
    00105           _Base;
    00106   typedef typename _Base::allocator_type allocator_type;
    00107
    00108   _Vector_base(const allocator_type& __a) : _Base(__a) {}
    00109   _Vector_base(size_t __n, const allocator_type& __a) : _Base(__a) {
    00110     _M_start = _M_allocate(__n);
    00111     _M_finish = _M_start;
    00112     _M_end_of_storage = _M_start + __n;
    00113   }
    00114
    00115   ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
    00116 };
    00117
    00118 #else /* __STL_USE_STD_ALLOCATORS */
    00119
    00120 template <class _Tp, class _Alloc>
    00121 class _Vector_base {
    00122 public:
    00123   typedef _Alloc allocator_type;
    00124   allocator_type get_allocator() const { return allocator_type(); }
    00125
    00126   _Vector_base(const _Alloc&)
    00127     : _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
    00128   _Vector_base(size_t __n, const _Alloc&)
    00129     : _M_start(0), _M_finish(0), _M_end_of_storage(0)
    00130   {
    00131     _M_start = _M_allocate(__n);
    00132     _M_finish = _M_start;
    00133     _M_end_of_storage = _M_start + __n;
    00134   }
    00135
    00136   ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
    00137
    00138 protected:
    00139   _Tp* _M_start;
    00140   _Tp* _M_finish;
    00141   _Tp* _M_end_of_storage;
    00142
    00143   typedef simple_alloc<_Tp, _Alloc> _M_data_allocator;
    00144   _Tp* _M_allocate(size_t __n)
    00145     { return _M_data_allocator::allocate(__n); }
    00146   void _M_deallocate(_Tp* __p, size_t __n)
    00147     { _M_data_allocator::deallocate(__p, __n); }
    00148 };
    00149
    00150 #endif /* __STL_USE_STD_ALLOCATORS */
    00151
    00152 template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
    00153 class vector : protected _Vector_base<_Tp, _Alloc>
    00154 {
    00155 private:
    00156   typedef _Vector_base<_Tp, _Alloc> _Base;
    00157 public:
    00158   typedef _Tp value_type;
    00159   typedef value_type* pointer;
    00160   typedef const value_type* const_pointer;
    00161   typedef value_type* iterator;
    00162   typedef const value_type* const_iterator;
    00163   typedef value_type& reference;
    00164   typedef const value_type& const_reference;
    00165   typedef size_t size_type;
    00166   typedef ptrdiff_t difference_type;
    00167
    00168   typedef typename _Base::allocator_type allocator_type;
    00169   allocator_type get_allocator() const { return _Base::get_allocator(); }
    00170
    00171 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    00172   typedef reverse_iterator<const_iterator> const_reverse_iterator;
    00173   typedef reverse_iterator<iterator> reverse_iterator;
    00174 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    00175   typedef reverse_iterator<const_iterator, value_type, const_reference,
    00176                            difference_type>  const_reverse_iterator;
    00177   typedef reverse_iterator<iterator, value_type, reference, difference_type>
    00178           reverse_iterator;
    00179 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    00180
    00181 protected:
    00182 #ifdef __STL_HAS_NAMESPACES
    00183   using _Base::_M_allocate;
    00184   using _Base::_M_deallocate;
    00185   using _Base::_M_start;
    00186   using _Base::_M_finish;
    00187   using _Base::_M_end_of_storage;
    00188 #endif /* __STL_HAS_NAMESPACES */
    00189
    00190 protected:
    00191   void _M_insert_aux(iterator __position, const _Tp& __x);
    00192   void _M_insert_aux(iterator __position);
    00193
    00194 public:
    00195   iterator begin() { return _M_start; }
    00196   const_iterator begin() const { return _M_start; }
    00197   iterator end() { return _M_finish; }
    00198   const_iterator end() const { return _M_finish; }
    00199
    00200   reverse_iterator rbegin()
    00201     { return reverse_iterator(end()); }
    00202   const_reverse_iterator rbegin() const
    00203     { return const_reverse_iterator(end()); }
    00204   reverse_iterator rend()
    00205     { return reverse_iterator(begin()); }
    00206   const_reverse_iterator rend() const
    00207     { return const_reverse_iterator(begin()); }
    00208
    00209   size_type size() const
    00210     { return size_type(end() - begin()); }
    00211   size_type max_size() const
    00212     { return size_type(-1) / sizeof(_Tp); }
    00213   size_type capacity() const
    00214     { return size_type(_M_end_of_storage - begin()); }
    00215   bool empty() const
    00216     { return begin() == end(); }
    00217
    00218   reference operator[](size_type __n) { return *(begin() + __n); }
    00219   const_reference operator[](size_type __n) const { return *(begin() + __n); }
    00220
    00221   explicit vector(const allocator_type& __a = allocator_type())
    00222     : _Base(__a) {}
    00223
    00224   vector(size_type __n, const _Tp& __value,
    00225          const allocator_type& __a = allocator_type())
    00226     : _Base(__n, __a)
    00227     { _M_finish = uninitialized_fill_n(_M_start, __n, __value); }
    00228
    00229   explicit vector(size_type __n)
    00230     : _Base(__n, allocator_type())
    00231     { _M_finish = uninitialized_fill_n(_M_start, __n, _Tp()); }
    00232
    00233   vector(const vector<_Tp, _Alloc>& __x)
    00234     : _Base(__x.size(), __x.get_allocator())
    00235     { _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); }
    00236
    00237 #ifdef __STL_MEMBER_TEMPLATES
    00238   // Check whether it's an integral type.  If so, it's not an iterator.
    00239   template <class _InputIterator>
    00240   vector(_InputIterator __first, _InputIterator __last,
    00241          const allocator_type& __a = allocator_type()) : _Base(__a) {
    00242     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    00243     _M_initialize_aux(__first, __last, _Integral());
    00244   }
    00245
    00246   template <class _Integer>
    00247   void _M_initialize_aux(_Integer __n, _Integer __value, __true_type) {
    00248     _M_start = _M_allocate(__n);
    00249     _M_end_of_storage = _M_start + __n;
    00250     _M_finish = uninitialized_fill_n(_M_start, __n, __value);
    00251   }
    00252
    00253   template <class _InputIterator>
    00254   void _M_initialize_aux(_InputIterator __first, _InputIterator __last,
    00255                          __false_type) {
    00256     _M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first));
    00257   }
    00258
    00259 #else
    00260   vector(const _Tp* __first, const _Tp* __last,
    00261          const allocator_type& __a = allocator_type())
    00262     : _Base(__last - __first, __a)
    00263     { _M_finish = uninitialized_copy(__first, __last, _M_start); }
    00264 #endif /* __STL_MEMBER_TEMPLATES */
    00265
    00266   ~vector() { destroy(_M_start, _M_finish); }
    00267
    00268   vector<_Tp, _Alloc>& operator=(const vector<_Tp, _Alloc>& __x);
    00269   void reserve(size_type __n) {
    00270     if (capacity() < __n) {
    00271       const size_type __old_size = size();
    00272       iterator __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
    00273       destroy(_M_start, _M_finish);
    00274       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
    00275       _M_start = __tmp;
    00276       _M_finish = __tmp + __old_size;
    00277       _M_end_of_storage = _M_start + __n;
    00278     }
    00279   }
    00280
    00281   // assign(), a generalized assignment member function.  Two
    00282   // versions: one that takes a count, and one that takes a range.
    00283   // The range version is a member template, so we dispatch on whether
    00284   // or not the type is an integer.
    00285
    00286   void assign(size_type __n, const _Tp& __val);
    00287
    00288 #ifdef __STL_MEMBER_TEMPLATES
    00289
    00290   template <class _InputIterator>
    00291   void assign(_InputIterator __first, _InputIterator __last) {
    00292     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    00293     _M_assign_dispatch(__first, __last, _Integral());
    00294   }
    00295
    00296   template <class _Integer>
    00297   void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
    00298     { assign((size_type) __n, (_Tp) __val); }
    00299
    00300   template <class _InputIter>
    00301   void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
    00302     { _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first)); }
    00303
    00304   template <class _InputIterator>
    00305   void _M_assign_aux(_InputIterator __first, _InputIterator __last,
    00306                      input_iterator_tag);
    00307
    00308   template <class _ForwardIterator>
    00309   void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
    00310                      forward_iterator_tag);
    00311
    00312 #endif /* __STL_MEMBER_TEMPLATES */
    00313
    00314   reference front() { return *begin(); }
    00315   const_reference front() const { return *begin(); }
    00316   reference back() { return *(end() - 1); }
    00317   const_reference back() const { return *(end() - 1); }
    00318
    00319   void push_back(const _Tp& __x) {
    00320     if (_M_finish != _M_end_of_storage) {
    00321       construct(_M_finish, __x);
    00322       ++_M_finish;
    00323     }
    00324     else
    00325       _M_insert_aux(end(), __x);
    00326   }
    00327   void push_back() {
    00328     if (_M_finish != _M_end_of_storage) {
    00329       construct(_M_finish);
    00330       ++_M_finish;
    00331     }
    00332     else
    00333       _M_insert_aux(end());
    00334   }
    00335   void swap(vector<_Tp, _Alloc>& __x) {
    00336     __STD::swap(_M_start, __x._M_start);
    00337     __STD::swap(_M_finish, __x._M_finish);
    00338     __STD::swap(_M_end_of_storage, __x._M_end_of_storage);
    00339   }
    00340
    00341   iterator insert(iterator __position, const _Tp& __x) {
    00342     size_type __n = __position - begin();
    00343     if (_M_finish != _M_end_of_storage && __position == end()) {
    00344       construct(_M_finish, __x);
    00345       ++_M_finish;
    00346     }
    00347     else
    00348       _M_insert_aux(__position, __x);
    00349     return begin() + __n;
    00350   }
    00351   iterator insert(iterator __position) {
    00352     size_type __n = __position - begin();
    00353     if (_M_finish != _M_end_of_storage && __position == end()) {
    00354       construct(_M_finish);
    00355       ++_M_finish;
    00356     }
    00357     else
    00358       _M_insert_aux(__position);
    00359     return begin() + __n;
    00360   }
    00361 #ifdef __STL_MEMBER_TEMPLATES
    00362   // Check whether it's an integral type.  If so, it's not an iterator.
    00363   template <class _InputIterator>
    00364   void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
    00365     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    00366     _M_insert_dispatch(__pos, __first, __last, _Integral());
    00367   }
    00368
    00369   template <class _Integer>
    00370   void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
    00371                           __true_type) {
    00372     insert(__pos, (size_type) __n, (_Tp) __val);
    00373   }
    00374
    00375   template <class _InputIterator>
    00376   void _M_insert_dispatch(iterator __pos,
    00377                           _InputIterator __first, _InputIterator __last,
    00378                           __false_type) {
    00379     _M_range_insert(__pos, __first, __last, __ITERATOR_CATEGORY(__first));
    00380   }
    00381 #else /* __STL_MEMBER_TEMPLATES */
    00382   void insert(iterator __position,
    00383               const_iterator __first, const_iterator __last);
    00384 #endif /* __STL_MEMBER_TEMPLATES */
    00385
    00386   void insert (iterator __pos, size_type __n, const _Tp& __x);
    00387
    00388   void pop_back() {
    00389     --_M_finish;
    00390     destroy(_M_finish);
    00391   }
    00392   iterator erase(iterator __position) {
    00393     if (__position + 1 != end())
    00394       copy(__position + 1, _M_finish, __position);
    00395     --_M_finish;
    00396     destroy(_M_finish);
    00397     return __position;
    00398   }
    00399   iterator erase(iterator __first, iterator __last) {
    00400     iterator __i = copy(__last, _M_finish, __first);
    00401     destroy(__i, _M_finish);
    00402     _M_finish = _M_finish - (__last - __first);
    00403     return __first;
    00404   }
    00405
    00406   void resize(size_type __new_size, const _Tp& __x) {
    00407     if (__new_size < size())
    00408       erase(begin() + __new_size, end());
    00409     else
    00410       insert(end(), __new_size - size(), __x);
    00411   }
    00412   void resize(size_type __new_size) { resize(__new_size, _Tp()); }
    00413   void clear() { erase(begin(), end()); }
    00414
    00415 protected:
    00416
    00417 #ifdef __STL_MEMBER_TEMPLATES
    00418   template <class _ForwardIterator>
    00419   iterator _M_allocate_and_copy(size_type __n, _ForwardIterator __first,
    00420                                                _ForwardIterator __last)
    00421 {
    00422     iterator __result = _M_allocate(__n);
    00423     __STL_TRY {
    00424       uninitialized_copy(__first, __last, __result);
    00425       return __result;
    00426     }
    00427     __STL_UNWIND(_M_deallocate(__result, __n));
    00428   }
    00429 #else /* __STL_MEMBER_TEMPLATES */
    00430   iterator _M_allocate_and_copy(size_type __n, const_iterator __first,
    00431                                                const_iterator __last)
    00432   {
    00433     iterator __result = _M_allocate(__n);
    00434     __STL_TRY {
    00435       uninitialized_copy(__first, __last, __result);
    00436       return __result;
    00437     }
    00438     __STL_UNWIND(_M_deallocate(__result, __n));
    00439   }
    00440 #endif /* __STL_MEMBER_TEMPLATES */
    00441
    00442
    00443 #ifdef __STL_MEMBER_TEMPLATES
    00444   template <class _InputIterator>
    00445   void _M_range_initialize(_InputIterator __first,
    00446                            _InputIterator __last, input_iterator_tag)
    00447   {
    00448     for ( ; __first != __last; ++__first)
    00449       push_back(*__first);
    00450   }
    00451
    00452   // This function is only called by the constructor.
    00453   template <class _ForwardIterator>
    00454   void _M_range_initialize(_ForwardIterator __first,
    00455                            _ForwardIterator __last, forward_iterator_tag)
    00456   {
    00457     size_type __n = 0;
    00458     distance(__first, __last, __n);
    00459     _M_start = _M_allocate(__n);
    00460     _M_end_of_storage = _M_start + __n;
    00461     _M_finish = uninitialized_copy(__first, __last, _M_start);
    00462   }
    00463
    00464   template <class _InputIterator>
    00465   void _M_range_insert(iterator __pos,
    00466                        _InputIterator __first, _InputIterator __last,
    00467                        input_iterator_tag);
    00468
    00469   template <class _ForwardIterator>
    00470   void _M_range_insert(iterator __pos,
    00471                        _ForwardIterator __first, _ForwardIterator __last,
    00472                        forward_iterator_tag);
    00473
    00474 #endif /* __STL_MEMBER_TEMPLATES */
    00475 };
    00476
    00477 template <class _Tp, class _Alloc>
    00478 inline bool
    00479 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
    00480 {
    00481   return __x.size() == __y.size() &&
    00482          equal(__x.begin(), __x.end(), __y.begin());
    00483 }
    00484
    00485 template <class _Tp, class _Alloc>
    00486 inline bool
    00487 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
    00488 {
    00489   return lexicographical_compare(__x.begin(), __x.end(),
    00490                                  __y.begin(), __y.end());
    00491 }
    00492
    00493 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
    00494
    00495 template <class _Tp, class _Alloc>
    00496 inline void swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
    00497 {
    00498   __x.swap(__y);
    00499 }
    00500
    00501 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
    00502
    00503 template <class _Tp, class _Alloc>
    00504 vector<_Tp,_Alloc>&
    00505 vector<_Tp,_Alloc>::operator=(const vector<_Tp, _Alloc>& __x)
    00506 {
    00507   if (&__x != this) {
    00508     const size_type __xlen = __x.size();
    00509     if (__xlen > capacity()) {
    00510       iterator __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end());
    00511       destroy(_M_start, _M_finish);
    00512       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
    00513       _M_start = __tmp;
    00514       _M_end_of_storage = _M_start + __xlen;
    00515     }
    00516     else if (size() >= __xlen) {
    00517       iterator __i = copy(__x.begin(), __x.end(), begin());
    00518       destroy(__i, _M_finish);
    00519     }
    00520     else {
    00521       copy(__x.begin(), __x.begin() + size(), _M_start);
    00522       uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish);
    00523     }
    00524     _M_finish = _M_start + __xlen;
    00525   }
    00526   return *this;
    00527 }
    00528
    00529 template <class _Tp, class _Alloc>
    00530 void vector<_Tp, _Alloc>::assign(size_t __n, const value_type& __val) {
    00531   if (__n > capacity()) {
    00532     vector<_Tp, _Alloc> __tmp(__n, __val, get_allocator());
    00533     __tmp.swap(*this);
    00534   }
    00535   else if (__n > size()) {
    00536     fill(begin(), end(), __val);
    00537     _M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val);
    00538   }
    00539   else
    00540     erase(fill_n(begin(), __n, __val), end());
    00541 }
    00542
    00543 #ifdef __STL_MEMBER_TEMPLATES
    00544
    00545 template <class _Tp, class _Alloc> template <class _InputIter>
    00546 void vector<_Tp, _Alloc>::_M_assign_aux(_InputIter __first, _InputIter __last,
    00547                                         input_iterator_tag) {
    00548   iterator __cur = begin();
    00549   for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
    00550     *__cur = *__first;
    00551   if (__first == __last)
    00552     erase(__cur, end());
    00553   else
    00554     insert(end(), __first, __last);
    00555 }
    00556
    00557 template <class _Tp, class _Alloc> template <class _ForwardIter>
    00558 void
    00559 vector<_Tp, _Alloc>::_M_assign_aux(_ForwardIter __first, _ForwardIter __last,
    00560                                    forward_iterator_tag) {
    00561   size_type __len = 0;
    00562   distance(__first, __last, __len);
    00563
    00564   if (__len > capacity()) {
    00565     iterator __tmp = _M_allocate_and_copy(__len, __first, __last);
    00566     destroy(_M_start, _M_finish);
    00567     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
    00568     _M_start = __tmp;
    00569     _M_end_of_storage = _M_finish = _M_start + __len;
    00570   }
    00571   else if (size() >= __len) {
    00572     iterator __new_finish = copy(__first, __last, _M_start);
    00573     destroy(__new_finish, _M_finish);
    00574     _M_finish = __new_finish;
    00575   }
    00576   else {
    00577     _ForwardIter __mid = __first;
    00578     advance(__mid, size());
    00579     copy(__first, __mid, _M_start);
    00580     _M_finish = uninitialized_copy(__mid, __last, _M_finish);
    00581   }
    00582 }
    00583
    00584 #endif /* __STL_MEMBER_TEMPLATES */
    00585
    00586 template <class _Tp, class _Alloc>
    00587 void
    00588 vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
    00589 {
    00590   if (_M_finish != _M_end_of_storage) {
    00591     construct(_M_finish, *(_M_finish - 1));
    00592     ++_M_finish;
    00593     _Tp __x_copy = __x;
    00594     copy_backward(__position, _M_finish - 2, _M_finish - 1);
    00595     *__position = __x_copy;
    00596   }
    00597   else {
    00598     const size_type __old_size = size();
    00599     const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
    00600     iterator __new_start = _M_allocate(__len);
    00601     iterator __new_finish = __new_start;
    00602     __STL_TRY {
    00603       __new_finish = uninitialized_copy(_M_start, __position, __new_start);
    00604       construct(__new_finish, __x);
    00605       ++__new_finish;
    00606       __new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
    00607     }
    00608     __STL_UNWIND((destroy(__new_start,__new_finish),
    00609                   _M_deallocate(__new_start,__len)));
    00610     destroy(begin(), end());
    00611     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
    00612     _M_start = __new_start;
    00613     _M_finish = __new_finish;
    00614     _M_end_of_storage = __new_start + __len;
    00615   }
    00616 }
    00617
    00618 template <class _Tp, class _Alloc>
    00619 void
    00620 vector<_Tp, _Alloc>::_M_insert_aux(iterator __position)
    00621 {
    00622   if (_M_finish != _M_end_of_storage) {
    00623     construct(_M_finish, *(_M_finish - 1));
    00624     ++_M_finish;
    00625     copy_backward(__position, _M_finish - 2, _M_finish - 1);
    00626     *__position = _Tp();
    00627   }
    00628   else {
    00629     const size_type __old_size = size();
    00630     const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
    00631     iterator __new_start = _M_allocate(__len);
    00632     iterator __new_finish = __new_start;
    00633     __STL_TRY {
    00634       __new_finish = uninitialized_copy(_M_start, __position, __new_start);
    00635       construct(__new_finish);
    00636       ++__new_finish;
    00637       __new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
    00638     }
    00639     __STL_UNWIND((destroy(__new_start,__new_finish),
    00640                   _M_deallocate(__new_start,__len)));
    00641     destroy(begin(), end());
    00642     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
    00643     _M_start = __new_start;
    00644     _M_finish = __new_finish;
    00645     _M_end_of_storage = __new_start + __len;
    00646   }
    00647 }
    00648
    00649 template <class _Tp, class _Alloc>
    00650 void vector<_Tp, _Alloc>::insert(iterator __position, size_type __n,
    00651                                  const _Tp& __x)
    00652 {
    00653   if (__n != 0) {
    00654     if (size_type(_M_end_of_storage - _M_finish) >= __n) {
    00655       _Tp __x_copy = __x;
    00656       const size_type __elems_after = _M_finish - __position;
    00657       iterator __old_finish = _M_finish;
    00658       if (__elems_after > __n) {
    00659         uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
    00660         _M_finish += __n;
    00661         copy_backward(__position, __old_finish - __n, __old_finish);
    00662         fill(__position, __position + __n, __x_copy);
    00663       }
    00664       else {
    00665         uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
    00666         _M_finish += __n - __elems_after;
    00667         uninitialized_copy(__position, __old_finish, _M_finish);
    00668         _M_finish += __elems_after;
    00669         fill(__position, __old_finish, __x_copy);
    00670       }
    00671     }
    00672     else {
    00673       const size_type __old_size = size();
    00674       const size_type __len = __old_size + max(__old_size, __n);
    00675       iterator __new_start = _M_allocate(__len);
    00676       iterator __new_finish = __new_start;
    00677       __STL_TRY {
    00678         __new_finish = uninitialized_copy(_M_start, __position, __new_start);
    00679         __new_finish = uninitialized_fill_n(__new_finish, __n, __x);
    00680         __new_finish
    00681           = uninitialized_copy(__position, _M_finish, __new_finish);
    00682       }
    00683       __STL_UNWIND((destroy(__new_start,__new_finish),
    00684                     _M_deallocate(__new_start,__len)));
    00685       destroy(_M_start, _M_finish);
    00686       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
    00687       _M_start = __new_start;
    00688       _M_finish = __new_finish;
    00689       _M_end_of_storage = __new_start + __len;
    00690     }
    00691   }
    00692 }
    00693
    00694 #ifdef __STL_MEMBER_TEMPLATES
    00695
    00696 template <class _Tp, class _Alloc> template <class _InputIterator>
    00697 void
    00698 vector<_Tp, _Alloc>::_M_range_insert(iterator __pos,
    00699                                      _InputIterator __first,
    00700                                      _InputIterator __last,
    00701                                      input_iterator_tag)
    00702 {
    00703   for ( ; __first != __last; ++__first) {
    00704     __pos = insert(__pos, *__first);
    00705     ++__pos;
    00706   }
    00707 }
    00708
    00709 template <class _Tp, class _Alloc> template <class _ForwardIterator>
    00710 void
    00711 vector<_Tp, _Alloc>::_M_range_insert(iterator __position,
    00712                                      _ForwardIterator __first,
    00713                                      _ForwardIterator __last,
    00714                                      forward_iterator_tag)
    00715 {
    00716   if (__first != __last) {
    00717     size_type __n = 0;
    00718     distance(__first, __last, __n);
    00719     if (size_type(_M_end_of_storage - _M_finish) >= __n) {
    00720       const size_type __elems_after = _M_finish - __position;
    00721       iterator __old_finish = _M_finish;
    00722       if (__elems_after > __n) {
    00723         uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
    00724         _M_finish += __n;
    00725         copy_backward(__position, __old_finish - __n, __old_finish);
    00726         copy(__first, __last, __position);
    00727       }
    00728       else {
    00729         _ForwardIterator __mid = __first;
    00730         advance(__mid, __elems_after);
    00731         uninitialized_copy(__mid, __last, _M_finish);
    00732         _M_finish += __n - __elems_after;
    00733         uninitialized_copy(__position, __old_finish, _M_finish);
    00734         _M_finish += __elems_after;
    00735         copy(__first, __mid, __position);
    00736       }
    00737     }
    00738     else {
    00739       const size_type __old_size = size();
    00740       const size_type __len = __old_size + max(__old_size, __n);
    00741       iterator __new_start = _M_allocate(__len);
    00742       iterator __new_finish = __new_start;
    00743       __STL_TRY {
    00744         __new_finish = uninitialized_copy(_M_start, __position, __new_start);
    00745         __new_finish = uninitialized_copy(__first, __last, __new_finish);
    00746         __new_finish
    00747           = uninitialized_copy(__position, _M_finish, __new_finish);
    00748       }
    00749       __STL_UNWIND((destroy(__new_start,__new_finish),
    00750                     _M_deallocate(__new_start,__len)));
    00751       destroy(_M_start, _M_finish);
    00752       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
    00753       _M_start = __new_start;
    00754       _M_finish = __new_finish;
    00755       _M_end_of_storage = __new_start + __len;
    00756     }
    00757   }
    00758 }
    00759
    00760 #else /* __STL_MEMBER_TEMPLATES */
    00761
    00762 template <class _Tp, class _Alloc>
    00763 void
    00764 vector<_Tp, _Alloc>::insert(iterator __position,
    00765                             const_iterator __first,
    00766                             const_iterator __last)
    00767 {
    00768   if (__first != __last) {
    00769     size_type __n = 0;
    00770     distance(__first, __last, __n);
    00771     if (size_type(_M_end_of_storage - _M_finish) >= __n) {
    00772       const size_type __elems_after = _M_finish - __position;
    00773       iterator __old_finish = _M_finish;
    00774       if (__elems_after > __n) {
    00775         uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
    00776         _M_finish += __n;
    00777         copy_backward(__position, __old_finish - __n, __old_finish);
    00778         copy(__first, __last, __position);
    00779       }
    00780       else {
    00781         uninitialized_copy(__first + __elems_after, __last, _M_finish);
    00782         _M_finish += __n - __elems_after;
    00783         uninitialized_copy(__position, __old_finish, _M_finish);
    00784         _M_finish += __elems_after;
    00785         copy(__first, __first + __elems_after, __position);
    00786       }
    00787     }
    00788     else {
    00789       const size_type __old_size = size();
    00790       const size_type __len = __old_size + max(__old_size, __n);
    00791       iterator __new_start = _M_allocate(__len);
    00792       iterator __new_finish = __new_start;
    00793       __STL_TRY {
    00794         __new_finish = uninitialized_copy(_M_start, __position, __new_start);
    00795         __new_finish = uninitialized_copy(__first, __last, __new_finish);
    00796         __new_finish
    00797           = uninitialized_copy(__position, _M_finish, __new_finish);
    00798       }
    00799       __STL_UNWIND((destroy(__new_start,__new_finish),
    00800                     _M_deallocate(__new_start,__len)));
    00801       destroy(_M_start, _M_finish);
    00802       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
    00803       _M_start = __new_start;
    00804       _M_finish = __new_finish;
    00805       _M_end_of_storage = __new_start + __len;
    00806     }
    00807   }
    00808 }
    00809
    00810 #endif /* __STL_MEMBER_TEMPLATES */
    00811
    00812 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    00813 #pragma reset woff 1174
    00814 #pragma reset woff 1375
    00815 #endif
    00816
    00817 __STL_END_NAMESPACE
    00818
    00819 #endif /* __SGI_STL_INTERNAL_VECTOR_H */
    00820
    00821 // Local Variables:
    00822 // mode:C++
    00823 // End: