diff options
Diffstat (limited to 'libstdc++-v3/include/ext/slist')
| -rw-r--r-- | libstdc++-v3/include/ext/slist | 1083 |
1 files changed, 1083 insertions, 0 deletions
diff --git a/libstdc++-v3/include/ext/slist b/libstdc++-v3/include/ext/slist new file mode 100644 index 000000000..e678190bf --- /dev/null +++ b/libstdc++-v3/include/ext/slist @@ -0,0 +1,1083 @@ +// Singly-linked list implementation -*- C++ -*- + +// Copyright (C) 2001, 2002, 2004, 2005, 2007, 2008, 2009 +// 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) 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> + +namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + 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; } + + bool + operator==(const _Slist_iterator_base& __x) const + { return _M_node == __x._M_node; } + + bool + operator!=(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) {} + + reference + operator*() const + { return ((_Node*) _M_node)->_M_data; } + + pointer + operator->() const + { return &(operator*()); } + + _Self& + operator++() + { + _M_incr(); + return *this; + } + + _Self + operator++(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_type + get_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_type + get_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: + explicit + slist(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); } + + explicit + slist(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. + + void + assign(size_type __n, const _Tp& __val) + { _M_fill_assign(__n, __val); } + + void + _M_fill_assign(size_type __n, const _Tp& __val); + + template <class _InputIterator> + void + assign(_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: + + iterator + begin() + { return iterator((_Node*)this->_M_head._M_next); } + + const_iterator + begin() const + { return const_iterator((_Node*)this->_M_head._M_next);} + + iterator + end() + { return iterator(0); } + + const_iterator + end() 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(). + iterator + before_begin() + { return iterator((_Node*) &this->_M_head); } + + const_iterator + before_begin() const + { return const_iterator((_Node*) &this->_M_head); } + + size_type + size() const + { return __slist_size(this->_M_head._M_next); } + + size_type + max_size() const + { return size_type(-1); } + + bool + empty() const + { return this->_M_head._M_next == 0; } + + void + swap(slist& __x) + { std::swap(this->_M_head._M_next, __x._M_head._M_next); } + + public: + + reference + front() + { return ((_Node*) this->_M_head._M_next)->_M_data; } + + const_reference + front() const + { return ((_Node*) this->_M_head._M_next)->_M_data; } + + void + push_front(const value_type& __x) + { __slist_make_link(&this->_M_head, _M_create_node(__x)); } + + void + push_front() + { __slist_make_link(&this->_M_head, _M_create_node()); } + + void + pop_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); + } + + iterator + previous(const_iterator __pos) + { return iterator((_Node*) __slist_previous(&this->_M_head, + __pos._M_node)); } + + const_iterator + previous(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: + iterator + insert_after(iterator __pos, const value_type& __x) + { return iterator(_M_insert_after(__pos._M_node, __x)); } + + iterator + insert_after(iterator __pos) + { return insert_after(__pos, value_type()); } + + void + insert_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> + void + insert_after(iterator __pos, _InIterator __first, _InIterator __last) + { _M_insert_after_range(__pos._M_node, __first, __last); } + + iterator + insert(iterator __pos, const value_type& __x) + { return iterator(_M_insert_after(__slist_previous(&this->_M_head, + __pos._M_node), + __x)); } + + iterator + insert(iterator __pos) + { return iterator(_M_insert_after(__slist_previous(&this->_M_head, + __pos._M_node), + value_type())); } + + void + insert(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> + void + insert(iterator __pos, _InIterator __first, _InIterator __last) + { _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), + __first, __last); } + + public: + iterator + erase_after(iterator __pos) + { return iterator((_Node*) this->_M_erase_after(__pos._M_node)); } + + iterator + erase_after(iterator __before_first, iterator __last) + { + return iterator((_Node*) this->_M_erase_after(__before_first._M_node, + __last._M_node)); + } + + iterator + erase(iterator __pos) + { + return iterator((_Node*) this->_M_erase_after + (__slist_previous(&this->_M_head, __pos._M_node))); + } + + iterator + erase(iterator __first, iterator __last) + { + return iterator((_Node*) this->_M_erase_after + (__slist_previous(&this->_M_head, __first._M_node), + __last._M_node)); + } + + void + resize(size_type new_size, const _Tp& __x); + + void + resize(size_type new_size) + { resize(new_size, _Tp()); } + + void + clear() + { 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. + void + splice_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. + void + splice_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(). + void + splice_after(iterator __pos, slist& __x) + { __slist_splice_after(__pos._M_node, &__x._M_head); } + + // Linear in distance(begin(), __pos), and linear in __x.size(). + void + splice(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). + void + splice(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). + void + splice(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: + void + reverse() + { + if (this->_M_head._M_next) + this->_M_head._M_next = __slist_reverse(this->_M_head._M_next); + } + + void + remove(const _Tp& __val); + + void + unique(); + + void + merge(slist& __x); + + void + sort(); + + template <class _Predicate> + void + remove_if(_Predicate __pred); + + template <class _BinaryPredicate> + void + unique(_BinaryPredicate __pred); + + template <class _StrictWeakOrdering> + void + merge(slist&, _StrictWeakOrdering); + + template <class _StrictWeakOrdering> + void + sort(_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> + void + slist<_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); + else + this->_M_erase_after(__prev, 0); + } + + template <class _Tp, class _Alloc> + template <class _InputIterator> + void + slist<_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); + else + this->_M_erase_after(__prev, 0); + } + + template <class _Tp, class _Alloc> + inline bool + operator==(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 bool + operator<(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 bool + operator!=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) + { return !(_SL1 == _SL2); } + + template <class _Tp, class _Alloc> + inline bool + operator>(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) + { return _SL2 < _SL1; } + + template <class _Tp, class _Alloc> + inline bool + operator<=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) + { return !(_SL2 < _SL1); } + + template <class _Tp, class _Alloc> + inline bool + operator>=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) + { return !(_SL1 < _SL2); } + + template <class _Tp, class _Alloc> + inline void + swap(slist<_Tp, _Alloc>& __x, slist<_Tp, _Alloc>& __y) + { __x.swap(__y); } + + template <class _Tp, class _Alloc> + void + slist<_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> + void + slist<_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> + void + slist<_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> + void + slist<_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> + void + slist<_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> + void + slist<_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> + void + slist<_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> + void + slist<_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_VERSION +} // namespace + +namespace std _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + // 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(); + else + iter = __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_VERSION +} // namespace + +#endif |