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 /** @file stl_vector.h
  57  *  This is an internal header file, included by other library headers.
  58  *  You should not attempt to use it directly.
  59  */
  60
  61 #ifndef __GLIBCPP_INTERNAL_VECTOR_H
  62 #define __GLIBCPP_INTERNAL_VECTOR_H
  63
  64 #include <bits/stl_iterator_base_funcs.h>
  65 #include <bits/functexcept.h>
  66 #include <bits/concept_check.h>
  67
  68 namespace std
  69 {
  70
  71 // The vector base class serves two purposes.  First, its constructor
  72 // and destructor allocate (but don't initialize) storage.  This makes
  73 // exception safety easier.  Second, the base class encapsulates all of
  74 // the differences between SGI-style allocators and standard-conforming
  75 // allocators.
  76
  77 // Base class for ordinary allocators.
  78 template <class _Tp, class _Allocator, bool _IsStatic>
  79 class _Vector_alloc_base {
  80 public:
  81   typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
  82           allocator_type;
  83   allocator_type get_allocator() const { return _M_data_allocator; }
  84
  85   _Vector_alloc_base(const allocator_type& __a)
  86     : _M_data_allocator(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
  87   {}
  88
  89 protected:
  90   allocator_type _M_data_allocator;
  91   _Tp* _M_start;
  92   _Tp* _M_finish;
  93   _Tp* _M_end_of_storage;
  94
  95   _Tp* _M_allocate(size_t __n)
  96     { return _M_data_allocator.allocate(__n); }
  97   void _M_deallocate(_Tp* __p, size_t __n)
  98     { if (__p) _M_data_allocator.deallocate(__p, __n); }
  99 };
 100
 101 // Specialization for allocators that have the property that we don't
 102 // actually have to store an allocator object.
 103 template <class _Tp, class _Allocator>
 104 class _Vector_alloc_base<_Tp, _Allocator, true> {
 105 public:
 106   typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
 107           allocator_type;
 108   allocator_type get_allocator() const { return allocator_type(); }
 109
 110   _Vector_alloc_base(const allocator_type&)
 111     : _M_start(0), _M_finish(0), _M_end_of_storage(0)
 112   {}
 113
 114 protected:
 115   _Tp* _M_start;
 116   _Tp* _M_finish;
 117   _Tp* _M_end_of_storage;
 118
 119   typedef typename _Alloc_traits<_Tp, _Allocator>::_Alloc_type _Alloc_type;
 120   _Tp* _M_allocate(size_t __n)
 121     { return _Alloc_type::allocate(__n); }
 122   void _M_deallocate(_Tp* __p, size_t __n)
 123     { _Alloc_type::deallocate(__p, __n);}
 124 };
 125
 126 template <class _Tp, class _Alloc>
 127 struct _Vector_base
 128   : public _Vector_alloc_base<_Tp, _Alloc,
 129                               _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
 130 {
 131   typedef _Vector_alloc_base<_Tp, _Alloc,
 132                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
 133           _Base;
 134   typedef typename _Base::allocator_type allocator_type;
 135
 136   _Vector_base(const allocator_type& __a) : _Base(__a) {}
 137   _Vector_base(size_t __n, const allocator_type& __a) : _Base(__a) {
 138     _M_start = _M_allocate(__n);
 139     _M_finish = _M_start;
 140     _M_end_of_storage = _M_start + __n;
 141   }
 142
 143   ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
 144 };
 145
 146
 147 template <class _Tp, class _Alloc = allocator<_Tp> >
 148 class vector : protected _Vector_base<_Tp, _Alloc>
 149 {
 150   // concept requirements
 151   __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
 152
 153 private:
 154   typedef _Vector_base<_Tp, _Alloc> _Base;
 155   typedef vector<_Tp, _Alloc> vector_type;
 156 public:
 157   typedef _Tp                                           value_type;
 158   typedef value_type*                                   pointer;
 159   typedef const value_type*                             const_pointer;
 160   typedef __normal_iterator<pointer, vector_type>       iterator;
 161   typedef __normal_iterator<const_pointer, vector_type> const_iterator;
 162   typedef value_type&                                   reference;
 163   typedef const value_type&                             const_reference;
 164   typedef size_t                                        size_type;
 165   typedef ptrdiff_t                                     difference_type;
 166
 167   typedef typename _Base::allocator_type allocator_type;
 168   allocator_type get_allocator() const { return _Base::get_allocator(); }
 169
 170   typedef reverse_iterator<const_iterator> const_reverse_iterator;
 171   typedef reverse_iterator<iterator> reverse_iterator;
 172
 173 protected:
 174   using _Base::_M_allocate;
 175   using _Base::_M_deallocate;
 176   using _Base::_M_start;
 177   using _Base::_M_finish;
 178   using _Base::_M_end_of_storage;
 179
 180 protected:
 181   void _M_insert_aux(iterator __position, const _Tp& __x);
 182   void _M_insert_aux(iterator __position);
 183
 184 public:
 185   iterator begin() { return iterator (_M_start); }
 186   const_iterator begin() const
 187     { return const_iterator (_M_start); }
 188   iterator end() { return iterator (_M_finish); }
 189   const_iterator end() const { return const_iterator (_M_finish); }
 190
 191   reverse_iterator rbegin()
 192     { return reverse_iterator(end()); }
 193   const_reverse_iterator rbegin() const
 194     { return const_reverse_iterator(end()); }
 195   reverse_iterator rend()
 196     { return reverse_iterator(begin()); }
 197   const_reverse_iterator rend() const
 198     { return const_reverse_iterator(begin()); }
 199
 200   size_type size() const
 201     { return size_type(end() - begin()); }
 202   size_type max_size() const
 203     { return size_type(-1) / sizeof(_Tp); }
 204   size_type capacity() const
 205     { return size_type(const_iterator(_M_end_of_storage) - begin()); }
 206   bool empty() const
 207     { return begin() == end(); }
 208
 209   reference operator[](size_type __n) { return *(begin() + __n); }
 210   const_reference operator[](size_type __n) const { return *(begin() + __n); }
 211
 212   void _M_range_check(size_type __n) const {
 213     if (__n >= this->size())
 214       __throw_out_of_range("vector");
 215   }
 216
 217   reference at(size_type __n)
 218     { _M_range_check(__n); return (*this)[__n]; }
 219   const_reference at(size_type __n) const
 220     { _M_range_check(__n); return (*this)[__n]; }
 221
 222   explicit vector(const allocator_type& __a = allocator_type())
 223     : _Base(__a) {}
 224
 225   vector(size_type __n, const _Tp& __value,
 226          const allocator_type& __a = allocator_type())
 227     : _Base(__n, __a)
 228     { _M_finish = uninitialized_fill_n(_M_start, __n, __value); }
 229
 230   explicit vector(size_type __n)
 231     : _Base(__n, allocator_type())
 232     { _M_finish = uninitialized_fill_n(_M_start, __n, _Tp()); }
 233
 234   vector(const vector<_Tp, _Alloc>& __x)
 235     : _Base(__x.size(), __x.get_allocator())
 236     { _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); }
 237
 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())
 242         : _Base(__a)
 243         {
 244       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 245       _M_initialize_aux(__first, __last, _Integral());
 246     }
 247
 248   template <class _Integer>
 249     void _M_initialize_aux(_Integer __n, _Integer __value, __true_type)
 250         {
 251       _M_start = _M_allocate(__n);
 252       _M_end_of_storage = _M_start + __n;
 253       _M_finish = uninitialized_fill_n(_M_start, __n, __value);
 254     }
 255
 256   template<class _InputIterator>
 257     void
 258         _M_initialize_aux(_InputIterator __first, _InputIterator __last, __false_type)
 259         {
 260           typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory;
 261           _M_range_initialize(__first, __last, _IterCategory());
 262         }
 263
 264   ~vector()
 265   { _Destroy(_M_start, _M_finish); }
 266
 267   vector<_Tp, _Alloc>& operator=(const vector<_Tp, _Alloc>& __x);
 268   void reserve(size_type __n) {
 269     if (capacity() < __n) {
 270       const size_type __old_size = size();
 271       pointer __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
 272       _Destroy(_M_start, _M_finish);
 273       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 274       _M_start = __tmp;
 275       _M_finish = __tmp + __old_size;
 276       _M_end_of_storage = _M_start + __n;
 277     }
 278   }
 279
 280   // assign(), a generalized assignment member function.  Two
 281   // versions: one that takes a count, and one that takes a range.
 282   // The range version is a member template, so we dispatch on whether
 283   // or not the type is an integer.
 284
 285   void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }
 286   void _M_fill_assign(size_type __n, const _Tp& __val);
 287
 288   template<class _InputIterator>
 289     void
 290         assign(_InputIterator __first, _InputIterator __last)
 291         {
 292       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 293       _M_assign_dispatch(__first, __last, _Integral());
 294     }
 295
 296   template<class _Integer>
 297     void
 298         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
 299     { _M_fill_assign((size_type) __n, (_Tp) __val); }
 300
 301   template<class _InputIter>
 302     void
 303         _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
 304     {
 305           typedef typename iterator_traits<_InputIter>::iterator_category _IterCategory;
 306           _M_assign_aux(__first, __last, _IterCategory());
 307         }
 308
 309   template <class _InputIterator>
 310   void _M_assign_aux(_InputIterator __first, _InputIterator __last,
 311                      input_iterator_tag);
 312
 313   template <class _ForwardIterator>
 314   void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
 315                      forward_iterator_tag);
 316
 317   reference front() { return *begin(); }
 318   const_reference front() const { return *begin(); }
 319   reference back() { return *(end() - 1); }
 320   const_reference back() const { return *(end() - 1); }
 321
 322   void
 323   push_back(const _Tp& __x)
 324   {
 325     if (_M_finish != _M_end_of_storage) {
 326       _Construct(_M_finish, __x);
 327       ++_M_finish;
 328     }
 329     else
 330       _M_insert_aux(end(), __x);
 331   }
 332
 333   void
 334   push_back()
 335   {
 336     if (_M_finish != _M_end_of_storage) {
 337       _Construct(_M_finish);
 338       ++_M_finish;
 339     }
 340     else
 341       _M_insert_aux(end());
 342   }
 343
 344   void
 345   swap(vector<_Tp, _Alloc>& __x)
 346   {
 347     std::swap(_M_start, __x._M_start);
 348     std::swap(_M_finish, __x._M_finish);
 349     std::swap(_M_end_of_storage, __x._M_end_of_storage);
 350   }
 351
 352   iterator
 353   insert(iterator __position, const _Tp& __x)
 354   {
 355     size_type __n = __position - begin();
 356     if (_M_finish != _M_end_of_storage && __position == end()) {
 357       _Construct(_M_finish, __x);
 358       ++_M_finish;
 359     }
 360     else
 361       _M_insert_aux(iterator(__position), __x);
 362     return begin() + __n;
 363   }
 364
 365   iterator
 366   insert(iterator __position)
 367   {
 368     size_type __n = __position - begin();
 369     if (_M_finish != _M_end_of_storage && __position == end()) {
 370       _Construct(_M_finish);
 371       ++_M_finish;
 372     }
 373     else
 374       _M_insert_aux(iterator(__position));
 375     return begin() + __n;
 376   }
 377
 378   // Check whether it's an integral type.  If so, it's not an iterator.
 379   template<class _InputIterator>
 380     void
 381         insert(iterator __pos, _InputIterator __first, _InputIterator __last)
 382         {
 383       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 384       _M_insert_dispatch(__pos, __first, __last, _Integral());
 385     }
 386
 387   template <class _Integer>
 388     void
 389         _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, __true_type)
 390     { _M_fill_insert(__pos, static_cast<size_type>(__n), static_cast<_Tp>(__val)); }
 391
 392   template<class _InputIterator>
 393     void
 394         _M_insert_dispatch(iterator __pos,
 395                        _InputIterator __first, _InputIterator __last,
 396                        __false_type)
 397         {
 398           typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory;
 399       _M_range_insert(__pos, __first, __last, _IterCategory());
 400     }
 401
 402   void insert (iterator __pos, size_type __n, const _Tp& __x)
 403     { _M_fill_insert(__pos, __n, __x); }
 404
 405   void _M_fill_insert (iterator __pos, size_type __n, const _Tp& __x);
 406
 407   void pop_back() {
 408     --_M_finish;
 409     _Destroy(_M_finish);
 410   }
 411   iterator erase(iterator __position) {
 412     if (__position + 1 != end())
 413       copy(__position + 1, end(), __position);
 414     --_M_finish;
 415     _Destroy(_M_finish);
 416     return __position;
 417   }
 418   iterator erase(iterator __first, iterator __last) {
 419     iterator __i(copy(__last, end(), __first));
 420     _Destroy(__i, end());
 421     _M_finish = _M_finish - (__last - __first);
 422     return __first;
 423   }
 424
 425   void resize(size_type __new_size, const _Tp& __x) {
 426     if (__new_size < size())
 427       erase(begin() + __new_size, end());
 428     else
 429       insert(end(), __new_size - size(), __x);
 430   }
 431   void resize(size_type __new_size) { resize(__new_size, _Tp()); }
 432   void clear() { erase(begin(), end()); }
 433
 434 protected:
 435
 436   template <class _ForwardIterator>
 437   pointer _M_allocate_and_copy(size_type __n, _ForwardIterator __first,
 438                                                _ForwardIterator __last)
 439   {
 440     pointer __result = _M_allocate(__n);
 441     try {
 442       uninitialized_copy(__first, __last, __result);
 443       return __result;
 444     }
 445     catch(...)
 446       {
 447         _M_deallocate(__result, __n);
 448         __throw_exception_again;
 449       }
 450   }
 451
 452   template <class _InputIterator>
 453   void _M_range_initialize(_InputIterator __first,
 454                            _InputIterator __last, input_iterator_tag)
 455   {
 456     for ( ; __first != __last; ++__first)
 457       push_back(*__first);
 458   }
 459
 460   // This function is only called by the constructor.
 461   template <class _ForwardIterator>
 462   void _M_range_initialize(_ForwardIterator __first,
 463                            _ForwardIterator __last, forward_iterator_tag)
 464   {
 465     size_type __n = distance(__first, __last);
 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 = distance(__first, __last);
 586
 587   if (__len > capacity()) {
 588     pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
 589     _Destroy(_M_start, _M_finish);
 590     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 591     _M_start = __tmp;
 592     _M_end_of_storage = _M_finish = _M_start + __len;
 593   }
 594   else if (size() >= __len) {
 595     iterator __new_finish(copy(__first, __last, _M_start));
 596     _Destroy(__new_finish, end());
 597     _M_finish = __new_finish.base();
 598   }
 599   else {
 600     _ForwardIter __mid = __first;
 601     advance(__mid, size());
 602     copy(__first, __mid, _M_start);
 603     _M_finish = uninitialized_copy(__mid, __last, _M_finish);
 604   }
 605 }
 606
 607 template <class _Tp, class _Alloc>
 608 void
 609 vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
 610 {
 611   if (_M_finish != _M_end_of_storage) {
 612     _Construct(_M_finish, *(_M_finish - 1));
 613     ++_M_finish;
 614     _Tp __x_copy = __x;
 615     copy_backward(__position, iterator(_M_finish - 2), iterator(_M_finish- 1));
 616     *__position = __x_copy;
 617   }
 618   else {
 619     const size_type __old_size = size();
 620     const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
 621     iterator __new_start(_M_allocate(__len));
 622     iterator __new_finish(__new_start);
 623     try {
 624       __new_finish = uninitialized_copy(iterator(_M_start), __position,
 625                                         __new_start);
 626       _Construct(__new_finish.base(), __x);
 627       ++__new_finish;
 628       __new_finish = uninitialized_copy(__position, iterator(_M_finish),
 629                                         __new_finish);
 630     }
 631     catch(...)
 632       {
 633         _Destroy(__new_start,__new_finish);
 634         _M_deallocate(__new_start.base(),__len);
 635         __throw_exception_again;
 636       }
 637     _Destroy(begin(), end());
 638     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 639     _M_start = __new_start.base();
 640     _M_finish = __new_finish.base();
 641     _M_end_of_storage = __new_start.base() + __len;
 642   }
 643 }
 644
 645 template <class _Tp, class _Alloc>
 646 void
 647 vector<_Tp, _Alloc>::_M_insert_aux(iterator __position)
 648 {
 649   if (_M_finish != _M_end_of_storage) {
 650     _Construct(_M_finish, *(_M_finish - 1));
 651     ++_M_finish;
 652     copy_backward(__position, iterator(_M_finish - 2),
 653                   iterator(_M_finish - 1));
 654     *__position = _Tp();
 655   }
 656   else {
 657     const size_type __old_size = size();
 658     const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
 659     pointer __new_start = _M_allocate(__len);
 660     pointer __new_finish = __new_start;
 661     try {
 662       __new_finish = uninitialized_copy(iterator(_M_start), __position,
 663                                         __new_start);
 664       _Construct(__new_finish);
 665       ++__new_finish;
 666       __new_finish = uninitialized_copy(__position, iterator(_M_finish),
 667                                         __new_finish);
 668     }
 669     catch(...)
 670       {
 671         _Destroy(__new_start,__new_finish);
 672         _M_deallocate(__new_start,__len);
 673         __throw_exception_again;
 674       }
 675     _Destroy(begin(), end());
 676     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 677     _M_start = __new_start;
 678     _M_finish = __new_finish;
 679     _M_end_of_storage = __new_start + __len;
 680   }
 681 }
 682
 683 template <class _Tp, class _Alloc>
 684 void vector<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n,
 685                                          const _Tp& __x)
 686 {
 687   if (__n != 0) {
 688     if (size_type(_M_end_of_storage - _M_finish) >= __n) {
 689       _Tp __x_copy = __x;
 690       const size_type __elems_after = end() - __position;
 691       iterator __old_finish(_M_finish);
 692       if (__elems_after > __n) {
 693         uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
 694         _M_finish += __n;
 695         copy_backward(__position, __old_finish - __n, __old_finish);
 696         fill(__position, __position + __n, __x_copy);
 697       }
 698       else {
 699         uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
 700         _M_finish += __n - __elems_after;
 701         uninitialized_copy(__position, __old_finish, _M_finish);
 702         _M_finish += __elems_after;
 703         fill(__position, __old_finish, __x_copy);
 704       }
 705     }
 706     else {
 707       const size_type __old_size = size();
 708       const size_type __len = __old_size + max(__old_size, __n);
 709       iterator __new_start(_M_allocate(__len));
 710       iterator __new_finish(__new_start);
 711       try {
 712         __new_finish = uninitialized_copy(begin(), __position, __new_start);
 713         __new_finish = uninitialized_fill_n(__new_finish, __n, __x);
 714         __new_finish
 715           = uninitialized_copy(__position, end(), __new_finish);
 716       }
 717       catch(...)
 718         {
 719           _Destroy(__new_start,__new_finish);
 720           _M_deallocate(__new_start.base(),__len);
 721           __throw_exception_again;
 722         }
 723       _Destroy(_M_start, _M_finish);
 724       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 725       _M_start = __new_start.base();
 726       _M_finish = __new_finish.base();
 727       _M_end_of_storage = __new_start.base() + __len;
 728     }
 729   }
 730 }
 731
 732 template <class _Tp, class _Alloc> template <class _InputIterator>
 733 void
 734 vector<_Tp, _Alloc>::_M_range_insert(iterator __pos,
 735                                      _InputIterator __first,
 736                                      _InputIterator __last,
 737                                      input_iterator_tag)
 738 {
 739   for ( ; __first != __last; ++__first) {
 740     __pos = insert(__pos, *__first);
 741     ++__pos;
 742   }
 743 }
 744
 745 template <class _Tp, class _Alloc> template <class _ForwardIterator>
 746 void
 747 vector<_Tp, _Alloc>::_M_range_insert(iterator __position,
 748                                      _ForwardIterator __first,
 749                                      _ForwardIterator __last,
 750                                      forward_iterator_tag)
 751 {
 752   if (__first != __last) {
 753     size_type __n = distance(__first, __last);
 754     if (size_type(_M_end_of_storage - _M_finish) >= __n) {
 755       const size_type __elems_after = end() - __position;
 756       iterator __old_finish(_M_finish);
 757       if (__elems_after > __n) {
 758         uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
 759         _M_finish += __n;
 760         copy_backward(__position, __old_finish - __n, __old_finish);
 761         copy(__first, __last, __position);
 762       }
 763       else {
 764         _ForwardIterator __mid = __first;
 765         advance(__mid, __elems_after);
 766         uninitialized_copy(__mid, __last, _M_finish);
 767         _M_finish += __n - __elems_after;
 768         uninitialized_copy(__position, __old_finish, _M_finish);
 769         _M_finish += __elems_after;
 770         copy(__first, __mid, __position);
 771       }
 772     }
 773     else {
 774       const size_type __old_size = size();
 775       const size_type __len = __old_size + max(__old_size, __n);
 776       iterator __new_start(_M_allocate(__len));
 777       iterator __new_finish(__new_start);
 778       try {
 779         __new_finish = uninitialized_copy(iterator(_M_start),
 780                                           __position, __new_start);
 781         __new_finish = uninitialized_copy(__first, __last, __new_finish);
 782         __new_finish
 783           = uninitialized_copy(__position, iterator(_M_finish), __new_finish);
 784       }
 785       catch(...)
 786         {
 787           _Destroy(__new_start,__new_finish);
 788           _M_deallocate(__new_start.base(), __len);
 789           __throw_exception_again;
 790         }
 791       _Destroy(_M_start, _M_finish);
 792       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 793       _M_start = __new_start.base();
 794       _M_finish = __new_finish.base();
 795       _M_end_of_storage = __new_start.base() + __len;
 796     }
 797   }
 798 }
 799
 800 } // namespace std
 801
 802 #endif /* __GLIBCPP_INTERNAL_VECTOR_H */
 803
 804 // Local Variables:
 805 // mode:C++
 806 // End: