The C and C++ Include Header Files

/usr/include/c++/11/bits/vector.tcc


$ cat -n /usr/include/c++/11/bits/vector.tcc

     1	// Vector implementation (out of line) -*- C++ -*-
     2	
     3	// Copyright (C) 2001-2021 Free Software Foundation, Inc.
     4	//
     5	// This file is part of the GNU ISO C++ Library.  This library is free
     6	// software; you can redistribute it and/or modify it under the
     7	// terms of the GNU General Public License as published by the
     8	// Free Software Foundation; either version 3, or (at your option)
     9	// any later version.
    10	
    11	// This library is distributed in the hope that it will be useful,
    12	// but WITHOUT ANY WARRANTY; without even the implied warranty of
    13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    14	// GNU General Public License for more details.
    15	
    16	// Under Section 7 of GPL version 3, you are granted additional
    17	// permissions described in the GCC Runtime Library Exception, version
    18	// 3.1, as published by the Free Software Foundation.
    19	
    20	// You should have received a copy of the GNU General Public License and
    21	// a copy of the GCC Runtime Library Exception along with this program;
    22	// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
    23	// <http://www.gnu.org/licenses/>.
    24	
    25	/*
    26	 *
    27	 * Copyright (c) 1994
    28	 * Hewlett-Packard Company
    29	 *
    30	 * Permission to use, copy, modify, distribute and sell this software
    31	 * and its documentation for any purpose is hereby granted without fee,
    32	 * provided that the above copyright notice appear in all copies and
    33	 * that both that copyright notice and this permission notice appear
    34	 * in supporting documentation.  Hewlett-Packard Company makes no
    35	 * representations about the suitability of this software for any
    36	 * purpose.  It is provided "as is" without express or implied warranty.
    37	 *
    38	 *
    39	 * Copyright (c) 1996
    40	 * Silicon Graphics Computer Systems, Inc.
    41	 *
    42	 * Permission to use, copy, modify, distribute and sell this software
    43	 * and its documentation for any purpose is hereby granted without fee,
    44	 * provided that the above copyright notice appear in all copies and
    45	 * that both that copyright notice and this permission notice appear
    46	 * in supporting documentation.  Silicon Graphics makes no
    47	 * representations about the suitability of this  software for any
    48	 * purpose.  It is provided "as is" without express or implied warranty.
    49	 */
    50	
    51	/** @file bits/vector.tcc
    52	 *  This is an internal header file, included by other library headers.
    53	 *  Do not attempt to use it directly. @headername{vector}
    54	 */
    55	
    56	#ifndef _VECTOR_TCC
    57	#define _VECTOR_TCC 1
    58	
    59	namespace std _GLIBCXX_VISIBILITY(default)
    60	{
    61	_GLIBCXX_BEGIN_NAMESPACE_VERSION
    62	_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
    63	
    64	  template<typename _Tp, typename _Alloc>
    65	    void
    66	    vector<_Tp, _Alloc>::
    67	    reserve(size_type __n)
    68	    {
    69	      if (__n > this->max_size())
    70		__throw_length_error(__N("vector::reserve"));
    71	      if (this->capacity() < __n)
    72		{
    73		  const size_type __old_size = size();
    74		  pointer __tmp;
    75	#if __cplusplus >= 201103L
    76		  if _GLIBCXX17_CONSTEXPR (_S_use_relocate())
    77		    {
    78		      __tmp = this->_M_allocate(__n);
    79		      _S_relocate(this->_M_impl._M_start, this->_M_impl._M_finish,
    80				  __tmp, _M_get_Tp_allocator());
    81		    }
    82		  else
    83	#endif
    84		    {
    85		      __tmp = _M_allocate_and_copy(__n,
    86			_GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start),
    87			_GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish));
    88		      std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
    89				    _M_get_Tp_allocator());
    90		    }
    91		  _GLIBCXX_ASAN_ANNOTATE_REINIT;
    92		  _M_deallocate(this->_M_impl._M_start,
    93				this->_M_impl._M_end_of_storage
    94				- this->_M_impl._M_start);
    95		  this->_M_impl._M_start = __tmp;
    96		  this->_M_impl._M_finish = __tmp + __old_size;
    97		  this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
    98		}
    99	    }
   100	
   101	#if __cplusplus >= 201103L
   102	  template<typename _Tp, typename _Alloc>
   103	    template<typename... _Args>
   104	#if __cplusplus > 201402L
   105	      typename vector<_Tp, _Alloc>::reference
   106	#else
   107	      void
   108	#endif
   109	      vector<_Tp, _Alloc>::
   110	      emplace_back(_Args&&... __args)
   111	      {
   112		if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
   113		  {
   114		    _GLIBCXX_ASAN_ANNOTATE_GROW(1);
   115		    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
   116					     std::forward<_Args>(__args)...);
   117		    ++this->_M_impl._M_finish;
   118		    _GLIBCXX_ASAN_ANNOTATE_GREW(1);
   119		  }
   120		else
   121		  _M_realloc_insert(end(), std::forward<_Args>(__args)...);
   122	#if __cplusplus > 201402L
   123		return back();
   124	#endif
   125	      }
   126	#endif
   127	
   128	  template<typename _Tp, typename _Alloc>
   129	    typename vector<_Tp, _Alloc>::iterator
   130	    vector<_Tp, _Alloc>::
   131	#if __cplusplus >= 201103L
   132	    insert(const_iterator __position, const value_type& __x)
   133	#else
   134	    insert(iterator __position, const value_type& __x)
   135	#endif
   136	    {
   137	      const size_type __n = __position - begin();
   138	      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
   139		if (__position == end())
   140		  {
   141		    _GLIBCXX_ASAN_ANNOTATE_GROW(1);
   142		    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
   143					     __x);
   144		    ++this->_M_impl._M_finish;
   145		    _GLIBCXX_ASAN_ANNOTATE_GREW(1);
   146		  }
   147		else
   148		  {
   149	#if __cplusplus >= 201103L
   150		    const auto __pos = begin() + (__position - cbegin());
   151		    // __x could be an existing element of this vector, so make a
   152		    // copy of it before _M_insert_aux moves elements around.
   153		    _Temporary_value __x_copy(this, __x);
   154		    _M_insert_aux(__pos, std::move(__x_copy._M_val()));
   155	#else
   156		    _M_insert_aux(__position, __x);
   157	#endif
   158		  }
   159	      else
   160	#if __cplusplus >= 201103L
   161		_M_realloc_insert(begin() + (__position - cbegin()), __x);
   162	#else
   163		_M_realloc_insert(__position, __x);
   164	#endif
   165	
   166	      return iterator(this->_M_impl._M_start + __n);
   167	    }
   168	
   169	  template<typename _Tp, typename _Alloc>
   170	    typename vector<_Tp, _Alloc>::iterator
   171	    vector<_Tp, _Alloc>::
   172	    _M_erase(iterator __position)
   173	    {
   174	      if (__position + 1 != end())
   175		_GLIBCXX_MOVE3(__position + 1, end(), __position);
   176	      --this->_M_impl._M_finish;
   177	      _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
   178	      _GLIBCXX_ASAN_ANNOTATE_SHRINK(1);
   179	      return __position;
   180	    }
   181	
   182	  template<typename _Tp, typename _Alloc>
   183	    typename vector<_Tp, _Alloc>::iterator
   184	    vector<_Tp, _Alloc>::
   185	    _M_erase(iterator __first, iterator __last)
   186	    {
   187	      if (__first != __last)
   188		{
   189		  if (__last != end())
   190		    _GLIBCXX_MOVE3(__last, end(), __first);
   191		  _M_erase_at_end(__first.base() + (end() - __last));
   192		}
   193	      return __first;
   194	    }
   195	
   196	  template<typename _Tp, typename _Alloc>
   197	    vector<_Tp, _Alloc>&
   198	    vector<_Tp, _Alloc>::
   199	    operator=(const vector<_Tp, _Alloc>& __x)
   200	    {
   201	      if (&__x != this)
   202		{
   203		  _GLIBCXX_ASAN_ANNOTATE_REINIT;
   204	#if __cplusplus >= 201103L
   205		  if (_Alloc_traits::_S_propagate_on_copy_assign())
   206		    {
   207		      if (!_Alloc_traits::_S_always_equal()
   208		          && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
   209		        {
   210			  // replacement allocator cannot free existing storage
   211			  this->clear();
   212			  _M_deallocate(this->_M_impl._M_start,
   213					this->_M_impl._M_end_of_storage
   214					- this->_M_impl._M_start);
   215			  this->_M_impl._M_start = nullptr;
   216			  this->_M_impl._M_finish = nullptr;
   217			  this->_M_impl._M_end_of_storage = nullptr;
   218			}
   219		      std::__alloc_on_copy(_M_get_Tp_allocator(),
   220					   __x._M_get_Tp_allocator());
   221		    }
   222	#endif
   223		  const size_type __xlen = __x.size();
   224		  if (__xlen > capacity())
   225		    {
   226		      pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
   227							   __x.end());
   228		      std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
   229				    _M_get_Tp_allocator());
   230		      _M_deallocate(this->_M_impl._M_start,
   231				    this->_M_impl._M_end_of_storage
   232				    - this->_M_impl._M_start);
   233		      this->_M_impl._M_start = __tmp;
   234		      this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
   235		    }
   236		  else if (size() >= __xlen)
   237		    {
   238		      std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
   239				    end(), _M_get_Tp_allocator());
   240		    }
   241		  else
   242		    {
   243		      std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
   244				this->_M_impl._M_start);
   245		      std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
   246						  __x._M_impl._M_finish,
   247						  this->_M_impl._M_finish,
   248						  _M_get_Tp_allocator());
   249		    }
   250		  this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
   251		}
   252	      return *this;
   253	    }
   254	
   255	  template<typename _Tp, typename _Alloc>
   256	    void
   257	    vector<_Tp, _Alloc>::
   258	    _M_fill_assign(size_t __n, const value_type& __val)
   259	    {
   260	      if (__n > capacity())
   261		{
   262		  vector __tmp(__n, __val, _M_get_Tp_allocator());
   263		  __tmp._M_impl._M_swap_data(this->_M_impl);
   264		}
   265	      else if (__n > size())
   266		{
   267		  std::fill(begin(), end(), __val);
   268		  const size_type __add = __n - size();
   269		  _GLIBCXX_ASAN_ANNOTATE_GROW(__add);
   270		  this->_M_impl._M_finish =
   271		    std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
   272						  __add, __val, _M_get_Tp_allocator());
   273		  _GLIBCXX_ASAN_ANNOTATE_GREW(__add);
   274		}
   275	      else
   276	        _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
   277	    }
   278	
   279	  template<typename _Tp, typename _Alloc>
   280	    template<typename _InputIterator>
   281	      void
   282	      vector<_Tp, _Alloc>::
   283	      _M_assign_aux(_InputIterator __first, _InputIterator __last,
   284			    std::input_iterator_tag)
   285	      {
   286		pointer __cur(this->_M_impl._M_start);
   287		for (; __first != __last && __cur != this->_M_impl._M_finish;
   288		     ++__cur, (void)++__first)
   289		  *__cur = *__first;
   290		if (__first == __last)
   291		  _M_erase_at_end(__cur);
   292		else
   293		  _M_range_insert(end(), __first, __last,
   294				  std::__iterator_category(__first));
   295	      }
   296	
   297	  template<typename _Tp, typename _Alloc>
   298	    template<typename _ForwardIterator>
   299	      void
   300	      vector<_Tp, _Alloc>::
   301	      _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
   302			    std::forward_iterator_tag)
   303	      {
   304		const size_type __len = std::distance(__first, __last);
   305	
   306		if (__len > capacity())
   307		  {
   308		    _S_check_init_len(__len, _M_get_Tp_allocator());
   309		    pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
   310		    std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
   311				  _M_get_Tp_allocator());
   312		    _GLIBCXX_ASAN_ANNOTATE_REINIT;
   313		    _M_deallocate(this->_M_impl._M_start,
   314				  this->_M_impl._M_end_of_storage
   315				  - this->_M_impl._M_start);
   316		    this->_M_impl._M_start = __tmp;
   317		    this->_M_impl._M_finish = this->_M_impl._M_start + __len;
   318		    this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
   319		  }
   320		else if (size() >= __len)
   321		  _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
   322		else
   323		  {
   324		    _ForwardIterator __mid = __first;
   325		    std::advance(__mid, size());
   326		    std::copy(__first, __mid, this->_M_impl._M_start);
   327		    const size_type __attribute__((__unused__)) __n = __len - size();
   328		    _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
   329		    this->_M_impl._M_finish =
   330		      std::__uninitialized_copy_a(__mid, __last,
   331						  this->_M_impl._M_finish,
   332						  _M_get_Tp_allocator());
   333		    _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
   334		  }
   335	      }
   336	
   337	#if __cplusplus >= 201103L
   338	  template<typename _Tp, typename _Alloc>
   339	    auto
   340	    vector<_Tp, _Alloc>::
   341	    _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator
   342	    {
   343	      const auto __n = __position - cbegin();
   344	      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
   345		if (__position == cend())
   346		  {
   347		    _GLIBCXX_ASAN_ANNOTATE_GROW(1);
   348		    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
   349					     std::move(__v));
   350		    ++this->_M_impl._M_finish;
   351		    _GLIBCXX_ASAN_ANNOTATE_GREW(1);
   352		  }
   353		else
   354		  _M_insert_aux(begin() + __n, std::move(__v));
   355	      else
   356		_M_realloc_insert(begin() + __n, std::move(__v));
   357	
   358	      return iterator(this->_M_impl._M_start + __n);
   359	    }
   360	
   361	  template<typename _Tp, typename _Alloc>
   362	    template<typename... _Args>
   363	      auto
   364	      vector<_Tp, _Alloc>::
   365	      _M_emplace_aux(const_iterator __position, _Args&&... __args)
   366	      -> iterator
   367	      {
   368		const auto __n = __position - cbegin();
   369		if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
   370		  if (__position == cend())
   371		    {
   372		      _GLIBCXX_ASAN_ANNOTATE_GROW(1);
   373		      _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
   374					       std::forward<_Args>(__args)...);
   375		      ++this->_M_impl._M_finish;
   376		      _GLIBCXX_ASAN_ANNOTATE_GREW(1);
   377		    }
   378		  else
   379		    {
   380		      // We need to construct a temporary because something in __args...
   381		      // could alias one of the elements of the container and so we
   382		      // need to use it before _M_insert_aux moves elements around.
   383		      _Temporary_value __tmp(this, std::forward<_Args>(__args)...);
   384		      _M_insert_aux(begin() + __n, std::move(__tmp._M_val()));
   385		    }
   386		else
   387		  _M_realloc_insert(begin() + __n, std::forward<_Args>(__args)...);
   388	
   389		return iterator(this->_M_impl._M_start + __n);
   390	      }
   391	
   392	  template<typename _Tp, typename _Alloc>
   393	    template<typename _Arg>
   394	      void
   395	      vector<_Tp, _Alloc>::
   396	      _M_insert_aux(iterator __position, _Arg&& __arg)
   397	#else
   398	  template<typename _Tp, typename _Alloc>
   399	    void
   400	    vector<_Tp, _Alloc>::
   401	    _M_insert_aux(iterator __position, const _Tp& __x)
   402	#endif
   403	    {
   404	      _GLIBCXX_ASAN_ANNOTATE_GROW(1);
   405	      _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
   406				       _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
   407	      ++this->_M_impl._M_finish;
   408	      _GLIBCXX_ASAN_ANNOTATE_GREW(1);
   409	#if __cplusplus < 201103L
   410	      _Tp __x_copy = __x;
   411	#endif
   412	      _GLIBCXX_MOVE_BACKWARD3(__position.base(),
   413				      this->_M_impl._M_finish - 2,
   414				      this->_M_impl._M_finish - 1);
   415	#if __cplusplus < 201103L
   416	      *__position = __x_copy;
   417	#else
   418	      *__position = std::forward<_Arg>(__arg);
   419	#endif
   420	    }
   421	
   422	#if __cplusplus >= 201103L
   423	  template<typename _Tp, typename _Alloc>
   424	    template<typename... _Args>
   425	      void
   426	      vector<_Tp, _Alloc>::
   427	      _M_realloc_insert(iterator __position, _Args&&... __args)
   428	#else
   429	  template<typename _Tp, typename _Alloc>
   430	    void
   431	    vector<_Tp, _Alloc>::
   432	    _M_realloc_insert(iterator __position, const _Tp& __x)
   433	#endif
   434	    {
   435	      const size_type __len =
   436		_M_check_len(size_type(1), "vector::_M_realloc_insert");
   437	      pointer __old_start = this->_M_impl._M_start;
   438	      pointer __old_finish = this->_M_impl._M_finish;
   439	      const size_type __elems_before = __position - begin();
   440	      pointer __new_start(this->_M_allocate(__len));
   441	      pointer __new_finish(__new_start);
   442	      __try
   443		{
   444		  // The order of the three operations is dictated by the C++11
   445		  // case, where the moves could alter a new element belonging
   446		  // to the existing vector.  This is an issue only for callers
   447		  // taking the element by lvalue ref (see last bullet of C++11
   448		  // [res.on.arguments]).
   449		  _Alloc_traits::construct(this->_M_impl,
   450					   __new_start + __elems_before,
   451	#if __cplusplus >= 201103L
   452					   std::forward<_Args>(__args)...);
   453	#else
   454					   __x);
   455	#endif
   456		  __new_finish = pointer();
   457	
   458	#if __cplusplus >= 201103L
   459		  if _GLIBCXX17_CONSTEXPR (_S_use_relocate())
   460		    {
   461		      __new_finish = _S_relocate(__old_start, __position.base(),
   462						 __new_start, _M_get_Tp_allocator());
   463	
   464		      ++__new_finish;
   465	
   466		      __new_finish = _S_relocate(__position.base(), __old_finish,
   467						 __new_finish, _M_get_Tp_allocator());
   468		    }
   469		  else
   470	#endif
   471		    {
   472		      __new_finish
   473			= std::__uninitialized_move_if_noexcept_a
   474			(__old_start, __position.base(),
   475			 __new_start, _M_get_Tp_allocator());
   476	
   477		      ++__new_finish;
   478	
   479		      __new_finish
   480			= std::__uninitialized_move_if_noexcept_a
   481			(__position.base(), __old_finish,
   482			 __new_finish, _M_get_Tp_allocator());
   483		    }
   484		}
   485	      __catch(...)
   486		{
   487		  if (!__new_finish)
   488		    _Alloc_traits::destroy(this->_M_impl,
   489					   __new_start + __elems_before);
   490		  else
   491		    std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
   492		  _M_deallocate(__new_start, __len);
   493		  __throw_exception_again;
   494		}
   495	#if __cplusplus >= 201103L
   496	      if _GLIBCXX17_CONSTEXPR (!_S_use_relocate())
   497	#endif
   498		std::_Destroy(__old_start, __old_finish, _M_get_Tp_allocator());
   499	      _GLIBCXX_ASAN_ANNOTATE_REINIT;
   500	      _M_deallocate(__old_start,
   501			    this->_M_impl._M_end_of_storage - __old_start);
   502	      this->_M_impl._M_start = __new_start;
   503	      this->_M_impl._M_finish = __new_finish;
   504	      this->_M_impl._M_end_of_storage = __new_start + __len;
   505	    }
   506	
   507	  template<typename _Tp, typename _Alloc>
   508	    void
   509	    vector<_Tp, _Alloc>::
   510	    _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
   511	    {
   512	      if (__n != 0)
   513		{
   514		  if (size_type(this->_M_impl._M_end_of_storage
   515				- this->_M_impl._M_finish) >= __n)
   516		    {
   517	#if __cplusplus < 201103L
   518		      value_type __x_copy = __x;
   519	#else
   520		      _Temporary_value __tmp(this, __x);
   521		      value_type& __x_copy = __tmp._M_val();
   522	#endif
   523		      const size_type __elems_after = end() - __position;
   524		      pointer __old_finish(this->_M_impl._M_finish);
   525		      if (__elems_after > __n)
   526			{
   527			  _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
   528			  std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
   529						      this->_M_impl._M_finish,
   530						      this->_M_impl._M_finish,
   531						      _M_get_Tp_allocator());
   532			  this->_M_impl._M_finish += __n;
   533			  _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
   534			  _GLIBCXX_MOVE_BACKWARD3(__position.base(),
   535						  __old_finish - __n, __old_finish);
   536			  std::fill(__position.base(), __position.base() + __n,
   537				    __x_copy);
   538			}
   539		      else
   540			{
   541			  _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
   542			  this->_M_impl._M_finish =
   543			    std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
   544							  __n - __elems_after,
   545							  __x_copy,
   546							  _M_get_Tp_allocator());
   547			  _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
   548			  std::__uninitialized_move_a(__position.base(), __old_finish,
   549						      this->_M_impl._M_finish,
   550						      _M_get_Tp_allocator());
   551			  this->_M_impl._M_finish += __elems_after;
   552			  _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
   553			  std::fill(__position.base(), __old_finish, __x_copy);
   554			}
   555		    }
   556		  else
   557		    {
   558		      const size_type __len =
   559			_M_check_len(__n, "vector::_M_fill_insert");
   560		      const size_type __elems_before = __position - begin();
   561		      pointer __new_start(this->_M_allocate(__len));
   562		      pointer __new_finish(__new_start);
   563		      __try
   564			{
   565			  // See _M_realloc_insert above.
   566			  std::__uninitialized_fill_n_a(__new_start + __elems_before,
   567							__n, __x,
   568							_M_get_Tp_allocator());
   569			  __new_finish = pointer();
   570	
   571			  __new_finish
   572			    = std::__uninitialized_move_if_noexcept_a
   573			    (this->_M_impl._M_start, __position.base(),
   574			     __new_start, _M_get_Tp_allocator());
   575	
   576			  __new_finish += __n;
   577	
   578			  __new_finish
   579			    = std::__uninitialized_move_if_noexcept_a
   580			    (__position.base(), this->_M_impl._M_finish,
   581			     __new_finish, _M_get_Tp_allocator());
   582			}
   583		      __catch(...)
   584			{
   585			  if (!__new_finish)
   586			    std::_Destroy(__new_start + __elems_before,
   587					  __new_start + __elems_before + __n,
   588					  _M_get_Tp_allocator());
   589			  else
   590			    std::_Destroy(__new_start, __new_finish,
   591					  _M_get_Tp_allocator());
   592			  _M_deallocate(__new_start, __len);
   593			  __throw_exception_again;
   594			}
   595		      std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
   596				    _M_get_Tp_allocator());
   597		      _GLIBCXX_ASAN_ANNOTATE_REINIT;
   598		      _M_deallocate(this->_M_impl._M_start,
   599				    this->_M_impl._M_end_of_storage
   600				    - this->_M_impl._M_start);
   601		      this->_M_impl._M_start = __new_start;
   602		      this->_M_impl._M_finish = __new_finish;
   603		      this->_M_impl._M_end_of_storage = __new_start + __len;
   604		    }
   605		}
   606	    }
   607	
   608	#if __cplusplus >= 201103L
   609	  template<typename _Tp, typename _Alloc>
   610	    void
   611	    vector<_Tp, _Alloc>::
   612	    _M_default_append(size_type __n)
   613	    {
   614	      if (__n != 0)
   615		{
   616		  const size_type __size = size();
   617		  size_type __navail = size_type(this->_M_impl._M_end_of_storage
   618						 - this->_M_impl._M_finish);
   619	
   620		  if (__size > max_size() || __navail > max_size() - __size)
   621		    __builtin_unreachable();
   622	
   623		  if (__navail >= __n)
   624		    {
   625		      _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
   626		      this->_M_impl._M_finish =
   627			std::__uninitialized_default_n_a(this->_M_impl._M_finish,
   628							 __n, _M_get_Tp_allocator());
   629		      _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
   630		    }
   631		  else
   632		    {
   633		      const size_type __len =
   634			_M_check_len(__n, "vector::_M_default_append");
   635		      pointer __new_start(this->_M_allocate(__len));
   636		      if _GLIBCXX17_CONSTEXPR (_S_use_relocate())
   637			{
   638			  __try
   639			    {
   640			      std::__uninitialized_default_n_a(__new_start + __size,
   641				      __n, _M_get_Tp_allocator());
   642			    }
   643			  __catch(...)
   644			    {
   645			      _M_deallocate(__new_start, __len);
   646			      __throw_exception_again;
   647			    }
   648			  _S_relocate(this->_M_impl._M_start, this->_M_impl._M_finish,
   649				      __new_start, _M_get_Tp_allocator());
   650			}
   651		      else
   652			{
   653			  pointer __destroy_from = pointer();
   654			  __try
   655			    {
   656			      std::__uninitialized_default_n_a(__new_start + __size,
   657				      __n, _M_get_Tp_allocator());
   658			      __destroy_from = __new_start + __size;
   659			      std::__uninitialized_move_if_noexcept_a(
   660				      this->_M_impl._M_start, this->_M_impl._M_finish,
   661				      __new_start, _M_get_Tp_allocator());
   662			    }
   663			  __catch(...)
   664			    {
   665			      if (__destroy_from)
   666				std::_Destroy(__destroy_from, __destroy_from + __n,
   667					      _M_get_Tp_allocator());
   668			      _M_deallocate(__new_start, __len);
   669			      __throw_exception_again;
   670			    }
   671			  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
   672					_M_get_Tp_allocator());
   673			}
   674		      _GLIBCXX_ASAN_ANNOTATE_REINIT;
   675		      _M_deallocate(this->_M_impl._M_start,
   676				    this->_M_impl._M_end_of_storage
   677				    - this->_M_impl._M_start);
   678		      this->_M_impl._M_start = __new_start;
   679		      this->_M_impl._M_finish = __new_start + __size + __n;
   680		      this->_M_impl._M_end_of_storage = __new_start + __len;
   681		    }
   682		}
   683	    }
   684	
   685	  template<typename _Tp, typename _Alloc>
   686	    bool
   687	    vector<_Tp, _Alloc>::
   688	    _M_shrink_to_fit()
   689	    {
   690	      if (capacity() == size())
   691		return false;
   692	      _GLIBCXX_ASAN_ANNOTATE_REINIT;
   693	      return std::__shrink_to_fit_aux<vector>::_S_do_it(*this);
   694	    }
   695	#endif
   696	
   697	  template<typename _Tp, typename _Alloc>
   698	    template<typename _InputIterator>
   699	      void
   700	      vector<_Tp, _Alloc>::
   701	      _M_range_insert(iterator __pos, _InputIterator __first,
   702			      _InputIterator __last, std::input_iterator_tag)
   703	      {
   704		if (__pos == end())
   705		  {
   706		    for (; __first != __last; ++__first)
   707		      insert(end(), *__first);
   708		  }
   709		else if (__first != __last)
   710		  {
   711		    vector __tmp(__first, __last, _M_get_Tp_allocator());
   712		    insert(__pos,
   713			   _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.begin()),
   714			   _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.end()));
   715		  }
   716	      }
   717	
   718	  template<typename _Tp, typename _Alloc>
   719	    template<typename _ForwardIterator>
   720	      void
   721	      vector<_Tp, _Alloc>::
   722	      _M_range_insert(iterator __position, _ForwardIterator __first,
   723			      _ForwardIterator __last, std::forward_iterator_tag)
   724	      {
   725		if (__first != __last)
   726		  {
   727		    const size_type __n = std::distance(__first, __last);
   728		    if (size_type(this->_M_impl._M_end_of_storage
   729				  - this->_M_impl._M_finish) >= __n)
   730		      {
   731			const size_type __elems_after = end() - __position;
   732			pointer __old_finish(this->_M_impl._M_finish);
   733			if (__elems_after > __n)
   734			  {
   735			    _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
   736			    std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
   737							this->_M_impl._M_finish,
   738							this->_M_impl._M_finish,
   739							_M_get_Tp_allocator());
   740			    this->_M_impl._M_finish += __n;
   741			    _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
   742			    _GLIBCXX_MOVE_BACKWARD3(__position.base(),
   743						    __old_finish - __n, __old_finish);
   744			    std::copy(__first, __last, __position);
   745			  }
   746			else
   747			  {
   748			    _ForwardIterator __mid = __first;
   749			    std::advance(__mid, __elems_after);
   750			    _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
   751			    std::__uninitialized_copy_a(__mid, __last,
   752							this->_M_impl._M_finish,
   753							_M_get_Tp_allocator());
   754			    this->_M_impl._M_finish += __n - __elems_after;
   755			    _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
   756			    std::__uninitialized_move_a(__position.base(),
   757							__old_finish,
   758							this->_M_impl._M_finish,
   759							_M_get_Tp_allocator());
   760			    this->_M_impl._M_finish += __elems_after;
   761			    _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
   762			    std::copy(__first, __mid, __position);
   763			  }
   764		      }
   765		    else
   766		      {
   767			const size_type __len =
   768			  _M_check_len(__n, "vector::_M_range_insert");
   769			pointer __new_start(this->_M_allocate(__len));
   770			pointer __new_finish(__new_start);
   771			__try
   772			  {
   773			    __new_finish
   774			      = std::__uninitialized_move_if_noexcept_a
   775			      (this->_M_impl._M_start, __position.base(),
   776			       __new_start, _M_get_Tp_allocator());
   777			    __new_finish
   778			      = std::__uninitialized_copy_a(__first, __last,
   779							    __new_finish,
   780							    _M_get_Tp_allocator());
   781			    __new_finish
   782			      = std::__uninitialized_move_if_noexcept_a
   783			      (__position.base(), this->_M_impl._M_finish,
   784			       __new_finish, _M_get_Tp_allocator());
   785			  }
   786			__catch(...)
   787			  {
   788			    std::_Destroy(__new_start, __new_finish,
   789					  _M_get_Tp_allocator());
   790			    _M_deallocate(__new_start, __len);
   791			    __throw_exception_again;
   792			  }
   793			std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
   794				      _M_get_Tp_allocator());
   795			_GLIBCXX_ASAN_ANNOTATE_REINIT;
   796			_M_deallocate(this->_M_impl._M_start,
   797				      this->_M_impl._M_end_of_storage
   798				      - this->_M_impl._M_start);
   799			this->_M_impl._M_start = __new_start;
   800			this->_M_impl._M_finish = __new_finish;
   801			this->_M_impl._M_end_of_storage = __new_start + __len;
   802		      }
   803		  }
   804	      }
   805	
   806	
   807	  // vector<bool>
   808	  template<typename _Alloc>
   809	    void
   810	    vector<bool, _Alloc>::
   811	    _M_reallocate(size_type __n)
   812	    {
   813	      _Bit_pointer __q = this->_M_allocate(__n);
   814	      iterator __start(std::__addressof(*__q), 0);
   815	      iterator __finish(_M_copy_aligned(begin(), end(), __start));
   816	      this->_M_deallocate();
   817	      this->_M_impl._M_start = __start;
   818	      this->_M_impl._M_finish = __finish;
   819	      this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
   820	    }
   821	
   822	  template<typename _Alloc>
   823	    void
   824	    vector<bool, _Alloc>::
   825	    _M_fill_insert(iterator __position, size_type __n, bool __x)
   826	    {
   827	      if (__n == 0)
   828		return;
   829	      if (capacity() - size() >= __n)
   830		{
   831		  std::copy_backward(__position, end(),
   832				     this->_M_impl._M_finish + difference_type(__n));
   833		  std::fill(__position, __position + difference_type(__n), __x);
   834		  this->_M_impl._M_finish += difference_type(__n);
   835		}
   836	      else
   837		{
   838		  const size_type __len = 
   839		    _M_check_len(__n, "vector<bool>::_M_fill_insert");
   840		  _Bit_pointer __q = this->_M_allocate(__len);
   841		  iterator __start(std::__addressof(*__q), 0);
   842		  iterator __i = _M_copy_aligned(begin(), __position, __start);
   843		  std::fill(__i, __i + difference_type(__n), __x);
   844		  iterator __finish = std::copy(__position, end(),
   845						__i + difference_type(__n));
   846		  this->_M_deallocate();
   847		  this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
   848		  this->_M_impl._M_start = __start;
   849		  this->_M_impl._M_finish = __finish;
   850		}
   851	    }
   852	
   853	  template<typename _Alloc>
   854	    template<typename _ForwardIterator>
   855	      void
   856	      vector<bool, _Alloc>::
   857	      _M_insert_range(iterator __position, _ForwardIterator __first, 
   858			      _ForwardIterator __last, std::forward_iterator_tag)
   859	      {
   860		if (__first != __last)
   861		  {
   862		    size_type __n = std::distance(__first, __last);
   863		    if (capacity() - size() >= __n)
   864		      {
   865			std::copy_backward(__position, end(),
   866					   this->_M_impl._M_finish
   867					   + difference_type(__n));
   868			std::copy(__first, __last, __position);
   869			this->_M_impl._M_finish += difference_type(__n);
   870		      }
   871		    else
   872		      {
   873			const size_type __len =
   874			  _M_check_len(__n, "vector<bool>::_M_insert_range");
   875			_Bit_pointer __q = this->_M_allocate(__len);
   876			iterator __start(std::__addressof(*__q), 0);
   877			iterator __i = _M_copy_aligned(begin(), __position, __start);
   878			__i = std::copy(__first, __last, __i);
   879			iterator __finish = std::copy(__position, end(), __i);
   880			this->_M_deallocate();
   881			this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
   882			this->_M_impl._M_start = __start;
   883			this->_M_impl._M_finish = __finish;
   884		      }
   885		  }
   886	      }
   887	
   888	  template<typename _Alloc>
   889	    void
   890	    vector<bool, _Alloc>::
   891	    _M_insert_aux(iterator __position, bool __x)
   892	    {
   893	      if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
   894		{
   895		  std::copy_backward(__position, this->_M_impl._M_finish, 
   896				     this->_M_impl._M_finish + 1);
   897		  *__position = __x;
   898		  ++this->_M_impl._M_finish;
   899		}
   900	      else
   901		{
   902		  const size_type __len =
   903		    _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
   904		  _Bit_pointer __q = this->_M_allocate(__len);
   905		  iterator __start(std::__addressof(*__q), 0);
   906		  iterator __i = _M_copy_aligned(begin(), __position, __start);
   907		  *__i++ = __x;
   908		  iterator __finish = std::copy(__position, end(), __i);
   909		  this->_M_deallocate();
   910		  this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
   911		  this->_M_impl._M_start = __start;
   912		  this->_M_impl._M_finish = __finish;
   913		}
   914	    }
   915	
   916	  template<typename _Alloc>
   917	    typename vector<bool, _Alloc>::iterator
   918	    vector<bool, _Alloc>::
   919	    _M_erase(iterator __position)
   920	    {
   921	      if (__position + 1 != end())
   922	        std::copy(__position + 1, end(), __position);
   923	      --this->_M_impl._M_finish;
   924	      return __position;
   925	    }
   926	
   927	  template<typename _Alloc>
   928	    typename vector<bool, _Alloc>::iterator
   929	    vector<bool, _Alloc>::
   930	    _M_erase(iterator __first, iterator __last)
   931	    {
   932	      if (__first != __last)
   933		_M_erase_at_end(std::copy(__last, end(), __first));
   934	      return __first;
   935	    }
   936	
   937	#if __cplusplus >= 201103L
   938	  template<typename _Alloc>
   939	    bool
   940	    vector<bool, _Alloc>::
   941	    _M_shrink_to_fit()
   942	    {
   943	      if (capacity() - size() < int(_S_word_bit))
   944		return false;
   945	      __try
   946		{
   947		  if (size_type __n = size())
   948		    _M_reallocate(__n);
   949		  else
   950		    {
   951		      this->_M_deallocate();
   952		      this->_M_impl._M_reset();
   953		    }
   954		  return true;
   955		}
   956	      __catch(...)
   957		{ return false; }
   958	    }
   959	#endif
   960	
   961	_GLIBCXX_END_NAMESPACE_CONTAINER
   962	_GLIBCXX_END_NAMESPACE_VERSION
   963	} // namespace std
   964	
   965	#if __cplusplus >= 201103L
   966	
   967	namespace std _GLIBCXX_VISIBILITY(default)
   968	{
   969	_GLIBCXX_BEGIN_NAMESPACE_VERSION
   970	
   971	  template<typename _Alloc>
   972	    size_t
   973	    hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>::
   974	    operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept
   975	    {
   976	      size_t __hash = 0;
   977	      using _GLIBCXX_STD_C::_S_word_bit;
   978	      using _GLIBCXX_STD_C::_Bit_type;
   979	
   980	      const size_t __words = __b.size() / _S_word_bit;
   981	      if (__words)
   982		{
   983		  const size_t __clength = __words * sizeof(_Bit_type);
   984		  __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength);
   985		}
   986	
   987	      const size_t __extrabits = __b.size() % _S_word_bit;
   988	      if (__extrabits)
   989		{
   990		  _Bit_type __hiword = *__b._M_impl._M_finish._M_p;
   991		  __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits);
   992	
   993		  const size_t __clength
   994		    = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__;
   995		  if (__words)
   996		    __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash);
   997		  else
   998		    __hash = std::_Hash_impl::hash(&__hiword, __clength);
   999		}
  1000	
  1001	      return __hash;
  1002	    }
  1003	
  1004	_GLIBCXX_END_NAMESPACE_VERSION
  1005	} // namespace std
  1006	
  1007	#endif // C++11
  1008	
  1009	#undef _GLIBCXX_ASAN_ANNOTATE_REINIT
  1010	#undef _GLIBCXX_ASAN_ANNOTATE_GROW
  1011	#undef _GLIBCXX_ASAN_ANNOTATE_GREW
  1012	#undef _GLIBCXX_ASAN_ANNOTATE_SHRINK
  1013	
  1014	#endif /* _VECTOR_TCC */