[thirdparty/gcc.git] / libstdc++-v3 / include / bits / list.tcc

// List implementation (out of line) -*- C++ -*-

// Copyright (C) 2001-2019 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1996,1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

/** @file bits/list.tcc
 *  This is an internal header file, included by other library headers.
 *  Do not attempt to use it directly. @headername{list}
 */

#ifndef _LIST_TCC
#define _LIST_TCC 1

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
_GLIBCXX_BEGIN_NAMESPACE_CONTAINER

  template<typename _Tp, typename _Alloc>
    void
    _List_base<_Tp, _Alloc>::
    _M_clear() _GLIBCXX_NOEXCEPT
    {
      typedef _List_node<_Tp>  _Node;
      __detail::_List_node_base* __cur = _M_impl._M_node._M_next;
      while (__cur != &_M_impl._M_node)
	{
	  _Node* __tmp = static_cast<_Node*>(__cur);
	  __cur = __tmp->_M_next;
	  _Tp* __val = __tmp->_M_valptr();
#if __cplusplus >= 201103L
	  _Node_alloc_traits::destroy(_M_get_Node_allocator(), __val);
#else
	  _Tp_alloc_type(_M_get_Node_allocator()).destroy(__val);
#endif
	  _M_put_node(__tmp);
	}
    }

#if __cplusplus >= 201103L
  template<typename _Tp, typename _Alloc>
    template<typename... _Args>
      typename list<_Tp, _Alloc>::iterator
      list<_Tp, _Alloc>::
      emplace(const_iterator __position, _Args&&... __args)
      {
	_Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
	__tmp->_M_hook(__position._M_const_cast()._M_node);
	this->_M_inc_size(1);
	return iterator(__tmp);
      }
#endif

  template<typename _Tp, typename _Alloc>
    typename list<_Tp, _Alloc>::iterator
    list<_Tp, _Alloc>::
#if __cplusplus >= 201103L
    insert(const_iterator __position, const value_type& __x)
#else
    insert(iterator __position, const value_type& __x)
#endif
    {
      _Node* __tmp = _M_create_node(__x);
      __tmp->_M_hook(__position._M_const_cast()._M_node);
      this->_M_inc_size(1);
      return iterator(__tmp);
    }

#if __cplusplus >= 201103L
  template<typename _Tp, typename _Alloc>
    typename list<_Tp, _Alloc>::iterator
    list<_Tp, _Alloc>::
    insert(const_iterator __position, size_type __n, const value_type& __x)
    {
      if (__n)
	{
	  list __tmp(__n, __x, get_allocator());
	  iterator __it = __tmp.begin();
	  splice(__position, __tmp);
	  return __it;
	}
      return __position._M_const_cast();
    }

  template<typename _Tp, typename _Alloc>
    template<typename _InputIterator, typename>
      typename list<_Tp, _Alloc>::iterator
      list<_Tp, _Alloc>::
      insert(const_iterator __position, _InputIterator __first,
	     _InputIterator __last)
      {
	list __tmp(__first, __last, get_allocator());
	if (!__tmp.empty())
	  {
	    iterator __it = __tmp.begin();
	    splice(__position, __tmp);
	    return __it;
	  }
	return __position._M_const_cast();
      }
#endif

  template<typename _Tp, typename _Alloc>
    typename list<_Tp, _Alloc>::iterator
    list<_Tp, _Alloc>::
#if __cplusplus >= 201103L
    erase(const_iterator __position) noexcept
#else
    erase(iterator __position)
#endif
    {
      iterator __ret = iterator(__position._M_node->_M_next);
      _M_erase(__position._M_const_cast());
      return __ret;
    }

  // Return a const_iterator indicating the position to start inserting or
  // erasing elements (depending whether the list is growing or shrinking),
  // and set __new_size to the number of new elements that must be appended.
  // Equivalent to the following, but performed optimally:
  // if (__new_size < size()) {
  //   __new_size = 0;
  //   return std::next(begin(), __new_size);
  // } else {
  //   __newsize -= size();
  //   return end();
  // }
  template<typename _Tp, typename _Alloc>
    typename list<_Tp, _Alloc>::const_iterator
    list<_Tp, _Alloc>::
    _M_resize_pos(size_type& __new_size) const
    {
      const_iterator __i;
#if _GLIBCXX_USE_CXX11_ABI
      const size_type __len = size();
      if (__new_size < __len)
	{
	  if (__new_size <= __len / 2)
	    {
	      __i = begin();
	      std::advance(__i, __new_size);
	    }
	  else
	    {
	      __i = end();
	      ptrdiff_t __num_erase = __len - __new_size;
	      std::advance(__i, -__num_erase);
	    }
	  __new_size = 0;
	  return __i;
	}
      else
	__i = end();
#else
      size_type __len = 0;
      for (__i = begin(); __i != end() && __len < __new_size; ++__i, ++__len)
        ;
#endif
      __new_size -= __len;
      return __i;
    }

#if __cplusplus >= 201103L
  template<typename _Tp, typename _Alloc>
    void
    list<_Tp, _Alloc>::
    _M_default_append(size_type __n)
    {
      size_type __i = 0;
      __try
	{
	  for (; __i < __n; ++__i)
	    emplace_back();
	}
      __catch(...)
	{
	  for (; __i; --__i)
	    pop_back();
	  __throw_exception_again;
	}
    }

  template<typename _Tp, typename _Alloc>
    void
    list<_Tp, _Alloc>::
    resize(size_type __new_size)
    {
      const_iterator __i = _M_resize_pos(__new_size);
      if (__new_size)
	_M_default_append(__new_size);
      else
        erase(__i, end());
    }

  template<typename _Tp, typename _Alloc>
    void
    list<_Tp, _Alloc>::
    resize(size_type __new_size, const value_type& __x)
    {
      const_iterator __i = _M_resize_pos(__new_size);
      if (__new_size)
        insert(end(), __new_size, __x);
      else
        erase(__i, end());
    }
#else
  template<typename _Tp, typename _Alloc>
    void
    list<_Tp, _Alloc>::
    resize(size_type __new_size, value_type __x)
    {
      const_iterator __i = _M_resize_pos(__new_size);
      if (__new_size)
        insert(end(), __new_size, __x);
      else
        erase(__i._M_const_cast(), end());
    }
#endif

  template<typename _Tp, typename _Alloc>
    list<_Tp, _Alloc>&
    list<_Tp, _Alloc>::
    operator=(const list& __x)
    {
      if (this != std::__addressof(__x))
	{
#if __cplusplus >= 201103L
	  if (_Node_alloc_traits::_S_propagate_on_copy_assign())
	    {
              auto& __this_alloc = this->_M_get_Node_allocator();
              auto& __that_alloc = __x._M_get_Node_allocator();
              if (!_Node_alloc_traits::_S_always_equal()
	          && __this_alloc != __that_alloc)
	        {
		  // replacement allocator cannot free existing storage
		  clear();
		}
	      std::__alloc_on_copy(__this_alloc, __that_alloc);
            }
#endif
	  _M_assign_dispatch(__x.begin(), __x.end(), __false_type());
	}
      return *this;
    }

  template<typename _Tp, typename _Alloc>
    void
    list<_Tp, _Alloc>::
    _M_fill_assign(size_type __n, const value_type& __val)
    {
      iterator __i = begin();
      for (; __i != end() && __n > 0; ++__i, --__n)
        *__i = __val;
      if (__n > 0)
        insert(end(), __n, __val);
      else
        erase(__i, end());
    }

  template<typename _Tp, typename _Alloc>
    template <typename _InputIterator>
      void
      list<_Tp, _Alloc>::
      _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
			 __false_type)
      {
        iterator __first1 = begin();
        iterator __last1 = end();
        for (; __first1 != __last1 && __first2 != __last2;
	     ++__first1, (void)++__first2)
          *__first1 = *__first2;
        if (__first2 == __last2)
          erase(__first1, __last1);
        else
          insert(__last1, __first2, __last2);
      }

#if __cplusplus > 201703L
# define _GLIBCXX20_ONLY(__expr) __expr
#else
# define _GLIBCXX20_ONLY(__expr)
#endif

  template<typename _Tp, typename _Alloc>
    typename list<_Tp, _Alloc>::__remove_return_type
    list<_Tp, _Alloc>::
    remove(const value_type& __value)
    {
      size_type __removed __attribute__((__unused__)) = 0;
      iterator __first = begin();
      iterator __last = end();
      iterator __extra = __last;
      while (__first != __last)
	{
	  iterator __next = __first;
	  ++__next;
	  if (*__first == __value)
	    {
	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
	      // 526. Is it undefined if a function in the standard changes
	      // in parameters?
	      if (std::__addressof(*__first) != std::__addressof(__value))
		{
		  _M_erase(__first);
		  _GLIBCXX20_ONLY( __removed++ );
		}
	      else
		__extra = __first;
	    }
	  __first = __next;
	}
      if (__extra != __last)
	{
	  _M_erase(__extra);
	  _GLIBCXX20_ONLY( __removed++ );
	}
      return _GLIBCXX20_ONLY( __removed );
    }

  template<typename _Tp, typename _Alloc>
    typename list<_Tp, _Alloc>::__remove_return_type
    list<_Tp, _Alloc>::
    unique()
    {
      iterator __first = begin();
      iterator __last = end();
      if (__first == __last)
	return _GLIBCXX20_ONLY( 0 );
      size_type __removed __attribute__((__unused__)) = 0;
      iterator __next = __first;
      while (++__next != __last)
	{
	  if (*__first == *__next)
	    {
	      _M_erase(__next);
	      _GLIBCXX20_ONLY( __removed++ );
	    }
	  else
	    __first = __next;
	  __next = __first;
	}
      return _GLIBCXX20_ONLY( __removed );
    }

  template<typename _Tp, typename _Alloc>
    void
    list<_Tp, _Alloc>::
#if __cplusplus >= 201103L
    merge(list&& __x)
#else
    merge(list& __x)
