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

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