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

// <forward_list.tcc> -*- C++ -*-

// Copyright (C) 2008, 2009, 2010, 2011 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/>.

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

#ifndef _FORWARD_LIST_TCC
#define _FORWARD_LIST_TCC 1

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_CONTAINER

  template<typename _Tp, typename _Alloc>
    _Fwd_list_base<_Tp, _Alloc>::
    _Fwd_list_base(const _Fwd_list_base& __lst, const _Alloc& __a)
    : _M_impl(__a)
    {
      this->_M_impl._M_head._M_next = 0;
      _Fwd_list_node_base* __to = &this->_M_impl._M_head;
      _Node* __curr = static_cast<_Node*>(__lst._M_impl._M_head._M_next);

      while (__curr)
        {
          __to->_M_next = _M_create_node(__curr->_M_value);
          __to = __to->_M_next;
          __curr = static_cast<_Node*>(__curr->_M_next);
        }
    }

  template<typename _Tp, typename _Alloc>
    template<typename... _Args>
      _Fwd_list_node_base*
      _Fwd_list_base<_Tp, _Alloc>::
      _M_insert_after(const_iterator __pos, _Args&&... __args)
      {
        _Fwd_list_node_base* __to
	  = const_cast<_Fwd_list_node_base*>(__pos._M_node);
	_Node* __thing = _M_create_node(std::forward<_Args>(__args)...);
        __thing->_M_next = __to->_M_next;
        __to->_M_next = __thing;
        return __to->_M_next;
      }

  template<typename _Tp, typename _Alloc>
    _Fwd_list_node_base*
    _Fwd_list_base<_Tp, _Alloc>::
    _M_erase_after(_Fwd_list_node_base* __pos)
    {
      _Node* __curr = static_cast<_Node*>(__pos->_M_next);
      __pos->_M_next = __curr->_M_next;
      _M_get_Node_allocator().destroy(__curr);
      _M_put_node(__curr);
      return __pos->_M_next;
    }

  template<typename _Tp, typename _Alloc>
    _Fwd_list_node_base*
    _Fwd_list_base<_Tp, _Alloc>::
    _M_erase_after(_Fwd_list_node_base* __pos, 
                   _Fwd_list_node_base* __last)
    {
      _Node* __curr = static_cast<_Node*>(__pos->_M_next);
      while (__curr != __last)
        {
          _Node* __temp = __curr;
          __curr = static_cast<_Node*>(__curr->_M_next);
          _M_get_Node_allocator().destroy(__temp);
          _M_put_node(__temp);
        }
      __pos->_M_next = __last;
      return __last;
    }

  // Called by the range constructor to implement [23.1.1]/9
  template<typename _Tp, typename _Alloc>
    template<typename _InputIterator>
      void
      forward_list<_Tp, _Alloc>::
      _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
                             __false_type)
      {
        _Node_base* __to = &this->_M_impl._M_head;
        for (; __first != __last; ++__first)
          {
            __to->_M_next = this->_M_create_node(*__first);
            __to = __to->_M_next;
          }
      }

  // Called by forward_list(n,v,a), and the range constructor
  // when it turns out to be the same thing.
  template<typename _Tp, typename _Alloc>
    void
    forward_list<_Tp, _Alloc>::
    _M_fill_initialize(size_type __n, const value_type& __value)
    {
      _Node_base* __to = &this->_M_impl._M_head;
      for (; __n; --__n)
        {
          __to->_M_next = this->_M_create_node(__value);
          __to = __to->_M_next;
        }
    }

  template<typename _Tp, typename _Alloc>
    void
    forward_list<_Tp, _Alloc>::
    _M_default_initialize(size_type __n)
    {
      _Node_base* __to = &this->_M_impl._M_head;
      for (; __n; --__n)
        {
          __to->_M_next = this->_M_create_node();
          __to = __to->_M_next;
        }
    }

  template<typename _Tp, typename _Alloc>
    forward_list<_Tp, _Alloc>&
    forward_list<_Tp, _Alloc>::
    operator=(const forward_list& __list)
    {
      if (&__list != this)
        {
          iterator __prev1 = before_begin();
          iterator __curr1 = begin();
          iterator __last1 = end();
          const_iterator __first2 = __list.cbegin();
          const_iterator __last2 = __list.cend();
          while (__curr1 != __last1 && __first2 != __last2)
            {
              *__curr1 = *__first2;
              ++__prev1;
              ++__curr1;
              ++__first2;
            }
          if (__first2 == __last2)
            erase_after(__prev1, __last1);
          else
            insert_after(__prev1, __first2, __last2);
        }
      return *this;
    }

  template<typename _Tp, typename _Alloc>
    void
    forward_list<_Tp, _Alloc>::
    _M_default_insert_after(const_iterator __pos, size_type __n)
    {
      const_iterator __saved_pos = __pos;
      __try
	{
	  for (; __n; --__n)
	    __pos = emplace_after(__pos);
	}
      __catch(...)
	{
	  erase_after(__saved_pos, ++__pos);
	  __throw_exception_again;
	}
    }

  template<typename _Tp, typename _Alloc>
    void
    forward_list<_Tp, _Alloc>::
    resize(size_type __sz)
    {
      iterator __k = before_begin();

      size_type __len = 0;
      while (__k._M_next() != end() && __len < __sz)
        {
          ++__k;
          ++__len;
        }
      if (__len == __sz)
        erase_after(__k, end());
      else
	_M_default_insert_after(__k, __sz - __len);
    }

  template<typename _Tp, typename _Alloc>
    void
    forward_list<_Tp, _Alloc>::
    resize(size_type __sz, const value_type& __val)
    {
      iterator __k = before_begin();

      size_type __len = 0;
      while (__k._M_next() != end() && __len < __sz)
        {
          ++__k;
          ++__len;
        }
      if (__len == __sz)
        erase_after(__k, end());
      else
        insert_after(__k, __sz - __len, __val);
    }

  template<typename _Tp, typename _Alloc>
    typename forward_list<_Tp, _Alloc>::iterator
    forward_list<_Tp, _Alloc>::
    _M_splice_after(const_iterator __pos, forward_list&& __list)
    {
      _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
      iterator __before = __list.before_begin();
      return iterator(__tmp->_M_transfer_after(__before._M_node));
    }

  template<typename _Tp, typename _Alloc>
    void
    forward_list<_Tp, _Alloc>::
    splice_after(const_iterator __pos, forward_list&&,
                 const_iterator __before, const_iterator __last)
    {
      _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
      __tmp->_M_transfer_after(const_cast<_Node_base*>(__before._M_node),
                               const_cast<_Node_base*>(__last._M_node));
    }

  template<typename _Tp, typename _Alloc>
    typename forward_list<_Tp, _Alloc>::iterator
    forward_list<_Tp, _Alloc>::
    insert_after(const_iterator __pos, size_type __n, const _Tp& __val)
    {
      if (__n)
	{
	  forward_list __tmp(__n, __val, this->_M_get_Node_allocator());
	  return _M_splice_after(__pos, std::move(__tmp));
	}
      else
	return iterator(const_cast<_Node_base*>(__pos._M_node));
    }

  template<typename _Tp, typename _Alloc>
    template<typename _InputIterator>
      typename forward_list<_Tp, _Alloc>::iterator
      forward_list<_Tp, _Alloc>::
      insert_after(const_iterator __pos,
		   _InputIterator __first, _InputIterator __last)
      {
	forward_list __tmp(__first, __last, this->_M_get_Node_allocator());
	if (!__tmp.empty())
	  return _M_splice_after(__pos, std::move(__tmp));
	else
	  return iterator(const_cast<_Node_base*>(__pos._M_node));
      }

  template<typename _Tp, typename _Alloc>
    typename forward_list<_Tp, _Alloc>::iterator
    forward_list<_Tp, _Alloc>::
    insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
    {
      if (__il.size())
	{
	  forward_list __tmp(__il, this->_M_get_Node_allocator());
	  return _M_splice_after(__pos, std::move(__tmp));
	}
      else
	return iterator(const_cast<_Node_base*>(__pos._M_node));
    }

  template<typename _Tp, typename _Alloc>
    void
    forward_list<_Tp, _Alloc>::
    remove(const _Tp& __val)
    {
      _Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
      _Node* __extra = 0;

      while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
        {
          if (__tmp->_M_value == __val)
	    {
	      if (std::__addressof(__tmp->_M_value)
		  != std::__addressof(__val))
		{
		  this->_M_erase_after(__curr);
		  continue;
		}
	      else
		__extra = __curr;
	    }
	  __curr = static_cast<_Node*>(__curr->_M_next);
        }

      if (__extra)
	this->_M_erase_after(__extra);
    }

  template<typename _Tp, typename _Alloc>
    template<typename _Pred>
      void
      forward_list<_Tp, _Alloc>::
      remove_if(_Pred __pred)
      {
	_Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
        while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
          {
            if (__pred(__tmp->_M_value))
              this->_M_erase_after(__curr);
            else
              __curr = static_cast<_Node*>(__curr->_M_next);
          }
      }

  template<typename _Tp, typename _Alloc>
    template<typename _BinPred>
      void
      forward_list<_Tp, _Alloc>::
      unique(_BinPred __binary_pred)
      {
        iterator __first = begin();
        iterator __last = end();
        if (__first == __last)
          return;
        iterator __next = __first;
        while (++__next != __last)
        {
          if (__binary_pred(*__first, *__next))
            erase_after(__first);
          else
            __first = __next;
          __next = __first;
        }
      }

  template<typename _Tp, typename _Alloc>
    template<typename _Comp>
      void
      forward_list<_Tp, _Alloc>::
      merge(forward_list&& __list, _Comp __comp)
      {
        _Node_base* __node = &this->_M_impl._M_head;
        while (__node->_M_next && __list._M_impl._M_head._M_next)
          {
            if (__comp(static_cast<_Node*>
                       (__list._M_impl._M_head._M_next)->_M_value,
                       static_cast<_Node*>
                       (__node->_M_next)->_M_value))
              __node->_M_transfer_after(&__list._M_impl._M_head,
                                        __list._M_impl._M_head._M_next);
            __node = __node->_M_next;
          }
        if (__list._M_impl._M_head._M_next)
          {
            __node->_M_next = __list._M_impl._M_head._M_next;
            __list._M_impl._M_head._M_next = 0;
          }
      }

  template<typename _Tp, typename _Alloc>
    bool
    operator==(const forward_list<_Tp, _Alloc>& __lx,
               const forward_list<_Tp, _Alloc>& __ly)
    {
      //  We don't have size() so we need to walk through both lists
      //  making sure both iterators are valid.
      auto __ix = __lx.cbegin();
      auto __iy = __ly.cbegin();
      while (__ix != __lx.cend() && __iy != __ly.cend())
        {
          if (*__ix != *__iy)
            return false;
          ++__ix;
          ++__iy;
        }
      if (__ix == __lx.cend() && __iy == __ly.cend())
        return true;
      else
        return false;
    }

  template<typename _Tp, class _Alloc>
    template<typename _Comp>
      void
      forward_list<_Tp, _Alloc>::
      sort(_Comp __comp)
      {
        // If `next' is 0, return immediately.
        _Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);
        if (!__list)
          return;

        unsigned long __insize = 1;

        while (1)
          {
            _Node* __p = __list;
            __list = 0;
            _Node* __tail = 0;

            // Count number of merges we do in this pass.
            unsigned long __nmerges = 0;

            while (__p)
              {
                ++__nmerges;
                // There exists a merge to be done.
                // Step `insize' places along from p.
                _Node* __q = __p;
                unsigned long __psize = 0;
                for (unsigned long __i = 0; __i < __insize; ++__i)
                  {
                    ++__psize;
                    __q = static_cast<_Node*>(__q->_M_next);
                    if (!__q)
                      break;
                  }

                // If q hasn't fallen off end, we have two lists to merge.
                unsigned long __qsize = __insize;

                // Now we have two lists; merge them.
                while (__psize > 0 || (__qsize > 0 && __q))
                  {
                    // Decide whether next node of merge comes from p or q.
                    _Node* __e;
                    if (__psize == 0)
                      {
                        // p is empty; e must come from q.
                        __e = __q;
                        __q = static_cast<_Node*>(__q->_M_next);
                        --__qsize;
                      }
                    else if (__qsize == 0 || !__q)
                      {
                        // q is empty; e must come from p.
                        __e = __p;
                        __p = static_cast<_Node*>(__p->_M_next);
                        --__psize;
                      }
                    else if (__comp(__p->_M_value, __q->_M_value))
                      {
                        // First node of p is lower; e must come from p.
                        __e = __p;
                        __p = static_cast<_Node*>(__p->_M_next);
                        --__psize;
                      }
                    else
                      {
                        // First node of q is lower; e must come from q.
                        __e = __q;
                        __q = static_cast<_Node*>(__q->_M_next);
                        --__qsize;
                      }

                    // Add the next node to the merged list.
                    if (__tail)
                      __tail->_M_next = __e;
                    else
                      __list = __e;
                    __tail = __e;
                  }

                // Now p has stepped `insize' places along, and q has too.
                __p = __q;
              }
            __tail->_M_next = 0;

            // If we have done only one merge, we're finished.
            // Allow for nmerges == 0, the empty list case.
            if (__nmerges <= 1)
              {
                this->_M_impl._M_head._M_next = __list;
                return;
              }

            // Otherwise repeat, merging lists twice the size.
            __insize *= 2;
          }
      }
 
_GLIBCXX_END_NAMESPACE_CONTAINER
} // namespace std

#endif /* _FORWARD_LIST_TCC */
Commit	Line	Data
3a63c9cd ESR	1	// <forward_list.tcc> -- C++ --
3a63c9cd ESR	2
12ffa228	3	// Copyright (C) 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
3a63c9cd ESR	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)
3a63c9cd ESR	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.
	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/>.
3a63c9cd	24
f910786b BK	25	/** @file bits/forward_list.tcc
	26	* This is an internal header file, included by other library headers.
	27	* Do not attempt to use it directly. @headername{forward_list}
3a63c9cd ESR	28	*/
	29
	30	#ifndef _FORWARD_LIST_TCC
	31	#define _FORWARD_LIST_TCC 1
	32
12ffa228 BK	33	namespace std _GLIBCXX_VISIBILITY(default)
	34	{
	35	_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
3a63c9cd	36
3a63c9cd ESR	37	template<typename _Tp, typename _Alloc>
	38	_Fwd_list_base<_Tp, _Alloc>::
	39	_Fwd_list_base(const _Fwd_list_base& __lst, const _Alloc& __a)
	40	: _M_impl(__a)
	41	{
	42	this->_M_impl._M_head._M_next = 0;
97ffcedf PC	43	_Fwd_list_node_base* __to = &this->_M_impl._M_head;
	44	_Node* __curr = static_cast<_Node*>(__lst._M_impl._M_head._M_next);
	45
3a63c9cd	46	while (__curr)
1b32e4e5 BW	47	{
	48	__to->_M_next = _M_create_node(__curr->_M_value);
	49	__to = __to->_M_next;
97ffcedf	50	__curr = static_cast<_Node*>(__curr->_M_next);
1b32e4e5	51	}
3a63c9cd ESR	52	}
3a63c9cd ESR	53
2a7ee2f9 PC	54	template<typename _Tp, typename _Alloc>
2a7ee2f9 PC	55	template<typename... _Args>
97ffcedf	56	_Fwd_list_node_base*
2a7ee2f9 PC	57	_Fwd_list_base<_Tp, _Alloc>::
	58	_M_insert_after(const_iterator __pos, _Args&&... __args)
	59	{
97ffcedf PC	60	_Fwd_list_node_base* __to
	61	= const_cast<_Fwd_list_node_base*>(__pos._M_node);
	62	_Node* __thing = _M_create_node(std::forward<_Args>(__args)...);
1b32e4e5 BW	63	__thing->_M_next = __to->_M_next;
1b32e4e5 BW	64	__to->_M_next = __thing;
97ffcedf	65	return __to->_M_next;
2a7ee2f9 PC	66	}
2a7ee2f9 PC	67
3a63c9cd	68	template<typename _Tp, typename _Alloc>
efb7b456	69	_Fwd_list_node_base*
3a63c9cd	70	_Fwd_list_base<_Tp, _Alloc>::
97ffcedf	71	_M_erase_after(_Fwd_list_node_base* __pos)
3a63c9cd	72	{
97ffcedf	73	_Node* __curr = static_cast<_Node*>(__pos->_M_next);
33913cfa PC	74	__pos->_M_next = __curr->_M_next;
	75	_M_get_Node_allocator().destroy(__curr);
	76	_M_put_node(__curr);
efb7b456	77	return __pos->_M_next;
3a63c9cd ESR	78	}
	79
	80	template<typename _Tp, typename _Alloc>
efb7b456	81	_Fwd_list_node_base*
3a63c9cd	82	_Fwd_list_base<_Tp, _Alloc>::
97ffcedf PC	83	_M_erase_after(_Fwd_list_node_base* __pos,
97ffcedf PC	84	_Fwd_list_node_base* __last)
3a63c9cd	85	{
97ffcedf	86	_Node* __curr = static_cast<_Node*>(__pos->_M_next);
33913cfa	87	while (__curr != __last)
1b32e4e5	88	{
97ffcedf PC	89	_Node* __temp = __curr;
97ffcedf PC	90	__curr = static_cast<_Node*>(__curr->_M_next);
1b32e4e5 BW	91	_M_get_Node_allocator().destroy(__temp);
1b32e4e5 BW	92	_M_put_node(__temp);
1b32e4e5	93	}
33913cfa	94	__pos->_M_next = __last;
efb7b456	95	return __last;
3a63c9cd	96	}
efb7b456	97
e73d6fe8	98	// Called by the range constructor to implement [23.1.1]/9
3a63c9cd ESR	99	template<typename _Tp, typename _Alloc>
3a63c9cd ESR	100	template<typename _InputIterator>
e73d6fe8	101	void
3a63c9cd	102	forward_list<_Tp, _Alloc>::
e73d6fe8 ESR	103	_M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
e73d6fe8 ESR	104	__false_type)
3a63c9cd	105	{
97ffcedf	106	_Node_base* __to = &this->_M_impl._M_head;
27caad2e	107	for (; __first != __last; ++__first)
3a63c9cd	108	{
27caad2e	109	__to->_M_next = this->_M_create_node(*__first);
3a63c9cd	110	__to = __to->_M_next;
3a63c9cd ESR	111	}
	112	}
	113
e73d6fe8 ESR	114	// Called by forward_list(n,v,a), and the range constructor
e73d6fe8 ESR	115	// when it turns out to be the same thing.
3a63c9cd	116	template<typename _Tp, typename _Alloc>
e73d6fe8	117	void
3a63c9cd	118	forward_list<_Tp, _Alloc>::
e73d6fe8	119	_M_fill_initialize(size_type __n, const value_type& __value)
3a63c9cd	120	{
97ffcedf	121	_Node_base* __to = &this->_M_impl._M_head;
dc2cf706	122	for (; __n; --__n)
e73d6fe8 ESR	123	{
	124	__to->_M_next = this->_M_create_node(__value);
	125	__to = __to->_M_next;
	126	}
3a63c9cd ESR	127	}
3a63c9cd ESR	128
1e3ca17d	129	template<typename _Tp, typename _Alloc>
dc2cf706	130	void
1e3ca17d	131	forward_list<_Tp, _Alloc>::
dc2cf706	132	_M_default_initialize(size_type __n)
1e3ca17d	133	{
97ffcedf	134	_Node_base* __to = &this->_M_impl._M_head;
dc2cf706	135	for (; __n; --__n)
1e3ca17d PC	136	{
	137	__to->_M_next = this->_M_create_node();
	138	__to = __to->_M_next;
	139	}
	140	}
	141
