stl_vector.h

Go to the documentation of this file.
00001 // Vector implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /*
00031  *
00032  * Copyright (c) 1994
00033  * Hewlett-Packard Company
00034  *
00035  * Permission to use, copy, modify, distribute and sell this software
00036  * and its documentation for any purpose is hereby granted without fee,
00037  * provided that the above copyright notice appear in all copies and
00038  * that both that copyright notice and this permission notice appear
00039  * in supporting documentation.  Hewlett-Packard Company makes no
00040  * representations about the suitability of this software for any
00041  * purpose.  It is provided "as is" without express or implied warranty.
00042  *
00043  *
00044  * Copyright (c) 1996
00045  * Silicon Graphics Computer Systems, Inc.
00046  *
00047  * Permission to use, copy, modify, distribute and sell this software
00048  * and its documentation for any purpose is hereby granted without fee,
00049  * provided that the above copyright notice appear in all copies and
00050  * that both that copyright notice and this permission notice appear
00051  * in supporting documentation.  Silicon Graphics makes no
00052  * representations about the suitability of this  software for any
00053  * purpose.  It is provided "as is" without express or implied warranty.
00054  */
00055 
00056 /** @file stl_vector.h
00057  *  This is an internal header file, included by other library headers.
00058  *  You should not attempt to use it directly.
00059  */
00060 
00061 #ifndef _VECTOR_H
00062 #define _VECTOR_H 1
00063 
00064 #include <bits/stl_iterator_base_funcs.h>
00065 #include <bits/functexcept.h>
00066 #include <bits/concept_check.h>
00067 
00068 namespace _GLIBCXX_STD
00069 {
00070   /**
00071    *  @if maint
00072    *  See bits/stl_deque.h's _Deque_base for an explanation.
00073    *  @endif
00074   */
00075   template<typename _Tp, typename _Alloc>
00076     struct _Vector_base
00077     {
00078       struct _Vector_impl 
00079     : public _Alloc {
00080     _Tp*           _M_start;
00081     _Tp*           _M_finish;
00082     _Tp*           _M_end_of_storage;
00083     _Vector_impl (_Alloc const& __a)
00084       : _Alloc(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
00085     { }
00086       };
00087       
00088     public:
00089       typedef _Alloc allocator_type;
00090 
00091       allocator_type
00092       get_allocator() const { return *static_cast<const _Alloc*>(&this->_M_impl); }
00093 
00094       _Vector_base(const allocator_type& __a) : _M_impl(__a)
00095       { }
00096 
00097       _Vector_base(size_t __n, const allocator_type& __a)
00098     : _M_impl(__a)
00099       {
00100     this->_M_impl._M_start = this->_M_allocate(__n);
00101     this->_M_impl._M_finish = this->_M_impl._M_start;
00102     this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
00103       }
00104 
00105       ~_Vector_base()
00106       { _M_deallocate(this->_M_impl._M_start,
00107               this->_M_impl._M_end_of_storage - this->_M_impl._M_start); }
00108 
00109     public:
00110       _Vector_impl _M_impl;
00111 
00112       _Tp*
00113       _M_allocate(size_t __n) { return _M_impl.allocate(__n); }
00114 
00115       void
00116       _M_deallocate(_Tp* __p, size_t __n)
00117       { if (__p) _M_impl.deallocate(__p, __n); }
00118     };
00119 
00120 
00121   /**
00122    *  @brief A standard container which offers fixed time access to
00123    *  individual elements in any order.
00124    *
00125    *  @ingroup Containers
00126    *  @ingroup Sequences
00127    *
00128    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
00129    *  <a href="tables.html#66">reversible container</a>, and a
00130    *  <a href="tables.html#67">sequence</a>, including the
00131    *  <a href="tables.html#68">optional sequence requirements</a> with the
00132    *  %exception of @c push_front and @c pop_front.
00133    *
00134    *  In some terminology a %vector can be described as a dynamic
00135    *  C-style array, it offers fast and efficient access to individual
00136    *  elements in any order and saves the user from worrying about
00137    *  memory and size allocation.  Subscripting ( @c [] ) access is
00138    *  also provided as with C-style arrays.
00139   */
00140   template<typename _Tp, typename _Alloc = allocator<_Tp> >
00141     class vector : protected _Vector_base<_Tp, _Alloc>
00142     {
00143       // Concept requirements.
00144       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00145 
00146       typedef _Vector_base<_Tp, _Alloc>         _Base;
00147       typedef vector<_Tp, _Alloc>           vector_type;
00148 
00149     public:
00150       typedef _Tp                    value_type;
00151       typedef typename _Alloc::pointer                   pointer;
00152       typedef typename _Alloc::const_pointer             const_pointer;
00153       typedef typename _Alloc::reference                 reference;
00154       typedef typename _Alloc::const_reference           const_reference;
00155       typedef __gnu_cxx::__normal_iterator<pointer, vector_type> iterator;
00156       typedef __gnu_cxx::__normal_iterator<const_pointer, vector_type>
00157       const_iterator;
00158       typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
00159       typedef std::reverse_iterator<iterator>        reverse_iterator;
00160       typedef size_t                     size_type;
00161       typedef ptrdiff_t                  difference_type;
00162       typedef typename _Base::allocator_type         allocator_type;
00163 
00164     protected:
00165       /** @if maint
00166        *  These two functions and three data members are all from the
00167        *  base class.  They should be pretty self-explanatory, as
00168        *  %vector uses a simple contiguous allocation scheme.  @endif
00169        */
00170       using _Base::_M_allocate;
00171       using _Base::_M_deallocate;
00172       using _Base::_M_impl;
00173 
00174     public:
00175       // [23.2.4.1] construct/copy/destroy
00176       // (assign() and get_allocator() are also listed in this section)
00177       /**
00178        *  @brief  Default constructor creates no elements.
00179        */
00180       explicit
00181       vector(const allocator_type& __a = allocator_type())
00182       : _Base(__a) { }
00183 
00184       /**
00185        *  @brief  Create a %vector with copies of an exemplar element.
00186        *  @param  n  The number of elements to initially create.
00187        *  @param  value  An element to copy.
00188        *
00189        *  This constructor fills the %vector with @a n copies of @a value.
00190        */
00191       vector(size_type __n, const value_type& __value,
00192          const allocator_type& __a = allocator_type())
00193       : _Base(__n, __a)
00194       { this->_M_impl._M_finish = std::uninitialized_fill_n(this->_M_impl._M_start,
00195                             __n, __value); }
00196 
00197       /**
00198        *  @brief  Create a %vector with default elements.
00199        *  @param  n  The number of elements to initially create.
00200        *
00201        *  This constructor fills the %vector with @a n copies of a
00202        *  default-constructed element.
00203        */
00204       explicit
00205       vector(size_type __n)
00206       : _Base(__n, allocator_type())
00207       { this->_M_impl._M_finish = std::uninitialized_fill_n(this->_M_impl._M_start,
00208                             __n, value_type()); }
00209 
00210       /**
00211        *  @brief  %Vector copy constructor.
00212        *  @param  x  A %vector of identical element and allocator types.
00213        *
00214        *  The newly-created %vector uses a copy of the allocation
00215        *  object used by @a x.  All the elements of @a x are copied,
00216        *  but any extra memory in
00217        *  @a x (for fast expansion) will not be copied.
00218        */
00219       vector(const vector& __x)
00220       : _Base(__x.size(), __x.get_allocator())
00221       { this->_M_impl._M_finish = std::uninitialized_copy(__x.begin(), __x.end(),
00222                           this->_M_impl._M_start);
00223       }
00224 
00225       /**
00226        *  @brief  Builds a %vector from a range.
00227        *  @param  first  An input iterator.
00228        *  @param  last  An input iterator.
00229        *
00230        *  Create a %vector consisting of copies of the elements from
00231        *  [first,last).
00232        *
00233        *  If the iterators are forward, bidirectional, or
00234        *  random-access, then this will call the elements' copy
00235        *  constructor N times (where N is distance(first,last)) and do
00236        *  no memory reallocation.  But if only input iterators are
00237        *  used, then this will do at most 2N calls to the copy
00238        *  constructor, and logN memory reallocations.
00239        */
00240       template<typename _InputIterator>
00241         vector(_InputIterator __first, _InputIterator __last,
00242            const allocator_type& __a = allocator_type())
00243     : _Base(__a)
00244         {
00245       // Check whether it's an integral type.  If so, it's not an iterator.
00246       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00247       _M_initialize_dispatch(__first, __last, _Integral());
00248     }
00249 
00250       /**
00251        *  The dtor only erases the elements, and note that if the
00252        *  elements themselves are pointers, the pointed-to memory is
00253        *  not touched in any way.  Managing the pointer is the user's
00254        *  responsibilty.
00255        */
00256       ~vector() { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); }
00257 
00258       /**
00259        *  @brief  %Vector assignment operator.
00260        *  @param  x  A %vector of identical element and allocator types.
00261        *
00262        *  All the elements of @a x are copied, but any extra memory in
00263        *  @a x (for fast expansion) will not be copied.  Unlike the
00264        *  copy constructor, the allocator object is not copied.
00265        */
00266       vector&
00267       operator=(const vector& __x);
00268 
00269       /**
00270        *  @brief  Assigns a given value to a %vector.
00271        *  @param  n  Number of elements to be assigned.
00272        *  @param  val  Value to be assigned.
00273        *
00274        *  This function fills a %vector with @a n copies of the given
00275        *  value.  Note that the assignment completely changes the
00276        *  %vector and that the resulting %vector's size is the same as
00277        *  the number of elements assigned.  Old data may be lost.
00278        */
00279       void
00280       assign(size_type __n, const value_type& __val)
00281       { _M_fill_assign(__n, __val); }
00282 
00283       /**
00284        *  @brief  Assigns a range to a %vector.
00285        *  @param  first  An input iterator.
00286        *  @param  last   An input iterator.
00287        *
00288        *  This function fills a %vector with copies of the elements in the
00289        *  range [first,last).
00290        *
00291        *  Note that the assignment completely changes the %vector and
00292        *  that the resulting %vector's size is the same as the number
00293        *  of elements assigned.  Old data may be lost.
00294        */
00295       template<typename _InputIterator>
00296         void
00297         assign(_InputIterator __first, _InputIterator __last)
00298         {
00299       // Check whether it's an integral type.  If so, it's not an iterator.
00300       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00301       _M_assign_dispatch(__first, __last, _Integral());
00302     }
00303 
00304       /// Get a copy of the memory allocation object.
00305       using _Base::get_allocator;
00306 
00307       // iterators
00308       /**
00309        *  Returns a read/write iterator that points to the first
00310        *  element in the %vector.  Iteration is done in ordinary
00311        *  element order.
00312        */
00313       iterator
00314       begin() { return iterator (this->_M_impl._M_start); }
00315 
00316       /**
00317        *  Returns a read-only (constant) iterator that points to the
00318        *  first element in the %vector.  Iteration is done in ordinary
00319        *  element order.
00320        */
00321       const_iterator
00322       begin() const { return const_iterator (this->_M_impl._M_start); }
00323 
00324       /**
00325        *  Returns a read/write iterator that points one past the last
00326        *  element in the %vector.  Iteration is done in ordinary
00327        *  element order.
00328        */
00329       iterator
00330       end() { return iterator (this->_M_impl._M_finish); }
00331 
00332       /**
00333        *  Returns a read-only (constant) iterator that points one past
00334        *  the last element in the %vector.  Iteration is done in
00335        *  ordinary element order.
00336        */
00337       const_iterator
00338       end() const { return const_iterator (this->_M_impl._M_finish); }
00339 
00340       /**
00341        *  Returns a read/write reverse iterator that points to the
00342        *  last element in the %vector.  Iteration is done in reverse
00343        *  element order.
00344        */
00345       reverse_iterator
00346       rbegin() { return reverse_iterator(end()); }
00347 
00348       /**
00349        *  Returns a read-only (constant) reverse iterator that points
00350        *  to the last element in the %vector.  Iteration is done in
00351        *  reverse element order.
00352        */
00353       const_reverse_iterator
00354       rbegin() const { return const_reverse_iterator(end()); }
00355 
00356       /**
00357        *  Returns a read/write reverse iterator that points to one
00358        *  before the first element in the %vector.  Iteration is done
00359        *  in reverse element order.
00360        */
00361       reverse_iterator
00362       rend() { return reverse_iterator(begin()); }
00363 
00364       /**
00365        *  Returns a read-only (constant) reverse iterator that points
00366        *  to one before the first element in the %vector.  Iteration
00367        *  is done in reverse element order.
00368        */
00369       const_reverse_iterator
00370       rend() const { return const_reverse_iterator(begin()); }
00371 
00372       // [23.2.4.2] capacity
00373       /**  Returns the number of elements in the %vector.  */
00374       size_type
00375       size() const { return size_type(end() - begin()); }
00376 
00377       /**  Returns the size() of the largest possible %vector.  */
00378       size_type
00379       max_size() const { return size_type(-1) / sizeof(value_type); }
00380 
00381       /**
00382        *  @brief  Resizes the %vector to the specified number of elements.
00383        *  @param  new_size  Number of elements the %vector should contain.
00384        *  @param  x  Data with which new elements should be populated.
00385        *
00386        *  This function will %resize the %vector to the specified
00387        *  number of elements.  If the number is smaller than the
00388        *  %vector's current size the %vector is truncated, otherwise
00389        *  the %vector is extended and new elements are populated with
00390        *  given data.
00391        */
00392       void
00393       resize(size_type __new_size, const value_type& __x)
00394       {
00395     if (__new_size < size())
00396       erase(begin() + __new_size, end());
00397     else
00398       insert(end(), __new_size - size(), __x);
00399       }
00400 
00401       /**
00402        *  @brief  Resizes the %vector to the specified number of elements.
00403        *  @param  new_size  Number of elements the %vector should contain.
00404        *
00405        *  This function will resize the %vector to the specified
00406        *  number of elements.  If the number is smaller than the
00407        *  %vector's current size the %vector is truncated, otherwise
00408        *  the %vector is extended and new elements are
00409        *  default-constructed.
00410        */
00411       void
00412       resize(size_type __new_size) { resize(__new_size, value_type()); }
00413 
00414       /**
00415        *  Returns the total number of elements that the %vector can
00416        *  hold before needing to allocate more memory.
00417        */
00418       size_type
00419       capacity() const
00420       { return size_type(const_iterator(this->_M_impl._M_end_of_storage) - begin()); }
00421 
00422       /**
00423        *  Returns true if the %vector is empty.  (Thus begin() would
00424        *  equal end().)
00425        */
00426       bool
00427       empty() const { return begin() == end(); }
00428 
00429       /**
00430        *  @brief  Attempt to preallocate enough memory for specified number of
00431        *          elements.
00432        *  @param  n  Number of elements required.
00433        *  @throw  std::length_error  If @a n exceeds @c max_size().
00434        *
00435        *  This function attempts to reserve enough memory for the
00436        *  %vector to hold the specified number of elements.  If the
00437        *  number requested is more than max_size(), length_error is
00438        *  thrown.
00439        *
00440        *  The advantage of this function is that if optimal code is a
00441        *  necessity and the user can determine the number of elements
00442        *  that will be required, the user can reserve the memory in
00443        *  %advance, and thus prevent a possible reallocation of memory
00444        *  and copying of %vector data.
00445        */
00446       void
00447       reserve(size_type __n);
00448 
00449       // element access
00450       /**
00451        *  @brief  Subscript access to the data contained in the %vector.
00452        *  @param n The index of the element for which data should be
00453        *  accessed.
00454        *  @return  Read/write reference to data.
00455        *
00456        *  This operator allows for easy, array-style, data access.
00457        *  Note that data access with this operator is unchecked and
00458        *  out_of_range lookups are not defined. (For checked lookups
00459        *  see at().)
00460        */
00461       reference
00462       operator[](size_type __n) { return *(begin() + __n); }
00463 
00464       /**
00465        *  @brief  Subscript access to the data contained in the %vector.
00466        *  @param n The index of the element for which data should be
00467        *  accessed.
00468        *  @return  Read-only (constant) reference to data.
00469        *
00470        *  This operator allows for easy, array-style, data access.
00471        *  Note that data access with this operator is unchecked and
00472        *  out_of_range lookups are not defined. (For checked lookups
00473        *  see at().)
00474        */
00475       const_reference
00476       operator[](size_type __n) const { return *(begin() + __n); }
00477 
00478     protected:
00479       /// @if maint Safety check used only from at().  @endif
00480       void
00481       _M_range_check(size_type __n) const
00482       {
00483     if (__n >= this->size())
00484       __throw_out_of_range(__N("vector::_M_range_check"));
00485       }
00486 
00487     public:
00488       /**
00489        *  @brief  Provides access to the data contained in the %vector.
00490        *  @param n The index of the element for which data should be
00491        *  accessed.
00492        *  @return  Read/write reference to data.
00493        *  @throw  std::out_of_range  If @a n is an invalid index.
00494        *
00495        *  This function provides for safer data access.  The parameter
00496        *  is first checked that it is in the range of the vector.  The
00497        *  function throws out_of_range if the check fails.
00498        */
00499       reference
00500       at(size_type __n) { _M_range_check(__n); return (*this)[__n]; }
00501 
00502       /**
00503        *  @brief  Provides access to the data contained in the %vector.
00504        *  @param n The index of the element for which data should be
00505        *  accessed.
00506        *  @return  Read-only (constant) reference to data.
00507        *  @throw  std::out_of_range  If @a n is an invalid index.
00508        *
00509        *  This function provides for safer data access.  The parameter
00510        *  is first checked that it is in the range of the vector.  The
00511        *  function throws out_of_range if the check fails.
00512        */
00513       const_reference
00514       at(size_type __n) const { _M_range_check(__n); return (*this)[__n]; }
00515 
00516       /**
00517        *  Returns a read/write reference to the data at the first
00518        *  element of the %vector.
00519        */
00520       reference
00521       front() { return *begin(); }
00522 
00523       /**
00524        *  Returns a read-only (constant) reference to the data at the first
00525        *  element of the %vector.
00526        */
00527       const_reference
00528       front() const { return *begin(); }
00529 
00530       /**
00531        *  Returns a read/write reference to the data at the last
00532        *  element of the %vector.
00533        */
00534       reference
00535       back() { return *(end() - 1); }
00536 
00537       /**
00538        *  Returns a read-only (constant) reference to the data at the
00539        *  last element of the %vector.
00540        */
00541       const_reference
00542       back() const { return *(end() - 1); }
00543 
00544       // [23.2.4.3] modifiers
00545       /**
00546        *  @brief  Add data to the end of the %vector.
00547        *  @param  x  Data to be added.
00548        *
00549        *  This is a typical stack operation.  The function creates an
00550        *  element at the end of the %vector and assigns the given data
00551        *  to it.  Due to the nature of a %vector this operation can be
00552        *  done in constant time if the %vector has preallocated space
00553        *  available.
00554        */
00555       void
00556       push_back(const value_type& __x)
00557       {
00558     if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
00559       {
00560         std::_Construct(this->_M_impl._M_finish, __x);
00561         ++this->_M_impl._M_finish;
00562       }
00563     else
00564       _M_insert_aux(end(), __x);
00565       }
00566 
00567       /**
00568        *  @brief  Removes last element.
00569        *
00570        *  This is a typical stack operation. It shrinks the %vector by one.
00571        *
00572        *  Note that no data is returned, and if the last element's
00573        *  data is needed, it should be retrieved before pop_back() is
00574        *  called.
00575        */
00576       void
00577       pop_back()
00578       {
00579     --this->_M_impl._M_finish;
00580     std::_Destroy(this->_M_impl._M_finish);
00581       }
00582 
00583       /**
00584        *  @brief  Inserts given value into %vector before specified iterator.
00585        *  @param  position  An iterator into the %vector.
00586        *  @param  x  Data to be inserted.
00587        *  @return  An iterator that points to the inserted data.
00588        *
00589        *  This function will insert a copy of the given value before
00590        *  the specified location.  Note that this kind of operation
00591        *  could be expensive for a %vector and if it is frequently
00592        *  used the user should consider using std::list.
00593        */
00594       iterator
00595       insert(iterator __position, const value_type& __x);
00596 
00597       /**
00598        *  @brief  Inserts a number of copies of given data into the %vector.
00599        *  @param  position  An iterator into the %vector.
00600        *  @param  n  Number of elements to be inserted.
00601        *  @param  x  Data to be inserted.
00602        *
00603        *  This function will insert a specified number of copies of
00604        *  the given data before the location specified by @a position.
00605        *
00606        *  Note that this kind of operation could be expensive for a
00607        *  %vector and if it is frequently used the user should
00608        *  consider using std::list.
00609        */
00610       void
00611       insert(iterator __position, size_type __n, const value_type& __x)
00612       { _M_fill_insert(__position, __n, __x); }
00613 
00614       /**
00615        *  @brief  Inserts a range into the %vector.
00616        *  @param  position  An iterator into the %vector.
00617        *  @param  first  An input iterator.
00618        *  @param  last   An input iterator.
00619        *
00620        *  This function will insert copies of the data in the range
00621        *  [first,last) into the %vector before the location specified
00622        *  by @a pos.
00623        *
00624        *  Note that this kind of operation could be expensive for a
00625        *  %vector and if it is frequently used the user should
00626        *  consider using std::list.
00627        */
00628       template<typename _InputIterator>
00629         void
00630         insert(iterator __position, _InputIterator __first,
00631            _InputIterator __last)
00632         {
00633       // Check whether it's an integral type.  If so, it's not an iterator.
00634       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00635       _M_insert_dispatch(__position, __first, __last, _Integral());
00636     }
00637 
00638       /**
00639        *  @brief  Remove element at given position.
00640        *  @param  position  Iterator pointing to element to be erased.
00641        *  @return  An iterator pointing to the next element (or end()).
00642        *
00643        *  This function will erase the element at the given position and thus
00644        *  shorten the %vector by one.
00645        *
00646        *  Note This operation could be expensive and if it is
00647        *  frequently used the user should consider using std::list.
00648        *  The user is also cautioned that this function only erases
00649        *  the element, and that if the element is itself a pointer,
00650        *  the pointed-to memory is not touched in any way.  Managing
00651        *  the pointer is the user's responsibilty.
00652        */
00653       iterator
00654       erase(iterator __position);
00655 
00656       /**
00657        *  @brief  Remove a range of elements.
00658        *  @param  first  Iterator pointing to the first element to be erased.
00659        *  @param  last  Iterator pointing to one past the last element to be
00660        *                erased.
00661        *  @return  An iterator pointing to the element pointed to by @a last
00662        *           prior to erasing (or end()).
00663        *
00664        *  This function will erase the elements in the range [first,last) and
00665        *  shorten the %vector accordingly.
00666        *
00667        *  Note This operation could be expensive and if it is
00668        *  frequently used the user should consider using std::list.
00669        *  The user is also cautioned that this function only erases
00670        *  the elements, and that if the elements themselves are
00671        *  pointers, the pointed-to memory is not touched in any way.
00672        *  Managing the pointer is the user's responsibilty.
00673        */
00674       iterator
00675       erase(iterator __first, iterator __last);
00676 
00677       /**
00678        *  @brief  Swaps data with another %vector.
00679        *  @param  x  A %vector of the same element and allocator types.
00680        *
00681        *  This exchanges the elements between two vectors in constant time.
00682        *  (Three pointers, so it should be quite fast.)
00683        *  Note that the global std::swap() function is specialized such that
00684        *  std::swap(v1,v2) will feed to this function.
00685        */
00686       void
00687       swap(vector& __x)
00688       {
00689     std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
00690     std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
00691     std::swap(this->_M_impl._M_end_of_storage, __x._M_impl._M_end_of_storage);
00692       }
00693 
00694       /**
00695        *  Erases all the elements.  Note that this function only erases the
00696        *  elements, and that if the elements themselves are pointers, the
00697        *  pointed-to memory is not touched in any way.  Managing the pointer is
00698        *  the user's responsibilty.
00699        */
00700       void
00701       clear() { erase(begin(), end()); }
00702 
00703     protected:
00704       /**
00705        *  @if maint
00706        *  Memory expansion handler.  Uses the member allocation function to
00707        *  obtain @a n bytes of memory, and then copies [first,last) into it.
00708        *  @endif
00709        */
00710       template<typename _ForwardIterator>
00711         pointer
00712         _M_allocate_and_copy(size_type __n,
00713                  _ForwardIterator __first, _ForwardIterator __last)
00714         {
00715       pointer __result = this->_M_allocate(__n);
00716       try
00717         {
00718           std::uninitialized_copy(__first, __last, __result);
00719           return __result;
00720         }
00721       catch(...)
00722         {
00723           _M_deallocate(__result, __n);
00724           __throw_exception_again;
00725         }
00726     }
00727 
00728 
00729       // Internal constructor functions follow.
00730 
00731       // Called by the range constructor to implement [23.1.1]/9
00732       template<typename _Integer>
00733         void
00734         _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
00735         {
00736       this->_M_impl._M_start = _M_allocate(__n);
00737       this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
00738       this->_M_impl._M_finish = std::uninitialized_fill_n(this->_M_impl._M_start,
00739                               __n, __value);
00740     }
00741 
00742       // Called by the range constructor to implement [23.1.1]/9
00743       template<typename _InputIterator>
00744         void
00745         _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
00746                    __false_type)
00747         {
00748       typedef typename iterator_traits<_InputIterator>::iterator_category
00749         _IterCategory;
00750       _M_range_initialize(__first, __last, _IterCategory());
00751     }
00752 
00753       // Called by the second initialize_dispatch above
00754       template<typename _InputIterator>
00755         void
00756         _M_range_initialize(_InputIterator __first,
00757                 _InputIterator __last, input_iterator_tag)
00758         {
00759       for ( ; __first != __last; ++__first)
00760         push_back(*__first);
00761     }
00762 
00763       // Called by the second initialize_dispatch above
00764       template<typename _ForwardIterator>
00765         void
00766         _M_range_initialize(_ForwardIterator __first,
00767                 _ForwardIterator __last, forward_iterator_tag)
00768         {
00769       size_type __n = std::distance(__first, __last);
00770       this->_M_impl._M_start = this->_M_allocate(__n);
00771       this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
00772       this->_M_impl._M_finish = std::uninitialized_copy(__first, __last,
00773                             this->_M_impl._M_start);
00774     }
00775 
00776 
00777       // Internal assign functions follow.  The *_aux functions do the actual
00778       // assignment work for the range versions.
00779 
00780       // Called by the range assign to implement [23.1.1]/9
00781       template<typename _Integer>
00782         void
00783         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
00784         {
00785       _M_fill_assign(static_cast<size_type>(__n),
00786              static_cast<value_type>(__val));
00787     }
00788 
00789       // Called by the range assign to implement [23.1.1]/9
00790       template<typename _InputIterator>
00791         void
00792         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
00793                __false_type)
00794         {
00795       typedef typename iterator_traits<_InputIterator>::iterator_category
00796         _IterCategory;
00797       _M_assign_aux(__first, __last, _IterCategory());
00798     }
00799 
00800       // Called by the second assign_dispatch above
00801       template<typename _InputIterator>
00802         void
00803         _M_assign_aux(_InputIterator __first, _InputIterator __last,
00804               input_iterator_tag);
00805 
00806       // Called by the second assign_dispatch above
00807       template<typename _ForwardIterator>
00808         void
00809         _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00810               forward_iterator_tag);
00811 
00812       // Called by assign(n,t), and the range assign when it turns out
00813       // to be the same thing.
00814       void
00815       _M_fill_assign(size_type __n, const value_type& __val);
00816 
00817 
00818       // Internal insert functions follow.
00819 
00820       // Called by the range insert to implement [23.1.1]/9
00821       template<typename _Integer>
00822         void
00823         _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
00824                __true_type)
00825         {
00826       _M_fill_insert(__pos, static_cast<size_type>(__n),
00827              static_cast<value_type>(__val));
00828     }
00829 
00830       // Called by the range insert to implement [23.1.1]/9
00831       template<typename _InputIterator>
00832         void
00833         _M_insert_dispatch(iterator __pos, _InputIterator __first,
00834                _InputIterator __last, __false_type)
00835         {
00836       typedef typename iterator_traits<_InputIterator>::iterator_category
00837         _IterCategory;
00838       _M_range_insert(__pos, __first, __last, _IterCategory());
00839     }
00840 
00841       // Called by the second insert_dispatch above
00842       template<typename _InputIterator>
00843         void
00844         _M_range_insert(iterator __pos, _InputIterator __first,
00845             _InputIterator __last, input_iterator_tag);
00846 
00847       // Called by the second insert_dispatch above
00848       template<typename _ForwardIterator>
00849         void
00850         _M_range_insert(iterator __pos, _ForwardIterator __first,
00851             _ForwardIterator __last, forward_iterator_tag);
00852 
00853       // Called by insert(p,n,x), and the range insert when it turns out to be
00854       // the same thing.
00855       void
00856       _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
00857 
00858       // Called by insert(p,x)
00859       void
00860       _M_insert_aux(iterator __position, const value_type& __x);
00861     };
00862 
00863 
00864   /**
00865    *  @brief  Vector equality comparison.
00866    *  @param  x  A %vector.
00867    *  @param  y  A %vector of the same type as @a x.
00868    *  @return  True iff the size and elements of the vectors are equal.
00869    *
00870    *  This is an equivalence relation.  It is linear in the size of the
00871    *  vectors.  Vectors are considered equivalent if their sizes are equal,
00872    *  and if corresponding elements compare equal.
00873   */
00874   template<typename _Tp, typename _Alloc>
00875     inline bool
00876     operator==(const vector<_Tp,_Alloc>& __x, const vector<_Tp,_Alloc>& __y)
00877     {
00878       return __x.size() == __y.size() &&
00879              std::equal(__x.begin(), __x.end(), __y.begin());
00880     }
00881 
00882   /**
00883    *  @brief  Vector ordering relation.
00884    *  @param  x  A %vector.
00885    *  @param  y  A %vector of the same type as @a x.
00886    *  @return  True iff @a x is lexicographically less than @a y.
00887    *
00888    *  This is a total ordering relation.  It is linear in the size of the
00889    *  vectors.  The elements must be comparable with @c <.
00890    *
00891    *  See std::lexicographical_compare() for how the determination is made.
00892   */
00893   template<typename _Tp, typename _Alloc>
00894     inline bool
00895     operator<(const vector<_Tp,_Alloc>& __x, const vector<_Tp,_Alloc>& __y)
00896     {
00897       return std::lexicographical_compare(__x.begin(), __x.end(),
00898                       __y.begin(), __y.end());
00899     }
00900 
00901   /// Based on operator==
00902   template<typename _Tp, typename _Alloc>
00903     inline bool
00904     operator!=(const vector<_Tp,_Alloc>& __x, const vector<_Tp,_Alloc>& __y)
00905     { return !(__x == __y); }
00906 
00907   /// Based on operator<
00908   template<typename _Tp, typename _Alloc>
00909     inline bool
00910     operator>(const vector<_Tp,_Alloc>& __x, const vector<_Tp,_Alloc>& __y)
00911     { return __y < __x; }
00912 
00913   /// Based on operator<
00914   template<typename _Tp, typename _Alloc>
00915     inline bool
00916     operator<=(const vector<_Tp,_Alloc>& __x, const vector<_Tp,_Alloc>& __y)
00917     { return !(__y < __x); }
00918 
00919   /// Based on operator<
00920   template<typename _Tp, typename _Alloc>
00921     inline bool
00922     operator>=(const vector<_Tp,_Alloc>& __x, const vector<_Tp,_Alloc>& __y)
00923     { return !(__x < __y); }
00924 
00925   /// See std::vector::swap().
00926   template<typename _Tp, typename _Alloc>
00927     inline void
00928     swap(vector<_Tp,_Alloc>& __x, vector<_Tp,_Alloc>& __y)
00929     { __x.swap(__y); }
00930 } // namespace std
00931 
00932 #endif /* _VECTOR_H */

Generated on Fri May 6 01:09:13 2005 for libstdc++-v3 Source by  doxygen 1.4.2