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

   1 // Vector implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002 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   /// @if maint Primary default version.  @endif
  71   /**
  72    *  @if maint
  73    *  See bits/stl_deque.h's _Deque_alloc_base for an explanation.
  74    *  @endif
  75   */
  76   template <typename _Tp, typename _Allocator, bool _IsStatic>
  77     class _Vector_alloc_base
  78   {
  79   public:
  80     typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
  81             allocator_type;
  82
  83     allocator_type
  84     get_allocator() const { return _M_data_allocator; }
  85
  86     _Vector_alloc_base(const allocator_type& __a)
  87       : _M_data_allocator(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
  88     {}
  89
  90   protected:
  91     allocator_type _M_data_allocator;
  92     _Tp*           _M_start;
  93     _Tp*           _M_finish;
  94     _Tp*           _M_end_of_storage;
  95
  96     _Tp*
  97     _M_allocate(size_t __n) { return _M_data_allocator.allocate(__n); }
  98
  99     void
 100     _M_deallocate(_Tp* __p, size_t __n)
 101     { if (__p) _M_data_allocator.deallocate(__p, __n); }
 102   };
 103
 104   /// @if maint Specialization for instanceless allocators.  @endif
 105   template <typename _Tp, typename _Allocator>
 106     class _Vector_alloc_base<_Tp, _Allocator, true>
 107   {
 108   public:
 109     typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
 110             allocator_type;
 111
 112     allocator_type
 113     get_allocator() const { return allocator_type(); }
 114
 115     _Vector_alloc_base(const allocator_type&)
 116       : _M_start(0), _M_finish(0), _M_end_of_storage(0)
 117     {}
 118
 119   protected:
 120     _Tp* _M_start;
 121     _Tp* _M_finish;
 122     _Tp* _M_end_of_storage;
 123
 124     typedef typename _Alloc_traits<_Tp, _Allocator>::_Alloc_type _Alloc_type;
 125
 126     _Tp*
 127     _M_allocate(size_t __n) { return _Alloc_type::allocate(__n); }
 128
 129     void
 130     _M_deallocate(_Tp* __p, size_t __n) { _Alloc_type::deallocate(__p, __n);}
 131   };
 132
 133
 134   /**
 135    *  @if maint
 136    *  See bits/stl_deque.h's _Deque_base for an explanation.
 137    *  @endif
 138   */
 139   template <typename _Tp, typename _Alloc>
 140     struct _Vector_base
 141     : public _Vector_alloc_base<_Tp, _Alloc,
 142                                 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
 143   {
 144   public:
 145     typedef _Vector_alloc_base<_Tp, _Alloc,
 146                                _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
 147             _Base;
 148     typedef typename _Base::allocator_type allocator_type;
 149
 150     _Vector_base(const allocator_type& __a)
 151       : _Base(__a) {}
 152     _Vector_base(size_t __n, const allocator_type& __a)
 153       : _Base(__a)
 154     {
 155       _M_start = _M_allocate(__n);
 156       _M_finish = _M_start;
 157       _M_end_of_storage = _M_start + __n;
 158     }
 159
 160     ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
 161   };
 162
 163
 164   /**
 165    *  @brief  A standard container which offers fixed time access to individual
 166    *  elements in any order.
 167    *
 168    *  @ingroup Containers
 169    *  @ingroup Sequences
 170    *
 171    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
 172    *  <a href="tables.html#66">reversible container</a>, and a
 173    *  <a href="tables.html#67">sequence</a>, including the
 174    *  <a href="tables.html#68">optional sequence requirements</a> with the
 175    *  %exception of @c push_front and @c pop_front.
 176    *
 177    *  In some terminology a %vector can be described as a dynamic C-style array,
 178    *  it offers fast and efficient access to individual elements in any order
 179    *  and saves the user from worrying about memory and size allocation.
 180    *  Subscripting ( @c [] ) access is also provided as with C-style arrays.
 181   */
 182   template <typename _Tp, typename _Alloc = allocator<_Tp> >
 183     class vector : protected _Vector_base<_Tp, _Alloc>
 184   {
 185     // concept requirements
 186     __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
 187
 188     typedef _Vector_base<_Tp, _Alloc>                     _Base;
 189     typedef vector<_Tp, _Alloc>                           vector_type;
 190
 191   public:
 192     typedef _Tp                                                 value_type;
 193     typedef value_type*                                         pointer;
 194     typedef const value_type*                           const_pointer;
 195     typedef __gnu_cxx::__normal_iterator<pointer, vector_type>  iterator;
 196     typedef __gnu_cxx::__normal_iterator<const_pointer, vector_type>
 197                                                           const_iterator;
 198     typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
 199     typedef std::reverse_iterator<iterator>                reverse_iterator;
 200     typedef value_type&                                         reference;
 201     typedef const value_type&                           const_reference;
 202     typedef size_t                                      size_type;
 203     typedef ptrdiff_t                                   difference_type;
 204     typedef typename _Base::allocator_type                allocator_type;
 205
 206   protected:
 207     /** @if maint
 208      *  These two functions and three data members are all from the top-most
 209      *  base class, which varies depending on the type of %allocator.  They
 210      *  should be pretty self-explanatory, as %vector uses a simple contiguous
 211      *  allocation scheme.
 212      *  @endif
 213     */
 214     using _Base::_M_allocate;
 215     using _Base::_M_deallocate;
 216     using _Base::_M_start;
 217     using _Base::_M_finish;
 218     using _Base::_M_end_of_storage;
 219
 220   public:
 221     // [23.2.4.1] construct/copy/destroy
 222     // (assign() and get_allocator() are also listed in this section)
 223     /**
 224      *  @brief  Default constructor creates no elements.
 225     */
 226     explicit
 227     vector(const allocator_type& __a = allocator_type())
 228       : _Base(__a) {}
 229
 230     /**
 231      *  @brief  Create a %vector with copies of an exemplar element.
 232      *  @param  n  The number of elements to initially create.
 233      *  @param  value  An element to copy.
 234      *
 235      *  This constructor fills the %vector with @a n copies of @a value.
 236     */
 237     vector(size_type __n, const value_type& __value,
 238            const allocator_type& __a = allocator_type())
 239       : _Base(__n, __a)
 240       { _M_finish = uninitialized_fill_n(_M_start, __n, __value); }
 241
 242     /**
 243      *  @brief  Create a %vector with default elements.
 244      *  @param  n  The number of elements to initially create.
 245      *
 246      *  This constructor fills the %vector with @a n copies of a
 247      *  default-constructed element.
 248     */
 249     explicit
 250     vector(size_type __n)
 251       : _Base(__n, allocator_type())
 252       { _M_finish = uninitialized_fill_n(_M_start, __n, value_type()); }
 253
 254     /**
 255      *  @brief  %Vector copy constructor.
 256      *  @param  x  A %vector of identical element and allocator types.
 257      *
 258      *  The newly-created %vector uses a copy of the allocation object used
 259      *  by @a x.  All the elements of @a x are copied, but any extra memory in
 260      *  @a x (for fast expansion) will not be copied.
 261     */
 262     vector(const vector& __x)
 263       : _Base(__x.size(), __x.get_allocator())
 264       { _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); }
 265
 266     /**
 267      *  @brief  Builds a %vector from a range.
 268      *  @param  first  An input iterator.
 269      *  @param  last  An input iterator.
 270      *
 271      *  Create a %vector consisting of copies of the elements from [first,last).
 272      *
 273      *  If the iterators are forward, bidirectional, or random-access, then
 274      *  this will call the elements' copy constructor N times (where N is
 275      *  distance(first,last)) and do no memory reallocation.  But if only
 276      *  input iterators are used, then this will do at most 2N calls to the
 277      *  copy constructor, and logN memory reallocations.
 278     */
 279     template <typename _InputIterator>
 280       vector(_InputIterator __first, _InputIterator __last,
 281              const allocator_type& __a = allocator_type())
 282         : _Base(__a)
 283       {
 284         // Check whether it's an integral type.  If so, it's not an iterator.
 285         typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 286         _M_initialize_dispatch(__first, __last, _Integral());
 287       }
 288
 289     /**
 290      *  The dtor only erases the elements, and note that if the elements
 291      *  themselves are pointers, the pointed-to memory is not touched in any
 292      *  way.  Managing the pointer is the user's responsibilty.
 293     */
 294     ~vector() { _Destroy(_M_start, _M_finish); }
 295
 296     /**
 297      *  @brief  %Vector assignment operator.
 298      *  @param  x  A %vector of identical element and allocator types.
 299      *
 300      *  All the elements of @a x are copied, but any extra memory in @a x (for
 301      *  fast expansion) will not be copied.  Unlike the copy constructor, the
 302      *  allocator object is not copied.
 303     */
 304     vector&
 305     operator=(const vector& __x);
 306
 307     /**
 308      *  @brief  Assigns a given value to a %vector.
 309      *  @param  n  Number of elements to be assigned.
 310      *  @param  val  Value to be assigned.
 311      *
 312      *  This function fills a %vector with @a n copies of the given value.
 313      *  Note that the assignment completely changes the %vector and that the
 314      *  resulting %vector's size is the same as the number of elements assigned.
 315      *  Old data may be lost.
 316     */
 317     void
 318     assign(size_type __n, const value_type& __val) { _M_fill_assign(__n, __val); }
 319
 320     /**
 321      *  @brief  Assigns a range to a %vector.
 322      *  @param  first  An input iterator.
 323      *  @param  last   An input iterator.
 324      *
 325      *  This function fills a %vector with copies of the elements in the
 326      *  range [first,last).
 327      *
 328      *  Note that the assignment completely changes the %vector and that the
 329      *  resulting %vector's size is the same as the number of elements assigned.
 330      *  Old data may be lost.
 331     */
 332     template<typename _InputIterator>
 333       void
 334       assign(_InputIterator __first, _InputIterator __last)
 335       {
 336         // Check whether it's an integral type.  If so, it's not an iterator.
 337         typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 338         _M_assign_dispatch(__first, __last, _Integral());
 339       }
 340
 341     /// Get a copy of the memory allocation object.
 342     allocator_type
 343     get_allocator() const { return _Base::get_allocator(); }
 344
 345     // iterators
 346     /**
 347      *  Returns a read/write iterator that points to the first element in the
 348      *  %vector.  Iteration is done in ordinary element order.
 349     */
 350     iterator
 351     begin() { return iterator (_M_start); }
 352
 353     /**
 354      *  Returns a read-only (constant) iterator that points to the first element
 355      *  in the %vector.  Iteration is done in ordinary element order.
 356     */
 357     const_iterator
 358     begin() const { return const_iterator (_M_start); }
 359
 360     /**
 361      *  Returns a read/write iterator that points one past the last element in
 362      *  the %vector.  Iteration is done in ordinary element order.
 363     */
 364     iterator
 365     end() { return iterator (_M_finish); }
 366
 367     /**
 368      *  Returns a read-only (constant) iterator that points one past the last
 369      *  element in the %vector.  Iteration is done in ordinary element order.
 370     */
 371     const_iterator
 372     end() const { return const_iterator (_M_finish); }
 373
 374     /**
 375      *  Returns a read/write reverse iterator that points to the last element in
 376      *  the %vector.  Iteration is done in reverse element order.
 377     */
 378     reverse_iterator
 379     rbegin() { return reverse_iterator(end()); }
 380
 381     /**
 382      *  Returns a read-only (constant) reverse iterator that points to the last
 383      *  element in the %vector.  Iteration is done in reverse element order.
 384     */
 385     const_reverse_iterator
 386     rbegin() const { return const_reverse_iterator(end()); }
 387
 388     /**
 389      *  Returns a read/write reverse iterator that points to one before the
 390      *  first element in the %vector.  Iteration is done in reverse element
 391      *  order.
 392     */
 393     reverse_iterator
 394     rend() { return reverse_iterator(begin()); }
 395
 396     /**
 397      *  Returns a read-only (constant) reverse iterator that points to one
 398      *  before the first element in the %vector.  Iteration is done in reverse
 399      *  element order.
 400     */
 401     const_reverse_iterator
 402     rend() const { return const_reverse_iterator(begin()); }
 403
 404     // [23.2.4.2] capacity
 405     /**  Returns the number of elements in the %vector.  */
 406     size_type
 407     size() const { return size_type(end() - begin()); }
 408
 409     /**  Returns the size() of the largest possible %vector.  */
 410     size_type
 411     max_size() const { return size_type(-1) / sizeof(value_type); }
 412
 413     /**
 414      *  @brief  Resizes the %vector to the specified number of elements.
 415      *  @param  new_size  Number of elements the %vector should contain.
 416      *  @param  x  Data with which new elements should be populated.
 417      *
 418      *  This function will %resize the %vector to the specified number of
 419      *  elements.  If the number is smaller than the %vector's current size the
 420      *  %vector is truncated, otherwise the %vector is extended and new elements
 421      *  are populated with given data.
 422     */
 423     void
 424     resize(size_type __new_size, const value_type& __x)
 425     {
 426       if (__new_size < size())
 427         erase(begin() + __new_size, end());
 428       else
 429         insert(end(), __new_size - size(), __x);
 430     }
 431
 432     /**
 433      *  @brief  Resizes the %vector to the specified number of elements.
 434      *  @param  new_size  Number of elements the %vector should contain.
 435      *
 436      *  This function will resize the %vector to the specified number of
 437      *  elements.  If the number is smaller than the %vector's current size the
 438      *  %vector is truncated, otherwise the %vector is extended and new elements
 439      *  are default-constructed.
 440     */
 441     void
 442     resize(size_type __new_size) { resize(__new_size, value_type()); }
 443
 444     /**
 445      *  Returns the total number of elements that the %vector can hold before
 446      *  needing to allocate more memory.
 447     */
 448     size_type
 449     capacity() const
 450     { return size_type(const_iterator(_M_end_of_storage) - begin()); }
 451
 452     /**
 453      *  Returns true if the %vector is empty.  (Thus begin() would equal end().)
 454     */
 455     bool
 456     empty() const { return begin() == end(); }
 457
 458     /**
 459      *  @brief  Attempt to preallocate enough memory for specified number of
 460      *          elements.
 461      *  @param  n  Number of elements required.
 462      *  @throw  std::length_error  If @a n exceeds @c max_size().
 463      *
 464      *  This function attempts to reserve enough memory for the %vector to hold
 465      *  the specified number of elements.  If the number requested is more than
 466      *  max_size(), length_error is thrown.
 467      *
 468      *  The advantage of this function is that if optimal code is a necessity
 469      *  and the user can determine the number of elements that will be required,
 470      *  the user can reserve the memory in %advance, and thus prevent a possible
 471      *  reallocation of memory and copying of %vector data.
 472     */
 473     void
 474     reserve(size_type __n);
 475
 476     // element access
 477     /**
 478      *  @brief  Subscript access to the data contained in the %vector.
 479      *  @param  n  The index of the element for which data should be accessed.
 480      *  @return  Read/write reference to data.
 481      *
 482      *  This operator allows for easy, array-style, data access.
 483      *  Note that data access with this operator is unchecked and out_of_range
 484      *  lookups are not defined. (For checked lookups see at().)
 485     */
 486     reference
 487     operator[](size_type __n) { return *(begin() + __n); }
 488
 489     /**
 490      *  @brief  Subscript access to the data contained in the %vector.
 491      *  @param  n  The index of the element for which data should be accessed.
 492      *  @return  Read-only (constant) reference to data.
 493      *
 494      *  This operator allows for easy, array-style, data access.
 495      *  Note that data access with this operator is unchecked and out_of_range
 496      *  lookups are not defined. (For checked lookups see at().)
 497     */
 498     const_reference
 499     operator[](size_type __n) const { return *(begin() + __n); }
 500
 501   protected:
 502     /// @if maint Safety check used only from at().  @endif
 503     void
 504     _M_range_check(size_type __n) const
 505     {
 506       if (__n >= this->size())
 507         __throw_out_of_range("vector [] access out of range");
 508     }
 509
 510   public:
 511     /**
 512      *  @brief  Provides access to the data contained in the %vector.
 513      *  @param  n  The index of the element for which data should be accessed.
 514      *  @return  Read/write reference to data.
 515      *  @throw  std::out_of_range  If @a n is an invalid index.
 516      *
 517      *  This function provides for safer data access.  The parameter is first
 518      *  checked that it is in the range of the vector.  The function throws
 519      *  out_of_range if the check fails.
 520     */
 521     reference
 522     at(size_type __n) { _M_range_check(__n); return (*this)[__n]; }
 523
 524     /**
 525      *  @brief  Provides access to the data contained in the %vector.
 526      *  @param  n  The index of the element for which data should be accessed.
 527      *  @return  Read-only (constant) reference to data.
 528      *  @throw  std::out_of_range  If @a n is an invalid index.
 529      *
 530      *  This function provides for safer data access.  The parameter is first
 531      *  checked that it is in the range of the vector.  The function throws
 532      *  out_of_range if the check fails.
 533     */
 534     const_reference
 535     at(size_type __n) const { _M_range_check(__n); return (*this)[__n]; }
 536
 537     /**
 538      *  Returns a read/write reference to the data at the first element of the
 539      *  %vector.
 540     */
 541     reference
 542     front() { return *begin(); }
 543
 544     /**
 545      *  Returns a read-only (constant) reference to the data at the first
 546      *  element of the %vector.
 547     */
 548     const_reference
 549     front() const { return *begin(); }
 550
 551     /**
 552      *  Returns a read/write reference to the data at the last element of the
 553      *  %vector.
 554     */
 555     reference
 556     back() { return *(end() - 1); }
 557
 558     /**
 559      *  Returns a read-only (constant) reference to the data at the last
 560      *  element of the %vector.
 561     */
 562     const_reference
 563     back() const { return *(end() - 1); }
 564
 565     // [23.2.4.3] modifiers
 566     /**
 567      *  @brief  Add data to the end of the %vector.
 568      *  @param  x  Data to be added.
 569      *
 570      *  This is a typical stack operation.  The function creates an element at
 571      *  the end of the %vector and assigns the given data to it.
 572      *  Due to the nature of a %vector this operation can be done in constant
 573      *  time if the %vector has preallocated space available.
 574     */
 575     void
 576     push_back(const value_type& __x)
 577     {
 578       if (_M_finish != _M_end_of_storage)
 579       {
 580         _Construct(_M_finish, __x);
 581         ++_M_finish;
 582       }
 583       else
 584         _M_insert_aux(end(), __x);
 585     }
 586
 587     /**
 588      *  @brief  Removes last element.
 589      *
 590      *  This is a typical stack operation. It shrinks the %vector by one.
 591      *
 592      *  Note that no data is returned, and if the last element's data is
 593      *  needed, it should be retrieved before pop_back() is called.
 594     */
 595     void
 596     pop_back()
 597     {
 598       --_M_finish;
 599       _Destroy(_M_finish);
 600     }
 601
 602     /**
 603      *  @brief  Inserts given value into %vector before specified iterator.
 604      *  @param  position  An iterator into the %vector.
 605      *  @param  x  Data to be inserted.
 606      *  @return  An iterator that points to the inserted data.
 607      *
 608      *  This function will insert a copy of the given value before the specified
 609      *  location.
 610      *  Note that this kind of operation could be expensive for a %vector and if
 611      *  it is frequently used the user should consider using std::list.
 612     */
 613     iterator
 614     insert(iterator __position, const value_type& __x);
 615
 616   #ifdef _GLIBCPP_DEPRECATED
 617     /**
 618      *  @brief  Inserts an element into the %vector.
 619      *  @param  position  An iterator into the %vector.
 620      *  @return  An iterator that points to the inserted element.
 621      *
 622      *  This function will insert a default-constructed element before the
 623      *  specified location.  You should consider using
 624      *  insert(position,value_type()) instead.
 625      *  Note that this kind of operation could be expensive for a vector and if
 626      *  it is frequently used the user should consider using std::list.
 627      *
 628      *  @note This was deprecated in 3.2 and will be removed in 3.4.  You must
 629      *        define @c _GLIBCPP_DEPRECATED to make this visible in 3.2; see
 630      *        c++config.h.
 631     */
 632     iterator
 633     insert(iterator __position)
 634     { return insert(__position, value_type()); }
 635   #endif
 636
 637     /**
 638      *  @brief  Inserts a number of copies of given data into the %vector.
 639      *  @param  position  An iterator into the %vector.
 640      *  @param  n  Number of elements to be inserted.
 641      *  @param  x  Data to be inserted.
 642      *
 643      *  This function will insert a specified number of copies of the given data
 644      *  before the location specified by @a position.
 645      *
 646      *  Note that this kind of operation could be expensive for a %vector and if
 647      *  it is frequently used the user should consider using std::list.
 648     */
 649     void
 650     insert (iterator __pos, size_type __n, const value_type& __x)
 651     { _M_fill_insert(__pos, __n, __x); }
 652
 653     /**
 654      *  @brief  Inserts a range into the %vector.
 655      *  @param  pos  An iterator into the %vector.
 656      *  @param  first  An input iterator.
 657      *  @param  last   An input iterator.
 658      *
 659      *  This function will insert copies of the data in the range [first,last)
 660      *  into the %vector before the location specified by @a pos.
 661      *
 662      *  Note that this kind of operation could be expensive for a %vector and if
 663      *  it is frequently used the user should consider using std::list.
 664     */
 665     template<typename _InputIterator>
 666       void
 667       insert(iterator __pos, _InputIterator __first, _InputIterator __last)
 668         {
 669           // Check whether it's an integral type.  If so, it's not an iterator.
 670           typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
 671           _M_insert_dispatch(__pos, __first, __last, _Integral());
 672         }
 673
 674     /**
 675      *  @brief  Remove element at given position.
 676      *  @param  position  Iterator pointing to element to be erased.
 677      *  @return  An iterator pointing to the next element (or end()).
 678      *
 679      *  This function will erase the element at the given position and thus
 680      *  shorten the %vector by one.
 681      *
 682      *  Note This operation could be expensive and if it is frequently used the
 683      *  user should consider using std::list.  The user is also cautioned that
 684      *  this function only erases the element, and that if the element is itself
 685      *  a pointer, the pointed-to memory is not touched in any way.  Managing
 686      *  the pointer is the user's responsibilty.
 687     */
 688     iterator
 689     erase(iterator __position);
 690
 691     /**
 692      *  @brief  Remove a range of elements.
 693      *  @param  first  Iterator pointing to the first element to be erased.
 694      *  @param  last  Iterator pointing to one past the last element to be
 695      *                erased.
 696      *  @return  An iterator pointing to the element pointed to by @a last
 697      *           prior to erasing (or end()).
 698      *
 699      *  This function will erase the elements in the range [first,last) and
 700      *  shorten the %vector accordingly.
 701      *
 702      *  Note This operation could be expensive and if it is frequently used the
 703      *  user should consider using std::list.  The user is also cautioned that
 704      *  this function only erases the elements, and that if the elements
 705      *  themselves are pointers, the pointed-to memory is not touched in any
 706      *  way.  Managing the pointer is the user's responsibilty.
 707     */
 708     iterator
 709     erase(iterator __first, iterator __last);
 710
 711     /**
 712      *  @brief  Swaps data with another %vector.
 713      *  @param  x  A %vector of the same element and allocator types.
 714      *
 715      *  This exchanges the elements between two vectors in constant time.
 716      *  (Three pointers, so it should be quite fast.)
 717      *  Note that the global std::swap() function is specialized such that
 718      *  std::swap(v1,v2) will feed to this function.
 719     */
 720     void
 721     swap(vector& __x)
 722     {
 723       std::swap(_M_start, __x._M_start);
 724       std::swap(_M_finish, __x._M_finish);
 725       std::swap(_M_end_of_storage, __x._M_end_of_storage);
 726     }
 727
 728     /**
 729      *  Erases all the elements.  Note that this function only erases the
 730      *  elements, and that if the elements themselves are pointers, the
 731      *  pointed-to memory is not touched in any way.  Managing the pointer is
 732      *  the user's responsibilty.
 733     */
 734     void
 735     clear() { erase(begin(), end()); }
 736
 737   protected:
 738     /**
 739      *  @if maint
 740      *  Memory expansion handler.  Uses the member allocation function to
 741      *  obtain @a n bytes of memory, and then copies [first,last) into it.
 742      *  @endif
 743     */
 744     template <typename _ForwardIterator>
 745     pointer
 746       _M_allocate_and_copy(size_type __n,
 747                            _ForwardIterator __first, _ForwardIterator __last)
 748     {
 749       pointer __result = _M_allocate(__n);
 750       try
 751         {
 752           uninitialized_copy(__first, __last, __result);
 753           return __result;
 754         }
 755       catch(...)
 756         {
 757         _M_deallocate(__result, __n);
 758         __throw_exception_again;
 759         }
 760     }
 761
 762
 763     // Internal constructor functions follow.
 764
 765     // called by the range constructor to implement [23.1.1]/9
 766     template<typename _Integer>
 767       void
 768       _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
 769       {
 770         _M_start = _M_allocate(__n);
 771         _M_end_of_storage = _M_start + __n;
 772         _M_finish = uninitialized_fill_n(_M_start, __n, __value);
 773       }
 774
 775     // called by the range constructor to implement [23.1.1]/9
 776     template<typename _InputIter>
 777       void
 778       _M_initialize_dispatch(_InputIter __first, _InputIter __last,
 779                              __false_type)
 780       {
 781         typedef typename iterator_traits<_InputIter>::iterator_category
 782                          _IterCategory;
 783         _M_range_initialize(__first, __last, _IterCategory());
 784       }
 785
 786     // called by the second initialize_dispatch above
 787     template <typename _InputIterator>
 788     void
 789       _M_range_initialize(_InputIterator __first,
 790                           _InputIterator __last, input_iterator_tag)
 791     {
 792       for ( ; __first != __last; ++__first)
 793         push_back(*__first);
 794     }
 795
 796     // called by the second initialize_dispatch above
 797     template <typename _ForwardIterator>
 798     void _M_range_initialize(_ForwardIterator __first,
 799                              _ForwardIterator __last, forward_iterator_tag)
 800     {
 801       size_type __n = distance(__first, __last);
 802       _M_start = _M_allocate(__n);
 803       _M_end_of_storage = _M_start + __n;
 804       _M_finish = uninitialized_copy(__first, __last, _M_start);
 805     }
 806
 807
 808     // Internal assign functions follow.  The *_aux functions do the actual
 809     // assignment work for the range versions.
 810
 811     // called by the range assign to implement [23.1.1]/9
 812     template<typename _Integer>
 813       void
 814        _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
 815        {
 816          _M_fill_assign(static_cast<size_type>(__n),
 817                         static_cast<value_type>(__val));
 818        }
 819
 820     // called by the range assign to implement [23.1.1]/9
 821     template<typename _InputIter>
 822       void
 823       _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
 824       {
 825         typedef typename iterator_traits<_InputIter>::iterator_category
 826                          _IterCategory;
 827         _M_assign_aux(__first, __last, _IterCategory());
 828       }
 829
 830     // called by the second assign_dispatch above
 831     template <typename _InputIterator>
 832       void
 833       _M_assign_aux(_InputIterator __first, _InputIterator __last,
 834                   input_iterator_tag);
 835
 836     // called by the second assign_dispatch above
 837     template <typename _ForwardIterator>
 838       void
 839       _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
 840                   forward_iterator_tag);
 841
 842     // Called by assign(n,t), and the range assign when it turns out to be the
 843     // same thing.
 844     void
 845     _M_fill_assign(size_type __n, const value_type& __val);
 846
 847
 848     // Internal insert functions follow.
 849
 850     // called by the range insert to implement [23.1.1]/9
 851     template<typename _Integer>
 852       void
 853       _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
 854                          __true_type)
 855       {
 856         _M_fill_insert(__pos, static_cast<size_type>(__n),
 857                               static_cast<value_type>(__val));
 858       }
 859
 860     // called by the range insert to implement [23.1.1]/9
 861     template<typename _InputIterator>
 862       void
 863       _M_insert_dispatch(iterator __pos, _InputIterator __first,
 864                          _InputIterator __last, __false_type)
 865       {
 866         typedef typename iterator_traits<_InputIterator>::iterator_category
 867                          _IterCategory;
 868         _M_range_insert(__pos, __first, __last, _IterCategory());
 869       }
 870
 871     // called by the second insert_dispatch above
 872     template <typename _InputIterator>
 873       void
 874       _M_range_insert(iterator __pos,
 875                       _InputIterator __first, _InputIterator __last,
 876                       input_iterator_tag);
 877
 878     // called by the second insert_dispatch above
 879     template <typename _ForwardIterator>
 880       void
 881       _M_range_insert(iterator __pos,
 882                       _ForwardIterator __first, _ForwardIterator __last,
 883                       forward_iterator_tag);
 884
 885     // Called by insert(p,n,x), and the range insert when it turns out to be
 886     // the same thing.
 887     void
 888     _M_fill_insert (iterator __pos, size_type __n, const value_type& __x);
 889
 890     // called by insert(p,x)
 891     void
 892     _M_insert_aux(iterator __position, const value_type& __x);
 893
 894   #ifdef _GLIBCPP_DEPRECATED
 895     // unused now (same situation as in deque)
 896     void _M_insert_aux(iterator __position);
 897   #endif
 898   };
 899
 900
 901   /**
 902    *  @brief  Vector equality comparison.
 903    *  @param  x  A %vector.
 904    *  @param  y  A %vector of the same type as @a x.
 905    *  @return  True iff the size and elements of the vectors are equal.
 906    *
 907    *  This is an equivalence relation.  It is linear in the size of the
 908    *  vectors.  Vectors are considered equivalent if their sizes are equal,
 909    *  and if corresponding elements compare equal.
 910   */
 911   template <typename _Tp, typename _Alloc>
 912     inline bool
 913     operator==(const vector<_Tp,_Alloc>& __x, const vector<_Tp,_Alloc>& __y)
 914     {
 915       return __x.size() == __y.size() &&
 916              equal(__x.begin(), __x.end(), __y.begin());
 917     }
 918
 919   /**
 920    *  @brief  Vector ordering relation.
 921    *  @param  x  A %vector.
 922    *  @param  y  A %vector of the same type as @a x.
 923    *  @return  True iff @a x is lexographically less than @a y.
 924    *
 925    *  This is a total ordering relation.  It is linear in the size of the
 926    *  vectors.  The elements must be comparable with @c <.
 927    *
 928    *  See std::lexographical_compare() for how the determination is made.
 929   */
 930   template <typename _Tp, typename _Alloc>
 931     inline bool
 932     operator<(const vector<_Tp,_Alloc>& __x, const vector<_Tp,_Alloc>& __y)
 933     {
 934       return lexicographical_compare(__x.begin(), __x.end(),
 935                                      __y.begin(), __y.end());
 936     }
 937
 938   /// Based on operator==
 939   template <typename _Tp, typename _Alloc>
 940     inline bool
 941     operator!=(const vector<_Tp,_Alloc>& __x, const vector<_Tp,_Alloc>& __y)
 942     { return !(__x == __y); }
 943
 944   /// Based on operator<
 945   template <typename _Tp, typename _Alloc>
 946     inline bool
 947     operator>(const vector<_Tp,_Alloc>& __x, const vector<_Tp,_Alloc>& __y)
 948     { return __y < __x; }
 949
 950   /// Based on operator<
 951   template <typename _Tp, typename _Alloc>
 952     inline bool
 953     operator<=(const vector<_Tp,_Alloc>& __x, const vector<_Tp,_Alloc>& __y)
 954     { return !(__y < __x); }
 955
 956   /// Based on operator<
 957   template <typename _Tp, typename _Alloc>
 958     inline bool
 959     operator>=(const vector<_Tp,_Alloc>& __x, const vector<_Tp,_Alloc>& __y)
 960     { return !(__x < __y); }
 961
 962   /// See std::vector::swap().
 963   template <typename _Tp, typename _Alloc>
 964     inline void
 965     swap(vector<_Tp,_Alloc>& __x, vector<_Tp,_Alloc>& __y)
 966     { __x.swap(__y); }
 967 } // namespace std
 968
 969 #endif /* __GLIBCPP_INTERNAL_VECTOR_H */