libstdc++
stl_vector.h
Go to the documentation of this file.
00001 // Vector implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
00004 // 2011 Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 3, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 /*
00027  *
00028  * Copyright (c) 1994
00029  * Hewlett-Packard Company
00030  *
00031  * Permission to use, copy, modify, distribute and sell this software
00032  * and its documentation for any purpose is hereby granted without fee,
00033  * provided that the above copyright notice appear in all copies and
00034  * that both that copyright notice and this permission notice appear
00035  * in supporting documentation.  Hewlett-Packard Company makes no
00036  * representations about the suitability of this software for any
00037  * purpose.  It is provided "as is" without express or implied warranty.
00038  *
00039  *
00040  * Copyright (c) 1996
00041  * Silicon Graphics Computer Systems, Inc.
00042  *
00043  * Permission to use, copy, modify, distribute and sell this software
00044  * and its documentation for any purpose is hereby granted without fee,
00045  * provided that the above copyright notice appear in all copies and
00046  * that both that copyright notice and this permission notice appear
00047  * in supporting documentation.  Silicon Graphics makes no
00048  * representations about the suitability of this  software for any
00049  * purpose.  It is provided "as is" without express or implied warranty.
00050  */
00051 
00052 /** @file bits/stl_vector.h
00053  *  This is an internal header file, included by other library headers.
00054  *  Do not attempt to use it directly. @headername{vector}
00055  */
00056 
00057 #ifndef _STL_VECTOR_H
00058 #define _STL_VECTOR_H 1
00059 
00060 #include <bits/stl_iterator_base_funcs.h>
00061 #include <bits/functexcept.h>
00062 #include <bits/concept_check.h>
00063 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00064 #include <initializer_list>
00065 #endif
00066 
00067 namespace std _GLIBCXX_VISIBILITY(default)
00068 {
00069 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00070 
00071   /// See bits/stl_deque.h's _Deque_base for an explanation.
00072   template<typename _Tp, typename _Alloc>
00073     struct _Vector_base
00074     {
00075       typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
00076         rebind<_Tp>::other _Tp_alloc_type;
00077       typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
00078         pointer;
00079 
00080       struct _Vector_impl 
00081       : public _Tp_alloc_type
00082       {
00083     pointer _M_start;
00084     pointer _M_finish;
00085     pointer _M_end_of_storage;
00086 
00087     _Vector_impl()
00088     : _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0)
00089     { }
00090 
00091     _Vector_impl(_Tp_alloc_type const& __a)
00092     : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
00093     { }
00094 
00095 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00096     _Vector_impl(_Tp_alloc_type&& __a)
00097     : _Tp_alloc_type(std::move(__a)),
00098       _M_start(0), _M_finish(0), _M_end_of_storage(0)
00099     { }
00100 #endif
00101 
00102     void _M_swap_data(_Vector_impl& __x)
00103     {
00104       std::swap(_M_start, __x._M_start);
00105       std::swap(_M_finish, __x._M_finish);
00106       std::swap(_M_end_of_storage, __x._M_end_of_storage);
00107     }
00108       };
00109       
00110     public:
00111       typedef _Alloc allocator_type;
00112 
00113       _Tp_alloc_type&
00114       _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
00115       { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
00116 
00117       const _Tp_alloc_type&
00118       _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
00119       { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
00120 
00121       allocator_type
00122       get_allocator() const _GLIBCXX_NOEXCEPT
00123       { return allocator_type(_M_get_Tp_allocator()); }
00124 
00125       _Vector_base()
00126       : _M_impl() { }
00127 
00128       _Vector_base(const allocator_type& __a)
00129       : _M_impl(__a) { }
00130 
00131       _Vector_base(size_t __n)
00132       : _M_impl()
00133       { _M_create_storage(__n); }
00134 
00135       _Vector_base(size_t __n, const allocator_type& __a)
00136       : _M_impl(__a)
00137       { _M_create_storage(__n); }
00138 
00139 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00140       _Vector_base(_Tp_alloc_type&& __a)
00141       : _M_impl(std::move(__a)) { }
00142 
00143       _Vector_base(_Vector_base&& __x)
00144       : _M_impl(std::move(__x._M_get_Tp_allocator()))
00145       { this->_M_impl._M_swap_data(__x._M_impl); }
00146 
00147       _Vector_base(_Vector_base&& __x, const allocator_type& __a)
00148       : _M_impl(__a)
00149       {
00150     if (__x.get_allocator() == __a)
00151       this->_M_impl._M_swap_data(__x._M_impl);
00152     else
00153       {
00154         size_t __n = __x._M_impl._M_finish - __x._M_impl._M_start;
00155         _M_create_storage(__n);
00156       }
00157       }
00158 #endif
00159 
00160       ~_Vector_base()
00161       { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
00162               - this->_M_impl._M_start); }
00163 
00164     public:
00165       _Vector_impl _M_impl;
00166 
00167       pointer
00168       _M_allocate(size_t __n)
00169       { return __n != 0 ? _M_impl.allocate(__n) : 0; }
00170 
00171       void
00172       _M_deallocate(pointer __p, size_t __n)
00173       {
00174     if (__p)
00175       _M_impl.deallocate(__p, __n);
00176       }
00177 
00178     private:
00179       void
00180       _M_create_storage(size_t __n)
00181       {
00182     this->_M_impl._M_start = this->_M_allocate(__n);
00183     this->_M_impl._M_finish = this->_M_impl._M_start;
00184     this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
00185       }
00186     };
00187 
00188 
00189   /**
00190    *  @brief A standard container which offers fixed time access to
00191    *  individual elements in any order.
00192    *
00193    *  @ingroup sequences
00194    *
00195    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
00196    *  <a href="tables.html#66">reversible container</a>, and a
00197    *  <a href="tables.html#67">sequence</a>, including the
00198    *  <a href="tables.html#68">optional sequence requirements</a> with the
00199    *  %exception of @c push_front and @c pop_front.
00200    *
00201    *  In some terminology a %vector can be described as a dynamic
00202    *  C-style array, it offers fast and efficient access to individual
00203    *  elements in any order and saves the user from worrying about
00204    *  memory and size allocation.  Subscripting ( @c [] ) access is
00205    *  also provided as with C-style arrays.
00206   */
00207   template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
00208     class vector : protected _Vector_base<_Tp, _Alloc>
00209     {
00210       // Concept requirements.
00211       typedef typename _Alloc::value_type                _Alloc_value_type;
00212       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00213       __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
00214       
00215       typedef _Vector_base<_Tp, _Alloc>          _Base;
00216       typedef typename _Base::_Tp_alloc_type         _Tp_alloc_type;
00217       typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type>  _Alloc_traits;
00218 
00219     public:
00220       typedef _Tp                    value_type;
00221       typedef typename _Base::pointer                    pointer;
00222       typedef typename _Alloc_traits::const_pointer      const_pointer;
00223       typedef typename _Alloc_traits::reference          reference;
00224       typedef typename _Alloc_traits::const_reference    const_reference;
00225       typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
00226       typedef __gnu_cxx::__normal_iterator<const_pointer, vector>
00227       const_iterator;
00228       typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
00229       typedef std::reverse_iterator<iterator>        reverse_iterator;
00230       typedef size_t                     size_type;
00231       typedef ptrdiff_t                  difference_type;
00232       typedef _Alloc                                 allocator_type;
00233 
00234     protected:
00235       using _Base::_M_allocate;
00236       using _Base::_M_deallocate;
00237       using _Base::_M_impl;
00238       using _Base::_M_get_Tp_allocator;
00239 
00240     public:
00241       // [23.2.4.1] construct/copy/destroy
00242       // (assign() and get_allocator() are also listed in this section)
00243       /**
00244        *  @brief  Default constructor creates no elements.
00245        */
00246       vector()
00247       : _Base() { }
00248 
00249       /**
00250        *  @brief  Creates a %vector with no elements.
00251        *  @param  __a  An allocator object.
00252        */
00253       explicit
00254       vector(const allocator_type& __a)
00255       : _Base(__a) { }
00256 
00257 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00258       /**
00259        *  @brief  Creates a %vector with default constructed elements.
00260        *  @param  __n  The number of elements to initially create.
00261        *
00262        *  This constructor fills the %vector with @a __n default
00263        *  constructed elements.
00264        */
00265       explicit
00266       vector(size_type __n)
00267       : _Base(__n)
00268       { _M_default_initialize(__n); }
00269 
00270       /**
00271        *  @brief  Creates a %vector with copies of an exemplar element.
00272        *  @param  __n  The number of elements to initially create.
00273        *  @param  __value  An element to copy.
00274        *  @param  __a  An allocator.
00275        *
00276        *  This constructor fills the %vector with @a __n copies of @a __value.
00277        */
00278       vector(size_type __n, const value_type& __value,
00279          const allocator_type& __a = allocator_type())
00280       : _Base(__n, __a)
00281       { _M_fill_initialize(__n, __value); }
00282 #else
00283       /**
00284        *  @brief  Creates a %vector with copies of an exemplar element.
00285        *  @param  __n  The number of elements to initially create.
00286        *  @param  __value  An element to copy.
00287        *  @param  __a  An allocator.
00288        *
00289        *  This constructor fills the %vector with @a __n copies of @a __value.
00290        */
00291       explicit
00292       vector(size_type __n, const value_type& __value = value_type(),
00293          const allocator_type& __a = allocator_type())
00294       : _Base(__n, __a)
00295       { _M_fill_initialize(__n, __value); }
00296 #endif
00297 
00298       /**
00299        *  @brief  %Vector copy constructor.
00300        *  @param  __x  A %vector of identical element and allocator types.
00301        *
00302        *  The newly-created %vector uses a copy of the allocation
00303        *  object used by @a __x.  All the elements of @a __x are copied,
00304        *  but any extra memory in
00305        *  @a __x (for fast expansion) will not be copied.
00306        */
00307       vector(const vector& __x)
00308       : _Base(__x.size(),
00309         _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()))
00310       { this->_M_impl._M_finish =
00311       std::__uninitialized_copy_a(__x.begin(), __x.end(),
00312                       this->_M_impl._M_start,
00313                       _M_get_Tp_allocator());
00314       }
00315 
00316 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00317       /**
00318        *  @brief  %Vector move constructor.
00319        *  @param  __x  A %vector of identical element and allocator types.
00320        *
00321        *  The newly-created %vector contains the exact contents of @a __x.
00322        *  The contents of @a __x are a valid, but unspecified %vector.
00323        */
00324       vector(vector&& __x) noexcept
00325       : _Base(std::move(__x)) { }
00326 
00327       /// Copy constructor with alternative allocator
00328       vector(const vector& __x, const allocator_type& __a)
00329       : _Base(__x.size(), __a)
00330       { this->_M_impl._M_finish =
00331       std::__uninitialized_copy_a(__x.begin(), __x.end(),
00332                       this->_M_impl._M_start,
00333                       _M_get_Tp_allocator());
00334       }
00335 
00336       /// Move constructor with alternative allocator
00337       vector(vector&& __rv, const allocator_type& __m)
00338       : _Base(std::move(__rv), __m)
00339       {
00340     if (__rv.get_allocator() != __m)
00341       {
00342         this->_M_impl._M_finish =
00343           std::__uninitialized_move_a(__rv.begin(), __rv.end(),
00344                       this->_M_impl._M_start,
00345                       _M_get_Tp_allocator());
00346         __rv.clear();
00347       }
00348       }
00349 
00350       /**
00351        *  @brief  Builds a %vector from an initializer list.
00352        *  @param  __l  An initializer_list.
00353        *  @param  __a  An allocator.
00354        *
00355        *  Create a %vector consisting of copies of the elements in the
00356        *  initializer_list @a __l.
00357        *
00358        *  This will call the element type's copy constructor N times
00359        *  (where N is @a __l.size()) and do no memory reallocation.
00360        */
00361       vector(initializer_list<value_type> __l,
00362          const allocator_type& __a = allocator_type())
00363       : _Base(__a)
00364       {
00365     _M_range_initialize(__l.begin(), __l.end(),
00366                 random_access_iterator_tag());
00367       }
00368 #endif
00369 
00370       /**
00371        *  @brief  Builds a %vector from a range.
00372        *  @param  __first  An input iterator.
00373        *  @param  __last  An input iterator.
00374        *  @param  __a  An allocator.
00375        *
00376        *  Create a %vector consisting of copies of the elements from
00377        *  [first,last).
00378        *
00379        *  If the iterators are forward, bidirectional, or
00380        *  random-access, then this will call the elements' copy
00381        *  constructor N times (where N is distance(first,last)) and do
00382        *  no memory reallocation.  But if only input iterators are
00383        *  used, then this will do at most 2N calls to the copy
00384        *  constructor, and logN memory reallocations.
00385        */
00386       template<typename _InputIterator>
00387         vector(_InputIterator __first, _InputIterator __last,
00388            const allocator_type& __a = allocator_type())
00389     : _Base(__a)
00390         {
00391       // Check whether it's an integral type.  If so, it's not an iterator.
00392       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00393       _M_initialize_dispatch(__first, __last, _Integral());
00394     }
00395 
00396       /**
00397        *  The dtor only erases the elements, and note that if the
00398        *  elements themselves are pointers, the pointed-to memory is
00399        *  not touched in any way.  Managing the pointer is the user's
00400        *  responsibility.
00401        */
00402       ~vector() _GLIBCXX_NOEXCEPT
00403       { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00404               _M_get_Tp_allocator()); }
00405 
00406       /**
00407        *  @brief  %Vector assignment operator.
00408        *  @param  __x  A %vector of identical element and allocator types.
00409        *
00410        *  All the elements of @a __x are copied, but any extra memory in
00411        *  @a __x (for fast expansion) will not be copied.  Unlike the
00412        *  copy constructor, the allocator object is not copied.
00413        */
00414       vector&
00415       operator=(const vector& __x);
00416 
00417 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00418       /**
00419        *  @brief  %Vector move assignment operator.
00420        *  @param  __x  A %vector of identical element and allocator types.
00421        *
00422        *  The contents of @a __x are moved into this %vector (without copying).
00423        *  @a __x is a valid, but unspecified %vector.
00424        */
00425       vector&
00426       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
00427       {
00428     if (_Alloc_traits::_S_propagate_on_move_assign())
00429       {
00430         // We're moving the rvalue's allocator so can move the data too.
00431         const vector __tmp(std::move(*this));     // discard existing data
00432         this->_M_impl._M_swap_data(__x._M_impl);
00433         std::__alloc_on_move(_M_get_Tp_allocator(),
00434                  __x._M_get_Tp_allocator());
00435       }
00436     else if (_Alloc_traits::_S_always_equal()
00437              || __x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
00438       {
00439         // The rvalue's allocator can free our storage and vice versa,
00440         // so can swap the data storage after destroying our contents.
00441         this->clear();
00442         this->_M_impl._M_swap_data(__x._M_impl);
00443       }
00444     else
00445       {
00446         // The rvalue's allocator cannot be moved, or is not equal,
00447         // so we need to individually move each element.
00448         this->assign(std::__make_move_if_noexcept_iterator(__x.begin()),
00449              std::__make_move_if_noexcept_iterator(__x.end()));
00450         __x.clear();
00451       }
00452     return *this;
00453       }
00454 
00455       /**
00456        *  @brief  %Vector list assignment operator.
00457        *  @param  __l  An initializer_list.
00458        *
00459        *  This function fills a %vector with copies of the elements in the
00460        *  initializer list @a __l.
00461        *
00462        *  Note that the assignment completely changes the %vector and
00463        *  that the resulting %vector's size is the same as the number
00464        *  of elements assigned.  Old data may be lost.
00465        */
00466       vector&
00467       operator=(initializer_list<value_type> __l)
00468       {
00469     this->assign(__l.begin(), __l.end());
00470     return *this;
00471       }
00472 #endif
00473 
00474       /**
00475        *  @brief  Assigns a given value to a %vector.
00476        *  @param  __n  Number of elements to be assigned.
00477        *  @param  __val  Value to be assigned.
00478        *
00479        *  This function fills a %vector with @a __n copies of the given
00480        *  value.  Note that the assignment completely changes the
00481        *  %vector and that the resulting %vector's size is the same as
00482        *  the number of elements assigned.  Old data may be lost.
00483        */
00484       void
00485       assign(size_type __n, const value_type& __val)
00486       { _M_fill_assign(__n, __val); }
00487 
00488       /**
00489        *  @brief  Assigns a range to a %vector.
00490        *  @param  __first  An input iterator.
00491        *  @param  __last   An input iterator.
00492        *
00493        *  This function fills a %vector with copies of the elements in the
00494        *  range [__first,__last).
00495        *
00496        *  Note that the assignment completely changes the %vector and
00497        *  that the resulting %vector's size is the same as the number
00498        *  of elements assigned.  Old data may be lost.
00499        */
00500       template<typename _InputIterator>
00501         void
00502         assign(_InputIterator __first, _InputIterator __last)
00503         {
00504       // Check whether it's an integral type.  If so, it's not an iterator.
00505       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00506       _M_assign_dispatch(__first, __last, _Integral());
00507     }
00508 
00509 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00510       /**
00511        *  @brief  Assigns an initializer list to a %vector.
00512        *  @param  __l  An initializer_list.
00513        *
00514        *  This function fills a %vector with copies of the elements in the
00515        *  initializer list @a __l.
00516        *
00517        *  Note that the assignment completely changes the %vector and
00518        *  that the resulting %vector's size is the same as the number
00519        *  of elements assigned.  Old data may be lost.
00520        */
00521       void
00522       assign(initializer_list<value_type> __l)
00523       { this->assign(__l.begin(), __l.end()); }
00524 #endif
00525 
00526       /// Get a copy of the memory allocation object.
00527       using _Base::get_allocator;
00528 
00529       // iterators
00530       /**
00531        *  Returns a read/write iterator that points to the first
00532        *  element in the %vector.  Iteration is done in ordinary
00533        *  element order.
00534        */
00535       iterator
00536       begin() _GLIBCXX_NOEXCEPT
00537       { return iterator(this->_M_impl._M_start); }
00538 
00539       /**
00540        *  Returns a read-only (constant) iterator that points to the
00541        *  first element in the %vector.  Iteration is done in ordinary
00542        *  element order.
00543        */
00544       const_iterator
00545       begin() const _GLIBCXX_NOEXCEPT
00546       { return const_iterator(this->_M_impl._M_start); }
00547 
00548       /**
00549        *  Returns a read/write iterator that points one past the last
00550        *  element in the %vector.  Iteration is done in ordinary
00551        *  element order.
00552        */
00553       iterator
00554       end() _GLIBCXX_NOEXCEPT
00555       { return iterator(this->_M_impl._M_finish); }
00556 
00557       /**
00558        *  Returns a read-only (constant) iterator that points one past
00559        *  the last element in the %vector.  Iteration is done in
00560        *  ordinary element order.
00561        */
00562       const_iterator
00563       end() const _GLIBCXX_NOEXCEPT
00564       { return const_iterator(this->_M_impl._M_finish); }
00565 
00566       /**
00567        *  Returns a read/write reverse iterator that points to the
00568        *  last element in the %vector.  Iteration is done in reverse
00569        *  element order.
00570        */
00571       reverse_iterator
00572       rbegin() _GLIBCXX_NOEXCEPT
00573       { return reverse_iterator(end()); }
00574 
00575       /**
00576        *  Returns a read-only (constant) reverse iterator that points
00577        *  to the last element in the %vector.  Iteration is done in
00578        *  reverse element order.
00579        */
00580       const_reverse_iterator
00581       rbegin() const _GLIBCXX_NOEXCEPT
00582       { return const_reverse_iterator(end()); }
00583 
00584       /**
00585        *  Returns a read/write reverse iterator that points to one
00586        *  before the first element in the %vector.  Iteration is done
00587        *  in reverse element order.
00588        */
00589       reverse_iterator
00590       rend() _GLIBCXX_NOEXCEPT
00591       { return reverse_iterator(begin()); }
00592 
00593       /**
00594        *  Returns a read-only (constant) reverse iterator that points
00595        *  to one before the first element in the %vector.  Iteration
00596        *  is done in reverse element order.
00597        */
00598       const_reverse_iterator
00599       rend() const _GLIBCXX_NOEXCEPT
00600       { return const_reverse_iterator(begin()); }
00601 
00602 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00603       /**
00604        *  Returns a read-only (constant) iterator that points to the
00605        *  first element in the %vector.  Iteration is done in ordinary
00606        *  element order.
00607        */
00608       const_iterator
00609       cbegin() const noexcept
00610       { return const_iterator(this->_M_impl._M_start); }
00611 
00612       /**
00613        *  Returns a read-only (constant) iterator that points one past
00614        *  the last element in the %vector.  Iteration is done in
00615        *  ordinary element order.
00616        */
00617       const_iterator
00618       cend() const noexcept
00619       { return const_iterator(this->_M_impl._M_finish); }
00620 
00621       /**
00622        *  Returns a read-only (constant) reverse iterator that points
00623        *  to the last element in the %vector.  Iteration is done in
00624        *  reverse element order.
00625        */
00626       const_reverse_iterator
00627       crbegin() const noexcept
00628       { return const_reverse_iterator(end()); }
00629 
00630       /**
00631        *  Returns a read-only (constant) reverse iterator that points
00632        *  to one before the first element in the %vector.  Iteration
00633        *  is done in reverse element order.
00634        */
00635       const_reverse_iterator
00636       crend() const noexcept
00637       { return const_reverse_iterator(begin()); }
00638 #endif
00639 
00640       // [23.2.4.2] capacity
00641       /**  Returns the number of elements in the %vector.  */
00642       size_type
00643       size() const _GLIBCXX_NOEXCEPT
00644       { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
00645 
00646       /**  Returns the size() of the largest possible %vector.  */
00647       size_type
00648       max_size() const _GLIBCXX_NOEXCEPT
00649       { return _Alloc_traits::max_size(_M_get_Tp_allocator()); }
00650 
00651 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00652       /**
00653        *  @brief  Resizes the %vector to the specified number of elements.
00654        *  @param  __new_size  Number of elements the %vector should contain.
00655        *
00656        *  This function will %resize the %vector to the specified
00657        *  number of elements.  If the number is smaller than the
00658        *  %vector's current size the %vector is truncated, otherwise
00659        *  default constructed elements are appended.
00660        */
00661       void
00662       resize(size_type __new_size)
00663       {
00664     if (__new_size > size())
00665       _M_default_append(__new_size - size());
00666     else if (__new_size < size())
00667       _M_erase_at_end(this->_M_impl._M_start + __new_size);
00668       }
00669 
00670       /**
00671        *  @brief  Resizes the %vector to the specified number of elements.
00672        *  @param  __new_size  Number of elements the %vector should contain.
00673        *  @param  __x  Data with which new elements should be populated.
00674        *
00675        *  This function will %resize the %vector to the specified
00676        *  number of elements.  If the number is smaller than the
00677        *  %vector's current size the %vector is truncated, otherwise
00678        *  the %vector is extended and new elements are populated with
00679        *  given data.
00680        */
00681       void
00682       resize(size_type __new_size, const value_type& __x)
00683       {
00684     if (__new_size > size())
00685       insert(end(), __new_size - size(), __x);
00686     else if (__new_size < size())
00687       _M_erase_at_end(this->_M_impl._M_start + __new_size);
00688       }
00689 #else
00690       /**
00691        *  @brief  Resizes the %vector to the specified number of elements.
00692        *  @param  __new_size  Number of elements the %vector should contain.
00693        *  @param  __x  Data with which new elements should be populated.
00694        *
00695        *  This function will %resize the %vector to the specified
00696        *  number of elements.  If the number is smaller than the
00697        *  %vector's current size the %vector is truncated, otherwise
00698        *  the %vector is extended and new elements are populated with
00699        *  given data.
00700        */
00701       void
00702       resize(size_type __new_size, value_type __x = value_type())
00703       {
00704     if (__new_size > size())
00705       insert(end(), __new_size - size(), __x);
00706     else if (__new_size < size())
00707       _M_erase_at_end(this->_M_impl._M_start + __new_size);
00708       }
00709 #endif
00710 
00711 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00712       /**  A non-binding request to reduce capacity() to size().  */
00713       void
00714       shrink_to_fit()
00715       { _M_shrink_to_fit(); }
00716 #endif
00717 
00718       /**
00719        *  Returns the total number of elements that the %vector can
00720        *  hold before needing to allocate more memory.
00721        */
00722       size_type
00723       capacity() const _GLIBCXX_NOEXCEPT
00724       { return size_type(this->_M_impl._M_end_of_storage
00725              - this->_M_impl._M_start); }
00726 
00727       /**
00728        *  Returns true if the %vector is empty.  (Thus begin() would
00729        *  equal end().)
00730        */
00731       bool
00732       empty() const _GLIBCXX_NOEXCEPT
00733       { return begin() == end(); }
00734 
00735       /**
00736        *  @brief  Attempt to preallocate enough memory for specified number of
00737        *          elements.
00738        *  @param  __n  Number of elements required.
00739        *  @throw  std::length_error  If @a n exceeds @c max_size().
00740        *
00741        *  This function attempts to reserve enough memory for the
00742        *  %vector to hold the specified number of elements.  If the
00743        *  number requested is more than max_size(), length_error is
00744        *  thrown.
00745        *
00746        *  The advantage of this function is that if optimal code is a
00747        *  necessity and the user can determine the number of elements
00748        *  that will be required, the user can reserve the memory in
00749        *  %advance, and thus prevent a possible reallocation of memory
00750        *  and copying of %vector data.
00751        */
00752       void
00753       reserve(size_type __n);
00754 
00755       // element access
00756       /**
00757        *  @brief  Subscript access to the data contained in the %vector.
00758        *  @param __n The index of the element for which data should be
00759        *  accessed.
00760        *  @return  Read/write reference to data.
00761        *
00762        *  This operator allows for easy, array-style, data access.
00763        *  Note that data access with this operator is unchecked and
00764        *  out_of_range lookups are not defined. (For checked lookups
00765        *  see at().)
00766        */
00767       reference
00768       operator[](size_type __n)
00769       { return *(this->_M_impl._M_start + __n); }
00770 
00771       /**
00772        *  @brief  Subscript access to the data contained in the %vector.
00773        *  @param __n The index of the element for which data should be
00774        *  accessed.
00775        *  @return  Read-only (constant) reference to data.
00776        *
00777        *  This operator allows for easy, array-style, data access.
00778        *  Note that data access with this operator is unchecked and
00779        *  out_of_range lookups are not defined. (For checked lookups
00780        *  see at().)
00781        */
00782       const_reference
00783       operator[](size_type __n) const
00784       { return *(this->_M_impl._M_start + __n); }
00785 
00786     protected:
00787       /// Safety check used only from at().
00788       void
00789       _M_range_check(size_type __n) const
00790       {
00791     if (__n >= this->size())
00792       __throw_out_of_range(__N("vector::_M_range_check"));
00793       }
00794 
00795     public:
00796       /**
00797        *  @brief  Provides access to the data contained in the %vector.
00798        *  @param __n The index of the element for which data should be
00799        *  accessed.
00800        *  @return  Read/write reference to data.
00801        *  @throw  std::out_of_range  If @a __n is an invalid index.
00802        *
00803        *  This function provides for safer data access.  The parameter
00804        *  is first checked that it is in the range of the vector.  The
00805        *  function throws out_of_range if the check fails.
00806        */
00807       reference
00808       at(size_type __n)
00809       {
00810     _M_range_check(__n);
00811     return (*this)[__n]; 
00812       }
00813 
00814       /**
00815        *  @brief  Provides access to the data contained in the %vector.
00816        *  @param __n The index of the element for which data should be
00817        *  accessed.
00818        *  @return  Read-only (constant) reference to data.
00819        *  @throw  std::out_of_range  If @a __n is an invalid index.
00820        *
00821        *  This function provides for safer data access.  The parameter
00822        *  is first checked that it is in the range of the vector.  The
00823        *  function throws out_of_range if the check fails.
00824        */
00825       const_reference
00826       at(size_type __n) const
00827       {
00828     _M_range_check(__n);
00829     return (*this)[__n];
00830       }
00831 
00832       /**
00833        *  Returns a read/write reference to the data at the first
00834        *  element of the %vector.
00835        */
00836       reference
00837       front()
00838       { return *begin(); }
00839 
00840       /**
00841        *  Returns a read-only (constant) reference to the data at the first
00842        *  element of the %vector.
00843        */
00844       const_reference
00845       front() const
00846       { return *begin(); }
00847 
00848       /**
00849        *  Returns a read/write reference to the data at the last
00850        *  element of the %vector.
00851        */
00852       reference
00853       back()
00854       { return *(end() - 1); }
00855       
00856       /**
00857        *  Returns a read-only (constant) reference to the data at the
00858        *  last element of the %vector.
00859        */
00860       const_reference
00861       back() const
00862       { return *(end() - 1); }
00863 
00864       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00865       // DR 464. Suggestion for new member functions in standard containers.
00866       // data access
00867       /**
00868        *   Returns a pointer such that [data(), data() + size()) is a valid
00869        *   range.  For a non-empty %vector, data() == &front().
00870        */
00871 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00872       _Tp*
00873 #else
00874       pointer
00875 #endif
00876       data() _GLIBCXX_NOEXCEPT
00877       { return std::__addressof(front()); }
00878 
00879 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00880       const _Tp*
00881 #else
00882       const_pointer
00883 #endif
00884       data() const _GLIBCXX_NOEXCEPT
00885       { return std::__addressof(front()); }
00886 
00887       // [23.2.4.3] modifiers
00888       /**
00889        *  @brief  Add data to the end of the %vector.
00890        *  @param  __x  Data to be added.
00891        *
00892        *  This is a typical stack operation.  The function creates an
00893        *  element at the end of the %vector and assigns the given data
00894        *  to it.  Due to the nature of a %vector this operation can be
00895        *  done in constant time if the %vector has preallocated space
00896        *  available.
00897        */
00898       void
00899       push_back(const value_type& __x)
00900       {
00901     if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
00902       {
00903         _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
00904                                  __x);
00905         ++this->_M_impl._M_finish;
00906       }
00907     else
00908 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00909       _M_emplace_back_aux(__x);
00910 #else
00911       _M_insert_aux(end(), __x);
00912 #endif
00913       }
00914 
00915 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00916       void
00917       push_back(value_type&& __x)
00918       { emplace_back(std::move(__x)); }
00919 
00920       template<typename... _Args>
00921         void
00922         emplace_back(_Args&&... __args);
00923 #endif
00924 
00925       /**
00926        *  @brief  Removes last element.
00927        *
00928        *  This is a typical stack operation. It shrinks the %vector by one.
00929        *
00930        *  Note that no data is returned, and if the last element's
00931        *  data is needed, it should be retrieved before pop_back() is
00932        *  called.
00933        */
00934       void
00935       pop_back()
00936       {
00937     --this->_M_impl._M_finish;
00938     _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
00939       }
00940 
00941 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00942       /**
00943        *  @brief  Inserts an object in %vector before specified iterator.
00944        *  @param  __position  An iterator into the %vector.
00945        *  @param  __args  Arguments.
00946        *  @return  An iterator that points to the inserted data.
00947        *
00948        *  This function will insert an object of type T constructed
00949        *  with T(std::forward<Args>(args)...) before the specified location.
00950        *  Note that this kind of operation could be expensive for a %vector
00951        *  and if it is frequently used the user should consider using
00952        *  std::list.
00953        */
00954       template<typename... _Args>
00955         iterator
00956         emplace(iterator __position, _Args&&... __args);
00957 #endif
00958 
00959       /**
00960        *  @brief  Inserts given value into %vector before specified iterator.
00961        *  @param  __position  An iterator into the %vector.
00962        *  @param  __x  Data to be inserted.
00963        *  @return  An iterator that points to the inserted data.
00964        *
00965        *  This function will insert a copy of the given value before
00966        *  the specified location.  Note that this kind of operation
00967        *  could be expensive for a %vector and if it is frequently
00968        *  used the user should consider using std::list.
00969        */
00970       iterator
00971       insert(iterator __position, const value_type& __x);
00972 
00973 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00974       /**
00975        *  @brief  Inserts given rvalue into %vector before specified iterator.
00976        *  @param  __position  An iterator into the %vector.
00977        *  @param  __x  Data to be inserted.
00978        *  @return  An iterator that points to the inserted data.
00979        *
00980        *  This function will insert a copy of the given rvalue before
00981        *  the specified location.  Note that this kind of operation
00982        *  could be expensive for a %vector and if it is frequently
00983        *  used the user should consider using std::list.
00984        */
00985       iterator
00986       insert(iterator __position, value_type&& __x)
00987       { return emplace(__position, std::move(__x)); }
00988 
00989       /**
00990        *  @brief  Inserts an initializer_list into the %vector.
00991        *  @param  __position  An iterator into the %vector.
00992        *  @param  __l  An initializer_list.
00993        *
00994        *  This function will insert copies of the data in the 
00995        *  initializer_list @a l into the %vector before the location
00996        *  specified by @a position.
00997        *
00998        *  Note that this kind of operation could be expensive for a
00999        *  %vector and if it is frequently used the user should
01000        *  consider using std::list.
01001        */
01002       void
01003       insert(iterator __position, initializer_list<value_type> __l)
01004       { this->insert(__position, __l.begin(), __l.end()); }
01005 #endif
01006 
01007       /**
01008        *  @brief  Inserts a number of copies of given data into the %vector.
01009        *  @param  __position  An iterator into the %vector.
01010        *  @param  __n  Number of elements to be inserted.
01011        *  @param  __x  Data to be inserted.
01012        *
01013        *  This function will insert a specified number of copies of
01014        *  the given data before the location specified by @a position.
01015        *
01016        *  Note that this kind of operation could be expensive for a
01017        *  %vector and if it is frequently used the user should
01018        *  consider using std::list.
01019        */
01020       void
01021       insert(iterator __position, size_type __n, const value_type& __x)
01022       { _M_fill_insert(__position, __n, __x); }
01023 
01024       /**
01025        *  @brief  Inserts a range into the %vector.
01026        *  @param  __position  An iterator into the %vector.
01027        *  @param  __first  An input iterator.
01028        *  @param  __last   An input iterator.
01029        *
01030        *  This function will insert copies of the data in the range
01031        *  [__first,__last) into the %vector before the location specified
01032        *  by @a pos.
01033        *
01034        *  Note that this kind of operation could be expensive for a
01035        *  %vector and if it is frequently used the user should
01036        *  consider using std::list.
01037        */
01038       template<typename _InputIterator>
01039         void
01040         insert(iterator __position, _InputIterator __first,
01041            _InputIterator __last)
01042         {
01043       // Check whether it's an integral type.  If so, it's not an iterator.
01044       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
01045       _M_insert_dispatch(__position, __first, __last, _Integral());
01046     }
01047 
01048       /**
01049        *  @brief  Remove element at given position.
01050        *  @param  __position  Iterator pointing to element to be erased.
01051        *  @return  An iterator pointing to the next element (or end()).
01052        *
01053        *  This function will erase the element at the given position and thus
01054        *  shorten the %vector by one.
01055        *
01056        *  Note This operation could be expensive and if it is
01057        *  frequently used the user should consider using std::list.
01058        *  The user is also cautioned that this function only erases
01059        *  the element, and that if the element is itself a pointer,
01060        *  the pointed-to memory is not touched in any way.  Managing
01061        *  the pointer is the user's responsibility.
01062        */
01063       iterator
01064       erase(iterator __position);
01065 
01066       /**
01067        *  @brief  Remove a range of elements.
01068        *  @param  __first  Iterator pointing to the first element to be erased.
01069        *  @param  __last  Iterator pointing to one past the last element to be
01070        *                  erased.
01071        *  @return  An iterator pointing to the element pointed to by @a __last
01072        *           prior to erasing (or end()).
01073        *
01074        *  This function will erase the elements in the range
01075        *  [__first,__last) and shorten the %vector accordingly.
01076        *
01077        *  Note This operation could be expensive and if it is
01078        *  frequently used the user should consider using std::list.
01079        *  The user is also cautioned that this function only erases
01080        *  the elements, and that if the elements themselves are
01081        *  pointers, the pointed-to memory is not touched in any way.
01082        *  Managing the pointer is the user's responsibility.
01083        */
01084       iterator
01085       erase(iterator __first, iterator __last);
01086 
01087       /**
01088        *  @brief  Swaps data with another %vector.
01089        *  @param  __x  A %vector of the same element and allocator types.
01090        *
01091        *  This exchanges the elements between two vectors in constant time.
01092        *  (Three pointers, so it should be quite fast.)
01093        *  Note that the global std::swap() function is specialized such that
01094        *  std::swap(v1,v2) will feed to this function.
01095        */
01096       void
01097       swap(vector& __x)
01098 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01099             noexcept(_Alloc_traits::_S_nothrow_swap())
01100 #endif
01101       {
01102     this->_M_impl._M_swap_data(__x._M_impl);
01103     _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
01104                               __x._M_get_Tp_allocator());
01105       }
01106 
01107       /**
01108        *  Erases all the elements.  Note that this function only erases the
01109        *  elements, and that if the elements themselves are pointers, the
01110        *  pointed-to memory is not touched in any way.  Managing the pointer is
01111        *  the user's responsibility.
01112        */
01113       void
01114       clear() _GLIBCXX_NOEXCEPT
01115       { _M_erase_at_end(this->_M_impl._M_start); }
01116 
01117     protected:
01118       /**
01119        *  Memory expansion handler.  Uses the member allocation function to
01120        *  obtain @a n bytes of memory, and then copies [first,last) into it.
01121        */
01122       template<typename _ForwardIterator>
01123         pointer
01124         _M_allocate_and_copy(size_type __n,
01125                  _ForwardIterator __first, _ForwardIterator __last)
01126         {
01127       pointer __result = this->_M_allocate(__n);
01128       __try
01129         {
01130           std::__uninitialized_copy_a(__first, __last, __result,
01131                       _M_get_Tp_allocator());
01132           return __result;
01133         }
01134       __catch(...)
01135         {
01136           _M_deallocate(__result, __n);
01137           __throw_exception_again;
01138         }
01139     }
01140 
01141 
01142       // Internal constructor functions follow.
01143 
01144       // Called by the range constructor to implement [23.1.1]/9
01145 
01146       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01147       // 438. Ambiguity in the "do the right thing" clause
01148       template<typename _Integer>
01149         void
01150         _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
01151         {
01152       this->_M_impl._M_start = _M_allocate(static_cast<size_type>(__n));
01153       this->_M_impl._M_end_of_storage =
01154         this->_M_impl._M_start + static_cast<size_type>(__n);
01155       _M_fill_initialize(static_cast<size_type>(__n), __value);
01156     }
01157 
01158       // Called by the range constructor to implement [23.1.1]/9
01159       template<typename _InputIterator>
01160         void
01161         _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
01162                    __false_type)
01163         {
01164       typedef typename std::iterator_traits<_InputIterator>::
01165         iterator_category _IterCategory;
01166       _M_range_initialize(__first, __last, _IterCategory());
01167     }
01168 
01169       // Called by the second initialize_dispatch above
01170       template<typename _InputIterator>
01171         void
01172         _M_range_initialize(_InputIterator __first,
01173                 _InputIterator __last, std::input_iterator_tag)
01174         {
01175       for (; __first != __last; ++__first)
01176         push_back(*__first);
01177     }
01178 
01179       // Called by the second initialize_dispatch above
01180       template<typename _ForwardIterator>
01181         void
01182         _M_range_initialize(_ForwardIterator __first,
01183                 _ForwardIterator __last, std::forward_iterator_tag)
01184         {
01185       const size_type __n = std::distance(__first, __last);
01186       this->_M_impl._M_start = this->_M_allocate(__n);
01187       this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
01188       this->_M_impl._M_finish =
01189         std::__uninitialized_copy_a(__first, __last,
01190                     this->_M_impl._M_start,
01191                     _M_get_Tp_allocator());
01192     }
01193 
01194       // Called by the first initialize_dispatch above and by the
01195       // vector(n,value,a) constructor.
01196       void
01197       _M_fill_initialize(size_type __n, const value_type& __value)
01198       {
01199     std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, 
01200                       _M_get_Tp_allocator());
01201     this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
01202       }
01203 
01204 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01205       // Called by the vector(n) constructor.
01206       void
01207       _M_default_initialize(size_type __n)
01208       {
01209     std::__uninitialized_default_n_a(this->_M_impl._M_start, __n, 
01210                      _M_get_Tp_allocator());
01211     this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
01212       }
01213 #endif
01214 
01215       // Internal assign functions follow.  The *_aux functions do the actual
01216       // assignment work for the range versions.
01217 
01218       // Called by the range assign to implement [23.1.1]/9
01219 
01220       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01221       // 438. Ambiguity in the "do the right thing" clause
01222       template<typename _Integer>
01223         void
01224         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
01225         { _M_fill_assign(__n, __val); }
01226 
01227       // Called by the range assign to implement [23.1.1]/9
01228       template<typename _InputIterator>
01229         void
01230         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
01231                __false_type)
01232         {
01233       typedef typename std::iterator_traits<_InputIterator>::
01234         iterator_category _IterCategory;
01235       _M_assign_aux(__first, __last, _IterCategory());
01236     }
01237 
01238       // Called by the second assign_dispatch above
01239       template<typename _InputIterator>
01240         void
01241         _M_assign_aux(_InputIterator __first, _InputIterator __last,
01242               std::input_iterator_tag);
01243 
01244       // Called by the second assign_dispatch above
01245       template<typename _ForwardIterator>
01246         void
01247         _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
01248               std::forward_iterator_tag);
01249 
01250       // Called by assign(n,t), and the range assign when it turns out
01251       // to be the same thing.
01252       void
01253       _M_fill_assign(size_type __n, const value_type& __val);
01254 
01255 
01256       // Internal insert functions follow.
01257 
01258       // Called by the range insert to implement [23.1.1]/9
01259 
01260       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01261       // 438. Ambiguity in the "do the right thing" clause
01262       template<typename _Integer>
01263         void
01264         _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
01265                __true_type)
01266         { _M_fill_insert(__pos, __n, __val); }
01267 
01268       // Called by the range insert to implement [23.1.1]/9
01269       template<typename _InputIterator>
01270         void
01271         _M_insert_dispatch(iterator __pos, _InputIterator __first,
01272                _InputIterator __last, __false_type)
01273         {
01274       typedef typename std::iterator_traits<_InputIterator>::
01275         iterator_category _IterCategory;
01276       _M_range_insert(__pos, __first, __last, _IterCategory());
01277     }
01278 
01279       // Called by the second insert_dispatch above
01280       template<typename _InputIterator>
01281         void
01282         _M_range_insert(iterator __pos, _InputIterator __first,
01283             _InputIterator __last, std::input_iterator_tag);
01284 
01285       // Called by the second insert_dispatch above
01286       template<typename _ForwardIterator>
01287         void
01288         _M_range_insert(iterator __pos, _ForwardIterator __first,
01289             _ForwardIterator __last, std::forward_iterator_tag);
01290 
01291       // Called by insert(p,n,x), and the range insert when it turns out to be
01292       // the same thing.
01293       void
01294       _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
01295 
01296 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01297       // Called by resize(n).
01298       void
01299       _M_default_append(size_type __n);
01300 
01301       bool
01302       _M_shrink_to_fit();
01303 #endif
01304 
01305       // Called by insert(p,x)
01306 #ifndef __GXX_EXPERIMENTAL_CXX0X__
01307       void
01308       _M_insert_aux(iterator __position, const value_type& __x);
01309 #else
01310       template<typename... _Args>
01311         void
01312         _M_insert_aux(iterator __position, _Args&&... __args);
01313 
01314       template<typename... _Args>
01315         void
01316         _M_emplace_back_aux(_Args&&... __args);
01317 #endif
01318 
01319       // Called by the latter.
01320       size_type
01321       _M_check_len(size_type __n, const char* __s) const
01322       {
01323     if (max_size() - size() < __n)
01324       __throw_length_error(__N(__s));
01325 
01326     const size_type __len = size() + std::max(size(), __n);
01327     return (__len < size() || __len > max_size()) ? max_size() : __len;
01328       }
01329 
01330       // Internal erase functions follow.
01331 
01332       // Called by erase(q1,q2), clear(), resize(), _M_fill_assign,
01333       // _M_assign_aux.
01334       void
01335       _M_erase_at_end(pointer __pos)
01336       {
01337     std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator());
01338     this->_M_impl._M_finish = __pos;
01339       }
01340     };
01341 
01342 
01343   /**
01344    *  @brief  Vector equality comparison.
01345    *  @param  __x  A %vector.
01346    *  @param  __y  A %vector of the same type as @a __x.
01347    *  @return  True iff the size and elements of the vectors are equal.
01348    *
01349    *  This is an equivalence relation.  It is linear in the size of the
01350    *  vectors.  Vectors are considered equivalent if their sizes are equal,
01351    *  and if corresponding elements compare equal.
01352   */
01353   template<typename _Tp, typename _Alloc>
01354     inline bool
01355     operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
01356     { return (__x.size() == __y.size()
01357           && std::equal(__x.begin(), __x.end(), __y.begin())); }
01358 
01359   /**
01360    *  @brief  Vector ordering relation.
01361    *  @param  __x  A %vector.
01362    *  @param  __y  A %vector of the same type as @a __x.
01363    *  @return  True iff @a __x is lexicographically less than @a __y.
01364    *
01365    *  This is a total ordering relation.  It is linear in the size of the
01366    *  vectors.  The elements must be comparable with @c <.
01367    *
01368    *  See std::lexicographical_compare() for how the determination is made.
01369   */
01370   template<typename _Tp, typename _Alloc>
01371     inline bool
01372     operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
01373     { return std::lexicographical_compare(__x.begin(), __x.end(),
01374                       __y.begin(), __y.end()); }
01375 
01376   /// Based on operator==
01377   template<typename _Tp, typename _Alloc>
01378     inline bool
01379     operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
01380     { return !(__x == __y); }
01381 
01382   /// Based on operator<
01383   template<typename _Tp, typename _Alloc>
01384     inline bool
01385     operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
01386     { return __y < __x; }
01387 
01388   /// Based on operator<
01389   template<typename _Tp, typename _Alloc>
01390     inline bool
01391     operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
01392     { return !(__y < __x); }
01393 
01394   /// Based on operator<
01395   template<typename _Tp, typename _Alloc>
01396     inline bool
01397     operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
01398     { return !(__x < __y); }
01399 
01400   /// See std::vector::swap().
01401   template<typename _Tp, typename _Alloc>
01402     inline void
01403     swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
01404     { __x.swap(__y); }
01405 
01406 _GLIBCXX_END_NAMESPACE_CONTAINER
01407 } // namespace std
01408 
01409 #endif /* _STL_VECTOR_H */