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