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