libstdc++-v3/bits/stl_vector.h

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