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