// Singly-linked list implementation -*- C++ -*-// Copyright (C) 2001, 2002, 2004, 2005, 2007 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./** Copyright (c) 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 ext/slist* This file is a GNU extension to the Standard C++ Library (possibly* containing extensions from the HP/SGI STL subset).*/#ifndef _SLIST#define _SLIST 1#include <algorithm>#include <bits/allocator.h>#include <bits/stl_construct.h>#include <bits/stl_uninitialized.h>#include <bits/concept_check.h>_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)using std::size_t;using std::ptrdiff_t;using std::_Construct;using std::_Destroy;using std::allocator;using std::__true_type;using std::__false_type;struct _Slist_node_base{_Slist_node_base* _M_next;};inline _Slist_node_base*__slist_make_link(_Slist_node_base* __prev_node,_Slist_node_base* __new_node){__new_node->_M_next = __prev_node->_M_next;__prev_node->_M_next = __new_node;return __new_node;}inline _Slist_node_base*__slist_previous(_Slist_node_base* __head,const _Slist_node_base* __node){while (__head && __head->_M_next != __node)__head = __head->_M_next;return __head;}inline const _Slist_node_base*__slist_previous(const _Slist_node_base* __head,const _Slist_node_base* __node){while (__head && __head->_M_next != __node)__head = __head->_M_next;return __head;}inline void__slist_splice_after(_Slist_node_base* __pos,_Slist_node_base* __before_first,_Slist_node_base* __before_last){if (__pos != __before_first && __pos != __before_last){_Slist_node_base* __first = __before_first->_M_next;_Slist_node_base* __after = __pos->_M_next;__before_first->_M_next = __before_last->_M_next;__pos->_M_next = __first;__before_last->_M_next = __after;}}inline void__slist_splice_after(_Slist_node_base* __pos, _Slist_node_base* __head){_Slist_node_base* __before_last = __slist_previous(__head, 0);if (__before_last != __head){_Slist_node_base* __after = __pos->_M_next;__pos->_M_next = __head->_M_next;__head->_M_next = 0;__before_last->_M_next = __after;}}inline _Slist_node_base*__slist_reverse(_Slist_node_base* __node){_Slist_node_base* __result = __node;__node = __node->_M_next;__result->_M_next = 0;while(__node){_Slist_node_base* __next = __node->_M_next;__node->_M_next = __result;__result = __node;__node = __next;}return __result;}inline size_t__slist_size(_Slist_node_base* __node){size_t __result = 0;for (; __node != 0; __node = __node->_M_next)++__result;return __result;}template <class _Tp>struct _Slist_node : public _Slist_node_base{_Tp _M_data;};struct _Slist_iterator_base{typedef size_t size_type;typedef ptrdiff_t difference_type;typedef std::forward_iterator_tag iterator_category;_Slist_node_base* _M_node;_Slist_iterator_base(_Slist_node_base* __x): _M_node(__x) {}void_M_incr(){ _M_node = _M_node->_M_next; }booloperator==(const _Slist_iterator_base& __x) const{ return _M_node == __x._M_node; }booloperator!=(const _Slist_iterator_base& __x) const{ return _M_node != __x._M_node; }};template <class _Tp, class _Ref, class _Ptr>struct _Slist_iterator : public _Slist_iterator_base{typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator;typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;typedef _Slist_iterator<_Tp, _Ref, _Ptr> _Self;typedef _Tp value_type;typedef _Ptr pointer;typedef _Ref reference;typedef _Slist_node<_Tp> _Node;explicit_Slist_iterator(_Node* __x): _Slist_iterator_base(__x) {}_Slist_iterator(): _Slist_iterator_base(0) {}_Slist_iterator(const iterator& __x): _Slist_iterator_base(__x._M_node) {}referenceoperator*() const{ return ((_Node*) _M_node)->_M_data; }pointeroperator->() const{ return &(operator*()); }_Self&operator++(){_M_incr();return *this;}_Selfoperator++(int){_Self __tmp = *this;_M_incr();return __tmp;}};template <class _Tp, class _Alloc>struct _Slist_base: public _Alloc::template rebind<_Slist_node<_Tp> >::other{typedef typename _Alloc::template rebind<_Slist_node<_Tp> >::other_Node_alloc;typedef _Alloc allocator_type;allocator_typeget_allocator() const{ return *static_cast<const _Node_alloc*>(this); }_Slist_base(const allocator_type& __a): _Node_alloc(__a){ this->_M_head._M_next = 0; }~_Slist_base(){ _M_erase_after(&this->_M_head, 0); }protected:_Slist_node_base _M_head;_Slist_node<_Tp>*_M_get_node(){ return _Node_alloc::allocate(1); }void_M_put_node(_Slist_node<_Tp>* __p){ _Node_alloc::deallocate(__p, 1); }protected:_Slist_node_base* _M_erase_after(_Slist_node_base* __pos){_Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);_Slist_node_base* __next_next = __next->_M_next;__pos->_M_next = __next_next;get_allocator().destroy(&__next->_M_data);_M_put_node(__next);return __next_next;}_Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);};template <class _Tp, class _Alloc>_Slist_node_base*_Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first,_Slist_node_base* __last_node){_Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next);while (__cur != __last_node){_Slist_node<_Tp>* __tmp = __cur;__cur = (_Slist_node<_Tp>*) __cur->_M_next;get_allocator().destroy(&__tmp->_M_data);_M_put_node(__tmp);}__before_first->_M_next = __last_node;return __last_node;}/*** This is an SGI extension.* @ingroup SGIextensions* @doctodo*/template <class _Tp, class _Alloc = allocator<_Tp> >class slist : private _Slist_base<_Tp,_Alloc>{// concept requirements__glibcxx_class_requires(_Tp, _SGIAssignableConcept)private:typedef _Slist_base<_Tp,_Alloc> _Base;public:typedef _Tp value_type;typedef value_type* pointer;typedef const value_type* const_pointer;typedef value_type& reference;typedef const value_type& const_reference;typedef size_t size_type;typedef ptrdiff_t difference_type;typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator;typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;typedef typename _Base::allocator_type allocator_type;allocator_typeget_allocator() const{ return _Base::get_allocator(); }private:typedef _Slist_node<_Tp> _Node;typedef _Slist_node_base _Node_base;typedef _Slist_iterator_base _Iterator_base;_Node*_M_create_node(const value_type& __x){_Node* __node = this->_M_get_node();try{get_allocator().construct(&__node->_M_data, __x);__node->_M_next = 0;}catch(...){this->_M_put_node(__node);__throw_exception_again;}return __node;}_Node*_M_create_node(){_Node* __node = this->_M_get_node();try{get_allocator().construct(&__node->_M_data, value_type());__node->_M_next = 0;}catch(...){this->_M_put_node(__node);__throw_exception_again;}return __node;}public:explicitslist(const allocator_type& __a = allocator_type()): _Base(__a) {}slist(size_type __n, const value_type& __x,const allocator_type& __a = allocator_type()): _Base(__a){ _M_insert_after_fill(&this->_M_head, __n, __x); }explicitslist(size_type __n): _Base(allocator_type()){ _M_insert_after_fill(&this->_M_head, __n, value_type()); }// We don't need any dispatching tricks here, because// _M_insert_after_range already does them.template <class _InputIterator>slist(_InputIterator __first, _InputIterator __last,const allocator_type& __a = allocator_type()): _Base(__a){ _M_insert_after_range(&this->_M_head, __first, __last); }slist(const slist& __x): _Base(__x.get_allocator()){ _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); }slist&operator= (const slist& __x);~slist() {}public:// assign(), a generalized assignment member function. Two// versions: one that takes a count, and one that takes a range.// The range version is a member template, so we dispatch on whether// or not the type is an integer.voidassign(size_type __n, const _Tp& __val){ _M_fill_assign(__n, __val); }void_M_fill_assign(size_type __n, const _Tp& __val);template <class _InputIterator>voidassign(_InputIterator __first, _InputIterator __last){typedef typename std::__is_integer<_InputIterator>::__type _Integral;_M_assign_dispatch(__first, __last, _Integral());}template <class _Integer>void_M_assign_dispatch(_Integer __n, _Integer __val, __true_type){ _M_fill_assign((size_type) __n, (_Tp) __val); }template <class _InputIterator>void_M_assign_dispatch(_InputIterator __first, _InputIterator __last,__false_type);public:iteratorbegin(){ return iterator((_Node*)this->_M_head._M_next); }const_iteratorbegin() const{ return const_iterator((_Node*)this->_M_head._M_next);}iteratorend(){ return iterator(0); }const_iteratorend() const{ return const_iterator(0); }// Experimental new feature: before_begin() returns a// non-dereferenceable iterator that, when incremented, yields// begin(). This iterator may be used as the argument to// insert_after, erase_after, etc. Note that even for an empty// slist, before_begin() is not the same iterator as end(). It// is always necessary to increment before_begin() at least once to// obtain end().iteratorbefore_begin(){ return iterator((_Node*) &this->_M_head); }const_iteratorbefore_begin() const{ return const_iterator((_Node*) &this->_M_head); }size_typesize() const{ return __slist_size(this->_M_head._M_next); }size_typemax_size() const{ return size_type(-1); }boolempty() const{ return this->_M_head._M_next == 0; }voidswap(slist& __x){ std::swap(this->_M_head._M_next, __x._M_head._M_next); }public:referencefront(){ return ((_Node*) this->_M_head._M_next)->_M_data; }const_referencefront() const{ return ((_Node*) this->_M_head._M_next)->_M_data; }voidpush_front(const value_type& __x){ __slist_make_link(&this->_M_head, _M_create_node(__x)); }voidpush_front(){ __slist_make_link(&this->_M_head, _M_create_node()); }voidpop_front(){_Node* __node = (_Node*) this->_M_head._M_next;this->_M_head._M_next = __node->_M_next;get_allocator().destroy(&__node->_M_data);this->_M_put_node(__node);}iteratorprevious(const_iterator __pos){ return iterator((_Node*) __slist_previous(&this->_M_head,__pos._M_node)); }const_iteratorprevious(const_iterator __pos) const{ return const_iterator((_Node*) __slist_previous(&this->_M_head,__pos._M_node)); }private:_Node*_M_insert_after(_Node_base* __pos, const value_type& __x){ return (_Node*) (__slist_make_link(__pos, _M_create_node(__x))); }_Node*_M_insert_after(_Node_base* __pos){ return (_Node*) (__slist_make_link(__pos, _M_create_node())); }void_M_insert_after_fill(_Node_base* __pos,size_type __n, const value_type& __x){for (size_type __i = 0; __i < __n; ++__i)__pos = __slist_make_link(__pos, _M_create_node(__x));}// Check whether it's an integral type. If so, it's not an iterator.template <class _InIterator>void_M_insert_after_range(_Node_base* __pos,_InIterator __first, _InIterator __last){typedef typename std::__is_integer<_InIterator>::__type _Integral;_M_insert_after_range(__pos, __first, __last, _Integral());}template <class _Integer>void_M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x,__true_type){ _M_insert_after_fill(__pos, __n, __x); }template <class _InIterator>void_M_insert_after_range(_Node_base* __pos,_InIterator __first, _InIterator __last,__false_type){while (__first != __last){__pos = __slist_make_link(__pos, _M_create_node(*__first));++__first;}}public:iteratorinsert_after(iterator __pos, const value_type& __x){ return iterator(_M_insert_after(__pos._M_node, __x)); }iteratorinsert_after(iterator __pos){ return insert_after(__pos, value_type()); }voidinsert_after(iterator __pos, size_type __n, const value_type& __x){ _M_insert_after_fill(__pos._M_node, __n, __x); }// We don't need any dispatching tricks here, because// _M_insert_after_range already does them.template <class _InIterator>voidinsert_after(iterator __pos, _InIterator __first, _InIterator __last){ _M_insert_after_range(__pos._M_node, __first, __last); }iteratorinsert(iterator __pos, const value_type& __x){ return iterator(_M_insert_after(__slist_previous(&this->_M_head,__pos._M_node),__x)); }iteratorinsert(iterator __pos){ return iterator(_M_insert_after(__slist_previous(&this->_M_head,__pos._M_node),value_type())); }voidinsert(iterator __pos, size_type __n, const value_type& __x){ _M_insert_after_fill(__slist_previous(&this->_M_head, __pos._M_node),__n, __x); }// We don't need any dispatching tricks here, because// _M_insert_after_range already does them.template <class _InIterator>voidinsert(iterator __pos, _InIterator __first, _InIterator __last){ _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node),__first, __last); }public:iteratorerase_after(iterator __pos){ return iterator((_Node*) this->_M_erase_after(__pos._M_node)); }iteratorerase_after(iterator __before_first, iterator __last){return iterator((_Node*) this->_M_erase_after(__before_first._M_node,__last._M_node));}iteratorerase(iterator __pos){return iterator((_Node*) this->_M_erase_after(__slist_previous(&this->_M_head, __pos._M_node)));}iteratorerase(iterator __first, iterator __last){return iterator((_Node*) this->_M_erase_after(__slist_previous(&this->_M_head, __first._M_node),__last._M_node));}voidresize(size_type new_size, const _Tp& __x);voidresize(size_type new_size){ resize(new_size, _Tp()); }voidclear(){ this->_M_erase_after(&this->_M_head, 0); }public:// Moves the range [__before_first + 1, __before_last + 1) to *this,// inserting it immediately after __pos. This is constant time.voidsplice_after(iterator __pos,iterator __before_first, iterator __before_last){if (__before_first != __before_last)__slist_splice_after(__pos._M_node, __before_first._M_node,__before_last._M_node);}// Moves the element that follows __prev to *this, inserting it// immediately after __pos. This is constant time.voidsplice_after(iterator __pos, iterator __prev){ __slist_splice_after(__pos._M_node,__prev._M_node, __prev._M_node->_M_next); }// Removes all of the elements from the list __x to *this, inserting// them immediately after __pos. __x must not be *this. Complexity:// linear in __x.size().voidsplice_after(iterator __pos, slist& __x){ __slist_splice_after(__pos._M_node, &__x._M_head); }// Linear in distance(begin(), __pos), and linear in __x.size().voidsplice(iterator __pos, slist& __x){if (__x._M_head._M_next)__slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),&__x._M_head,__slist_previous(&__x._M_head, 0)); }// Linear in distance(begin(), __pos), and in distance(__x.begin(), __i).voidsplice(iterator __pos, slist& __x, iterator __i){ __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),__slist_previous(&__x._M_head, __i._M_node),__i._M_node); }// Linear in distance(begin(), __pos), in distance(__x.begin(), __first),// and in distance(__first, __last).voidsplice(iterator __pos, slist& __x, iterator __first, iterator __last){if (__first != __last)__slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node),__slist_previous(&__x._M_head, __first._M_node),__slist_previous(__first._M_node,__last._M_node));}public:voidreverse(){if (this->_M_head._M_next)this->_M_head._M_next = __slist_reverse(this->_M_head._M_next);}voidremove(const _Tp& __val);voidunique();voidmerge(slist& __x);voidsort();template <class _Predicate>voidremove_if(_Predicate __pred);template <class _BinaryPredicate>voidunique(_BinaryPredicate __pred);template <class _StrictWeakOrdering>voidmerge(slist&, _StrictWeakOrdering);template <class _StrictWeakOrdering>voidsort(_StrictWeakOrdering __comp);};template <class _Tp, class _Alloc>slist<_Tp, _Alloc>&slist<_Tp, _Alloc>::operator=(const slist<_Tp, _Alloc>& __x){if (&__x != this){_Node_base* __p1 = &this->_M_head;_Node* __n1 = (_Node*) this->_M_head._M_next;const _Node* __n2 = (const _Node*) __x._M_head._M_next;while (__n1 && __n2){__n1->_M_data = __n2->_M_data;__p1 = __n1;__n1 = (_Node*) __n1->_M_next;__n2 = (const _Node*) __n2->_M_next;}if (__n2 == 0)this->_M_erase_after(__p1, 0);else_M_insert_after_range(__p1, const_iterator((_Node*)__n2),const_iterator(0));}return *this;}template <class _Tp, class _Alloc>voidslist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val){_Node_base* __prev = &this->_M_head;_Node* __node = (_Node*) this->_M_head._M_next;for (; __node != 0 && __n > 0; --__n){__node->_M_data = __val;__prev = __node;__node = (_Node*) __node->_M_next;}if (__n > 0)_M_insert_after_fill(__prev, __n, __val);elsethis->_M_erase_after(__prev, 0);}template <class _Tp, class _Alloc>template <class _InputIterator>voidslist<_Tp, _Alloc>::_M_assign_dispatch(_InputIterator __first,_InputIterator __last,__false_type){_Node_base* __prev = &this->_M_head;_Node* __node = (_Node*) this->_M_head._M_next;while (__node != 0 && __first != __last){__node->_M_data = *__first;__prev = __node;__node = (_Node*) __node->_M_next;++__first;}if (__first != __last)_M_insert_after_range(__prev, __first, __last);elsethis->_M_erase_after(__prev, 0);}template <class _Tp, class _Alloc>inline booloperator==(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2){typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator;const_iterator __end1 = _SL1.end();const_iterator __end2 = _SL2.end();const_iterator __i1 = _SL1.begin();const_iterator __i2 = _SL2.begin();while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2){++__i1;++__i2;}return __i1 == __end1 && __i2 == __end2;}template <class _Tp, class _Alloc>inline booloperator<(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2){ return std::lexicographical_compare(_SL1.begin(), _SL1.end(),_SL2.begin(), _SL2.end()); }template <class _Tp, class _Alloc>inline booloperator!=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2){ return !(_SL1 == _SL2); }template <class _Tp, class _Alloc>inline booloperator>(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2){ return _SL2 < _SL1; }template <class _Tp, class _Alloc>inline booloperator<=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2){ return !(_SL2 < _SL1); }template <class _Tp, class _Alloc>inline booloperator>=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2){ return !(_SL1 < _SL2); }template <class _Tp, class _Alloc>inline voidswap(slist<_Tp, _Alloc>& __x, slist<_Tp, _Alloc>& __y){ __x.swap(__y); }template <class _Tp, class _Alloc>voidslist<_Tp, _Alloc>::resize(size_type __len, const _Tp& __x){_Node_base* __cur = &this->_M_head;while (__cur->_M_next != 0 && __len > 0){--__len;__cur = __cur->_M_next;}if (__cur->_M_next)this->_M_erase_after(__cur, 0);else_M_insert_after_fill(__cur, __len, __x);}template <class _Tp, class _Alloc>voidslist<_Tp, _Alloc>::remove(const _Tp& __val){_Node_base* __cur = &this->_M_head;while (__cur && __cur->_M_next){if (((_Node*) __cur->_M_next)->_M_data == __val)this->_M_erase_after(__cur);else__cur = __cur->_M_next;}}template <class _Tp, class _Alloc>voidslist<_Tp, _Alloc>::unique(){_Node_base* __cur = this->_M_head._M_next;if (__cur){while (__cur->_M_next){if (((_Node*)__cur)->_M_data== ((_Node*)(__cur->_M_next))->_M_data)this->_M_erase_after(__cur);else__cur = __cur->_M_next;}}}template <class _Tp, class _Alloc>voidslist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x){_Node_base* __n1 = &this->_M_head;while (__n1->_M_next && __x._M_head._M_next){if (((_Node*) __x._M_head._M_next)->_M_data< ((_Node*) __n1->_M_next)->_M_data)__slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);__n1 = __n1->_M_next;}if (__x._M_head._M_next){__n1->_M_next = __x._M_head._M_next;__x._M_head._M_next = 0;}}template <class _Tp, class _Alloc>voidslist<_Tp, _Alloc>::sort(){if (this->_M_head._M_next && this->_M_head._M_next->_M_next){slist __carry;slist __counter[64];int __fill = 0;while (!empty()){__slist_splice_after(&__carry._M_head,&this->_M_head, this->_M_head._M_next);int __i = 0;while (__i < __fill && !__counter[__i].empty()){__counter[__i].merge(__carry);__carry.swap(__counter[__i]);++__i;}__carry.swap(__counter[__i]);if (__i == __fill)++__fill;}for (int __i = 1; __i < __fill; ++__i)__counter[__i].merge(__counter[__i-1]);this->swap(__counter[__fill-1]);}}template <class _Tp, class _Alloc>template <class _Predicate>void slist<_Tp, _Alloc>::remove_if(_Predicate __pred){_Node_base* __cur = &this->_M_head;while (__cur->_M_next){if (__pred(((_Node*) __cur->_M_next)->_M_data))this->_M_erase_after(__cur);else__cur = __cur->_M_next;}}template <class _Tp, class _Alloc>template <class _BinaryPredicate>voidslist<_Tp, _Alloc>::unique(_BinaryPredicate __pred){_Node* __cur = (_Node*) this->_M_head._M_next;if (__cur){while (__cur->_M_next){if (__pred(((_Node*)__cur)->_M_data,((_Node*)(__cur->_M_next))->_M_data))this->_M_erase_after(__cur);else__cur = (_Node*) __cur->_M_next;}}}template <class _Tp, class _Alloc>template <class _StrictWeakOrdering>voidslist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x,_StrictWeakOrdering __comp){_Node_base* __n1 = &this->_M_head;while (__n1->_M_next && __x._M_head._M_next){if (__comp(((_Node*) __x._M_head._M_next)->_M_data,((_Node*) __n1->_M_next)->_M_data))__slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);__n1 = __n1->_M_next;}if (__x._M_head._M_next){__n1->_M_next = __x._M_head._M_next;__x._M_head._M_next = 0;}}template <class _Tp, class _Alloc>template <class _StrictWeakOrdering>voidslist<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp){if (this->_M_head._M_next && this->_M_head._M_next->_M_next){slist __carry;slist __counter[64];int __fill = 0;while (!empty()){__slist_splice_after(&__carry._M_head,&this->_M_head, this->_M_head._M_next);int __i = 0;while (__i < __fill && !__counter[__i].empty()){__counter[__i].merge(__carry, __comp);__carry.swap(__counter[__i]);++__i;}__carry.swap(__counter[__i]);if (__i == __fill)++__fill;}for (int __i = 1; __i < __fill; ++__i)__counter[__i].merge(__counter[__i-1], __comp);this->swap(__counter[__fill-1]);}}_GLIBCXX_END_NAMESPACE_GLIBCXX_BEGIN_NAMESPACE(std)// Specialization of insert_iterator so that insertions will be constant// time rather than linear time.template <class _Tp, class _Alloc>class insert_iterator<__gnu_cxx::slist<_Tp, _Alloc> >{protected:typedef __gnu_cxx::slist<_Tp, _Alloc> _Container;_Container* container;typename _Container::iterator iter;public:typedef _Container container_type;typedef output_iterator_tag iterator_category;typedef void value_type;typedef void difference_type;typedef void pointer;typedef void reference;insert_iterator(_Container& __x, typename _Container::iterator __i): container(&__x){if (__i == __x.begin())iter = __x.before_begin();elseiter = __x.previous(__i);}insert_iterator<_Container>&operator=(const typename _Container::value_type& __value){iter = container->insert_after(iter, __value);return *this;}insert_iterator<_Container>&operator*(){ return *this; }insert_iterator<_Container>&operator++(){ return *this; }insert_iterator<_Container>&operator++(int){ return *this; }};_GLIBCXX_END_NAMESPACE#endif