#endif
    {
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 300. list::merge() specification incomplete
      if (this != std::__addressof(__x))
	{
	  _M_check_equal_allocators(__x);

	  iterator __first1 = begin();
	  iterator __last1 = end();
	  iterator __first2 = __x.begin();
	  iterator __last2 = __x.end();
	  const size_t __orig_size = __x.size();
	  __try {
	    while (__first1 != __last1 && __first2 != __last2)
	      if (*__first2 < *__first1)
		{
		  iterator __next = __first2;
		  _M_transfer(__first1, __first2, ++__next);
		  __first2 = __next;
		}
	      else
		++__first1;
	    if (__first2 != __last2)
	      _M_transfer(__last1, __first2, __last2);

	    this->_M_inc_size(__x._M_get_size());
	    __x._M_set_size(0);
	  }
	  __catch(...)
	    {
	      const size_t __dist = std::distance(__first2, __last2);
	      this->_M_inc_size(__orig_size - __dist);
	      __x._M_set_size(__dist);
	      __throw_exception_again;
	    }
	}
    }

  template<typename _Tp, typename _Alloc>
    template <typename _StrictWeakOrdering>
      void
      list<_Tp, _Alloc>::
#if __cplusplus >= 201103L
      merge(list&& __x, _StrictWeakOrdering __comp)
#else
      merge(list& __x, _StrictWeakOrdering __comp)
#endif
      {
	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	// 300. list::merge() specification incomplete
	if (this != std::__addressof(__x))
	  {
	    _M_check_equal_allocators(__x);

	    iterator __first1 = begin();
	    iterator __last1 = end();
	    iterator __first2 = __x.begin();
	    iterator __last2 = __x.end();
	    const size_t __orig_size = __x.size();
	    __try
	      {
		while (__first1 != __last1 && __first2 != __last2)
		  if (__comp(*__first2, *__first1))
		    {
		      iterator __next = __first2;
		      _M_transfer(__first1, __first2, ++__next);
		      __first2 = __next;
		    }
		  else
		    ++__first1;
		if (__first2 != __last2)
		  _M_transfer(__last1, __first2, __last2);

		this->_M_inc_size(__x._M_get_size());
		__x._M_set_size(0);
	      }
	    __catch(...)
	      {
		const size_t __dist = std::distance(__first2, __last2);
		this->_M_inc_size(__orig_size - __dist);
		__x._M_set_size(__dist);
		__throw_exception_again;
	      }
	  }
      }

  template<typename _Tp, typename _Alloc>
    void
    list<_Tp, _Alloc>::
    sort()
    {
      // Do nothing if the list has length 0 or 1.
      if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
	  && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
      {
        list __carry;
        list __tmp[64];
        list * __fill = __tmp;
        list * __counter;
	__try
	  {
	    do
	      {
		__carry.splice(__carry.begin(), *this, begin());

		for(__counter = __tmp;
		    __counter != __fill && !__counter->empty();
		    ++__counter)
		  {
		    __counter->merge(__carry);
		    __carry.swap(*__counter);
		  }
		__carry.swap(*__counter);
		if (__counter == __fill)
		  ++__fill;
	      }
	    while ( !empty() );

	    for (__counter = __tmp + 1; __counter != __fill; ++__counter)
	      __counter->merge(*(__counter - 1));
	    swap( *(__fill - 1) );
	  }
	__catch(...)
	  {
	    this->splice(this->end(), __carry);
	    for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
	      this->splice(this->end(), __tmp[__i]);
	    __throw_exception_again;
	  }
      }
    }

  template<typename _Tp, typename _Alloc>
    template <typename _Predicate>
      typename list<_Tp, _Alloc>::__remove_return_type
      list<_Tp, _Alloc>::
      remove_if(_Predicate __pred)
      {
	size_type __removed __attribute__((__unused__)) = 0;
        iterator __first = begin();
        iterator __last = end();
        while (__first != __last)
	  {
	    iterator __next = __first;
	    ++__next;
	    if (__pred(*__first))
	      {
		_M_erase(__first);
		_GLIBCXX20_ONLY( __removed++ );
	      }
	    __first = __next;
	  }
	return _GLIBCXX20_ONLY( __removed );
      }

  template<typename _Tp, typename _Alloc>
    template <typename _BinaryPredicate>
      typename list<_Tp, _Alloc>::__remove_return_type
      list<_Tp, _Alloc>::
      unique(_BinaryPredicate __binary_pred)
      {
        iterator __first = begin();
        iterator __last = end();
        if (__first == __last)
	  return _GLIBCXX20_ONLY(0);
        size_type __removed __attribute__((__unused__)) = 0;
        iterator __next = __first;
        while (++__next != __last)
	  {
	    if (__binary_pred(*__first, *__next))
	      {
		_M_erase(__next);
		_GLIBCXX20_ONLY( __removed++ );
	      }
	    else
	      __first = __next;
	    __next = __first;
	  }
	return _GLIBCXX20_ONLY( __removed );
      }