3a63c9cd ESR	142	template<typename _Tp, typename _Alloc>
	143	forward_list<_Tp, _Alloc>&
	144	forward_list<_Tp, _Alloc>::
	145	operator=(const forward_list& __list)
	146	{
	147	if (&__list != this)
1b32e4e5 BW	148	{
	149	iterator __prev1 = before_begin();
	150	iterator __curr1 = begin();
	151	iterator __last1 = end();
	152	const_iterator __first2 = __list.cbegin();
	153	const_iterator __last2 = __list.cend();
	154	while (__curr1 != __last1 && __first2 != __last2)
	155	{
	156	__curr1 = __first2;
	157	++__prev1;
	158	++__curr1;
	159	++__first2;
	160	}
	161	if (__first2 == __last2)
	162	erase_after(__prev1, __last1);
	163	else
	164	insert_after(__prev1, __first2, __last2);
	165	}
3a63c9cd ESR	166	return *this;
	167	}
	168
dc2cf706 PC	169	template<typename _Tp, typename _Alloc>
	170	void
	171	forward_list<_Tp, _Alloc>::
	172	_M_default_insert_after(const_iterator __pos, size_type __n)
	173	{
	174	const_iterator __saved_pos = __pos;
	175	__try
	176	{
	177	for (; __n; --__n)
	178	__pos = emplace_after(__pos);
	179	}
	180	__catch(...)
	181	{
	182	erase_after(__saved_pos, ++__pos);
	183	__throw_exception_again;
	184	}
	185	}
	186
1e3ca17d PC	187	template<typename _Tp, typename _Alloc>
	188	void
	189	forward_list<_Tp, _Alloc>::
	190	resize(size_type __sz)
	191	{
	192	iterator __k = before_begin();
	193
	194	size_type __len = 0;
	195	while (__k._M_next() != end() && __len < __sz)
	196	{
	197	++__k;
	198	++__len;
	199	}
	200	if (__len == __sz)
	201	erase_after(__k, end());
	202	else
dc2cf706	203	_M_default_insert_after(__k, __sz - __len);
1e3ca17d PC	204	}
1e3ca17d PC	205
3a63c9cd ESR	206	template<typename _Tp, typename _Alloc>
	207	void
	208	forward_list<_Tp, _Alloc>::
ac42c960	209	resize(size_type __sz, const value_type& __val)
3a63c9cd ESR	210	{
	211	iterator __k = before_begin();
	212
	213	size_type __len = 0;
	214	while (__k._M_next() != end() && __len < __sz)
1b32e4e5 BW	215	{
	216	++__k;
	217	++__len;
	218	}
3a63c9cd	219	if (__len == __sz)
1b32e4e5	220	erase_after(__k, end());
3a63c9cd	221	else
1b32e4e5	222	insert_after(__k, __sz - __len, __val);
3a63c9cd ESR	223	}
3a63c9cd ESR	224
2a7ee2f9	225	template<typename _Tp, typename _Alloc>
16920896	226	typename forward_list<_Tp, _Alloc>::iterator
2a7ee2f9	227	forward_list<_Tp, _Alloc>::
16920896	228	_M_splice_after(const_iterator __pos, forward_list&& __list)
2a7ee2f9	229	{
16920896 PC	230	_Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
	231	iterator __before = __list.before_begin();
	232	return iterator(__tmp->_M_transfer_after(__before._M_node));
2a7ee2f9 PC	233	}
	234
	235	template<typename _Tp, typename _Alloc>
	236	void
	237	forward_list<_Tp, _Alloc>::
16920896	238	splice_after(const_iterator __pos, forward_list&&,
1b32e4e5	239	const_iterator __before, const_iterator __last)
2a7ee2f9	240	{
97ffcedf PC	241	_Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
	242	__tmp->_M_transfer_after(const_cast<_Node_base*>(__before._M_node),
	243	const_cast<_Node_base*>(__last._M_node));
2a7ee2f9 PC	244	}
2a7ee2f9 PC	245
16920896 PC	246	template<typename _Tp, typename _Alloc>
	247	typename forward_list<_Tp, _Alloc>::iterator
	248	forward_list<_Tp, _Alloc>::
	249	insert_after(const_iterator __pos, size_type __n, const _Tp& __val)
	250	{
	251	if (__n)
	252	{
	253	forward_list __tmp(__n, __val, this->_M_get_Node_allocator());
	254	return _M_splice_after(__pos, std::move(__tmp));
	255	}
	256	else
	257	return iterator(const_cast<_Node_base*>(__pos._M_node));
	258	}
	259
	260	template<typename _Tp, typename _Alloc>
	261	template<typename _InputIterator>
	262	typename forward_list<_Tp, _Alloc>::iterator
	263	forward_list<_Tp, _Alloc>::
	264	insert_after(const_iterator __pos,
	265	_InputIterator __first, _InputIterator __last)
	266	{
	267	forward_list __tmp(__first, __last, this->_M_get_Node_allocator());
	268	if (!__tmp.empty())
	269	return _M_splice_after(__pos, std::move(__tmp));
	270	else
	271	return iterator(const_cast<_Node_base*>(__pos._M_node));
	272	}
	273
	274	template<typename _Tp, typename _Alloc>
	275	typename forward_list<_Tp, _Alloc>::iterator
	276	forward_list<_Tp, _Alloc>::
	277	insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
	278	{
	279	if (__il.size())
	280	{
	281	forward_list __tmp(__il, this->_M_get_Node_allocator());
	282	return _M_splice_after(__pos, std::move(__tmp));
	283	}
	284	else
	285	return iterator(const_cast<_Node_base*>(__pos._M_node));
	286	}
	287
3a63c9cd ESR	288	template<typename _Tp, typename _Alloc>
	289	void
	290	forward_list<_Tp, _Alloc>::
	291	remove(const _Tp& __val)
	292	{
97ffcedf	293	_Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
afb767b4 PC	294	_Node* __extra = 0;
	295
	296	while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
1b32e4e5	297	{
afb767b4 PC	298	if (__tmp->_M_value == __val)
	299	{
	300	if (std::__addressof(__tmp->_M_value)
	301	!= std::__addressof(__val))
	302	{
	303	this->_M_erase_after(__curr);
	304	continue;
	305	}
	306	else
	307	__extra = __curr;
	308	}
	309	__curr = static_cast<_Node*>(__curr->_M_next);
1b32e4e5	310	}
afb767b4 PC	311
	312	if (__extra)
	313	this->_M_erase_after(__extra);
3a63c9cd ESR	314	}
	315
	316	template<typename _Tp, typename _Alloc>
	317	template<typename _Pred>
	318	void
	319	forward_list<_Tp, _Alloc>::
	320	remove_if(_Pred __pred)
	321	{
97ffcedf	322	_Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
afb767b4	323	while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
1b32e4e5	324	{
afb767b4	325	if (__pred(__tmp->_M_value))
1b32e4e5 BW	326	this->_M_erase_after(__curr);
1b32e4e5 BW	327	else
97ffcedf	328	__curr = static_cast<_Node*>(__curr->_M_next);
1b32e4e5	329	}
3a63c9cd ESR	330	}
3a63c9cd ESR	331
3a63c9cd ESR	332	template<typename _Tp, typename _Alloc>
	333	template<typename _BinPred>
	334	void
	335	forward_list<_Tp, _Alloc>::
	336	unique(_BinPred __binary_pred)
	337	{
	338	iterator __first = begin();
	339	iterator __last = end();
	340	if (__first == __last)
1b32e4e5	341	return;
3a63c9cd ESR	342	iterator __next = __first;
3a63c9cd ESR	343	while (++__next != __last)
1b32e4e5 BW	344	{
	345	if (__binary_pred(__first, __next))
	346	erase_after(__first);
	347	else
	348	__first = __next;
	349	__next = __first;
	350	}
3a63c9cd ESR	351	}
	352
	353	template<typename _Tp, typename _Alloc>
	354	template<typename _Comp>
	355	void
	356	forward_list<_Tp, _Alloc>::
	357	merge(forward_list&& __list, _Comp __comp)
	358	{
97ffcedf	359	_Node_base* __node = &this->_M_impl._M_head;
3a63c9cd ESR	360	while (__node->_M_next && __list._M_impl._M_head._M_next)
3a63c9cd ESR	361	{
97ffcedf	362	if (__comp(static_cast<_Node*>
1b32e4e5	363	(__list._M_impl._M_head._M_next)->_M_value,
97ffcedf	364	static_cast<_Node*>
1b32e4e5	365	(__node->_M_next)->_M_value))
3a63c9cd ESR	366	__node->_M_transfer_after(&__list._M_impl._M_head,
	367	__list._M_impl._M_head._M_next);
	368	__node = __node->_M_next;
	369	}
	370	if (__list._M_impl._M_head._M_next)
	371	{
	372	__node->_M_next = __list._M_impl._M_head._M_next;
	373	__list._M_impl._M_head._M_next = 0;
	374	}
	375	}
	376
2a7ee2f9 PC	377	template<typename _Tp, typename _Alloc>
	378	bool
	379	operator==(const forward_list<_Tp, _Alloc>& __lx,
	380	const forward_list<_Tp, _Alloc>& __ly)
	381	{
	382	// We don't have size() so we need to walk through both lists
	383	// making sure both iterators are valid.
919e5c5e PC	384	auto __ix = __lx.cbegin();
919e5c5e PC	385	auto __iy = __ly.cbegin();
2a7ee2f9 PC	386	while (__ix != __lx.cend() && __iy != __ly.cend())
	387	{
	388	if (__ix != __iy)
	389	return false;
	390	++__ix;
	391	++__iy;
	392	}
	393	if (__ix == __lx.cend() && __iy == __ly.cend())
	394	return true;
	395	else
	396	return false;
	397	}
	398
fc52f99d PC	399	template<typename _Tp, class _Alloc>
	400	template<typename _Comp>
	401	void
	402	forward_list<_Tp, _Alloc>::
	403	sort(_Comp __comp)
	404	{
fc52f99d	405	// If `next' is 0, return immediately.
97ffcedf	406	_Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);
fc52f99d PC	407	if (!__list)
	408	return;
	409
	410	unsigned long __insize = 1;
	411
	412	while (1)
	413	{
97ffcedf	414	_Node* __p = __list;
fc52f99d	415	__list = 0;
97ffcedf	416	_Node* __tail = 0;
fc52f99d PC	417
	418	// Count number of merges we do in this pass.
	419	unsigned long __nmerges = 0;
	420
	421	while (__p)
	422	{
	423	++__nmerges;
	424	// There exists a merge to be done.
	425	// Step `insize' places along from p.
97ffcedf	426	_Node* __q = __p;
fc52f99d PC	427	unsigned long __psize = 0;
	428	for (unsigned long __i = 0; __i < __insize; ++__i)
	429	{
	430	++__psize;
97ffcedf	431	__q = static_cast<_Node*>(__q->_M_next);
fc52f99d PC	432	if (!__q)
	433	break;
	434	}
	435
	436	// If q hasn't fallen off end, we have two lists to merge.
	437	unsigned long __qsize = __insize;
	438
	439	// Now we have two lists; merge them.
	440	while (__psize > 0 \|\| (__qsize > 0 && __q))
	441	{
	442	// Decide whether next node of merge comes from p or q.
97ffcedf	443	_Node* __e;
fc52f99d PC	444	if (__psize == 0)
	445	{
	446	// p is empty; e must come from q.
	447	__e = __q;
97ffcedf	448	__q = static_cast<_Node*>(__q->_M_next);
fc52f99d PC	449	--__qsize;
	450	}
	451	else if (__qsize == 0 \|\| !__q)
	452	{
	453	// q is empty; e must come from p.
	454	__e = __p;
97ffcedf	455	__p = static_cast<_Node*>(__p->_M_next);
fc52f99d PC	456	--__psize;
	457	}
	458	else if (__comp(__p->_M_value, __q->_M_value))
	459	{
	460	// First node of p is lower; e must come from p.
	461	__e = __p;
97ffcedf	462	__p = static_cast<_Node*>(__p->_M_next);
fc52f99d PC	463	--__psize;
	464	}
	465	else
	466	{
	467	// First node of q is lower; e must come from q.
	468	__e = __q;
97ffcedf	469	__q = static_cast<_Node*>(__q->_M_next);
fc52f99d PC	470	--__qsize;
	471	}
	472
	473	// Add the next node to the merged list.
	474	if (__tail)
	475	__tail->_M_next = __e;
	476	else
	477	__list = __e;
	478	__tail = __e;
	479	}
	480
	481	// Now p has stepped `insize' places along, and q has too.
	482	__p = __q;
	483	}
	484	__tail->_M_next = 0;
	485
	486	// If we have done only one merge, we're finished.
	487	// Allow for nmerges == 0, the empty list case.
	488	if (__nmerges <= 1)
	489	{
	490	this->_M_impl._M_head._M_next = __list;
	491	return;
	492	}
	493
	494	// Otherwise repeat, merging lists twice the size.
	495	__insize *= 2;
	496	}
	497	}
	498
12ffa228 BK	499	_GLIBCXX_END_NAMESPACE_CONTAINER
12ffa228 BK	500	} // namespace std
3a63c9cd ESR	501
	502	#endif /* _FORWARD_LIST_TCC */
	503