| // 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 |
