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