#undef _GLIBCXX20_ONLY

  template<typename _Tp, typename _Alloc>
    template <typename _StrictWeakOrdering>
      void
      list<_Tp, _Alloc>::
      sort(_StrictWeakOrdering __comp)
      {
	// Do nothing if the list has length 0 or 1.
	if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
	    && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
	  {
	    list __carry;
	    list __tmp[64];
	    list * __fill = __tmp;
	    list * __counter;
	    __try
	      {
		do
		  {
		    __carry.splice(__carry.begin(), *this, begin());

		    for(__counter = __tmp;
			__counter != __fill && !__counter->empty();
			++__counter)
		      {
			__counter->merge(__carry, __comp);
			__carry.swap(*__counter);
		      }
		    __carry.swap(*__counter);
		    if (__counter == __fill)
		      ++__fill;
		  }
		while ( !empty() );

		for (__counter = __tmp + 1; __counter != __fill; ++__counter)
		  __counter->merge(*(__counter - 1), __comp);
		swap(*(__fill - 1));
	      }
	    __catch(...)
	      {
		this->splice(this->end(), __carry);
		for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
		  this->splice(this->end(), __tmp[__i]);
		__throw_exception_again;
	      }
	  }
      }

_GLIBCXX_END_NAMESPACE_CONTAINER
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std

#endif /* _LIST_TCC */
Commit	Line	Data
83144cfc PE	1	// List implementation (out of line) -- C++ --
83144cfc PE	2
a5544970	3	// Copyright (C) 2001-2019 Free Software Foundation, Inc.
83144cfc PE	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
748086b7	8	// Free Software Foundation; either version 3, or (at your option)
83144cfc PE	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
748086b7 JJ	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.
83144cfc	19
748086b7 JJ	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/>.
83144cfc PE	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,1997
	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
