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

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