--- /dev/null
+/////////////////////////////////////////////////////////////////////////////\r
+//\r
+// (C) Copyright Olaf Krzikalla 2004-2006.\r
+// (C) Copyright Ion Gaztañaga 2006-2007\r
+//\r
+// Distributed under the Boost Software License, Version 1.0.\r
+// (See accompanying file LICENSE_1_0.txt or copy at\r
+// http://www.boost.org/LICENSE_1_0.txt)\r
+//\r
+// See http://www.boost.org/libs/intrusive for documentation.\r
+//\r
+/////////////////////////////////////////////////////////////////////////////\r
+\r
+#ifndef BOOST_INTRUSIVE_ISLIST_HPP\r
+#define BOOST_INTRUSIVE_ISLIST_HPP\r
+\r
+#include "detail/config_begin.hpp"\r
+#include <boost/utility.hpp>\r
+#include <boost/static_assert.hpp>\r
+#include <boost/assert.hpp>\r
+#include <boost/type_traits/is_convertible.hpp>\r
+#include "islist_hook.hpp"\r
+#include "slist_algorithms.hpp"\r
+#include "detail/pointer_type.hpp"\r
+#include "detail/pointer_to_other.hpp"\r
+#include "linking_policy.hpp"\r
+#include <iterator>\r
+#include <cstddef>\r
+\r
+namespace boost {\r
+namespace intrusive {\r
+\r
+//! The class template islist is an intrusive container, that encapsulates \r
+//! a singly-linked list. You can use such a list to squeeze the last bit \r
+//! of performance from your application. Unfortunately, the little gains \r
+//! come with some huge drawbacks. A lot of member functions can't be \r
+//! implemented as efficiently as for standard containers. To overcome \r
+//! this limitation some other member functions with rather unusual semantics \r
+//! have to be introduced.\r
+//!\r
+//! The template parameter ValueTraits is called "value traits". It stores\r
+//! information and operations about the type to be stored in the container.\r
+//!\r
+//! If the user specifies ConstantTimeSize as "true", a member of type SizeType\r
+//! will be embedded in the class, that will keep track of the number of stored objects.\r
+//! This will allow constant-time O(1) size() member, instead of default O(N) size.\r
+//! \r
+//! The iterators of islist are forward iterators. islist provides a static \r
+//! function called "previous" to compute the previous iterator of a given iterator. \r
+//! This function has linear complexity. To improve the usability esp. with \r
+//! the '*_after' functions, ++end() == begin() and previous(begin()) == end() \r
+//! are defined. In addition, whenever you have an end iterator, 'after this \r
+//! iterator' means 'at the beginning of the list'. To improve the self-documentation\r
+//! a "before_begin()" function is defined, returning the end() iterator.\r
+template < class ValueTraits\r
+ , bool ConstantTimeSize = true\r
+ , class SizeType = std::size_t>\r
+class islist\r
+ : private detail::size_holder<ConstantTimeSize, SizeType>\r
+{\r
+ private:\r
+ typedef islist<ValueTraits, ConstantTimeSize, SizeType> this_type; \r
+ typedef typename ValueTraits::node_traits node_traits;\r
+ typedef detail::size_holder<ConstantTimeSize, SizeType> size_traits;\r
+\r
+ //! This class is\r
+ //! non-copyable\r
+ islist (const islist&);\r
+\r
+ //! This class is\r
+ //! non-asignable\r
+ islist &operator =(const islist&);\r
+\r
+ //Public typedefs\r
+ public:\r
+ typedef typename ValueTraits::value_type value_type;\r
+ typedef typename ValueTraits::pointer pointer;\r
+ typedef typename ValueTraits::const_pointer const_pointer;\r
+ typedef value_type& reference;\r
+ typedef const value_type& const_reference;\r
+ typedef SizeType size_type;\r
+ typedef typename std::iterator_traits\r
+ <pointer>::difference_type difference_type;\r
+\r
+ class iterator;\r
+ class const_iterator;\r
+ friend class iterator;\r
+ friend class const_iterator;\r
+\r
+ private:\r
+ typedef typename node_traits::node node;\r
+ typedef typename boost::pointer_to_other\r
+ <pointer, node>::type node_ptr;\r
+ typedef typename boost::pointer_to_other\r
+ <pointer, const node>::type const_node_ptr;\r
+ typedef slist_algorithms<node_traits> node_algorithms;\r
+ enum { safemode_or_autounlink = \r
+ (int)ValueTraits::linking_policy == (int)auto_unlink ||\r
+ (int)ValueTraits::linking_policy == (int)safe_mode_link };\r
+\r
+ //Constant-time size is incompatible with auto-unlink hooks!\r
+ BOOST_STATIC_ASSERT(!(ConstantTimeSize && ((int)ValueTraits::linking_policy == (int)auto_unlink)));\r
+\r
+ node root;\r
+\r
+ node_ptr get_root_node()\r
+ { return node_ptr(&root); }\r
+\r
+ const_node_ptr get_root_node() const\r
+ { return const_node_ptr(&root); }\r
+\r
+ static node_ptr uncast(const_node_ptr ptr)\r
+ {\r
+ using boost::get_pointer;\r
+ return node_ptr(const_cast<node*>(get_pointer(ptr)));\r
+ }\r
+\r
+ static iterator previous_node(iterator beg, iterator i)\r
+ {\r
+ return iterator\r
+ (node_algorithms::get_previous_node(beg.list_node(), i.list_node()));\r
+ }\r
+\r
+ static const_iterator previous_node(const_iterator beg, const_iterator i)\r
+ {\r
+ return const_iterator\r
+ (node_algorithms::get_previous_node(beg.list_node(), i.list_node()));\r
+ }\r
+\r
+ //This functor compares a stored value\r
+ //and the one passed as an argument\r
+ class equal_to_value\r
+ {\r
+ const value_type &t_;\r
+\r
+ public:\r
+ equal_to_value(const value_type &t)\r
+ : t_(t)\r
+ {}\r
+\r
+ bool operator()(const value_type &t)const\r
+ { return t_ == t; }\r
+ };\r
+\r
+ public:\r
+\r
+ //!The forward iterator of the container\r
+ class iterator\r
+ : public detail::slist_iterator<value_type, iterator, node_traits>\r
+ {\r
+ private:\r
+ // gcc warns about an ambiguity between iterator::value_type and\r
+ // islist<ValueTraits>::value_type, thus I introduce a unique name:\r
+ typedef typename islist<ValueTraits, ConstantTimeSize, SizeType>::value_type private_vt;\r
+ typedef typename islist<ValueTraits, ConstantTimeSize, SizeType>::pointer private_pointer;\r
+ typedef typename islist<ValueTraits, ConstantTimeSize, SizeType>::reference private_reference;\r
+ typedef detail::slist_iterator<private_vt, iterator, node_traits> inherited;\r
+\r
+ public:\r
+ iterator ()\r
+ {}\r
+\r
+ private_pointer operator->() const\r
+ { return ValueTraits::to_value_ptr(this->list_node()); }\r
+\r
+ private_reference operator*() const\r
+ { return *ValueTraits::to_value_ptr(this->list_node()); }\r
+\r
+ node_ptr list_node()const\r
+ { return inherited::list_node(); }\r
+\r
+ private:\r
+ explicit iterator (node_ptr node)\r
+ : inherited (node)\r
+ {}\r
+\r
+ friend class islist<ValueTraits, ConstantTimeSize, SizeType>;\r
+ friend class detail::slist_iterator<private_vt, iterator, node_traits>;\r
+ friend class const_iterator;\r
+ };\r
+\r
+ //!The forward const_iterator of the container\r
+ class const_iterator\r
+ : public detail::slist_iterator<const value_type, const_iterator, node_traits>\r
+ {\r
+ private:\r
+ typedef const typename islist<ValueTraits, ConstantTimeSize, SizeType>::value_type private_vt;\r
+ typedef typename islist<ValueTraits, ConstantTimeSize, SizeType>::const_pointer private_pointer;\r
+ typedef typename islist<ValueTraits, ConstantTimeSize, SizeType>::const_reference private_reference;\r
+ typedef detail::slist_iterator<private_vt, const_iterator, node_traits> inherited;\r
+ \r
+ public: \r
+ const_iterator()\r
+ {}\r
+\r
+ const_iterator(const typename islist::iterator& it)\r
+ : inherited (it.list_node())\r
+ {}\r
+\r
+ const_iterator & operator=(const typename islist::iterator& it)\r
+ { return inherited::operator=(it.list_node()); }\r
+\r
+ private_pointer operator->()\r
+ { return ValueTraits::to_value_ptr(this->list_node()); }\r
+\r
+ private_reference operator*()\r
+ { return *ValueTraits::to_value_ptr(this->list_node()); }\r
+ \r
+ private:\r
+ explicit const_iterator (const_node_ptr node)\r
+ : inherited (uncast(node))\r
+ {}\r
+\r
+ friend class islist<ValueTraits, ConstantTimeSize, SizeType>;\r
+ friend class detail::slist_iterator<private_vt, const_iterator, node_traits>;\r
+ };\r
+\r
+ public:\r
+\r
+ //! <b>Effects</b>: constructs an empty list. \r
+ //! \r
+ //! <b>Complexity</b>: Constant \r
+ //! \r
+ //! <b>Throws</b>: If value_traits::node_traits::node\r
+ //! constructor throws (this does not happen with predefined Boost.Intrusive hooks).\r
+ islist()\r
+ {\r
+ size_traits::set_size(size_type(0));\r
+ node_algorithms::init(node_ptr(&root)); \r
+ }\r
+\r
+ //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type.\r
+ //! \r
+ //! <b>Effects</b>: Constructs a list equal to [first,last).\r
+ //! \r
+ //! <b>Complexity</b>: Linear in std::distance(b, e). No copy constructors are called. \r
+ //! \r
+ //! <b>Throws</b>: If value_traits::node_traits::node\r
+ //! constructor throws (this does not happen with predefined Boost.Intrusive hooks).\r
+ template<class Iterator>\r
+ islist(Iterator b, Iterator e)\r
+ {\r
+ size_traits::set_size(size_type(0));\r
+ node_algorithms::init(node_ptr(&root));\r
+ insert_after(before_begin(), b, e);\r
+ }\r
+\r
+ //! <b>Effects</b>: If it's a safe-mode\r
+ //! or auto-unlink value, the destructor does nothing\r
+ //! (ie. no code is generated). Otherwise it detaches all elements from this. \r
+ //! In this case the objects in the list are not deleted (i.e. no destructors \r
+ //! are called), but the hooks according to the ValueTraits template parameter\r
+ //! are set to their default value.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the number of elements in the list, if \r
+ //! it's a safe-mode or auto-unlink value. Otherwise constant.\r
+ ~islist()\r
+ { this->clear(); }\r
+\r
+ //! <b>Effects</b>: Erases all the elements of the container.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the number of elements of the list.\r
+ //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased elements.\r
+ void clear()\r
+ {\r
+ if(safemode_or_autounlink){\r
+ this->erase_after(this->before_begin(), this->end()); \r
+ }\r
+ else{\r
+ node_algorithms::init(node_ptr(&root));\r
+ size_traits::set_size(size_type(0));\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
+ //!\r
+ //! <b>Effects</b>: Erases all the elements of the container\r
+ //! Destroyer::operator()(pointer) is called for the removed elements.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the number of elements of the list.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators to the erased elements.\r
+ template <class Destroyer>\r
+ void clear_and_destroy(Destroyer destroyer)\r
+ { this->erase_after_and_destroy(this->before_begin(), this->end(), destroyer); }\r
+\r
+ //! <b>Requires</b>: value must be an lvalue.\r
+ //! \r
+ //! <b>Effects</b>: Inserts the value in the front of the list.\r
+ //! No copy constructors are called.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Note</b>: Does not affect the validity of iterators and references.\r
+ void push_front(value_type &value) \r
+ {\r
+ node_ptr to_insert(ValueTraits::to_node_ptr(value));\r
+ if(safemode_or_autounlink)\r
+ BOOST_ASSERT(node_algorithms::unique(to_insert));\r
+ node_algorithms::link_after(get_root_node(), to_insert); \r
+ size_traits::increment();\r
+ }\r
+\r
+ //! <b>Effects</b>: Erases the first element of the list.\r
+ //! No destructors are called.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased element.\r
+ void pop_front() \r
+ {\r
+ node_ptr to_erase = node_traits::get_next(get_root_node());\r
+ node_algorithms::unlink_after(get_root_node());\r
+ size_traits::decrement();\r
+ if(safemode_or_autounlink)\r
+ node_algorithms::init(to_erase);\r
+ }\r
+\r
+ //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
+ //!\r
+ //! <b>Effects</b>: Erases the first element of the list.\r
+ //! Destroyer::operator()(pointer) is called for the removed element.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators to the erased element.\r
+ template<class Destroyer>\r
+ void pop_front_and_destroy(Destroyer destroyer)\r
+ {\r
+ node_ptr to_erase = node_traits::get_next(get_root_node());\r
+ this->pop_front();\r
+ destroyer(ValueTraits::to_value_ptr(to_erase));\r
+ }\r
+\r
+ //! <b>Effects</b>: Returns a reference to the first element of the list.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ reference front()\r
+ { return *ValueTraits::to_value_ptr(node_traits::get_next(get_root_node())); }\r
+\r
+ //! <b>Effects</b>: Returns a const_reference to the first element of the list.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ const_reference front() const\r
+ { return *ValueTraits::to_value_ptr(uncast(node_traits::get_next(const_node_ptr(&root)))); }\r
+\r
+ //! <b>Effects</b>: Returns an iterator to the first element contained in the list.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ iterator begin() \r
+ { return iterator (node_traits::get_next(get_root_node())); }\r
+\r
+ //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ const_iterator begin() const \r
+ { return const_iterator (node_traits::get_next(get_root_node())); }\r
+\r
+ //! <b>Effects</b>: Returns an iterator to the end of the list.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ iterator end() \r
+ { return iterator (get_root_node()); }\r
+\r
+ //! <b>Effects</b>: Returns a const_iterator to the end of the list.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ const_iterator end() const \r
+ { return const_iterator (get_root_node()); }\r
+\r
+ //! <b>Effects</b>: Returns an iterator that points to a position\r
+ //! before the first element. Equivalent to "end()"\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ iterator before_begin() \r
+ { return end(); }\r
+\r
+ //! <b>Effects</b>: Returns an iterator that points to a position\r
+ //! before the first element. Equivalent to "end()"\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ const_iterator before_begin() const \r
+ { return end(); }\r
+\r
+ //! <b>Effects</b>: Returns the number of the elements contained in the list.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the number of elements contained in the list.\r
+ //! if ConstantTimeSize is false. Constant time otherwise.\r
+ //! \r
+ //! <b>Note</b>: Does not affect the validity of iterators and references.\r
+ size_type size() const\r
+ {\r
+ if(ConstantTimeSize)\r
+ return size_traits::get_size();\r
+ else\r
+ return node_algorithms::count(const_node_ptr(&root)) - 1; \r
+ }\r
+\r
+ //! <b>Effects</b>: Returns true if the list contains no elements.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Note</b>: Does not affect the validity of iterators and references.\r
+ bool empty() const\r
+ { return node_algorithms::unique(get_root_node()); }\r
+\r
+ //! <b>Effects</b>: Swaps the elements of x and *this.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the number of elements of both lists.\r
+ //! \r
+ //! <b>Note</b>: Does not affect the validity of iterators and references.\r
+ void swap(islist& other)\r
+ {\r
+ node_algorithms::swap_nodes(get_root_node(), &other.root);\r
+ if(ConstantTimeSize){\r
+ size_type backup = size_traits::get_size();\r
+ size_traits::set_size(other.get_size());\r
+ other.set_size(backup);\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
+ //!\r
+ //! <b>Effects</b>: Erases all the elements from *this\r
+ //! calling Destroyer::operator()(pointer), clones all the \r
+ //! elements from src calling Cloner::operator()(const value_type &)\r
+ //! and inserts them on *this.\r
+ //!\r
+ //! If cloner throws, all cloned elements are unlinked and destroyed\r
+ //! calling Destroyer::operator()(pointer).\r
+ //! \r
+ //! <b>Complexity</b>: Linear to erased plus inserted elements.\r
+ //! \r
+ //! <b>Throws</b>: If cloner throws.\r
+ template <class Cloner, class Destroyer>\r
+ void clone_from(const islist &src, Cloner cloner, Destroyer destroyer)\r
+ { \r
+ clone_and_reverse_from(src, cloner, destroyer);\r
+ this->reverse();\r
+ }\r
+\r
+ //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
+ //!\r
+ //! <b>Effects</b>: Erases all the elements from *this\r
+ //! calling Destroyer::operator()(pointer), clones all the \r
+ //! elements from src calling Cloner::operator()(const value_type &)\r
+ //! and inserts them on *this in the reverse order than\r
+ //! the original container.\r
+ //!\r
+ //! If cloner throws, all cloned elements are unlinked and destroyed\r
+ //! calling Destroyer::operator()(pointer).\r
+ //! \r
+ //! <b>Complexity</b>: Linear to erased plus inserted elements.\r
+ //! \r
+ //! <b>Throws</b>: If cloner throws.\r
+ //! \r
+ //! <b>Note</b>: This function is more efficient than "clone_from".\r
+ template <class Cloner, class Destroyer>\r
+ void clone_and_reverse_from(const islist &src, Cloner cloner, Destroyer destroyer)\r
+ {\r
+ this->clear_and_destroy(destroyer);\r
+ try{\r
+ const_iterator b(src.begin()), e(src.end());\r
+ for(; b != e; ++b){\r
+ this->push_front(*cloner(*b));\r
+ }\r
+ }\r
+ catch(...){\r
+ clear_and_destroy(destroyer);\r
+ throw;\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: value must be an lvalue and prev_p must point to an element\r
+ //! contained by the list or to end().\r
+ //!\r
+ //! <b>Effects</b>: Inserts the value after the position pointed by prev_p.\r
+ //! No copy constructor is called.\r
+ //!\r
+ //! <b>Returns</b>: An iterator to the inserted element.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Note</b>: Does not affect the validity of iterators and references.\r
+ iterator insert_after(iterator prev_p, value_type &value)\r
+ {\r
+ node_ptr n = ValueTraits::to_node_ptr(value);\r
+ if(safemode_or_autounlink)\r
+ BOOST_ASSERT(node_algorithms::unique(n));\r
+ node_algorithms::link_after(prev_p.list_node(), n);\r
+ size_traits::increment();\r
+ return iterator (n);\r
+ }\r
+\r
+ //! <b>Requires</b>: Dereferencing iterator must yield \r
+ //! an lvalue of type value_type and prev_p must point to an element\r
+ //! contained by the list or to the end node.\r
+ //! \r
+ //! <b>Effects</b>: Inserts the [first, last)\r
+ //! after the position prev_p.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the number of elements inserted.\r
+ //! \r
+ //! <b>Note</b>: Does not affect the validity of iterators and references.\r
+ template<class Iterator>\r
+ void insert_after(iterator prev_p, Iterator first, Iterator last)\r
+ {\r
+ for (; first != last; ++first)\r
+ prev_p = insert_after(prev_p, *first);\r
+ }\r
+\r
+ //! <b>Requires</b>: value must be an lvalue and p must point to an element\r
+ //! contained by the list or to end().\r
+ //!\r
+ //! <b>Effects</b>: Inserts the value before the position pointed by p.\r
+ //! No copy constructor is called.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the number of elements before p. \r
+ //! \r
+ //! <b>Note</b>: Does not affect the validity of iterators and references.\r
+ iterator insert(iterator p, value_type &value)\r
+ { return insert_after(this->previous(p), value); }\r
+\r
+ //! <b>Requires</b>: Dereferencing iterator must yield \r
+ //! an lvalue of type value_type and p must point to an element \r
+ //! contained by the list or to the end node.\r
+ //! \r
+ //! <b>Effects</b>: Inserts the pointed by b and e\r
+ //! before the position p. No copy constructors are called.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the number of elements inserted plus linear\r
+ //! to the elements before b.\r
+ //! \r
+ //! <b>Note</b>: Does not affect the validity of iterators and references.\r
+ template<class Iterator>\r
+ void insert(iterator p, Iterator b, Iterator e)\r
+ { return insert_after(this->previous(p), b, e); }\r
+\r
+ //! <b>Effects</b>: Erases the element after the element pointed by prev of \r
+ //! the list. No destructors are called.\r
+ //!\r
+ //! <b>Returns</b>: the first element remaining beyond the removed elements,\r
+ //! or end() if no such element exists.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators (but not the references) to the\r
+ //! erased element.\r
+ iterator erase_after(iterator prev)\r
+ {\r
+ iterator it(prev); ++it;\r
+ node_ptr to_erase(it.list_node());\r
+ node_algorithms::unlink_after(prev.list_node());\r
+ size_traits::decrement();\r
+ iterator ret(++prev);\r
+ if(safemode_or_autounlink)\r
+ node_algorithms::init(to_erase);\r
+ return ret;\r
+ }\r
+\r
+ //! <b>Effects</b>: Erases the range (before_first, last) from\r
+ //! the list. No destructors are called.\r
+ //!\r
+ //! <b>Returns</b>: the first element remaining beyond the removed elements,\r
+ //! or end() if no such element exists.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Lineal to the elements (last - before_first).\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators (but not the references) to the\r
+ //! erased element.\r
+ iterator erase_after(iterator before_first, iterator last)\r
+ {\r
+ iterator first;\r
+ while(++(first = before_first) != last){\r
+ this->erase_after(before_first);\r
+ }\r
+ return last;\r
+ }\r
+\r
+ //! <b>Effects</b>: Erases the element pointed by i of the list. \r
+ //! No destructors are called.\r
+ //!\r
+ //! <b>Returns</b>: the first element remaining beyond the removed element,\r
+ //! or end() if no such element exists.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the elements before i.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators (but not the references) to the\r
+ //! erased element.\r
+ iterator erase(iterator i)\r
+ { return this->erase_after(this->previous(i)); }\r
+\r
+ //! <b>Requires</b>: first and last must be valid iterator to elements in *this.\r
+ //! \r
+ //! <b>Effects</b>: Erases the range pointed by b and e.\r
+ //! No destructors are called.\r
+ //!\r
+ //! <b>Returns</b>: the first element remaining beyond the removed elements,\r
+ //! or end() if no such element exists.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the number of elements erased plus linear\r
+ //! to the elements before first.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators (but not the references) to the\r
+ //! erased elements.\r
+ iterator erase(iterator first, iterator last)\r
+ { return erase_after(this->previous(first), last); }\r
+\r
+ //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
+ //!\r
+ //! <b>Effects</b>: Erases the element after the element pointed by prev of \r
+ //! the list.\r
+ //! Destroyer::operator()(pointer) is called for the removed element.\r
+ //!\r
+ //! <b>Returns</b>: the first element remaining beyond the removed elements,\r
+ //! or end() if no such element exists.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators to the erased element.\r
+ template<class Destroyer>\r
+ iterator erase_after_and_destroy(iterator prev, Destroyer destroyer)\r
+ {\r
+ iterator it(prev); ++it;\r
+ node_ptr to_erase(it.list_node());\r
+ iterator ret(this->erase_after(prev));\r
+ destroyer(ValueTraits::to_value_ptr(to_erase));\r
+ return ret;\r
+ }\r
+\r
+ //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
+ //!\r
+ //! <b>Effects</b>: Erases the range (before_first, last) from\r
+ //! the list.\r
+ //! Destroyer::operator()(pointer) is called for the removed elements.\r
+ //!\r
+ //! <b>Returns</b>: the first element remaining beyond the removed elements,\r
+ //! or end() if no such element exists.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Lineal to the elements (last - before_first).\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators to the erased element.\r
+ template<class Destroyer>\r
+ iterator erase_after_and_destroy(iterator before_first, iterator last, Destroyer destroyer)\r
+ {\r
+ iterator first;\r
+ while(++(first = before_first) != last){\r
+ this->erase_after_and_destroy(before_first, destroyer);\r
+ }\r
+ return last;\r
+ }\r
+\r
+ //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
+ //!\r
+ //! <b>Effects</b>: Erases the element pointed by i of the list. \r
+ //! No destructors are called.\r
+ //! Destroyer::operator()(pointer) is called for the removed element.\r
+ //!\r
+ //! <b>Returns</b>: the first element remaining beyond the removed element,\r
+ //! or end() if no such element exists.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the elements before i.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators (but not the references) to the\r
+ //! erased element.\r
+ template<class Destroyer>\r
+ iterator erase_and_destroy(iterator i, Destroyer destroyer)\r
+ { return this->erase_after_and_destroy(this->previous(i), destroyer); }\r
+\r
+ //! <b>Requires</b>: first and last must be valid iterator to elements in *this.\r
+ //! Destroyer::operator()(pointer) shouldn't throw.\r
+ //! \r
+ //! <b>Effects</b>: Erases the range pointed by b and e.\r
+ //! No destructors are called.\r
+ //! Destroyer::operator()(pointer) is called for the removed elements.\r
+ //!\r
+ //! <b>Returns</b>: the first element remaining beyond the removed elements,\r
+ //! or end() if no such element exists.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the number of elements erased plus linear\r
+ //! to the elements before first.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators (but not the references) to the\r
+ //! erased elements.\r
+ template<class Destroyer>\r
+ iterator erase_and_destroy(iterator first, iterator last, Destroyer destroyer)\r
+ { return erase_after_and_destroy(this->previous(first), last, destroyer); }\r
+\r
+ //! <b>Requires</b>: Dereferencing iterator must yield \r
+ //! an lvalue of type value_type.\r
+ //! \r
+ //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e.\r
+ //! No destructors or copy constructors are called.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the number of elements inserted plus\r
+ //! linear to the elements contained in the list if it's a safe-mode\r
+ //! or auto-unlink value.\r
+ //! Linear to the number of elements inserted in the list otherwise.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators (but not the references)\r
+ //! to the erased elements.\r
+ template<class Iterator>\r
+ void assign(Iterator b, Iterator e)\r
+ {\r
+ this->clear();\r
+ this->insert_after(before_begin(), b, e);\r
+ }\r
+\r
+ //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
+ //!\r
+ //! <b>Requires</b>: Dereferencing iterator must yield \r
+ //! an lvalue of type value_type.\r
+ //! \r
+ //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e.\r
+ //! No destructors or copy constructors are called.\r
+ //! Destroyer::operator()(pointer) is called for the removed elements.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the number of elements inserted plus\r
+ //! linear to the elements contained in the list.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators (but not the references)\r
+ //! to the erased elements.\r
+ template<class Iterator, class Destroyer>\r
+ void assign_and_destroy(Iterator b, Iterator e, Destroyer destroyer)\r
+ {\r
+ this->clear_and_destroy(destroyer);\r
+ this->insert_after_and_destroy(before_begin(), b, e, destroyer);\r
+ }\r
+\r
+ //! <b>Requires</b>: prev is an iterator to an element or x.end()/x.before_begin() in x.\r
+ //! \r
+ //! <b>Effects</b>: Transfers all the elements of list x to this list, after the\r
+ //! the element pointed by prev. No destructors or copy constructors are called.\r
+ //! \r
+ //! <b>Returns</b>: The last element inserted of x or prev if x is empty.\r
+ //! This iterator can be used as new "prev" iterator for a new splice_after call.\r
+ //! that will splice new values after the previously spliced values.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //!\r
+ //! <b>Complexity</b>: Linear to the elements contained in x\r
+ //! \r
+ //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this\r
+ //! list. Iterators of this list and all the references are not invalidated.\r
+ iterator splice_after(iterator prev, islist &x)\r
+ {\r
+ if (!x.empty()){\r
+ iterator last_x(x.previous(x.end()));\r
+ node_algorithms::transfer_after\r
+ ( prev.list_node()\r
+ , x.end().list_node()\r
+ , last_x.list_node());\r
+ size_traits::set_size(size_traits::get_size() + x.get_size());\r
+ x.set_size(size_type(0));\r
+ return last_x;\r
+ }\r
+ else{\r
+ return prev;\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: prev must point to an element contained by this list or\r
+ //! to the before_begin() element. prev_ele must point to an element contained in list\r
+ //! x or must be x.before_begin().\r
+ //! \r
+ //! <b>Effects</b>: Transfers the element after prev_ele, from list x to this list, \r
+ //! after the element pointed by prev. No destructors or copy constructors are called.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ //! \r
+ //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this\r
+ //! list. Iterators of this list and all the references are not invalidated.\r
+ void splice_after(iterator prev, islist &x, iterator prev_ele)\r
+ {\r
+ iterator nxt = prev_ele;\r
+ ++nxt;\r
+ if (nxt != prev && prev_ele != prev){\r
+ node_algorithms::transfer_after\r
+ (prev.list_node(), prev_ele.list_node(), nxt.list_node());\r
+ size_traits::increment();\r
+ x.decrement();\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be\r
+ //! before_begin(), and before_first and before_last belong to x and\r
+ //! ++before_first != x.end() && before_last != x.end(). \r
+ //! \r
+ //! <b>Effects</b>: Transfers the range (before_first, before_last] from list x to this\r
+ //! list, after the element pointed by prev_pos.\r
+ //! No destructors or copy constructors are called.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the number of elements transferred\r
+ //! if ConstantTimeSize is true. Constant-time otherwise.\r
+ //! \r
+ //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this\r
+ //! list. Iterators of this list and all the references are not invalidated.\r
+ void splice_after(iterator prev_pos, islist &x, iterator before_first, iterator before_last)\r
+ {\r
+ if (before_first != before_last){\r
+ if(ConstantTimeSize){\r
+ size_type increment = std::distance(before_first, before_last);\r
+ node_algorithms::transfer_after\r
+ (prev_pos.list_node(), before_first.list_node(), before_last.list_node());\r
+ size_traits::set_size(size_traits::get_size() + increment);\r
+ x.set_size(x.get_size() - increment);\r
+ }\r
+ else{\r
+ node_algorithms::transfer_after\r
+ (prev_pos.list_node(), before_first.list_node(), before_last.list_node());\r
+ }\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be\r
+ //! before_begin(), and before_first and before_last belong to x and\r
+ //! ++before_first != x.end() && before_last != x.end() and\r
+ //! n == std::distance(before_first, before_last).\r
+ //! \r
+ //! <b>Effects</b>: Transfers the range (before_first, before_last] from list x to this\r
+ //! list, after the element pointed by p. No destructors or copy constructors are called.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant time.\r
+ //! \r
+ //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this\r
+ //! list. Iterators of this list and all the references are not invalidated.\r
+ void splice_after(iterator prev_pos, islist &x, iterator before_first, iterator before_last, difference_type n)\r
+ {\r
+ if(n){\r
+ if(ConstantTimeSize){\r
+ BOOST_ASSERT(std::distance(before_first, before_last) == n);\r
+ node_algorithms::transfer_after\r
+ (prev_pos.list_node(), before_first.list_node(), before_last.list_node());\r
+ size_traits::set_size(size_traits::get_size() + n);\r
+ x.set_size(x.get_size() - n);\r
+ }\r
+ else{\r
+ node_algorithms::transfer_after\r
+ (prev_pos.list_node(), before_first.list_node(), before_last.list_node());\r
+ }\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: it is an iterator to an element in x.\r
+ //! \r
+ //! <b>Effects</b>: Transfers all the elements of list x to this list, before the\r
+ //! the element pointed by it. No destructors or copy constructors are called.\r
+ //! \r
+ //! <b>Returns</b>: The last element inserted of x or the previous element\r
+ //! of it if x is empty.\r
+ //! This iterator can be used as new "prev" iterator for a new splice call.\r
+ //! that will splice new values after the previously spliced values.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //!\r
+ //! <b>Complexity</b>: Linear to the elements contained in x plus linear to\r
+ //! the elements before it.\r
+ //! \r
+ //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this\r
+ //! list. Iterators of this list and all the references are not invalidated.\r
+ iterator splice(iterator it, islist &x)\r
+ { return splice_after(this->previous(it), x); }\r
+\r
+ //! <b>Requires</b>: it p must be a valid iterator of *this.\r
+ //! elem must point to an element contained in list\r
+ //! x.\r
+ //! \r
+ //! <b>Effects</b>: Transfers the element elem, from list x to this list, \r
+ //! before the element pointed by pos. No destructors or copy constructors are called.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the elements before pos and before elem.\r
+ //! \r
+ //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this\r
+ //! list. Iterators of this list and all the references are not invalidated.\r
+ void splice(iterator pos, islist &x, iterator elem)\r
+ { return splice_after(this->previous(pos), x, this->previous(elem)); }\r
+\r
+ //! <b>Requires</b>: pos must be a dereferenceable iterator in *this\r
+ //! and first and last belong to x and first and last a valid range on x. \r
+ //! \r
+ //! <b>Effects</b>: Transfers the range [first, last) from list x to this\r
+ //! list, before the element pointed by pos.\r
+ //! No destructors or copy constructors are called.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the sum of elements before pos, first, and last.\r
+ //! Plus linear to the number of elements transferred if ConstantTimeSize is true.\r
+ //! \r
+ //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this\r
+ //! list. Iterators of this list and all the references are not invalidated.\r
+ void splice(iterator pos, islist &x, iterator first, iterator last)\r
+ { return splice_after(this->previous(pos), x, this->previous(first), this->previous(last)); }\r
+\r
+ //! <b>Requires</b>: pos must be a dereferenceable iterator in *this\r
+ //! and first and last belong to x and first and last a valid range on x. \r
+ //! n == std::distance(first, last).\r
+ //! \r
+ //! <b>Effects</b>: Transfers the range [first, last) from list x to this\r
+ //! list, before the element pointed by pos.\r
+ //! No destructors or copy constructors are called.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the sum of elements before pos, first, and last.\r
+ //! \r
+ //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this\r
+ //! list. Iterators of this list and all the references are not invalidated.\r
+ void splice(iterator pos, islist &x, iterator first, iterator last, difference_type n)\r
+ { return splice_after(this->previous(pos), x, this->previous(first), this->previous(last), n); }\r
+\r
+ //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. \r
+ //! The sort is stable, that is, the relative order of equivalent elements is preserved.\r
+ //! \r
+ //! <b>Throws</b>: If value_traits::node_traits::node\r
+ //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)\r
+ //! or the predicate throws. Basic guarantee.\r
+ //! \r
+ //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N\r
+ //! is the list's size.\r
+ //!\r
+ //! <b>Note</b>: Iterators and references are not invalidated\r
+ template<class Predicate>\r
+ void sort(Predicate p)\r
+ {\r
+ if (!this->empty() &&\r
+ node_traits::get_next(node_traits::get_next(get_root_node()))\r
+ != this->get_root_node()) {\r
+ islist carry;\r
+ islist counter[64];\r
+ int fill = 0;\r
+ iterator last_inserted;\r
+ while(!this->empty()){\r
+ last_inserted = this->begin();\r
+ carry.splice_after(carry.before_begin(), *this, this->before_begin());\r
+ int i = 0;\r
+ while(i < fill && !counter[i].empty()) {\r
+ last_inserted = carry.merge(counter[i++], p);\r
+ }\r
+ BOOST_ASSERT(counter[i].empty());\r
+\r
+ iterator last_element(previous_node(last_inserted, carry.end()));\r
+ if(ConstantTimeSize){\r
+ counter[i].splice_after( counter[i].end(), carry\r
+ , carry.before_begin(), last_element\r
+ , carry.size());\r
+ }\r
+ else{\r
+ counter[i].splice_after( counter[i].end(), carry\r
+ , carry.before_begin(), last_element);\r
+ }\r
+ //counter[i].splice_after(counter[i].end(), carry, carry.end(), previous_node(last_inserted, carry.end()));\r
+ //carry.swap(counter[i]);\r
+ if(i == fill)\r
+ ++fill;\r
+ }\r
+\r
+ for (int i = 1; i < fill; ++i)\r
+ last_inserted = counter[i].merge(counter[i-1], p);\r
+ //this->swap(counter[fill-1]);\r
+ BOOST_ASSERT(this->empty());\r
+\r
+ iterator last_element(previous_node(last_inserted, counter[--fill].end()));\r
+ if(ConstantTimeSize){\r
+ this->splice_after( end(), counter[fill], counter[fill].before_begin()\r
+ , last_element, counter[fill].size());\r
+ }\r
+ else{\r
+ this->splice_after( end(), counter[fill], counter[fill].before_begin()\r
+ , last_element);\r
+ }\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: p must be a comparison function that induces a strict weak\r
+ //! ordering and both *this and x must be sorted according to that ordering\r
+ //! The lists x and *this must be distinct. \r
+ //! \r
+ //! <b>Effects</b>: This function removes all of x's elements and inserts them\r
+ //! in order into *this. The merge is stable; that is, if an element from *this is \r
+ //! equivalent to one from x, then the element from *this will precede the one from x. \r
+ //! \r
+ //! <b>Throws</b>: If value_traits::node_traits::node\r
+ //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)\r
+ //! or std::less<value_type> throws. Basic guarantee.\r
+ //! \r
+ //! <b>Complexity</b>: This function is linear time: it performs at most\r
+ //! size() + x.size() - 1 comparisons.\r
+ //! \r
+ //! <b>Note</b>: Iterators and references are not invalidated.\r
+ void sort()\r
+ { this->sort(std::less<value_type>()); }\r
+\r
+ //! <b>Requires</b>: p must be a comparison function that induces a strict weak\r
+ //! ordering and both *this and x must be sorted according to that ordering\r
+ //! The lists x and *this must be distinct. \r
+ //! \r
+ //! <b>Effects</b>: This function removes all of x's elements and inserts them\r
+ //! in order into *this. The merge is stable; that is, if an element from *this is \r
+ //! equivalent to one from x, then the element from *this will precede the one from x. \r
+ //! \r
+ //! <b>Returns</b>: An iterator to the last transferred value, end() is x is empty.\r
+ //! \r
+ //! <b>Throws</b>: If the predicate throws. Basic guarantee.\r
+ //! \r
+ //! <b>Complexity</b>: This function is linear time: it performs at most\r
+ //! size() + x.size() - 1 comparisons.\r
+ //! \r
+ //! <b>Note</b>: Iterators and references are not invalidated.\r
+ template<class Predicate>\r
+ iterator merge(islist& x, Predicate p) \r
+ {\r
+ iterator a(before_begin()), e(end()), ax(x.before_begin());\r
+ iterator last_inserted(e);\r
+ iterator a_next;\r
+ while(++(a_next = a) != e && !x.empty()) {\r
+ iterator ix(ax);\r
+ iterator cx;\r
+ size_type n(0);\r
+ while(++(cx = ix) != ax && p(*cx, *a_next)){\r
+ ++ix; ++n;\r
+ }\r
+ if(ax != ix){\r
+ this->splice_after(a, x, ax, ix, n);\r
+ last_inserted = ix;\r
+ }\r
+ a = a_next;\r
+ } \r
+ if (!x.empty()){\r
+ last_inserted = this->splice_after(a, x);\r
+ }\r
+ return last_inserted;\r
+ }\r
+\r
+ //! <b>Effects</b>: This function removes all of x's elements and inserts them\r
+ //! in order into *this according to std::less<value_type>. The merge is stable; \r
+ //! that is, if an element from *this is equivalent to one from x, then the element \r
+ //! from *this will precede the one from x. \r
+ //! \r
+ //! <b>Throws</b>: if std::less<value_type> throws. Basic guarantee.\r
+ //! \r
+ //! <b>Complexity</b>: This function is linear time: it performs at most\r
+ //! size() + x.size() - 1 comparisons.\r
+ //! \r
+ //! <b>Note</b>: Iterators and references are not invalidated\r
+ void merge(islist& x)\r
+ { this->merge(x, std::less<value_type>()); }\r
+\r
+ //! <b>Effects</b>: Reverses the order of elements in the list. \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: This function is linear to the contained elements.\r
+ //! \r
+ //! <b>Note</b>: Iterators and references are not invalidated\r
+ void reverse() \r
+ { node_algorithms::reverse(node_ptr(&root)); }\r
+\r
+ //! <b>Effects</b>: Removes all the elements that compare equal to value.\r
+ //! No destructors are called.\r
+ //! \r
+ //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.\r
+ //! \r
+ //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.\r
+ //! \r
+ //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
+ //! and iterators to elements that are not removed remain valid. This function is \r
+ //! linear time: it performs exactly size() comparisons for equality.\r
+ void remove(const value_type &value)\r
+ { remove_if(equal_to_value(value)); }\r
+\r
+ //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
+ //!\r
+ //! <b>Effects</b>: Removes all the elements that compare equal to value.\r
+ //! Destroyer::operator()(pointer) is called for every removed element.\r
+ //!\r
+ //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.\r
+ //! \r
+ //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.\r
+ //! \r
+ //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
+ //! and iterators to elements that are not removed remain valid.\r
+ template<class Destroyer>\r
+ void remove_and_destroy(const value_type &value, Destroyer destroyer)\r
+ { remove_and_destroy_if(equal_to_value(value), destroyer); }\r
+\r
+ //! <b>Effects</b>: Removes all the elements for which a specified\r
+ //! predicate is satisfied. No destructors are called.\r
+ //! \r
+ //! <b>Throws</b>: If pred throws. Basic guarantee.\r
+ //! \r
+ //! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate.\r
+ //! \r
+ //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
+ //! and iterators to elements that are not removed remain valid.\r
+ template<class Pred>\r
+ void remove_if(Pred pred)\r
+ { remove_and_destroy_if(pred, detail::null_destroyer()); }\r
+\r
+ //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
+ //!\r
+ //! <b>Effects</b>: Removes all the elements for which a specified\r
+ //! predicate is satisfied.\r
+ //! Destroyer::operator()(pointer) is called for every removed element.\r
+ //!\r
+ //! <b>Throws</b>: If pred throws. Basic guarantee.\r
+ //! \r
+ //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.\r
+ //!\r
+ //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
+ //! and iterators to elements that are not removed remain valid.\r
+ template<class Pred, class Destroyer>\r
+ void remove_and_destroy_if(Pred pred, Destroyer destroyer)\r
+ {\r
+ iterator bcur(this->before_begin()), cur, e(this->end());\r
+ \r
+ while(++(cur = bcur) != e){\r
+ if (pred(*cur)){\r
+ pointer p = cur.operator->();\r
+ this->erase_after(bcur);\r
+ destroyer(p);\r
+ }\r
+ else{\r
+ ++bcur;\r
+ }\r
+ }\r
+ }\r
+\r
+ //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent \r
+ //! elements that are equal from the list. No destructors are called.\r
+ //! \r
+ //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.\r
+ //! \r
+ //! <b>Complexity</b>: Linear time (size()-1) comparisons calls to pred()).\r
+ //! \r
+ //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
+ //! and iterators to elements that are not removed remain valid.\r
+ void unique()\r
+ { unique_and_destroy(std::equal_to<value_type>(), detail::null_destroyer()); }\r
+\r
+ //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent \r
+ //! elements that satisfy some binary predicate from the list.\r
+ //! No destructors are called.\r
+ //! \r
+ //! <b>Throws</b>: If the predicate throws. Basic guarantee.\r
+ //! \r
+ //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.\r
+ //! \r
+ //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
+ //! and iterators to elements that are not removed remain valid.\r
+ template<class BinaryPredicate>\r
+ void unique(BinaryPredicate pred)\r
+ { unique_and_destroy(pred, detail::null_destroyer()); }\r
+\r
+ //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
+ //!\r
+ //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent \r
+ //! elements that satisfy some binary predicate from the list.\r
+ //! Destroyer::operator()(pointer) is called for every removed element.\r
+ //! \r
+ //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee.\r
+ //! \r
+ //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.\r
+ //! \r
+ //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
+ //! and iterators to elements that are not removed remain valid.\r
+ template<class Destroyer>\r
+ void unique_and_destroy(Destroyer destroyer)\r
+ { unique(std::equal_to<value_type>(), destroyer); }\r
+\r
+ //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
+ //!\r
+ //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent \r
+ //! elements that satisfy some binary predicate from the list.\r
+ //! Destroyer::operator()(pointer) is called for every removed element.\r
+ //! \r
+ //! <b>Throws</b>: If the predicate throws. Basic guarantee.\r
+ //! \r
+ //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons.\r
+ //! \r
+ //! <b>Note</b>: The relative order of elements that are not removed is unchanged,\r
+ //! and iterators to elements that are not removed remain valid.\r
+ template<class BinaryPredicate, class Destroyer>\r
+ void unique_and_destroy(BinaryPredicate pred, Destroyer destroyer)\r
+ {\r
+ iterator end_n(end());\r
+ iterator cur(begin());\r
+ iterator cur_next;\r
+\r
+ if (cur != end_n) {\r
+ while(++(cur_next = cur) != end_n) {\r
+ if (pred(*cur, *cur_next)){\r
+ pointer p = cur_next.operator->();\r
+ this->erase_after(cur);\r
+ destroyer(p);\r
+ }\r
+ else{\r
+ ++cur;\r
+ }\r
+ }\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: value must be a reference to a value inserted in a list.\r
+ //! \r
+ //! <b>Effects</b>: This function returns a const_iterator pointing to the element\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant time.\r
+ //! \r
+ //! <b>Note</b>: Iterators and references are not invalidated.\r
+ static iterator current(value_type &value) \r
+ { \r
+ BOOST_ASSERT (!node_algorithms::unique(ValueTraits::to_node_ptr(value)));\r
+ return iterator (ValueTraits::to_node_ptr(value)); \r
+ }\r
+\r
+ //! <b>Requires</b>: value must be a const reference to a value inserted in a list.\r
+ //! \r
+ //! <b>Effects</b>: This function returns an iterator pointing to the element.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant time.\r
+ //! \r
+ //! <b>Note</b>: Iterators and references are not invalidated.\r
+ static const_iterator current(const value_type &value) \r
+ { \r
+ BOOST_ASSERT (!node_algorithms::unique(ValueTraits::to_node_ptr(const_cast<value_type&> (value))));\r
+ return const_iterator (ValueTraits::to_node_ptr(const_cast<value_type&> (value))); \r
+ }\r
+\r
+ //! <b>Returns</b>: The iterator to the element before i in the list. \r
+ //! Returns the end-iterator, if either i is the begin-iterator or the \r
+ //! list is empty. \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the number of elements before i. \r
+ iterator previous(iterator i)\r
+ {\r
+ return iterator\r
+ (node_algorithms::get_previous_node\r
+ (before_begin().list_node(), i.list_node()));\r
+ }\r
+\r
+ //! <b>Returns</b>: The const_iterator to the element before i in the list. \r
+ //! Returns the end-const_iterator, if either i is the begin-const_iterator or \r
+ //! the list is empty. \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Linear to the number of elements before i. \r
+ const_iterator previous(const_iterator i) const\r
+ {\r
+ return const_iterator\r
+ (node_algorithms::get_previous_node\r
+ (before_begin().list_node(), i.list_node()));\r
+ }\r
+};\r
+\r
+template <class V, bool C, class S>\r
+inline bool operator==(const islist<V, C, S>& x, const islist<V, C, S>& y)\r
+{\r
+ if(C && x.size() != y.size()){\r
+ return false;\r
+ }\r
+ typedef typename islist<V, C, S>::const_iterator const_iterator;\r
+ const_iterator end1 = x.end();\r
+\r
+ const_iterator i1 = x.begin();\r
+ const_iterator i2 = y.begin();\r
+ if(C){\r
+ while (i1 != end1 && *i1 == *i2) {\r
+ ++i1;\r
+ ++i2;\r
+ }\r
+ return i1 == end1;\r
+ }\r
+ else{\r
+ const_iterator end2 = y.end();\r
+ while (i1 != end1 && i2 != end2 && *i1 == *i2) {\r
+ ++i1;\r
+ ++i2;\r
+ }\r
+ return i1 == end1 && i2 == end2;\r
+ }\r
+}\r
+\r
+template <class V, bool C, class S>\r
+inline bool operator<(const islist<V, C, S>& x,\r
+ const islist<V, C, S>& y)\r
+{ return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }\r
+\r
+template <class V, bool C, class S>\r
+inline bool operator!=(const islist<V, C, S>& x, const islist<V, C, S>& y) \r
+{ return !(x == y); }\r
+\r
+template <class V, bool C, class S>\r
+inline bool operator>(const islist<V, C, S>& x, const islist<V, C, S>& y) \r
+{ return y < x; }\r
+\r
+template <class V, bool C, class S>\r
+inline bool operator<=(const islist<V, C, S>& x, const islist<V, C, S>& y) \r
+{ return !(y < x); }\r
+\r
+template <class V, bool C, class S>\r
+inline bool operator>=(const islist<V, C, S>& x, const islist<V, C, S>& y) \r
+{ return !(x < y); }\r
+\r
+template <class V, bool C, class S>\r
+inline void swap(islist<V, C, S>& x, islist<V, C, S>& y)\r
+{ x.swap(y); }\r
+\r
+} //namespace intrusive \r
+} //namespace boost \r
+\r
+#include "detail/config_end.hpp"\r
+\r
+#endif //BOOST_INTRUSIVE_ISLIST_HPP\r
projects / senf.git / blobdiff