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