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 /**
 148  *  @brief  A standard container which offers fixed time access to individual
 149  *  elements in any order.
 150  *
 151  *  In some terminology a vector can be described as a dynamic C-style array,
 152  *  it offers fast and efficient access to individual elements in any order
 153  *  and saves the user from worrying about memory and size allocation.
 154  *  Subscripting ( [] ) access is also provided as with C-style arrays.
 155 */
 156 template <class _Tp, class _Alloc = allocator<_Tp> >
 157 class vector : protected _Vector_base<_Tp, _Alloc>
 158 {
 159   // concept requirements
 160   __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
 161
 162 private:
 163   typedef _Vector_base<_Tp, _Alloc> _Base;
 164   typedef vector<_Tp, _Alloc> vector_type;
 165 public:
 166   typedef _Tp                                           value_type;
 167   typedef value_type*                                   pointer;
 168   typedef const value_type*                             const_pointer;
 169   typedef __normal_iterator<pointer, vector_type>       iterator;
 170   typedef __normal_iterator<const_pointer, vector_type> const_iterator;
 171   typedef value_type&                                   reference;
 172   typedef const value_type&                             const_reference;
 173   typedef size_t                                        size_type;
 174   typedef ptrdiff_t                                     difference_type;
 175
 176   typedef typename _Base::allocator_type allocator_type;
 177   allocator_type get_allocator() const { return _Base::get_allocator(); }
 178
 179   typedef reverse_iterator<const_iterator> const_reverse_iterator;
 180   typedef reverse_iterator<iterator> reverse_iterator;
 181
 182 protected:
 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
 189 protected:
 190   void _M_insert_aux(iterator __position, const _Tp& __x);
 191   void _M_insert_aux(iterator __position);
 192
 193 public:
 194   /**
 195    *  Returns a read/write iterator that points to the first element in the
 196    *  vector.  Iteration is done in ordinary element order.
 197   */
 198   iterator begin() { return iterator (_M_start); }
 199
 200   /**
 201    *  Returns a read-only (constant) iterator that points to the first element
 202    *  in the vector.  Iteration is done in ordinary element order.
 203   */
 204   const_iterator begin() const
 205     { return const_iterator (_M_start); }
 206
 207   /**
 208    *  Returns a read/write iterator that points one past the last element in
 209    *  the vector.  Iteration is done in ordinary element order.
 210   */
 211   iterator end() { return iterator (_M_finish); }
 212
 213   /**
 214    *  Returns a read-only (constant) iterator that points one past the last
 215    *  element in the vector.  Iteration is done in ordinary element order.
 216   */
 217   const_iterator end() const { return const_iterator (_M_finish); }
 218
 219   /**
 220    *  Returns a read/write reverse iterator that points to the last element in
 221    *  the vector.  Iteration is done in reverse element order.
 222   */
 223   reverse_iterator rbegin()
 224     { return reverse_iterator(end()); }
 225
 226   /**
 227    *  Returns a read-only (constant) reverse iterator that points to the last
 228    *  element in the vector.  Iteration is done in reverse element order.
 229   */
 230   const_reverse_iterator rbegin() const
 231     { return const_reverse_iterator(end()); }
 232
 233   /**
 234    *  Returns a read/write reverse iterator that points to one before the
 235    *  first element in the vector.  Iteration is done in reverse element
 236    *  order.
 237   */
 238   reverse_iterator rend()
 239     { return reverse_iterator(begin()); }
 240
 241   /**
 242    *  Returns a read-only (constant) reverse iterator that points to one
 243    *  before the first element in the vector.  Iteration is done in reverse
 244    *  element order.
 245   */
 246   const_reverse_iterator rend() const
 247     { return const_reverse_iterator(begin()); }
 248
 249   /**  Returns the number of elements in the vector.  */
 250   size_type size() const
 251     { return size_type(end() - begin()); }
 252
 253   /**  Returns the size of the largest possible vector.  */
 254   size_type max_size() const
 255     { return size_type(-1) / sizeof(_Tp); }
 256
 257   /**
 258    *  Returns the amount of memory that has been alocated for the current
 259    *  elements (?).
 260   */
 261   size_type capacity() const
 262     { return size_type(const_iterator(_M_end_of_storage) - begin()); }
 263
 264   /**
 265    *  Returns true if the vector is empty.  (Thus begin() would equal end().)
 266   */
 267   bool empty() const
 268     { return begin() == end(); }
 269
 270   /**
 271    *  @brief  Subscript access to the data contained in the vector.
 272    *  @param  n  The element for which data should be accessed.
 273    *  @return  Read/write reference to data.
 274    *
 275    *  This operator allows for easy, array-style, data access.
 276    *  Note that data access with this operator is unchecked and out_of_range
 277    *  lookups are not defined. (For checked lookups see at().)
 278   */
 279   reference operator[](size_type __n) { return *(begin() + __n); }
 280
 281   /**
 282    *  @brief  Subscript access to the data contained in the vector.
 283    *  @param  n  The element for which data should be accessed.
 284    *  @return  Read-only (constant) reference to data.
 285    *
 286    *  This operator allows for easy, array-style, data access.
 287    *  Note that data access with this operator is unchecked and out_of_range
 288    *  lookups are not defined. (For checked lookups see at().)
 289   */
 290   const_reference operator[](size_type __n) const { return *(begin() + __n); }
 291
 292   void _M_range_check(size_type __n) const {
 293     if (__n >= this->size())
 294       __throw_out_of_range("vector");
 295   }
 296
 297   /**
 298    *  @brief  Provides access to the data contained in the vector.
 299    *  @param  n  The element for which data should be accessed.
 300    *  @return  Read/write reference to data.
 301    *
 302    *  This function provides for safer data access.  The parameter is first
 303    *  checked that it is in the range of the vector.  The function throws
 304    *  out_of_range if the check fails.
 305   */
 306   reference at(size_type __n)
 307     { _M_range_check(__n); return (*this)[__n]; }
 308
 309   /**
 310    *  @brief  Provides access to the data contained in the vector.
 311    *  @param  n  The element for which data should be accessed.
 312    *  @return  Read-only (constant) reference to data.
 313    *
 314    *  This function provides for safer data access.  The parameter is first
 315    *  checked that it is in the range of the vector.  The function throws
 316    *  out_of_range if the check fails.
 317   */
 318   const_reference at(size_type __n) const
 319     { _M_range_check(__n); return (*this)[__n]; }
 320
 321
 322   explicit vector(const allocator_type& __a = allocator_type())
 323     : _Base(__a) {}
 324
 325   vector(size_type __n, const _Tp& __value,
 326          const allocator_type& __a = allocator_type())
 327     : _Base(__n, __a)
 328     { _M_finish = uninitialized_fill_n(_M_start, __n, __value); }
 329
 330   explicit vector(size_type __n)
 331     : _Base(__n, allocator_type())
 332     { _M_finish = uninitialized_fill_n(_M_start, __n, _Tp()); }
 333
 334   vector(const vector<_Tp, _Alloc>& __x)
 335     : _Base(__x.size(), __x.get_allocator())
 336     { _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); }
 337
 338   // Check whether it's an integral type.  If so, it's not an iterator.
 339   template <class _InputIterator>
 340     vector(_InputIterator __first, _InputIterator __last,
 341            const allocator_type& __a = allocator_type())
 342         : _Base(__a)
 343         {
 344       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 345       _M_initialize_aux(__first, __last, _Integral());
 346     }
 347
 348   template <class _Integer>
 349     void _M_initialize_aux(_Integer __n, _Integer __value, __true_type)
 350         {
 351       _M_start = _M_allocate(__n);
 352       _M_end_of_storage = _M_start + __n;
 353       _M_finish = uninitialized_fill_n(_M_start, __n, __value);
 354     }
 355
 356   template<class _InputIterator>
 357     void
 358         _M_initialize_aux(_InputIterator __first, _InputIterator __last, __false_type)
 359         {
 360           typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory;
 361           _M_range_initialize(__first, __last, _IterCategory());
 362         }
 363
 364   ~vector()
 365   { _Destroy(_M_start, _M_finish); }
 366
 367   vector<_Tp, _Alloc>& operator=(const vector<_Tp, _Alloc>& __x);
 368
 369   /**
 370    *  @brief  Attempt to preallocate enough memory for specified number of
 371    *          elements.
 372    *  @param  n  Number of elements required
 373    *
 374    *  This function attempts to reserve enough memory for the vector to hold
 375    *  the specified number of elements.  If the number requested is more than
 376    *  max_size() length_error is thrown.
 377    *
 378    *  The advantage of this function is that if optimal code is a necessity
 379    *  and the user can determine the number of elements that will be required
 380    *  the user can reserve the memory and thus prevent a possible
 381    *  reallocation of memory and copy of vector data.
 382   */
 383   void reserve(size_type __n) {
 384     if (capacity() < __n) {
 385       const size_type __old_size = size();
 386       pointer __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
 387       _Destroy(_M_start, _M_finish);
 388       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 389       _M_start = __tmp;
 390       _M_finish = __tmp + __old_size;
 391       _M_end_of_storage = _M_start + __n;
 392     }
 393   }
 394
 395   // assign(), a generalized assignment member function.  Two
 396   // versions: one that takes a count, and one that takes a range.
 397   // The range version is a member template, so we dispatch on whether
 398   // or not the type is an integer.
 399
 400   /**
 401    *  @brief  Assigns a given value or range to a vector.
 402    *  @param  n  Number of elements to be assigned.
 403    *  @param  val  Value to be assigned.
 404    *
 405    *  This function can be used to assign a range to a vector or fill it
 406    *  with a specified number of copies of the given value.
 407    *  Note that the assignment completely changes the vector and that the
 408    *  resulting vector's size is the same as the number of elements assigned.
 409    *  Old data may be lost.
 410   */
 411   void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }
 412   void _M_fill_assign(size_type __n, const _Tp& __val);
 413
 414   template<class _InputIterator>
 415     void
 416         assign(_InputIterator __first, _InputIterator __last)
 417         {
 418       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 419       _M_assign_dispatch(__first, __last, _Integral());
 420     }
 421
 422   template<class _Integer>
 423     void
 424         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
 425     { _M_fill_assign((size_type) __n, (_Tp) __val); }
 426
 427   template<class _InputIter>
 428     void
 429         _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
 430     {
 431           typedef typename iterator_traits<_InputIter>::iterator_category _IterCategory;
 432           _M_assign_aux(__first, __last, _IterCategory());
 433         }
 434
 435   template <class _InputIterator>
 436   void _M_assign_aux(_InputIterator __first, _InputIterator __last,
 437                      input_iterator_tag);
 438
 439   template <class _ForwardIterator>
 440   void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
 441                      forward_iterator_tag);
 442
 443   /**
 444    *  Returns a read/write reference to the data at the first element of the
 445    *  vector.
 446   */
 447   reference front() { return *begin(); }
 448
 449   /**
 450    *  Returns a read-only (constant) reference to the data at the first
 451    *  element of the vector.
 452   */
 453   const_reference front() const { return *begin(); }
 454
 455   /**
 456    *  Returns a read/write reference to the data at the last element of the
 457    *  vector.
 458   */
 459   reference back() { return *(end() - 1); }
 460
 461   /**
 462    *  Returns a read-only (constant) reference to the data at the first
 463    *  element of the vector.
 464   */
 465   const_reference back() const { return *(end() - 1); }
 466
 467   /**
 468    *  @brief  Add data to the end of the vector.
 469    *  @param  x  Data to be added.
 470    *
 471    *  This is a typical stack operation.  The function creates an element at
 472    *  the end of the vector and assigns the given data to it.
 473    *  Due to the nature of a vector this operation can be done in constant
 474    *  time if the vector has preallocated space available.
 475   */
 476   void
 477   push_back(const _Tp& __x)
 478   {
 479     if (_M_finish != _M_end_of_storage) {
 480       _Construct(_M_finish, __x);
 481       ++_M_finish;
 482     }
 483     else
 484       _M_insert_aux(end(), __x);
 485   }
 486
 487 #ifdef _GLIBCPP_DEPRECATED
 488   /**
 489    *  Add an element to the end of the vector.  The element is
 490    *  default-constructed.
 491    *
 492    *  @note You must define _GLIBCPP_DEPRECATED to make this visible; see
 493    *        c++config.h.
 494   */
 495   void
 496   push_back()
 497   {
 498     if (_M_finish != _M_end_of_storage) {
 499       _Construct(_M_finish);
 500       ++_M_finish;
 501     }
 502     else
 503       _M_insert_aux(end());
 504   }
 505 #endif
 506
 507   void
 508   swap(vector<_Tp, _Alloc>& __x)
 509   {
 510     std::swap(_M_start, __x._M_start);
 511     std::swap(_M_finish, __x._M_finish);
 512     std::swap(_M_end_of_storage, __x._M_end_of_storage);
 513   }
 514
 515   /**
 516    *  @brief  Inserts given value into vector at specified element.
 517    *  @param  position  An iterator that points to the element where data
 518    *                    should be inserted.
 519    *  @param  x  Data to be inserted.
 520    *  @return  An iterator that points to the inserted data.
 521    *
 522    *  This function will insert the given value into the specified location.
 523    *  Note that this kind of operation could be expensive for a vector and if
 524    *  it is frequently used the user should consider using std::list.
 525   */
 526   iterator
 527   insert(iterator __position, const _Tp& __x)
 528   {
 529     size_type __n = __position - begin();
 530     if (_M_finish != _M_end_of_storage && __position == end()) {
 531       _Construct(_M_finish, __x);
 532       ++_M_finish;
 533     }
 534     else
 535       _M_insert_aux(iterator(__position), __x);
 536     return begin() + __n;
 537   }
 538
 539   /**
 540    *  @brief  Inserts an empty element into the vector.
 541    *  @param  position  An iterator that points to the element where empty
 542    *                    element should be inserted.
 543    *  @param  x  Data to be inserted.
 544    *  @return  An iterator that points to the inserted element.
 545    *
 546    *  This function will insert an empty element into the specified location.
 547    *  Note that this kind of operation could be expensive for a vector and if
 548    *  it is frequently used the user should consider using std::list.
 549   */
 550   iterator
 551   insert(iterator __position)
 552   {
 553     size_type __n = __position - begin();
 554     if (_M_finish != _M_end_of_storage && __position == end()) {
 555       _Construct(_M_finish);
 556       ++_M_finish;
 557     }
 558     else
 559       _M_insert_aux(iterator(__position));
 560     return begin() + __n;
 561   }
 562
 563   // Check whether it's an integral type.  If so, it's not an iterator.
 564   template<class _InputIterator>
 565     void
 566         insert(iterator __pos, _InputIterator __first, _InputIterator __last)
 567         {
 568       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 569       _M_insert_dispatch(__pos, __first, __last, _Integral());
 570     }
 571
 572   template <class _Integer>
 573     void
 574         _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, __true_type)
 575     { _M_fill_insert(__pos, static_cast<size_type>(__n), static_cast<_Tp>(__val)); }
 576
 577   template<class _InputIterator>
 578     void
 579         _M_insert_dispatch(iterator __pos,
 580                        _InputIterator __first, _InputIterator __last,
 581                        __false_type)
 582         {
 583           typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory;
 584       _M_range_insert(__pos, __first, __last, _IterCategory());
 585     }
 586
 587   /**
 588    *  @brief  Inserts a number of copies of given data into the vector.
 589    *  @param  position  An iterator that points to the element where data
 590    *                    should be inserted.
 591    *  @param  n  Amount of elements to be inserted.
 592    *  @param  x  Data to be inserted.
 593    *
 594    *  This function will insert a specified number of copies of the given data
 595    *  into the specified location.
 596    *
 597    *  Note that this kind of operation could be expensive for a vector and if
 598    *  it is frequently used the user should consider using std::list.
 599   */
 600   void insert (iterator __pos, size_type __n, const _Tp& __x)
 601     { _M_fill_insert(__pos, __n, __x); }
 602
 603   void _M_fill_insert (iterator __pos, size_type __n, const _Tp& __x);
 604
 605   /**
 606    *  @brief  Removes last element from vector.
 607    *
 608    *  This is a typical stack operation. It allows us to shrink the vector by
 609    *  one.
 610    *
 611    *  Note that no data is returned and if last element's data is needed it
 612    *  should be retrieved before pop_back() is called.
 613   */
 614   void pop_back() {
 615     --_M_finish;
 616     _Destroy(_M_finish);
 617   }
 618
 619   /**
 620    *  @brief  Remove element at given position
 621    *  @param  position  Iterator pointing to element to be erased.
 622    *  @return  Doc Me! (Iterator pointing to new element at old location?)
 623    *
 624    *  This function will erase the element at the given position and thus
 625    *  shorten the vector by one.
 626    *
 627    *  Note This operation could be expensive and if it is frequently used the
 628    *  user should consider using std::list.  The user is also cautioned that
 629    *  this function only erases the element, and that if the element is itself
 630    *  a pointer, the pointed-to memory is not touched in any way.  Managing
 631    *  the pointer is the user's responsibilty.
 632   */
 633   iterator erase(iterator __position) {
 634     if (__position + 1 != end())
 635       copy(__position + 1, end(), __position);
 636     --_M_finish;
 637     _Destroy(_M_finish);
 638     return __position;
 639   }
 640
 641   /**
 642    *  @brief  Remove a range of elements from a vector.
 643    *  @param  first  Iterator pointing to the first element to be erased.
 644    *  @param  last  Iterator pointing to the last element to be erased.
 645    *  @return  Doc Me! (Iterator pointing to new element at old location?)
 646    *
 647    *  This function will erase the elements in the given range and shorten the
 648    *  vector accordingly.
 649    *
 650    *  Note This operation could be expensive and if it is frequently used the
 651    *  user should consider using std::list.  The user is also cautioned that
 652    *  this function only erases the elements, and that if the elements
 653    *  themselves are pointers, the pointed-to memory is not touched in any
 654    *  way.  Managing the pointer is the user's responsibilty.
 655   */
 656   iterator erase(iterator __first, iterator __last) {
 657     iterator __i(copy(__last, end(), __first));
 658     _Destroy(__i, end());
 659     _M_finish = _M_finish - (__last - __first);
 660     return __first;
 661   }
 662
 663   /**
 664    *  @brief  Resizes the vector to the specified number of elements.
 665    *  @param  new_size  Number of elements the vector should contain.
 666    *  @param  x  Data with which new elements should be populated.
 667    *
 668    *  This function will resize the vector to the specified number of
 669    *  elements.  If the number is smaller than the vector's current size the
 670    *  vector is truncated, otherwise the vector is extended and new elements
 671    *  are populated with given data.
 672   */
 673   void resize(size_type __new_size, const _Tp& __x) {
 674     if (__new_size < size())
 675       erase(begin() + __new_size, end());
 676     else
 677       insert(end(), __new_size - size(), __x);
 678   }
 679
 680   /**
 681    *  @brief  Resizes the vector to the specified number of elements.
 682    *  @param  new_size  Number of elements the vector should contain.
 683    *
 684    *  This function will resize the vector to the specified number of
 685    *  elements.  If the number is smaller than the vector's current size the
 686    *  vector is truncated, otherwise the vector is extended and new elements
 687    *  are left uninitialized.
 688   */
 689   void resize(size_type __new_size) { resize(__new_size, _Tp()); }
 690
 691   /**
 692    *  Erases all elements in vector.  Note that this function only erases the
 693    *  elements, and that if the elements themselves are pointers, the
 694    *  pointed-to memory is not touched in any way.  Managing the pointer is
 695    *  the user's responsibilty.
 696   */
 697   void clear() { erase(begin(), end()); }
 698
 699 protected:
 700
 701   template <class _ForwardIterator>
 702   pointer _M_allocate_and_copy(size_type __n, _ForwardIterator __first,
 703                                                _ForwardIterator __last)
 704   {
 705     pointer __result = _M_allocate(__n);
 706     try {
 707       uninitialized_copy(__first, __last, __result);
 708       return __result;
 709     }
 710     catch(...)
 711       {
 712         _M_deallocate(__result, __n);
 713         __throw_exception_again;
 714       }
 715   }
 716
 717   template <class _InputIterator>
 718   void _M_range_initialize(_InputIterator __first,
 719                            _InputIterator __last, input_iterator_tag)
 720   {
 721     for ( ; __first != __last; ++__first)
 722       push_back(*__first);
 723   }
 724
 725   // This function is only called by the constructor.
 726   template <class _ForwardIterator>
 727   void _M_range_initialize(_ForwardIterator __first,
 728                            _ForwardIterator __last, forward_iterator_tag)
 729   {
 730     size_type __n = distance(__first, __last);
 731     _M_start = _M_allocate(__n);
 732     _M_end_of_storage = _M_start + __n;
 733     _M_finish = uninitialized_copy(__first, __last, _M_start);
 734   }
 735
 736   template <class _InputIterator>
 737   void _M_range_insert(iterator __pos,
 738                        _InputIterator __first, _InputIterator __last,
 739                        input_iterator_tag);
 740
 741   template <class _ForwardIterator>
 742   void _M_range_insert(iterator __pos,
 743                        _ForwardIterator __first, _ForwardIterator __last,
 744                        forward_iterator_tag);
 745 };
 746
 747 template <class _Tp, class _Alloc>
 748 inline bool
 749 operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
 750 {
 751   return __x.size() == __y.size() &&
 752          equal(__x.begin(), __x.end(), __y.begin());
 753 }
 754
 755 template <class _Tp, class _Alloc>
 756 inline bool
 757 operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
 758 {
 759   return lexicographical_compare(__x.begin(), __x.end(),
 760                                  __y.begin(), __y.end());
 761 }
 762
 763 template <class _Tp, class _Alloc>
 764 inline void swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
 765 {
 766   __x.swap(__y);
 767 }
 768
 769 template <class _Tp, class _Alloc>
 770 inline bool
 771 operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
 772   return !(__x == __y);
 773 }
 774
 775 template <class _Tp, class _Alloc>
 776 inline bool
 777 operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
 778   return __y < __x;
 779 }
 780
 781 template <class _Tp, class _Alloc>
 782 inline bool
 783 operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
 784   return !(__y < __x);
 785 }
 786
 787 template <class _Tp, class _Alloc>
 788 inline bool
 789 operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
 790   return !(__x < __y);
 791 }
 792
 793 template <class _Tp, class _Alloc>
 794 vector<_Tp,_Alloc>&
 795 vector<_Tp,_Alloc>::operator=(const vector<_Tp, _Alloc>& __x)
 796 {
 797   if (&__x != this) {
 798     const size_type __xlen = __x.size();
 799     if (__xlen > capacity()) {
 800       pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end());
 801       _Destroy(_M_start, _M_finish);
 802       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 803       _M_start = __tmp;
 804       _M_end_of_storage = _M_start + __xlen;
 805     }
 806     else if (size() >= __xlen) {
 807       iterator __i(copy(__x.begin(), __x.end(), begin()));
 808       _Destroy(__i, end());
 809     }
 810     else {
 811       copy(__x.begin(), __x.begin() + size(), _M_start);
 812       uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish);
 813     }
 814     _M_finish = _M_start + __xlen;
 815   }
 816   return *this;
 817 }
 818
 819 template <class _Tp, class _Alloc>
 820 void vector<_Tp, _Alloc>::_M_fill_assign(size_t __n, const value_type& __val)
 821 {
 822   if (__n > capacity()) {
 823     vector<_Tp, _Alloc> __tmp(__n, __val, get_allocator());
 824     __tmp.swap(*this);
 825   }
 826   else if (__n > size()) {
 827     fill(begin(), end(), __val);
 828     _M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val);
 829   }
 830   else
 831     erase(fill_n(begin(), __n, __val), end());
 832 }
 833
 834 template <class _Tp, class _Alloc> template <class _InputIter>
 835 void vector<_Tp, _Alloc>::_M_assign_aux(_InputIter __first, _InputIter __last,
 836                                         input_iterator_tag) {
 837   iterator __cur(begin());
 838   for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
 839     *__cur = *__first;
 840   if (__first == __last)
 841     erase(__cur, end());
 842   else
 843     insert(end(), __first, __last);
 844 }
 845
 846 template <class _Tp, class _Alloc> template <class _ForwardIter>
 847 void
 848 vector<_Tp, _Alloc>::_M_assign_aux(_ForwardIter __first, _ForwardIter __last,
 849                                    forward_iterator_tag) {
 850   size_type __len = distance(__first, __last);
 851
 852   if (__len > capacity()) {
 853     pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
 854     _Destroy(_M_start, _M_finish);
 855     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 856     _M_start = __tmp;
 857     _M_end_of_storage = _M_finish = _M_start + __len;
 858   }
 859   else if (size() >= __len) {
 860     iterator __new_finish(copy(__first, __last, _M_start));
 861     _Destroy(__new_finish, end());
 862     _M_finish = __new_finish.base();
 863   }
 864   else {
 865     _ForwardIter __mid = __first;
 866     advance(__mid, size());
 867     copy(__first, __mid, _M_start);
 868     _M_finish = uninitialized_copy(__mid, __last, _M_finish);
 869   }
 870 }
 871
 872 template <class _Tp, class _Alloc>
 873 void
 874 vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
 875 {
 876   if (_M_finish != _M_end_of_storage) {
 877     _Construct(_M_finish, *(_M_finish - 1));
 878     ++_M_finish;
 879     _Tp __x_copy = __x;
 880     copy_backward(__position, iterator(_M_finish - 2), iterator(_M_finish- 1));
 881     *__position = __x_copy;
 882   }
 883   else {
 884     const size_type __old_size = size();
 885     const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
 886     iterator __new_start(_M_allocate(__len));
 887     iterator __new_finish(__new_start);
 888     try {
 889       __new_finish = uninitialized_copy(iterator(_M_start), __position,
 890                                         __new_start);
 891       _Construct(__new_finish.base(), __x);
 892       ++__new_finish;
 893       __new_finish = uninitialized_copy(__position, iterator(_M_finish),
 894                                         __new_finish);
 895     }
 896     catch(...)
 897       {
 898         _Destroy(__new_start,__new_finish);
 899         _M_deallocate(__new_start.base(),__len);
 900         __throw_exception_again;
 901       }
 902     _Destroy(begin(), end());
 903     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 904     _M_start = __new_start.base();
 905     _M_finish = __new_finish.base();
 906     _M_end_of_storage = __new_start.base() + __len;
 907   }
 908 }
 909
 910 template <class _Tp, class _Alloc>
 911 void
 912 vector<_Tp, _Alloc>::_M_insert_aux(iterator __position)
 913 {
 914   if (_M_finish != _M_end_of_storage) {
 915     _Construct(_M_finish, *(_M_finish - 1));
 916     ++_M_finish;
 917     copy_backward(__position, iterator(_M_finish - 2),
 918                   iterator(_M_finish - 1));
 919     *__position = _Tp();
 920   }
 921   else {
 922     const size_type __old_size = size();
 923     const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
 924     pointer __new_start = _M_allocate(__len);
 925     pointer __new_finish = __new_start;
 926     try {
 927       __new_finish = uninitialized_copy(iterator(_M_start), __position,
 928                                         __new_start);
 929       _Construct(__new_finish);
 930       ++__new_finish;
 931       __new_finish = uninitialized_copy(__position, iterator(_M_finish),
 932                                         __new_finish);
 933     }
 934     catch(...)
 935       {
 936         _Destroy(__new_start,__new_finish);
 937         _M_deallocate(__new_start,__len);
 938         __throw_exception_again;
 939       }
 940     _Destroy(begin(), end());
 941     _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 942     _M_start = __new_start;
 943     _M_finish = __new_finish;
 944     _M_end_of_storage = __new_start + __len;
 945   }
 946 }
 947
 948 template <class _Tp, class _Alloc>
 949 void vector<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n,
 950                                          const _Tp& __x)
 951 {
 952   if (__n != 0) {
 953     if (size_type(_M_end_of_storage - _M_finish) >= __n) {
 954       _Tp __x_copy = __x;
 955       const size_type __elems_after = end() - __position;
 956       iterator __old_finish(_M_finish);
 957       if (__elems_after > __n) {
 958         uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
 959         _M_finish += __n;
 960         copy_backward(__position, __old_finish - __n, __old_finish);
 961         fill(__position, __position + __n, __x_copy);
 962       }
 963       else {
 964         uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
 965         _M_finish += __n - __elems_after;
 966         uninitialized_copy(__position, __old_finish, _M_finish);
 967         _M_finish += __elems_after;
 968         fill(__position, __old_finish, __x_copy);
 969       }
 970     }
 971     else {
 972       const size_type __old_size = size();
 973       const size_type __len = __old_size + max(__old_size, __n);
 974       iterator __new_start(_M_allocate(__len));
 975       iterator __new_finish(__new_start);
 976       try {
 977         __new_finish = uninitialized_copy(begin(), __position, __new_start);
 978         __new_finish = uninitialized_fill_n(__new_finish, __n, __x);
 979         __new_finish
 980           = uninitialized_copy(__position, end(), __new_finish);
 981       }
 982       catch(...)
 983         {
 984           _Destroy(__new_start,__new_finish);
 985           _M_deallocate(__new_start.base(),__len);
 986           __throw_exception_again;
 987         }
 988       _Destroy(_M_start, _M_finish);
 989       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
 990       _M_start = __new_start.base();
 991       _M_finish = __new_finish.base();
 992       _M_end_of_storage = __new_start.base() + __len;
 993     }
 994   }
 995 }
 996
 997 template <class _Tp, class _Alloc> template <class _InputIterator>
 998 void
 999 vector<_Tp, _Alloc>::_M_range_insert(iterator __pos,
1000                                      _InputIterator __first,
1001                                      _InputIterator __last,
1002                                      input_iterator_tag)
1003 {
1004   for ( ; __first != __last; ++__first) {
1005     __pos = insert(__pos, *__first);
1006     ++__pos;
1007   }
1008 }
1009
1010 template <class _Tp, class _Alloc> template <class _ForwardIterator>
1011 void
1012 vector<_Tp, _Alloc>::_M_range_insert(iterator __position,
1013                                      _ForwardIterator __first,
1014                                      _ForwardIterator __last,
1015                                      forward_iterator_tag)
1016 {
1017   if (__first != __last) {
1018     size_type __n = distance(__first, __last);
1019     if (size_type(_M_end_of_storage - _M_finish) >= __n) {
1020       const size_type __elems_after = end() - __position;
1021       iterator __old_finish(_M_finish);
1022       if (__elems_after > __n) {
1023         uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
1024         _M_finish += __n;
1025         copy_backward(__position, __old_finish - __n, __old_finish);
1026         copy(__first, __last, __position);
1027       }
1028       else {
1029         _ForwardIterator __mid = __first;
1030         advance(__mid, __elems_after);
1031         uninitialized_copy(__mid, __last, _M_finish);
1032         _M_finish += __n - __elems_after;
1033         uninitialized_copy(__position, __old_finish, _M_finish);
1034         _M_finish += __elems_after;
1035         copy(__first, __mid, __position);
1036       }
1037     }
1038     else {
1039       const size_type __old_size = size();
1040       const size_type __len = __old_size + max(__old_size, __n);
1041       iterator __new_start(_M_allocate(__len));
1042       iterator __new_finish(__new_start);
1043       try {
1044         __new_finish = uninitialized_copy(iterator(_M_start),
1045                                           __position, __new_start);
1046         __new_finish = uninitialized_copy(__first, __last, __new_finish);
1047         __new_finish
1048           = uninitialized_copy(__position, iterator(_M_finish), __new_finish);
1049       }
1050       catch(...)
1051         {
1052           _Destroy(__new_start,__new_finish);
1053           _M_deallocate(__new_start.base(), __len);
1054           __throw_exception_again;
1055         }
1056       _Destroy(_M_start, _M_finish);
1057       _M_deallocate(_M_start, _M_end_of_storage - _M_start);
1058       _M_start = __new_start.base();
1059       _M_finish = __new_finish.base();
1060       _M_end_of_storage = __new_start.base() + __len;
1061     }
1062   }
1063 }
1064
1065 } // namespace std
1066
1067 #endif /* __GLIBCPP_INTERNAL_VECTOR_H */
1068
1069 // Local Variables:
1070 // mode:C++
1071 // End: