libstdc++-v3/include/bits/stl_vector.h

   1 // Vector implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /*
  31  *
  32  * Copyright (c) 1994
  33  * Hewlett-Packard Company
  34  *
  35  * Permission to use, copy, modify, distribute and sell this software
  36  * and its documentation for any purpose is hereby granted without fee,
  37  * provided that the above copyright notice appear in all copies and
  38  * that both that copyright notice and this permission notice appear
  39  * in supporting documentation.  Hewlett-Packard Company makes no
  40  * representations about the suitability of this software for any
  41  * purpose.  It is provided "as is" without express or implied warranty.
  42  *
  43  *
  44  * Copyright (c) 1996
  45  * Silicon Graphics Computer Systems, Inc.
  46  *
  47  * Permission to use, copy, modify, distribute and sell this software
  48  * and its documentation for any purpose is hereby granted without fee,
  49  * provided that the above copyright notice appear in all copies and
  50  * that both that copyright notice and this permission notice appear
  51  * in supporting documentation.  Silicon Graphics makes no
  52  * representations about the suitability of this  software for any
  53  * purpose.  It is provided "as is" without express or implied warranty.
  54  */
  55
  56 /* NOTE: This is an internal header file, included by other STL headers.
  57  *   You should not attempt to use it directly.
  58  */
  59
  60 #ifndef __SGI_STL_INTERNAL_VECTOR_H
  61 #define __SGI_STL_INTERNAL_VECTOR_H
  62
  63 #include <bits/stl_iterator_base_funcs.h>
  64 #include <bits/functexcept.h>
  65 #include <bits/concept_check.h>
  66
  67 namespace std
  68 {
  69
  70 // The vector base class serves two purposes.  First, its constructor
  71 // and destructor allocate (but don't initialize) storage.  This makes
  72 // exception safety easier.  Second, the base class encapsulates all of
  73 // the differences between SGI-style allocators and standard-conforming
  74 // allocators.
  75
  76 // Base class for ordinary allocators.
  77 template <class _Tp, class _Allocator, bool _IsStatic>
  78 class _Vector_alloc_base {
  79 public:
  80   typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
  81           allocator_type;
  82   allocator_type get_allocator() const { return _M_data_allocator; }
  83
  84   _Vector_alloc_base(const allocator_type& __a)
  85     : _M_data_allocator(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
  86   {}
  87
  88 protected:
  89   allocator_type _M_data_allocator;
  90   _Tp* _M_start;
  91   _Tp* _M_finish;
  92   _Tp* _M_end_of_storage;
  93
  94   _Tp* _M_allocate(size_t __n)
  95     { return _M_data_allocator.allocate(__n); }
  96   void _M_deallocate(_Tp* __p, size_t __n)
  97     { if (__p) _M_data_allocator.deallocate(__p, __n); }
  98 };
  99
 100 // Specialization for allocators that have the property that we don't
 101 // actually have to store an allocator object.
 102 template <class _Tp, class _Allocator>
 103 class _Vector_alloc_base<_Tp, _Allocator, true> {
 104 public:
 105   typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
 106           allocator_type;
 107   allocator_type get_allocator() const { return allocator_type(); }
 108
 109   _Vector_alloc_base(const allocator_type&)
 110     : _M_start(0), _M_finish(0), _M_end_of_storage(0)
 111   {}
 112
 113 protected:
 114   _Tp* _M_start;
 115   _Tp* _M_finish;
 116   _Tp* _M_end_of_storage;
 117
 118   typedef typename _Alloc_traits<_Tp, _Allocator>::_Alloc_type _Alloc_type;
 119   _Tp* _M_allocate(size_t __n)
 120     { return _Alloc_type::allocate(__n); }
 121   void _M_deallocate(_Tp* __p, size_t __n)
 122     { _Alloc_type::deallocate(__p, __n);}
 123 };
 124
 125 template <class _Tp, class _Alloc>
 126 struct _Vector_base
 127   : public _Vector_alloc_base<_Tp, _Alloc,
 128                               _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
 129 {
 130   typedef _Vector_alloc_base<_Tp, _Alloc,
 131                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
 132           _Base;
 133   typedef typename _Base::allocator_type allocator_type;
 134
 135   _Vector_base(const allocator_type& __a) : _Base(__a) {}
 136   _Vector_base(size_t __n, const allocator_type& __a) : _Base(__a) {
 137     _M_start = _M_allocate(__n);
 138     _M_finish = _M_start;
 139     _M_end_of_storage = _M_start + __n;
 140   }
 141
 142   ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
 143 };
 144
 145
 146 template <class _Tp, class _Alloc = allocator<_Tp> >
 147 class vector : protected _Vector_base<_Tp, _Alloc>
 148 {
 149   // concept requirements
 150   __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
 151
 152 private:
 153   typedef _Vector_base<_Tp, _Alloc> _Base;
 154   typedef vector<_Tp, _Alloc> vector_type;
 155 public:
 156   typedef _Tp value_type;
 157   typedef value_type* pointer;
 158   typedef const value_type* const_pointer;
 159   typedef __normal_iterator<pointer, vector_type> iterator;
 160   typedef __normal_iterator<const_pointer, vector_type> const_iterator;
 161   typedef value_type& reference;
 162   typedef const value_type& const_reference;
 163   typedef size_t size_type;
 164   typedef ptrdiff_t difference_type;
 165
 166   typedef typename _Base::allocator_type allocator_type;
 167   allocator_type get_allocator() const { return _Base::get_allocator(); }
 168
 169   typedef reverse_iterator<const_iterator> const_reverse_iterator;
 170   typedef reverse_iterator<iterator> reverse_iterator;
 171
 172 protected:
 173   using _Base::_M_allocate;
 174   using _Base::_M_deallocate;
 175   using _Base::_M_start;
 176   using _Base::_M_finish;
 177   using _Base::_M_end_of_storage;
 178
 179 protected:
 180   void _M_insert_aux(iterator __position, const _Tp& __x);
 181   void _M_insert_aux(iterator __position);
 182
 183 public:
 184   iterator begin() { return iterator (_M_start); }
 185   const_iterator begin() const
 186     { return const_iterator (_M_start); }
 187   iterator end() { return iterator (_M_finish); }
 188   const_iterator end() const { return const_iterator (_M_finish); }
 189
 190   reverse_iterator rbegin()
 191     { return reverse_iterator(end()); }
 192   const_reverse_iterator rbegin() const
 193     { return const_reverse_iterator(end()); }
 194   reverse_iterator rend()
 195     { return reverse_iterator(begin()); }
 196   const_reverse_iterator rend() const
 197     { return const_reverse_iterator(begin()); }
 198
 199   size_type size() const
 200     { return size_type(end() - begin()); }
 201   size_type max_size() const
 202     { return size_type(-1) / sizeof(_Tp); }
 203   size_type capacity() const
 204     { return size_type(const_iterator(_M_end_of_storage) - begin()); }
 205   bool empty() const
 206     { return begin() == end(); }
 207
 208   reference operator[](size_type __n) { return *(begin() + __n); }
 209   const_reference operator[](size_type __n) const { return *(begin() + __n); }
 210
 211   void _M_range_check(size_type __n) const {
 212     if (__n >= this->size())
 213       __throw_out_of_range("vector");
 214   }
 215
 216   reference at(size_type __n)
 217     { _M_range_check(__n); return (*this)[__n]; }
 218   const_reference at(size_type __n) const
 219     { _M_range_check(__n); return (*this)[__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   // Check whether it's an integral type.  If so, it's not an iterator.
 238   template <class _InputIterator>
 239     vector(_InputIterator __first, _InputIterator __last,
 240            const allocator_type& __a = allocator_type())
 241         : _Base(__a)
 242         {
 243       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 244       _M_initialize_aux(__first, __last, _Integral());
 245     }
 246
 247   template <class _Integer>
 248     void _M_initialize_aux(_Integer __n, _Integer __value, __true_type)
 249         {
 250       _M_start = _M_allocate(__n);
 251       _M_end_of_storage = _M_start + __n;
 252       _M_finish = uninitialized_fill_n(_M_start, __n, __value);
 253     }
 254
 255   template<class _InputIterator>
 256     void
 257         _M_initialize_aux(_InputIterator __first, _InputIterator __last, __false_type)
 258         {
 259           typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory;
 260           _M_range_initialize(__first, __last, _IterCategory());
 261         }
 262
 263   ~vector()
 264   { _Destroy(_M_start, _M_finish); }
 265
 266   vector<_Tp, _Alloc>& operator=(const vector<_Tp, _Alloc>& __x);
 267   void reserve(size_type __n) {
 268     if (capacity() < __n) {
 269       const size_type __old_size = size();
 270       pointer __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
 271       _Destroy(_M_start, _M_finish);
 272       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 273       _M_start = __tmp;
 274       _M_finish = __tmp + __old_size;
 275       _M_end_of_storage = _M_start + __n;
 276     }
 277   }
 278
 279   // assign(), a generalized assignment member function.  Two
 280   // versions: one that takes a count, and one that takes a range.
 281   // The range version is a member template, so we dispatch on whether
 282   // or not the type is an integer.
 283
 284   void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }
 285   void _M_fill_assign(size_type __n, const _Tp& __val);
 286
 287   template<class _InputIterator>
 288     void
 289         assign(_InputIterator __first, _InputIterator __last)
 290         {
 291       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 292       _M_assign_dispatch(__first, __last, _Integral());
 293     }
 294
 295   template<class _Integer>
 296     void
 297         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
 298     { _M_fill_assign((size_type) __n, (_Tp) __val); }
 299
 300   template<class _InputIter>
 301     void
 302         _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
 303     {
 304           typedef typename iterator_traits<_InputIter>::iterator_category _IterCategory;
 305           _M_assign_aux(__first, __last, _IterCategory());
 306         }
 307
 308   template <class _InputIterator>
 309   void _M_assign_aux(_InputIterator __first, _InputIterator __last,
 310                      input_iterator_tag);
 311
 312   template <class _ForwardIterator>
 313   void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
 314                      forward_iterator_tag);
 315
 316   reference front() { return *begin(); }
 317   const_reference front() const { return *begin(); }
 318   reference back() { return *(end() - 1); }
 319   const_reference back() const { return *(end() - 1); }
 320
 321   void
 322   push_back(const _Tp& __x)
 323   {
 324     if (_M_finish != _M_end_of_storage) {
 325       _Construct(_M_finish, __x);
 326       ++_M_finish;
 327     }
 328     else
 329       _M_insert_aux(end(), __x);
 330   }
 331
 332   void
 333   push_back()
 334   {
 335     if (_M_finish != _M_end_of_storage) {
 336       _Construct(_M_finish);
 337       ++_M_finish;
 338     }
 339     else
 340       _M_insert_aux(end());
 341   }
 342
 343   void
 344   swap(vector<_Tp, _Alloc>& __x)
 345   {
 346     std::swap(_M_start, __x._M_start);
 347     std::swap(_M_finish, __x._M_finish);
 348     std::swap(_M_end_of_storage, __x._M_end_of_storage);
 349   }
 350
 351   iterator
 352   insert(iterator __position, const _Tp& __x)
 353   {
 354     size_type __n = __position - begin();
 355     if (_M_finish != _M_end_of_storage && __position == end()) {
 356       _Construct(_M_finish, __x);
 357       ++_M_finish;
 358     }
 359     else
 360       _M_insert_aux(iterator(__position), __x);
 361     return begin() + __n;
 362   }
 363
 364   iterator
 365   insert(iterator __position)
 366   {
 367     size_type __n = __position - begin();
 368     if (_M_finish != _M_end_of_storage && __position == end()) {
 369       _Construct(_M_finish);
 370       ++_M_finish;
 371     }
 372     else
 373       _M_insert_aux(iterator(__position));
 374     return begin() + __n;
 375   }
 376
 377   // Check whether it's an integral type.  If so, it's not an iterator.
 378   template<class _InputIterator>
 379     void
 380         insert(iterator __pos, _InputIterator __first, _InputIterator __last)
 381         {
 382       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 383       _M_insert_dispatch(__pos, __first, __last, _Integral());
 384     }
 385
 386   template <class _Integer>
 387     void
 388         _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, __true_type)
 389     { _M_fill_insert(__pos, static_cast<size_type>(__n), static_cast<_Tp>(__val)); }
 390
 391   template<class _InputIterator>
 392     void
 393         _M_insert_dispatch(iterator __pos,
 394                        _InputIterator __first, _InputIterator __last,
 395                        __false_type)
 396         {
 397           typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory;
 398       _M_range_insert(__pos, __first, __last, _IterCategory());
 399     }
 400
 401   void insert (iterator __pos, size_type __n, const _Tp& __x)
 402     { _M_fill_insert(__pos, __n, __x); }
 403
 404   void _M_fill_insert (iterator __pos, size_type __n, const _Tp& __x);
 405
 406   void pop_back() {
 407     --_M_finish;
 408     _Destroy(_M_finish);
 409   }
 410   iterator erase(iterator __position) {
 411     if (__position + 1 != end())
 412       copy(__position + 1, end(), __position);
 413     --_M_finish;
 414     _Destroy(_M_finish);
 415     return __position;
 416   }
 417   iterator erase(iterator __first, iterator __last) {
 418     iterator __i(copy(__last, end(), __first));
 419     _Destroy(__i, end());
 420     _M_finish = _M_finish - (__last - __first);
 421     return __first;
 422   }
 423
 424   void resize(size_type __new_size, const _Tp& __x) {
 425     if (__new_size < size())
 426       erase(begin() + __new_size, end());
 427     else
 428       insert(end(), __new_size - size(), __x);
 429   }
 430   void resize(size_type __new_size) { resize(__new_size, _Tp()); }
 431   void clear() { erase(begin(), end()); }
 432
 433 protected:
 434
 435   template <class _ForwardIterator>
 436   pointer _M_allocate_and_copy(size_type __n, _ForwardIterator __first,
 437                                                _ForwardIterator __last)
 438   {
 439     pointer __result = _M_allocate(__n);
 440     try {
 441       uninitialized_copy(__first, __last, __result);
 442       return __result;
 443     }
 444     catch(...)
 445       {
 446         _M_deallocate(__result, __n);
 447         __throw_exception_again;
 448       }
 449   }
 450
 451   template <class _InputIterator>
 452   void _M_range_initialize(_InputIterator __first,
 453                            _InputIterator __last, input_iterator_tag)
 454   {
 455     for ( ; __first != __last; ++__first)
 456       push_back(*__first);
 457   }
 458
 459   // This function is only called by the constructor.
 460   template <class _ForwardIterator>
 461   void _M_range_initialize(_ForwardIterator __first,
 462                            _ForwardIterator __last, forward_iterator_tag)
 463   {
 464     size_type __n = 0;
 465     distance(__first, __last, __n);
 466     _M_start = _M_allocate(__n);
 467     _M_end_of_storage = _M_start + __n;
 468     _M_finish = uninitialized_copy(__first, __last, _M_start);
 469   }
 470
 471   template <class _InputIterator>
 472   void _M_range_insert(iterator __pos,
 473                        _InputIterator __first, _InputIterator __last,
 474                        input_iterator_tag);
 475
 476   template <class _ForwardIterator>
 477   void _M_range_insert(iterator __pos,
 478                        _ForwardIterator __first, _ForwardIterator __last,
 479                        forward_iterator_tag);
 480 };
 481
 482 template <class _Tp, class _Alloc>
 483 inline bool
 484 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
 485 {
 486   return __x.size() == __y.size() &&
 487          equal(__x.begin(), __x.end(), __y.begin());
 488 }
 489
 490 template <class _Tp, class _Alloc>
 491 inline bool
 492 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
 493 {
 494   return lexicographical_compare(__x.begin(), __x.end(),
 495                                  __y.begin(), __y.end());
 496 }
 497
 498 template <class _Tp, class _Alloc>
 499 inline void swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
 500 {
 501   __x.swap(__y);
 502 }
 503
 504 template <class _Tp, class _Alloc>
 505 inline bool
 506 operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
 507   return !(__x == __y);
 508 }
 509
 510 template <class _Tp, class _Alloc>
 511 inline bool
 512 operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
 513   return __y < __x;
 514 }
 515
 516 template <class _Tp, class _Alloc>
 517 inline bool
 518 operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
 519   return !(__y < __x);
 520 }
 521
 522 template <class _Tp, class _Alloc>
 523 inline bool
 524 operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
 525   return !(__x < __y);
 526 }
 527
 528 template <class _Tp, class _Alloc>
 529 vector<_Tp,_Alloc>&
 530 vector<_Tp,_Alloc>::operator=(const vector<_Tp, _Alloc>& __x)
 531 {
 532   if (&__x != this) {
 533     const size_type __xlen = __x.size();
 534     if (__xlen > capacity()) {
 535       pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end());
 536       _Destroy(_M_start, _M_finish);
 537       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 538       _M_start = __tmp;
 539       _M_end_of_storage = _M_start + __xlen;
 540     }
 541     else if (size() >= __xlen) {
 542       iterator __i(copy(__x.begin(), __x.end(), begin()));
 543       _Destroy(__i, end());
 544     }
 545     else {
 546       copy(__x.begin(), __x.begin() + size(), _M_start);
 547       uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish);
 548     }
 549     _M_finish = _M_start + __xlen;
 550   }
 551   return *this;
 552 }
 553
 554 template <class _Tp, class _Alloc>
 555 void vector<_Tp, _Alloc>::_M_fill_assign(size_t __n, const value_type& __val)
 556 {
 557   if (__n > capacity()) {
 558     vector<_Tp, _Alloc> __tmp(__n, __val, get_allocator());
 559     __tmp.swap(*this);
 560   }
 561   else if (__n > size()) {
 562     fill(begin(), end(), __val);
 563     _M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val);
 564   }
 565   else
 566     erase(fill_n(begin(), __n, __val), end());
 567 }
 568
 569 template <class _Tp, class _Alloc> template <class _InputIter>
 570 void vector<_Tp, _Alloc>::_M_assign_aux(_InputIter __first, _InputIter __last,
 571                                         input_iterator_tag) {
 572   iterator __cur(begin());
 573   for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
 574     *__cur = *__first;
 575   if (__first == __last)
 576     erase(__cur, end());
 577   else
 578     insert(end(), __first, __last);
 579 }
 580
 581 template <class _Tp, class _Alloc> template <class _ForwardIter>
 582 void
 583 vector<_Tp, _Alloc>::_M_assign_aux(_ForwardIter __first, _ForwardIter __last,
 584                                    forward_iterator_tag) {
 585   size_type __len = 0;
 586   distance(__first, __last, __len);
 587
 588   if (__len > capacity()) {
 589     pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
 590     _Destroy(_M_start, _M_finish);
 591     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 592     _M_start = __tmp;
 593     _M_end_of_storage = _M_finish = _M_start + __len;
 594   }
 595   else if (size() >= __len) {
 596     iterator __new_finish(copy(__first, __last, _M_start));
 597     _Destroy(__new_finish, end());
 598     _M_finish = __new_finish.base();
 599   }
 600   else {
 601     _ForwardIter __mid = __first;
 602     advance(__mid, size());
 603     copy(__first, __mid, _M_start);
 604     _M_finish = uninitialized_copy(__mid, __last, _M_finish);
 605   }
 606 }
 607
 608 template <class _Tp, class _Alloc>
 609 void
 610 vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
 611 {
 612   if (_M_finish != _M_end_of_storage) {
 613     _Construct(_M_finish, *(_M_finish - 1));
 614     ++_M_finish;
 615     _Tp __x_copy = __x;
 616     copy_backward(__position, iterator(_M_finish - 2), iterator(_M_finish- 1));
 617     *__position = __x_copy;
 618   }
 619   else {
 620     const size_type __old_size = size();
 621     const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
 622     iterator __new_start(_M_allocate(__len));
 623     iterator __new_finish(__new_start);
 624     try {
 625       __new_finish = uninitialized_copy(iterator(_M_start), __position,
 626                                         __new_start);
 627       _Construct(__new_finish.base(), __x);
 628       ++__new_finish;
 629       __new_finish = uninitialized_copy(__position, iterator(_M_finish),
 630                                         __new_finish);
 631     }
 632     catch(...)
 633       {
 634         _Destroy(__new_start,__new_finish);
 635         _M_deallocate(__new_start.base(),__len);
 636         __throw_exception_again;
 637       }
 638     _Destroy(begin(), end());
 639     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 640     _M_start = __new_start.base();
 641     _M_finish = __new_finish.base();
 642     _M_end_of_storage = __new_start.base() + __len;
 643   }
 644 }
 645
 646 template <class _Tp, class _Alloc>
 647 void
 648 vector<_Tp, _Alloc>::_M_insert_aux(iterator __position)
 649 {
 650   if (_M_finish != _M_end_of_storage) {
 651     _Construct(_M_finish, *(_M_finish - 1));
 652     ++_M_finish;
 653     copy_backward(__position, iterator(_M_finish - 2),
 654                   iterator(_M_finish - 1));
 655     *__position = _Tp();
 656   }
 657   else {
 658     const size_type __old_size = size();
 659     const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
 660     pointer __new_start = _M_allocate(__len);
 661     pointer __new_finish = __new_start;
 662     try {
 663       __new_finish = uninitialized_copy(iterator(_M_start), __position,
 664                                         __new_start);
 665       _Construct(__new_finish);
 666       ++__new_finish;
 667       __new_finish = uninitialized_copy(__position, iterator(_M_finish),
 668                                         __new_finish);
 669     }
 670     catch(...)
 671       {
 672         _Destroy(__new_start,__new_finish);
 673         _M_deallocate(__new_start,__len);
 674         __throw_exception_again;
 675       }
 676     _Destroy(begin(), end());
 677     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 678     _M_start = __new_start;
 679     _M_finish = __new_finish;
 680     _M_end_of_storage = __new_start + __len;
 681   }
 682 }
 683
 684 template <class _Tp, class _Alloc>
 685 void vector<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n,
 686                                          const _Tp& __x)
 687 {
 688   if (__n != 0) {
 689     if (size_type(_M_end_of_storage - _M_finish) >= __n) {
 690       _Tp __x_copy = __x;
 691       const size_type __elems_after = end() - __position;
 692       iterator __old_finish(_M_finish);
 693       if (__elems_after > __n) {
 694         uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
 695         _M_finish += __n;
 696         copy_backward(__position, __old_finish - __n, __old_finish);
 697         fill(__position, __position + __n, __x_copy);
 698       }
 699       else {
 700         uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
 701         _M_finish += __n - __elems_after;
 702         uninitialized_copy(__position, __old_finish, _M_finish);
 703         _M_finish += __elems_after;
 704         fill(__position, __old_finish, __x_copy);
 705       }
 706     }
 707     else {
 708       const size_type __old_size = size();
 709       const size_type __len = __old_size + max(__old_size, __n);
 710       iterator __new_start(_M_allocate(__len));
 711       iterator __new_finish(__new_start);
 712       try {
 713         __new_finish = uninitialized_copy(begin(), __position, __new_start);
 714         __new_finish = uninitialized_fill_n(__new_finish, __n, __x);
 715         __new_finish
 716           = uninitialized_copy(__position, end(), __new_finish);
 717       }
 718       catch(...)
 719         {
 720           _Destroy(__new_start,__new_finish);
 721           _M_deallocate(__new_start.base(),__len);
 722           __throw_exception_again;
 723         }
 724       _Destroy(_M_start, _M_finish);
 725       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 726       _M_start = __new_start.base();
 727       _M_finish = __new_finish.base();
 728       _M_end_of_storage = __new_start.base() + __len;
 729     }
 730   }
 731 }
 732
 733 template <class _Tp, class _Alloc> template <class _InputIterator>
 734 void
 735 vector<_Tp, _Alloc>::_M_range_insert(iterator __pos,
 736                                      _InputIterator __first,
 737                                      _InputIterator __last,
 738                                      input_iterator_tag)
 739 {
 740   for ( ; __first != __last; ++__first) {
 741     __pos = insert(__pos, *__first);
 742     ++__pos;
 743   }
 744 }
 745
 746 template <class _Tp, class _Alloc> template <class _ForwardIterator>
 747 void
 748 vector<_Tp, _Alloc>::_M_range_insert(iterator __position,
 749                                      _ForwardIterator __first,
 750                                      _ForwardIterator __last,
 751                                      forward_iterator_tag)
 752 {
 753   if (__first != __last) {
 754     size_type __n = 0;
 755     distance(__first, __last, __n);
 756     if (size_type(_M_end_of_storage - _M_finish) >= __n) {
 757       const size_type __elems_after = end() - __position;
 758       iterator __old_finish(_M_finish);
 759       if (__elems_after > __n) {
 760         uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
 761         _M_finish += __n;
 762         copy_backward(__position, __old_finish - __n, __old_finish);
 763         copy(__first, __last, __position);
 764       }
 765       else {
 766         _ForwardIterator __mid = __first;
 767         advance(__mid, __elems_after);
 768         uninitialized_copy(__mid, __last, _M_finish);
 769         _M_finish += __n - __elems_after;
 770         uninitialized_copy(__position, __old_finish, _M_finish);
 771         _M_finish += __elems_after;
 772         copy(__first, __mid, __position);
 773       }
 774     }
 775     else {
 776       const size_type __old_size = size();
 777       const size_type __len = __old_size + max(__old_size, __n);
 778       iterator __new_start(_M_allocate(__len));
 779       iterator __new_finish(__new_start);
 780       try {
 781         __new_finish = uninitialized_copy(iterator(_M_start),
 782                                           __position, __new_start);
 783         __new_finish = uninitialized_copy(__first, __last, __new_finish);
 784         __new_finish
 785           = uninitialized_copy(__position, iterator(_M_finish), __new_finish);
 786       }
 787       catch(...)
 788         {
 789           _Destroy(__new_start,__new_finish);
 790           _M_deallocate(__new_start.base(), __len);
 791           __throw_exception_again;
 792         }
 793       _Destroy(_M_start, _M_finish);
 794       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 795       _M_start = __new_start.base();
 796       _M_finish = __new_finish.base();
 797       _M_end_of_storage = __new_start.base() + __len;
 798     }
 799   }
 800 }
 801
 802 } // namespace std
 803
 804 #endif /* __SGI_STL_INTERNAL_VECTOR_H */
 805
 806 // Local Variables:
 807 // mode:C++
 808 // End: