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