f910786b	51	/** @file bits/list.tcc
83144cfc	52	* This is an internal header file, included by other library headers.
f910786b	53	* Do not attempt to use it directly. @headername{list}
83144cfc PE	54	*/
83144cfc PE	55
3d7c150e BK	56	#ifndef _LIST_TCC
3d7c150e BK	57	#define _LIST_TCC 1
83144cfc	58
12ffa228 BK	59	namespace std _GLIBCXX_VISIBILITY(default)
12ffa228 BK	60	{
4a15d842	61	_GLIBCXX_BEGIN_NAMESPACE_VERSION
12ffa228	62	_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
3cbc7af0	63
3971a4d2 PE	64	template<typename _Tp, typename _Alloc>
3971a4d2 PE	65	void
6e0a7f2b	66	_List_base<_Tp, _Alloc>::
837bf511	67	_M_clear() _GLIBCXX_NOEXCEPT
83144cfc	68	{
3971a4d2	69	typedef _List_node<_Tp> _Node;
2a527383	70	__detail::_List_node_base* __cur = _M_impl._M_node._M_next;
0e83f45a	71	while (__cur != &_M_impl._M_node)
6e0a7f2b	72	{
2a527383 MG	73	_Node* __tmp = static_cast<_Node*>(__cur);
2a527383 MG	74	__cur = __tmp->_M_next;
cc7f3d0e	75	_Tp* __val = __tmp->_M_valptr();
734f5023	76	#if __cplusplus >= 201103L
cc7f3d0e	77	_Node_alloc_traits::destroy(_M_get_Node_allocator(), __val);
c841843f	78	#else
cc7f3d0e	79	_Tp_alloc_type(_M_get_Node_allocator()).destroy(__val);
c841843f	80	#endif
6e0a7f2b PC	81	_M_put_node(__tmp);
6e0a7f2b PC	82	}
e3d51be2	83	}
ed6814f7	84
734f5023	85	#if __cplusplus >= 201103L
84237dbb PC	86	template<typename _Tp, typename _Alloc>
	87	template<typename... _Args>
	88	typename list<_Tp, _Alloc>::iterator
	89	list<_Tp, _Alloc>::
7b61c5a9	90	emplace(const_iterator __position, _Args&&... __args)
84237dbb PC	91	{
84237dbb PC	92	_Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
7b61c5a9	93	__tmp->_M_hook(__position._M_const_cast()._M_node);
375f837b	94	this->_M_inc_size(1);
84237dbb PC	95	return iterator(__tmp);
	96	}
	97	#endif
	98
3971a4d2	99	template<typename _Tp, typename _Alloc>
6e0a7f2b PC	100	typename list<_Tp, _Alloc>::iterator
6e0a7f2b PC	101	list<_Tp, _Alloc>::
7b61c5a9 PC	102	#if __cplusplus >= 201103L
	103	insert(const_iterator __position, const value_type& __x)
	104	#else
3971a4d2	105	insert(iterator __position, const value_type& __x)
7b61c5a9	106	#endif
83144cfc	107	{
3971a4d2	108	_Node* __tmp = _M_create_node(__x);
7b61c5a9	109	__tmp->_M_hook(__position._M_const_cast()._M_node);
375f837b	110	this->_M_inc_size(1);
e182017e	111	return iterator(__tmp);
83144cfc	112	}
ed6814f7	113
019fdb79 PC	114	#if __cplusplus >= 201103L
	115	template<typename _Tp, typename _Alloc>
	116	typename list<_Tp, _Alloc>::iterator
	117	list<_Tp, _Alloc>::
	118	insert(const_iterator __position, size_type __n, const value_type& __x)
	119	{
	120	if (__n)
	121	{
	122	list __tmp(__n, __x, get_allocator());
	123	iterator __it = __tmp.begin();
	124	splice(__position, __tmp);
	125	return __it;
	126	}
	127	return __position._M_const_cast();
	128	}
	129
	130	template<typename _Tp, typename _Alloc>
	131	template<typename _InputIterator, typename>
	132	typename list<_Tp, _Alloc>::iterator
	133	list<_Tp, _Alloc>::
	134	insert(const_iterator __position, _InputIterator __first,
	135	_InputIterator __last)
	136	{
	137	list __tmp(__first, __last, get_allocator());
	138	if (!__tmp.empty())
	139	{
	140	iterator __it = __tmp.begin();
	141	splice(__position, __tmp);
	142	return __it;
	143	}
	144	return __position._M_const_cast();
	145	}
	146	#endif
	147
3971a4d2	148	template<typename _Tp, typename _Alloc>
6e0a7f2b PC	149	typename list<_Tp, _Alloc>::iterator
6e0a7f2b PC	150	list<_Tp, _Alloc>::
94938aec	151	#if __cplusplus >= 201103L
837bf511	152	erase(const_iterator __position) noexcept
94938aec	153	#else
3971a4d2	154	erase(iterator __position)
94938aec	155	#endif
83144cfc	156	{
e182017e	157	iterator __ret = iterator(__position._M_node->_M_next);
94938aec	158	_M_erase(__position._M_const_cast());
e135a038	159	return __ret;
83144cfc	160	}
ed6814f7	161
8e725716 JW	162	// Return a const_iterator indicating the position to start inserting or
	163	// erasing elements (depending whether the list is growing or shrinking),
	164	// and set __new_size to the number of new elements that must be appended.
	165	// Equivalent to the following, but performed optimally:
	166	// if (__new_size < size()) {
	167	// __new_size = 0;
	168	// return std::next(begin(), __new_size);
	169	// } else {
	170	// __newsize -= size();
	171	// return end();
	172	// }
	173	template<typename _Tp, typename _Alloc>
	174	typename list<_Tp, _Alloc>::const_iterator
	175	list<_Tp, _Alloc>::
	176	_M_resize_pos(size_type& __new_size) const
	177	{
	178	const_iterator __i;
	179	#if _GLIBCXX_USE_CXX11_ABI
	180	const size_type __len = size();
	181	if (__new_size < __len)
	182	{
	183	if (__new_size <= __len / 2)
	184	{
	185	__i = begin();
	186	std::advance(__i, __new_size);
	187	}
	188	else
	189	{
	190	__i = end();
	191	ptrdiff_t __num_erase = __len - __new_size;
	192	std::advance(__i, -__num_erase);
	193	}
	194	__new_size = 0;
	195	return __i;
	196	}
	197	else
	198	__i = end();
	199	#else
	200	size_type __len = 0;
	201	for (__i = begin(); __i != end() && __len < __new_size; ++__i, ++__len)
	202	;
	203	#endif
	204	__new_size -= __len;
	205	return __i;
	206	}
	207
734f5023	208	#if __cplusplus >= 201103L
dc2cf706 PC	209	template<typename _Tp, typename _Alloc>
	210	void
	211	list<_Tp, _Alloc>::
	212	_M_default_append(size_type __n)
	213	{
	214	size_type __i = 0;
	215	__try
	216	{
	217	for (; __i < __n; ++__i)
	218	emplace_back();
	219	}
	220	__catch(...)
	221	{
	222	for (; __i; --__i)
	223	pop_back();
	224	__throw_exception_again;
	225	}
	226	}
	227
	228	template<typename _Tp, typename _Alloc>
	229	void
	230	list<_Tp, _Alloc>::
	231	resize(size_type __new_size)
	232	{
8e725716 JW	233	const_iterator __i = _M_resize_pos(__new_size);
	234	if (__new_size)
	235	_M_default_append(__new_size);
	236	else
d695f915	237	erase(__i, end());
dc2cf706 PC	238	}
	239
	240	template<typename _Tp, typename _Alloc>
	241	void
	242	list<_Tp, _Alloc>::
	243	resize(size_type __new_size, const value_type& __x)
	244	{
8e725716 JW	245	const_iterator __i = _M_resize_pos(__new_size);
	246	if (__new_size)
	247	insert(end(), __new_size, __x);
	248	else
d695f915	249	erase(__i, end());
dc2cf706 PC	250	}
dc2cf706 PC	251	#else
3971a4d2 PE	252	template<typename _Tp, typename _Alloc>
3971a4d2 PE	253	void
6e0a7f2b	254	list<_Tp, _Alloc>::
2fecaef4	255	resize(size_type __new_size, value_type __x)
83144cfc	256	{
8e725716 JW	257	const_iterator __i = _M_resize_pos(__new_size);
	258	if (__new_size)
	259	insert(end(), __new_size, __x);
	260	else
	261	erase(__i._M_const_cast(), end());
83144cfc	262	}
dc2cf706	263	#endif
ed6814f7	264
3971a4d2	265	template<typename _Tp, typename _Alloc>
6e0a7f2b PC	266	list<_Tp, _Alloc>&
6e0a7f2b PC	267	list<_Tp, _Alloc>::
3971a4d2	268	operator=(const list& __x)
83144cfc	269	{
200fcd33	270	if (this != std::__addressof(__x))
f6592a9e	271	{
cc7f3d0e JW	272	#if __cplusplus >= 201103L
	273	if (_Node_alloc_traits::_S_propagate_on_copy_assign())
	274	{
	275	auto& __this_alloc = this->_M_get_Node_allocator();
	276	auto& __that_alloc = __x._M_get_Node_allocator();
	277	if (!_Node_alloc_traits::_S_always_equal()
	278	&& __this_alloc != __that_alloc)
	279	{
	280	// replacement allocator cannot free existing storage
	281	clear();
	282	}
	283	std::__alloc_on_copy(__this_alloc, __that_alloc);
	284	}
	285	#endif
	286	_M_assign_dispatch(__x.begin(), __x.end(), __false_type());
f6592a9e	287	}
3971a4d2 PE	288	return *this;
3971a4d2 PE	289	}
ed6814f7	290
3971a4d2 PE	291	template<typename _Tp, typename _Alloc>
3971a4d2 PE	292	void
6e0a7f2b	293	list<_Tp, _Alloc>::
3971a4d2	294	_M_fill_assign(size_type __n, const value_type& __val)
83144cfc	295	{
3971a4d2	296	iterator __i = begin();
6e0a7f2b	297	for (; __i != end() && __n > 0; ++__i, --__n)
3971a4d2 PE	298	*__i = __val;
	299	if (__n > 0)
	300	insert(end(), __n, __val);
	301	else
	302	erase(__i, end());
	303	}
ed6814f7	304
3971a4d2	305	template<typename _Tp, typename _Alloc>
08addde6	306	template <typename _InputIterator>
3971a4d2	307	void
6e0a7f2b	308	list<_Tp, _Alloc>::
ed6814f7	309	_M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
4d54539c	310	__false_type)
83144cfc	311	{
3971a4d2 PE	312	iterator __first1 = begin();
3971a4d2 PE	313	iterator __last1 = end();
ed6814f7	314	for (; __first1 != __last1 && __first2 != __last2;
27db01d8	315	++__first1, (void)++__first2)
3971a4d2 PE	316	__first1 = __first2;
	317	if (__first2 == __last2)
	318	erase(__first1, __last1);
	319	else
	320	insert(__last1, __first2, __last2);
83144cfc	321	}
ed6814f7	322
ef45724a JW	323	#if __cplusplus > 201703L
	324	# define _GLIBCXX20_ONLY(__expr) __expr
	325	#else
	326	# define _GLIBCXX20_ONLY(__expr)
	327	#endif
	328
