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

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

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

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 51 Franklin Street, Fifth Floor,
// Boston, MA 02110-1301, USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/** @file forward_list.tcc
 *  This is a Standard C++ Library header.
 */

#ifndef _FORWARD_LIST_TCC
#define _FORWARD_LIST_TCC 1

_GLIBCXX_BEGIN_NAMESPACE(std)

 /**
  *  @brief  Sort the singly linked list starting after this node.
  *          This node is assumed to be an empty head node (of type
  *          _Fwd_list_node_base).
  */
  template<typename _Tp>
    template<typename _Comp>
      void
      _Fwd_list_node<_Tp>::
      _M_sort_after(_Comp __comp)
      {
	// If `next' is 0, return immediately.
	_Fwd_list_node* __list = static_cast<_Fwd_list_node*>(this->_M_next);
	if (!__list)
	  return;

	unsigned long __insize = 1;

	while (1)
	  {
	    _Fwd_list_node* __p = __list;
	    __list = 0;
	    _Fwd_list_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.
		_Fwd_list_node* __q = __p;
		unsigned long __psize = 0;
		for (unsigned long __i = 0; __i < __insize; ++__i)
		  {
		    ++__psize;
		    __q = static_cast<_Fwd_list_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.
		    _Fwd_list_node<_Tp>* __e;
		    if (__psize == 0)
		      {
			// p is empty; e must come from q.
			__e = __q;
			__q = static_cast<_Fwd_list_node*>(__q->_M_next);
			--__qsize;
		      }
		    else if (__qsize == 0 || !__q)
		      {
			// q is empty; e must come from p.
			__e = __p;
			__p = static_cast<_Fwd_list_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<_Fwd_list_node*>(__p->_M_next);
			--__psize;
		      }
		    else
		      {
			// First node of q is lower; e must come from q.
			__e = __q;
			__q = static_cast<_Fwd_list_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_next = __list;
		return;
	      }

	    // Otherwise repeat, merging lists twice the size.
	    __insize *= 2;
	  }
      }
 
  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);
      if (__curr)
	{
	  _Fwd_list_node_base* __next = __curr->_M_next;
	  __pos->_M_next = __next;
	  _M_get_Node_allocator().destroy(__curr);
	  _M_put_node(__curr);
	}
      return __pos;
    }

  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)
	{
	  _Node* __temp = __curr;
	  __curr = static_cast<_Node*>(__curr->_M_next);
	  _M_get_Node_allocator().destroy(__temp);
	  _M_put_node(__temp);
	  __pos->_M_next = __curr;
	  if (__temp == __last)
	    break;
	}
      return __pos;
    }
  
  template<typename _Tp, typename _Alloc>
    forward_list<_Tp, _Alloc>::
    forward_list(size_type __n)
    : _Base()
    {
      _Fwd_list_node_base* __to = &this->_M_impl._M_head;
      for (size_type __i = 0; __i < __n; ++__i)
	{
	  __to->_M_next = this->_M_create_node(_Tp());
	  __to = __to->_M_next;
	}
    }

  template<typename _Tp, typename _Alloc>
    forward_list<_Tp, _Alloc>::
    forward_list(size_type __n, const _Tp& __value, const _Alloc& __al)
    : _Base(__al)
    {
      _Fwd_list_node_base* __to = &this->_M_impl._M_head;
      for (size_type __i = 0; __i < __n; ++__i)
	{
	  __to->_M_next = this->_M_create_node(__value);
	  __to = __to->_M_next;
	}
    }

  template<typename _Tp, typename _Alloc>
    template<typename _InputIterator>
      forward_list<_Tp, _Alloc>::
      forward_list(_InputIterator __first, _InputIterator __last,
                   const _Alloc& __al)
      : _Base(__al)
      {
        _Fwd_list_node_base* __to = &this->_M_impl._M_head;
        _InputIterator __curr = __first;
        while (__curr != __last)
          {
            __to->_M_next = this->_M_create_node(*__curr);
            __to = __to->_M_next;
            ++__curr;
          }
      }

  template<typename _Tp, typename _Alloc>
    forward_list<_Tp, _Alloc>::
    forward_list(const forward_list& __list)
    : _Base(__list._M_get_Node_allocator())
    {
      const _Fwd_list_node_base* __from = &__list._M_impl._M_head;
      _Fwd_list_node_base* __to = &this->_M_impl._M_head;
      while (__from->_M_next != 0)
	{
	  const _Node* __temp = static_cast<_Node*>(__from->_M_next);
	  __to->_M_next = this->_M_create_node(__temp->_M_value);
	  __from = __from->_M_next;
	  __to = __to->_M_next;
	}
    }

  template<typename _Tp, typename _Alloc>
    forward_list<_Tp, _Alloc>::
    forward_list(std::initializer_list<_Tp> __il, const _Alloc& __al)
    : _Base(__al)
    {
      _Fwd_list_node_base* __to = &this->_M_impl._M_head;
      for (const _Tp* __item = __il.begin();
	   __item != __il.end(); ++__item)
	{
	  __to->_M_next = this->_M_create_node(*__item);
	  __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>::
    insert_after(const_iterator __pos,
		 size_type __n, const _Tp& __val)
    {
      _Fwd_list_node_base* __to
	= const_cast<_Fwd_list_node_base*>(__pos._M_node);
      _Fwd_list_node_base* __keep = __to->_M_next;
      for (size_type __i = 0; __i < __n; ++__i)
	{
	  __to->_M_next = this->_M_create_node(__val);
	  __to = __to->_M_next;
	}
      __to->_M_next = __keep;
    }

  template<typename _Tp, typename _Alloc>
    template<typename _InputIterator>
      void
      forward_list<_Tp, _Alloc>::
      insert_after(const_iterator __pos,
		   _InputIterator __first, _InputIterator __last)
      {
	_Fwd_list_node_base* __to
	  = const_cast<_Fwd_list_node_base*>(__pos._M_node);
	_Fwd_list_node_base* __keep = __to->_M_next;
	_InputIterator __curr = __first;
	while (__curr != __last)
	  {
	    __to->_M_next = this->_M_create_node(*__curr);
	    __to = __to->_M_next;
	    ++__curr;
	  }
	__to->_M_next = __keep;
      }

  template<typename _Tp, typename _Alloc>
    void
    forward_list<_Tp, _Alloc>::
    insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
    {
      _Fwd_list_node_base* __to
	= const_cast<_Fwd_list_node_base*>(__pos._M_node);
      _Fwd_list_node_base* __keep = __to->_M_next;
      const _Tp* __item = __il.begin();
      while (__item != __il.end())
	{
	  __to->_M_next = this->_M_create_node(*__item);
	  __to = __to->_M_next;
	  ++__item;
	}
      __to->_M_next = __keep;
    }

  template<typename _Tp, typename _Alloc>
    void
    forward_list<_Tp, _Alloc>::
    resize(size_type __sz, 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>
    void
    forward_list<_Tp, _Alloc>::
    splice_after(const_iterator __pos, forward_list&& __list)
    {
      if (!__list.empty() && &__list != this)
	{
	  _Fwd_list_node_base* __tmp
	    = const_cast<_Fwd_list_node_base*>(__pos._M_node);
	  const_iterator __before = __list.cbefore_begin();
	  __tmp->_M_transfer_after(const_cast<_Fwd_list_node_base*>
				   (__before._M_node));
	}
    }

  template<typename _Tp, typename _Alloc>
    void
    forward_list<_Tp, _Alloc>::
    splice_after(const_iterator __pos, forward_list&& __list,
		 const_iterator __before, const_iterator __last)
    {
      _Fwd_list_node_base* __tmp
	= const_cast<_Fwd_list_node_base*>(__pos._M_node);
      __tmp->_M_transfer_after(const_cast<_Fwd_list_node_base*>
			       (__before._M_node),
			       const_cast<_Fwd_list_node_base*>
			       (__last._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);
      while (_Node* __temp = static_cast<_Node*>(__curr->_M_next))
	{
	  if (__temp->_M_value == __val)
	    this->_M_erase_after(__curr);
	  else
	    __curr = static_cast<_Node*>(__curr->_M_next);
	}
    }

  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* __temp = static_cast<_Node*>(__curr->_M_next))
	  {
	    if (__pred(__temp->_M_value))
	      this->_M_erase_after(__curr);
	    else
	      __curr = static_cast<_Node*>(__curr->_M_next);
	  }
      }

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

  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)
      {
        _Fwd_list_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>
    void
    forward_list<_Tp, _Alloc>::
    reverse()
    { this->_M_impl._M_head._M_reverse_after(); }

  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.
      typename std::forward_list<_Tp, _Alloc>::const_iterator __ix
        = __lx.cbegin();
      typename std::forward_list<_Tp, _Alloc>::const_iterator __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;
    }

_GLIBCXX_END_NAMESPACE // namespace std

#endif /* _FORWARD_LIST_TCC */
Commit	Line	Data
3a63c9cd ESR	1	// <forward_list.tcc> -- C++ --
	2
	3	// Copyright (C) 2008 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 2, 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	// You should have received a copy of the GNU General Public License
	17	// along with this library; see the file COPYING. If not, write to
	18	// the Free Software Foundation, 51 Franklin Street, Fifth Floor,
	19	// Boston, MA 02110-1301, USA.
	20
	21	// As a special exception, you may use this file as part of a free software
	22	// library without restriction. Specifically, if other files instantiate
	23	// templates or use macros or inline functions from this file, or you compile
	24	// this file and link it with other files to produce an executable, this
	25	// file does not by itself cause the resulting executable to be covered by
	26	// the GNU General Public License. This exception does not however
	27	// invalidate any other reasons why the executable file might be covered by
	28	// the GNU General Public License.
	29
	30	/** @file forward_list.tcc
	31	* This is a Standard C++ Library header.
	32	*/
	33
	34	#ifndef _FORWARD_LIST_TCC
	35	#define _FORWARD_LIST_TCC 1
	36
	37	_GLIBCXX_BEGIN_NAMESPACE(std)
	38
	39	/**
	40	* @brief Sort the singly linked list starting after this node.
	41	* This node is assumed to be an empty head node (of type
	42	* _Fwd_list_node_base).
	43	*/
	44	template<typename _Tp>
	45	template<typename _Comp>
	46	void
	47	_Fwd_list_node<_Tp>::
	48	_M_sort_after(_Comp __comp)
	49	{
	50	// If `next' is 0, return immediately.
	51	_Fwd_list_node* __list = static_cast<_Fwd_list_node*>(this->_M_next);
	52	if (!__list)
	53	return;
	54
	55	unsigned long __insize = 1;
	56
	57	while (1)
	58	{
	59	_Fwd_list_node* __p = __list;
	60	__list = 0;
	61	_Fwd_list_node* __tail = 0;
	62
	63	// Count number of merges we do in this pass.
	64	unsigned long __nmerges = 0;
65
66	while (__p)
67	{
68	++__nmerges;
69	// There exists a merge to be done.
70	// Step `insize' places along from p.
71	_Fwd_list_node* __q = __p;
72	unsigned long __psize = 0;
73	for (unsigned long __i = 0; __i < __insize; ++__i)
74	{
75	++__psize;
76	__q = static_cast<_Fwd_list_node*>(__q->_M_next);
77	if (!__q)
78	break;
79	}
80
81	// If q hasn't fallen off end, we have two lists to merge.
82	unsigned long __qsize = __insize;
83
84	// Now we have two lists; merge them.
85	while (__psize > 0 \|\| (__qsize > 0 && __q))
86	{
87	// Decide whether next node of merge comes from p or q.
88	_Fwd_list_node<_Tp>* __e;
89	if (__psize == 0)
90	{
91	// p is empty; e must come from q.
92	__e = __q;
93	__q = static_cast<_Fwd_list_node*>(__q->_M_next);
94	--__qsize;
95	}
96	else if (__qsize == 0 \|\| !__q)
97	{
98	// q is empty; e must come from p.
99	__e = __p;
100	__p = static_cast<_Fwd_list_node*>(__p->_M_next);
101	--__psize;
102	}
103	else if (__comp(__p->_M_value, __q->_M_value))
104	{
105	// First node of p is lower; e must come from p.
106	__e = __p;
107	__p = static_cast<_Fwd_list_node*>(__p->_M_next);
108	--__psize;
109	}
110	else
111	{
112	// First node of q is lower; e must come from q.
113	__e = __q;
114	__q = static_cast<_Fwd_list_node*>(__q->_M_next);
115	--__qsize;
116	}
117
118	// Add the next node to the merged list.
119	if (__tail)
120	__tail->_M_next = __e;
121	else
122	__list = __e;
123	__tail = __e;
124	}
125
126	// Now p has stepped `insize' places along, and q has too.
127	__p = __q;
128	}
129	__tail->_M_next = 0;
130
131	// If we have done only one merge, we're finished.
132	// Allow for nmerges == 0, the empty list case.
133	if (__nmerges <= 1)
134	{
135	this->_M_next = __list;
136	return;
137	}
138
139	// Otherwise repeat, merging lists twice the size.
140	__insize *= 2;
141	}
142	}
143
144	template<typename _Tp, typename _Alloc>
145	_Fwd_list_base<_Tp, _Alloc>::
146	_Fwd_list_base(const _Fwd_list_base& __lst, const _Alloc& __a)
147	: _M_impl(__a)
148	{
149	this->_M_impl._M_head._M_next = 0;
150	_Fwd_list_node_base* __to = &this->_M_impl._M_head;
151	_Node* __curr = static_cast<_Node*>(__lst._M_impl._M_head._M_next);
152	while (__curr)
153	{
154	__to->_M_next = _M_create_node(__curr->_M_value);
155	__to = __to->_M_next;
156	__curr = static_cast<_Node*>(__curr->_M_next);
157	}
158	}
159
2a7ee2f9 PC	160	template<typename _Tp, typename _Alloc>
	161	template<typename... _Args>
	162	_Fwd_list_node_base*
	163	_Fwd_list_base<_Tp, _Alloc>::
	164	_M_insert_after(const_iterator __pos, _Args&&... __args)
	165	{
	166	_Fwd_list_node_base* __to
	167	= const_cast<_Fwd_list_node_base*>(__pos._M_node);
	168	_Node* __thing = _M_create_node(std::forward<_Args>(__args)...);
	169	__thing->_M_next = __to->_M_next;
	170	__to->_M_next = __thing;
	171	return __to->_M_next;
	172	}
	173
3a63c9cd ESR	174	template<typename _Tp, typename _Alloc>
	175	_Fwd_list_node_base*
	176	_Fwd_list_base<_Tp, _Alloc>::
	177	_M_erase_after(_Fwd_list_node_base* __pos)
	178	{
	179	_Node* __curr = static_cast<_Node*>(__pos->_M_next);
	180	if (__curr)
	181	{
	182	_Fwd_list_node_base* __next = __curr->_M_next;
	183	__pos->_M_next = __next;
	184	_M_get_Node_allocator().destroy(__curr);
	185	_M_put_node(__curr);
	186	}
	187	return __pos;
	188	}
	189
	190	template<typename _Tp, typename _Alloc>
	191	_Fwd_list_node_base*
	192	_Fwd_list_base<_Tp, _Alloc>::
	193	_M_erase_after(_Fwd_list_node_base* __pos, _Fwd_list_node_base* __last)
	194	{
	195	_Node* __curr = static_cast<_Node*>(__pos->_M_next);
	196	while (__curr)
	197	{
	198	_Node* __temp = __curr;
	199	__curr = static_cast<_Node*>(__curr->_M_next);
	200	_M_get_Node_allocator().destroy(__temp);
	201	_M_put_node(__temp);
	202	__pos->_M_next = __curr;
	203	if (__temp == __last)
	204	break;
	205	}
	206	return __pos;
	207	}
	208
	209	template<typename _Tp, typename _Alloc>
	210	forward_list<_Tp, _Alloc>::
	211	forward_list(size_type __n)
	212	: _Base()
	213	{
	214	_Fwd_list_node_base* __to = &this->_M_impl._M_head;
	215	for (size_type __i = 0; __i < __n; ++__i)
	216	{
2a7ee2f9	217	__to->_M_next = this->_M_create_node(_Tp());
3a63c9cd ESR	218	__to = __to->_M_next;
	219	}
	220	}
	221
	222	template<typename _Tp, typename _Alloc>
	223	forward_list<_Tp, _Alloc>::
	224	forward_list(size_type __n, const _Tp& __value, const _Alloc& __al)
	225	: _Base(__al)
	226	{
	227	_Fwd_list_node_base* __to = &this->_M_impl._M_head;
	228	for (size_type __i = 0; __i < __n; ++__i)
	229	{
2a7ee2f9	230	__to->_M_next = this->_M_create_node(__value);
3a63c9cd ESR	231	__to = __to->_M_next;
	232	}
	233	}
	234
	235	template<typename _Tp, typename _Alloc>
	236	template<typename _InputIterator>
	237	forward_list<_Tp, _Alloc>::
	238	forward_list(_InputIterator __first, _InputIterator __last,
	239	const _Alloc& __al)
	240	: _Base(__al)
	241	{
	242	_Fwd_list_node_base* __to = &this->_M_impl._M_head;
	243	_InputIterator __curr = __first;
	244	while (__curr != __last)
	245	{
2a7ee2f9	246	__to->_M_next = this->_M_create_node(*__curr);
3a63c9cd ESR	247	__to = __to->_M_next;
	248	++__curr;
	249	}
	250	}
	251
	252	template<typename _Tp, typename _Alloc>
	253	forward_list<_Tp, _Alloc>::
	254	forward_list(const forward_list& __list)
	255	: _Base(__list._M_get_Node_allocator())
	256	{
	257	const _Fwd_list_node_base* __from = &__list._M_impl._M_head;
	258	_Fwd_list_node_base* __to = &this->_M_impl._M_head;
	259	while (__from->_M_next != 0)
	260	{
	261	const _Node* __temp = static_cast<_Node*>(__from->_M_next);
2a7ee2f9	262	__to->_M_next = this->_M_create_node(__temp->_M_value);
3a63c9cd ESR	263	__from = __from->_M_next;
	264	__to = __to->_M_next;
	265	}
	266	}
	267
	268	template<typename _Tp, typename _Alloc>
	269	forward_list<_Tp, _Alloc>::
	270	forward_list(std::initializer_list<_Tp> __il, const _Alloc& __al)
	271	: _Base(__al)
	272	{
	273	_Fwd_list_node_base* __to = &this->_M_impl._M_head;
	274	for (const _Tp* __item = __il.begin();
	275	__item != __il.end(); ++__item)
	276	{
2a7ee2f9	277	__to->_M_next = this->_M_create_node(*__item);
3a63c9cd ESR	278	__to = __to->_M_next;
	279	}
	280	}
	281
	282	template<typename _Tp, typename _Alloc>
	283	forward_list<_Tp, _Alloc>&
	284	forward_list<_Tp, _Alloc>::
	285	operator=(const forward_list& __list)
	286	{
	287	if (&__list != this)
	288	{
	289	iterator __prev1 = before_begin();
	290	iterator __curr1 = begin();
	291	iterator __last1 = end();
	292	const_iterator __first2 = __list.cbegin();
	293	const_iterator __last2 = __list.cend();
	294	while (__curr1 != __last1 && __first2 != __last2)
	295	{
	296	__curr1 = __first2;
	297	++__prev1;
	298	++__curr1;
	299	++__first2;
	300	}
	301	if (__first2 == __last2)
	302	erase_after(__prev1, __last1);
	303	else
	304	insert_after(__prev1, __first2, __last2);
	305	}
	306	return *this;
	307	}
	308
	309	template<typename _Tp, typename _Alloc>
	310	void
	311	forward_list<_Tp, _Alloc>::
	312	insert_after(const_iterator __pos,
	313	size_type __n, const _Tp& __val)
	314	{
	315	_Fwd_list_node_base* __to
6bb76034	316	= const_cast<_Fwd_list_node_base*>(__pos._M_node);
3a63c9cd ESR	317	_Fwd_list_node_base* __keep = __to->_M_next;
	318	for (size_type __i = 0; __i < __n; ++__i)
	319	{
2a7ee2f9	320	__to->_M_next = this->_M_create_node(__val);
3a63c9cd ESR	321	__to = __to->_M_next;
	322	}
	323	__to->_M_next = __keep;
	324	}
	325
	326	template<typename _Tp, typename _Alloc>
	327	template<typename _InputIterator>
	328	void
	329	forward_list<_Tp, _Alloc>::
	330	insert_after(const_iterator __pos,
	331	_InputIterator __first, _InputIterator __last)
	332	{
	333	_Fwd_list_node_base* __to
6bb76034	334	= const_cast<_Fwd_list_node_base*>(__pos._M_node);
3a63c9cd ESR	335	_Fwd_list_node_base* __keep = __to->_M_next;
	336	_InputIterator __curr = __first;
	337	while (__curr != __last)
	338	{
2a7ee2f9	339	__to->_M_next = this->_M_create_node(*__curr);
3a63c9cd ESR	340	__to = __to->_M_next;
	341	++__curr;
	342	}
	343	__to->_M_next = __keep;
	344	}
	345
	346	template<typename _Tp, typename _Alloc>
	347	void
	348	forward_list<_Tp, _Alloc>::
	349	insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
	350	{
	351	_Fwd_list_node_base* __to
6bb76034	352	= const_cast<_Fwd_list_node_base*>(__pos._M_node);
3a63c9cd ESR	353	_Fwd_list_node_base* __keep = __to->_M_next;
	354	const _Tp* __item = __il.begin();
	355	while (__item != __il.end())
	356	{
2a7ee2f9	357	__to->_M_next = this->_M_create_node(*__item);
3a63c9cd ESR	358	__to = __to->_M_next;
	359	++__item;
	360	}
	361	__to->_M_next = __keep;
	362	}
	363
	364	template<typename _Tp, typename _Alloc>
	365	void
	366	forward_list<_Tp, _Alloc>::
	367	resize(size_type __sz, value_type __val)
	368	{
	369	iterator __k = before_begin();
	370
	371	size_type __len = 0;
	372	while (__k._M_next() != end() && __len < __sz)
	373	{
	374	++__k;
	375	++__len;
	376	}
	377	if (__len == __sz)
	378	erase_after(__k, end());
	379	else
	380	insert_after(__k, __sz - __len, __val);
	381	}
	382
2a7ee2f9 PC	383	template<typename _Tp, typename _Alloc>
	384	void
	385	forward_list<_Tp, _Alloc>::
	386	splice_after(const_iterator __pos, forward_list&& __list)
	387	{
	388	if (!__list.empty() && &__list != this)
	389	{
	390	_Fwd_list_node_base* __tmp
	391	= const_cast<_Fwd_list_node_base*>(__pos._M_node);
	392	const_iterator __before = __list.cbefore_begin();
	393	__tmp->_M_transfer_after(const_cast<_Fwd_list_node_base*>
	394	(__before._M_node));
	395	}
	396	}
	397
	398	template<typename _Tp, typename _Alloc>
	399	void
	400	forward_list<_Tp, _Alloc>::
	401	splice_after(const_iterator __pos, forward_list&& __list,
	402	const_iterator __before, const_iterator __last)
	403	{
	404	_Fwd_list_node_base* __tmp
	405	= const_cast<_Fwd_list_node_base*>(__pos._M_node);
	406	__tmp->_M_transfer_after(const_cast<_Fwd_list_node_base*>
	407	(__before._M_node),
	408	const_cast<_Fwd_list_node_base*>
	409	(__last._M_node));
	410	}
	411
3a63c9cd ESR	412	template<typename _Tp, typename _Alloc>
	413	void
	414	forward_list<_Tp, _Alloc>::
	415	remove(const _Tp& __val)
	416	{
	417	_Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
	418	while (_Node* __temp = static_cast<_Node*>(__curr->_M_next))
	419	{
	420	if (__temp->_M_value == __val)
2a7ee2f9	421	this->_M_erase_after(__curr);
3a63c9cd ESR	422	else
	423	__curr = static_cast<_Node*>(__curr->_M_next);
	424	}
	425	}
	426
	427	template<typename _Tp, typename _Alloc>
	428	template<typename _Pred>
	429	void
	430	forward_list<_Tp, _Alloc>::
	431	remove_if(_Pred __pred)
	432	{
	433	_Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
	434	while (_Node* __temp = static_cast<_Node*>(__curr->_M_next))
	435	{
	436	if (__pred(__temp->_M_value))
2a7ee2f9	437	this->_M_erase_after(__curr);
3a63c9cd ESR	438	else
	439	__curr = static_cast<_Node*>(__curr->_M_next);
	440	}
	441	}
	442
	443	template<typename _Tp, typename _Alloc>
	444	void
	445	forward_list<_Tp, _Alloc>::
	446	unique()
	447	{
	448	iterator __first = begin();
	449	iterator __last = end();
	450	if (__first == __last)
	451	return;
	452	iterator __next = __first;
	453	while (++__next != __last)
	454	{
	455	if (__first == __next)
	456	erase_after(__first);
	457	else
	458	__first = __next;
	459	__next = __first;
	460	}
	461	}
	462
	463	template<typename _Tp, typename _Alloc>
	464	template<typename _BinPred>
	465	void
	466	forward_list<_Tp, _Alloc>::
	467	unique(_BinPred __binary_pred)
	468	{
	469	iterator __first = begin();
	470	iterator __last = end();
	471	if (__first == __last)
	472	return;
	473	iterator __next = __first;
	474	while (++__next != __last)
	475	{
	476	if (__binary_pred(__first, __next))
6bb76034	477	erase_after(__first);
3a63c9cd ESR	478	else
	479	__first = __next;
	480	__next = __first;
	481	}
	482	}
	483
	484	template<typename _Tp, typename _Alloc>
	485	template<typename _Comp>
	486	void
	487	forward_list<_Tp, _Alloc>::
	488	merge(forward_list&& __list, _Comp __comp)
	489	{
	490	_Fwd_list_node_base* __node = &this->_M_impl._M_head;
	491	while (__node->_M_next && __list._M_impl._M_head._M_next)
	492	{
	493	if (__comp(static_cast<_Node*>
	494	(__list._M_impl._M_head._M_next)->_M_value,
	495	static_cast<_Node*>
	496	(__node->_M_next)->_M_value))
	497	__node->_M_transfer_after(&__list._M_impl._M_head,
	498	__list._M_impl._M_head._M_next);
	499	__node = __node->_M_next;
	500	}
	501	if (__list._M_impl._M_head._M_next)
	502	{
	503	__node->_M_next = __list._M_impl._M_head._M_next;
	504	__list._M_impl._M_head._M_next = 0;
	505	}
	506	}
	507
2a7ee2f9 PC	508	template<typename _Tp, typename _Alloc>
	509	void
	510	forward_list<_Tp, _Alloc>::
	511	reverse()
	512	{ this->_M_impl._M_head._M_reverse_after(); }
	513
	514	template<typename _Tp, typename _Alloc>
	515	bool
	516	operator==(const forward_list<_Tp, _Alloc>& __lx,
	517	const forward_list<_Tp, _Alloc>& __ly)
	518	{
	519	// We don't have size() so we need to walk through both lists
	520	// making sure both iterators are valid.
	521	typename std::forward_list<_Tp, _Alloc>::const_iterator __ix
	522	= __lx.cbegin();
	523	typename std::forward_list<_Tp, _Alloc>::const_iterator __iy
	524	= __ly.cbegin();
	525	while (__ix != __lx.cend() && __iy != __ly.cend())
	526	{
	527	if (__ix != __iy)
	528	return false;
	529	++__ix;
	530	++__iy;
	531	}
	532	if (__ix == __lx.cend() && __iy == __ly.cend())
	533	return true;
	534	else
	535	return false;
	536	}
	537
3a63c9cd ESR	538	_GLIBCXX_END_NAMESPACE // namespace std
	539
	540	#endif /* _FORWARD_LIST_TCC */
	541