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

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