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

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