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