3971a4d2	329	template<typename _Tp, typename _Alloc>
ef45724a	330	typename list<_Tp, _Alloc>::__remove_return_type
6e0a7f2b	331	list<_Tp, _Alloc>::
3971a4d2	332	remove(const value_type& __value)
83144cfc	333	{
ef45724a	334	size_type __removed __attribute__((__unused__)) = 0;
83144cfc PE	335	iterator __first = begin();
83144cfc PE	336	iterator __last = end();
687e00ee	337	iterator __extra = __last;
83144cfc	338	while (__first != __last)
6e0a7f2b PC	339	{
	340	iterator __next = __first;
	341	++__next;
	342	if (*__first == __value)
687e00ee HH	343	{
	344	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	345	// 526. Is it undefined if a function in the standard changes
	346	// in parameters?
882b3d5c	347	if (std::__addressof(*__first) != std::__addressof(__value))
ef45724a JW	348	{
	349	_M_erase(__first);
	350	_GLIBCXX20_ONLY( __removed++ );
	351	}
687e00ee HH	352	else
	353	__extra = __first;
	354	}
6e0a7f2b PC	355	__first = __next;
6e0a7f2b PC	356	}
687e00ee	357	if (__extra != __last)
ef45724a JW	358	{
	359	_M_erase(__extra);
	360	_GLIBCXX20_ONLY( __removed++ );
	361	}
	362	return _GLIBCXX20_ONLY( __removed );
83144cfc	363	}
ed6814f7	364
3971a4d2	365	template<typename _Tp, typename _Alloc>
ef45724a	366	typename list<_Tp, _Alloc>::__remove_return_type
6e0a7f2b	367	list<_Tp, _Alloc>::
3971a4d2	368	unique()
83144cfc PE	369	{
	370	iterator __first = begin();
	371	iterator __last = end();
f6592a9e	372	if (__first == __last)
ef45724a JW	373	return _GLIBCXX20_ONLY( 0 );
ef45724a JW	374	size_type __removed __attribute__((__unused__)) = 0;
83144cfc PE	375	iterator __next = __first;
83144cfc PE	376	while (++__next != __last)
6e0a7f2b PC	377	{
6e0a7f2b PC	378	if (__first == __next)
ef45724a JW	379	{
	380	_M_erase(__next);
	381	_GLIBCXX20_ONLY( __removed++ );
	382	}
6e0a7f2b PC	383	else
	384	__first = __next;
	385	__next = __first;
	386	}
ef45724a	387	return _GLIBCXX20_ONLY( __removed );
83144cfc	388	}
ed6814f7	389
3971a4d2	390	template<typename _Tp, typename _Alloc>
83144cfc	391	void
6e0a7f2b	392	list<_Tp, _Alloc>::
734f5023	393	#if __cplusplus >= 201103L
84237dbb PC	394	merge(list&& __x)
84237dbb PC	395	#else
3971a4d2	396	merge(list& __x)
84237dbb	397	#endif
83144cfc	398	{
41d3a0c3 PC	399	// _GLIBCXX_RESOLVE_LIB_DEFECTS
41d3a0c3 PC	400	// 300. list::merge() specification incomplete
200fcd33	401	if (this != std::__addressof(__x))
41d3a0c3	402	{
e5dcfacf	403	_M_check_equal_allocators(__x);
af8590d2	404
41d3a0c3 PC	405	iterator __first1 = begin();
	406	iterator __last1 = end();
	407	iterator __first2 = __x.begin();
	408	iterator __last2 = __x.end();
e5dcfacf VV	409	const size_t __orig_size = __x.size();
	410	__try {
	411	while (__first1 != __last1 && __first2 != __last2)
	412	if (__first2 < __first1)
	413	{
	414	iterator __next = __first2;
	415	_M_transfer(__first1, __first2, ++__next);
	416	__first2 = __next;
	417	}
	418	else
	419	++__first1;
	420	if (__first2 != __last2)
	421	_M_transfer(__last1, __first2, __last2);
375f837b	422
e5dcfacf VV	423	this->_M_inc_size(__x._M_get_size());
	424	__x._M_set_size(0);
	425	}
	426	__catch(...)
	427	{
648c9894	428	const size_t __dist = std::distance(__first2, __last2);
53426b63 VV	429	this->_M_inc_size(__orig_size - __dist);
53426b63 VV	430	__x._M_set_size(__dist);
e5dcfacf VV	431	__throw_exception_again;
e5dcfacf VV	432	}
41d3a0c3	433	}
83144cfc	434	}
ed6814f7	435
af8590d2 PC	436	template<typename _Tp, typename _Alloc>
	437	template <typename _StrictWeakOrdering>
	438	void
	439	list<_Tp, _Alloc>::
734f5023	440	#if __cplusplus >= 201103L
84237dbb PC	441	merge(list&& __x, _StrictWeakOrdering __comp)
84237dbb PC	442	#else
af8590d2	443	merge(list& __x, _StrictWeakOrdering __comp)
84237dbb	444	#endif
af8590d2 PC	445	{
	446	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	447	// 300. list::merge() specification incomplete
200fcd33	448	if (this != std::__addressof(__x))
af8590d2 PC	449	{
	450	_M_check_equal_allocators(__x);
	451
	452	iterator __first1 = begin();
	453	iterator __last1 = end();
	454	iterator __first2 = __x.begin();
	455	iterator __last2 = __x.end();
e5dcfacf VV	456	const size_t __orig_size = __x.size();
	457	__try
	458	{
	459	while (__first1 != __last1 && __first2 != __last2)
	460	if (__comp(__first2, __first1))
	461	{
	462	iterator __next = __first2;
	463	_M_transfer(__first1, __first2, ++__next);
	464	__first2 = __next;
	465	}
	466	else
	467	++__first1;
	468	if (__first2 != __last2)
	469	_M_transfer(__last1, __first2, __last2);
	470
	471	this->_M_inc_size(__x._M_get_size());
	472	__x._M_set_size(0);
	473	}
	474	__catch(...)
	475	{
648c9894	476	const size_t __dist = std::distance(__first2, __last2);
53426b63 VV	477	this->_M_inc_size(__orig_size - __dist);
53426b63 VV	478	__x._M_set_size(__dist);
e5dcfacf VV	479	__throw_exception_again;
e5dcfacf VV	480	}
af8590d2 PC	481	}
	482	}
	483
3971a4d2 PE	484	template<typename _Tp, typename _Alloc>
3971a4d2 PE	485	void
6e0a7f2b	486	list<_Tp, _Alloc>::
3971a4d2	487	sort()
83144cfc	488	{
3971a4d2	489	// Do nothing if the list has length 0 or 1.
03f9ea44 DM	490	if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
03f9ea44 DM	491	&& this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
83144cfc	492	{
3971a4d2	493	list __carry;
e135a038	494	list __tmp[64];
200fcd33	495	list * __fill = __tmp;
e135a038	496	list * __counter;
e5dcfacf	497	__try
f6592a9e	498	{
e5dcfacf	499	do
f6592a9e	500	{
e5dcfacf VV	501	__carry.splice(__carry.begin(), *this, begin());
	502
	503	for(__counter = __tmp;
	504	__counter != __fill && !__counter->empty();
	505	++__counter)
	506	{
	507	__counter->merge(__carry);
	508	__carry.swap(*__counter);
	509	}
f6592a9e	510	__carry.swap(*__counter);
e5dcfacf VV	511	if (__counter == __fill)
e5dcfacf VV	512	++__fill;
f6592a9e	513	}
e5dcfacf	514	while ( !empty() );
e135a038	515
e5dcfacf VV	516	for (__counter = __tmp + 1; __counter != __fill; ++__counter)
	517	__counter->merge(*(__counter - 1));
	518	swap( *(__fill - 1) );
	519	}
	520	__catch(...)
	521	{
	522	this->splice(this->end(), __carry);
d34d36ef JW	523	for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
d34d36ef JW	524	this->splice(this->end(), __tmp[__i]);
e5dcfacf VV	525	__throw_exception_again;
e5dcfacf VV	526	}
3971a4d2 PE	527	}
3971a4d2 PE	528	}
ed6814f7	529
3971a4d2 PE	530	template<typename _Tp, typename _Alloc>
3971a4d2 PE	531	template <typename _Predicate>
ef45724a	532	typename list<_Tp, _Alloc>::__remove_return_type
6e0a7f2b	533	list<_Tp, _Alloc>::
3971a4d2 PE	534	remove_if(_Predicate __pred)
3971a4d2 PE	535	{
ef45724a	536	size_type __removed __attribute__((__unused__)) = 0;
3971a4d2 PE	537	iterator __first = begin();
	538	iterator __last = end();
	539	while (__first != __last)
6e0a7f2b PC	540	{
	541	iterator __next = __first;
	542	++__next;
	543	if (__pred(*__first))
ef45724a JW	544	{
	545	_M_erase(__first);
	546	_GLIBCXX20_ONLY( __removed++ );
	547	}
6e0a7f2b PC	548	__first = __next;
6e0a7f2b PC	549	}
ef45724a	550	return _GLIBCXX20_ONLY( __removed );
3971a4d2	551	}
ed6814f7	552
3971a4d2 PE	553	template<typename _Tp, typename _Alloc>
3971a4d2 PE	554	template <typename _BinaryPredicate>
ef45724a	555	typename list<_Tp, _Alloc>::__remove_return_type
6e0a7f2b	556	list<_Tp, _Alloc>::
3971a4d2 PE	557	unique(_BinaryPredicate __binary_pred)
	558	{
	559	iterator __first = begin();
	560	iterator __last = end();
6e0a7f2b	561	if (__first == __last)
ef45724a JW	562	return _GLIBCXX20_ONLY(0);
ef45724a JW	563	size_type __removed __attribute__((__unused__)) = 0;
3971a4d2 PE	564	iterator __next = __first;
3971a4d2 PE	565	while (++__next != __last)
6e0a7f2b PC	566	{
6e0a7f2b PC	567	if (__binary_pred(__first, __next))
ef45724a JW	568	{
	569	_M_erase(__next);
	570	_GLIBCXX20_ONLY( __removed++ );
	571	}
6e0a7f2b PC	572	else
	573	__first = __next;
	574	__next = __first;
	575	}
ef45724a	576	return _GLIBCXX20_ONLY( __removed );
3971a4d2	577	}
ed6814f7	578
ef45724a JW	579	#undef _GLIBCXX20_ONLY
ef45724a JW	580
3971a4d2 PE	581	template<typename _Tp, typename _Alloc>
3971a4d2 PE	582	template <typename _StrictWeakOrdering>
f6592a9e	583	void
6e0a7f2b	584	list<_Tp, _Alloc>::
f6592a9e	585	sort(_StrictWeakOrdering __comp)
3971a4d2	586	{
f6592a9e	587	// Do nothing if the list has length 0 or 1.
03f9ea44 DM	588	if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
03f9ea44 DM	589	&& this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
f6592a9e PC	590	{
	591	list __carry;
	592	list __tmp[64];
200fcd33	593	list * __fill = __tmp;
f6592a9e	594	list * __counter;
e5dcfacf	595	__try
f6592a9e	596	{
e5dcfacf	597	do
f6592a9e	598	{
e5dcfacf VV	599	__carry.splice(__carry.begin(), *this, begin());
	600
	601	for(__counter = __tmp;
	602	__counter != __fill && !__counter->empty();
	603	++__counter)
	604	{
	605	__counter->merge(__carry, __comp);
	606	__carry.swap(*__counter);
	607	}
f6592a9e	608	__carry.swap(*__counter);
e5dcfacf VV	609	if (__counter == __fill)
e5dcfacf VV	610	++__fill;
f6592a9e	611	}
e5dcfacf	612	while ( !empty() );
ed6814f7	613
e5dcfacf VV	614	for (__counter = __tmp + 1; __counter != __fill; ++__counter)
	615	__counter->merge(*(__counter - 1), __comp);
	616	swap(*(__fill - 1));
	617	}
	618	__catch(...)
	619	{
	620	this->splice(this->end(), __carry);
d34d36ef JW	621	for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
d34d36ef JW	622	this->splice(this->end(), __tmp[__i]);
e5dcfacf VV	623	__throw_exception_again;
e5dcfacf VV	624	}
f6592a9e	625	}
83144cfc	626	}
3cbc7af0	627
12ffa228	628	_GLIBCXX_END_NAMESPACE_CONTAINER
4a15d842	629	_GLIBCXX_END_NAMESPACE_VERSION
12ffa228	630	} // namespace std
83144cfc	631
3d7c150e	632	#endif /* _LIST_TCC */
e135a038	633