--- /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_ILIST_HPP\r
+#define BOOST_INTRUSIVE_ILIST_HPP\r
+\r
+#include "detail/config_begin.hpp"\r
+#include <boost/utility.hpp>\r
+#include <boost/assert.hpp>\r
+#include "ilist_hook.hpp"\r
+#include "list_algorithms.hpp"\r
+#include "detail/pointer_type.hpp"\r
+#include "detail/pointer_to_other.hpp"\r
+#include "linking_policy.hpp"\r
+#include <boost/get_pointer.hpp>\r
+#include <boost/static_assert.hpp>\r
+#include <iterator>\r
+#include <algorithm>\r
+#include <stdexcept>\r
+#include <functional>\r
+#include <cstddef>\r
+#include <iterator>\r
+\r
+namespace boost {\r
+namespace intrusive {\r
+\r
+//! The class template ilist is an intrusive container that mimics most of the \r
+//! interface of std::list as described in the C++ standard.\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
+template< class ValueTraits\r
+ , bool ConstantTimeSize = true\r
+ , class SizeType = std::size_t>\r
+class ilist\r
+ : private detail::size_holder<ConstantTimeSize, SizeType>\r
+{\r
+ private:\r
+\r
+ typedef ilist<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
+ ilist (const ilist&);\r
+\r
+ //! This class is\r
+ //! non-assignable\r
+ ilist &operator =(const ilist&);\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
+ //!The bidirectional iterator\r
+ class iterator;\r
+\r
+ //!The bidirectional const_iterator\r
+ class const_iterator;\r
+\r
+ //!The bidirectional iterator\r
+ friend class iterator;\r
+\r
+ //!The bidirectional const_iterator\r
+ friend class const_iterator;\r
+\r
+ private:\r
+\r
+ typedef typename node_traits::node node;\r
+ typedef typename node_traits::node_ptr node_ptr;\r
+ typedef typename node_traits::const_node_ptr const_node_ptr;\r
+ typedef list_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
+ //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
+ //Const cast emulation for smart pointers\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
+ //This is the root node of the circular list\r
+ node root;\r
+\r
+ public:\r
+\r
+ //!The bidirectional iterator of the container\r
+ class iterator\r
+ : public detail::list_iterator<value_type, iterator, node_traits>\r
+ {\r
+ private:\r
+ // gcc warns about an ambiguity between iterator::value_type and\r
+ // ilist<ValueTraits>::value_type, thus I introduce a unique name:\r
+ typedef typename ilist<ValueTraits, ConstantTimeSize, SizeType>::value_type private_vt;\r
+ typedef typename ilist<ValueTraits, ConstantTimeSize, SizeType>::pointer private_pointer;\r
+ typedef typename ilist<ValueTraits, ConstantTimeSize, SizeType>::reference private_reference;\r
+ typedef detail::list_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
+ private:\r
+ explicit iterator(node_ptr node)\r
+ : inherited (node)\r
+ {}\r
+ friend class ilist<ValueTraits, ConstantTimeSize, SizeType>;\r
+ friend class detail::list_iterator<private_vt, iterator, node_traits>;\r
+ friend class const_iterator;\r
+ };\r
+\r
+ //!The bidirectional const_iterator of the container\r
+ class const_iterator\r
+ : public detail::list_iterator<const value_type, const_iterator, node_traits>\r
+ {\r
+ private:\r
+ // gcc warns about an ambiguity between const_iterator::value_type and\r
+ // ilist<ValueTraits>::value_type, thus I introduce a unique name:\r
+ typedef const typename ilist<ValueTraits, ConstantTimeSize, SizeType>::value_type private_vt;\r
+ typedef typename ilist<ValueTraits, ConstantTimeSize, SizeType>::const_pointer private_pointer;\r
+ typedef typename ilist<ValueTraits, ConstantTimeSize, SizeType>::const_reference private_reference;\r
+ typedef detail::list_iterator<private_vt, const_iterator, node_traits> inherited;\r
+ \r
+ public: \r
+ const_iterator()\r
+ {}\r
+\r
+ const_iterator(const typename ilist::iterator& it)\r
+ : inherited (it.list_node())\r
+ {}\r
+\r
+ const_iterator & operator=(const typename ilist::iterator& it)\r
+ { return inherited::operator=(it.list_node()); }\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
+ private:\r
+ explicit const_iterator(const_node_ptr node)\r
+ : inherited (uncast(node))\r
+ {}\r
+ friend class ilist<ValueTraits, ConstantTimeSize, SizeType>;\r
+ friend class detail::list_iterator<private_vt, const_iterator, node_traits>;\r
+ };\r
+\r
+ //!The bidirectional reverse iterator of the container\r
+ typedef std::reverse_iterator<iterator> reverse_iterator;\r
+\r
+ //!The bidirectional const_reverse iterator of the container\r
+ typedef std::reverse_iterator<const_iterator> const_reverse_iterator;\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
+ ilist()\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 the range [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
+ ilist(Iterator b, Iterator e)\r
+ {\r
+ size_traits::set_size(size_type(0));\r
+ node_algorithms::init(node_ptr(&root));\r
+ this->insert(this->end(), b, e);\r
+ }\r
+\r
+ //! <b>Effects</b>: If it's not a safe-mode or an auto-unlink value_type \r
+ //! 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
+ ~ilist() \r
+ {\r
+ if(safemode_or_autounlink){\r
+ this->clear(); \r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: value must be an lvalue.\r
+ //! \r
+ //! <b>Effects</b>: Inserts the value in the back 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_back(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_before(node_ptr(&root), to_insert);\r
+ size_traits::increment();\r
+ }\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_before(node_traits::get_next(const_node_ptr(&root)), to_insert); \r
+ size_traits::increment();\r
+ }\r
+\r
+ //! <b>Effects</b>: Erases the last 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_back() \r
+ {\r
+ node_ptr to_erase = node_traits::get_previous(const_node_ptr(&root));\r
+ node_algorithms::unlink(to_erase);\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 last element of the list.\r
+ //! No destructors are called.\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_back_and_destroy(Destroyer destroyer)\r
+ {\r
+ node_ptr to_erase = node_traits::get_previous(const_node_ptr(&root));\r
+ node_algorithms::unlink(to_erase);\r
+ size_traits::decrement();\r
+ if(safemode_or_autounlink)\r
+ node_algorithms::init(to_erase);\r
+ destroyer(ValueTraits::to_value_ptr(to_erase));\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(const_node_ptr(&root));\r
+ node_algorithms::unlink(to_erase);\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
+ //! No destructors are called.\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(const_node_ptr(&root));\r
+ node_algorithms::unlink(to_erase);\r
+ size_traits::decrement();\r
+ if(safemode_or_autounlink)\r
+ node_algorithms::init(to_erase);\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(const_node_ptr(&root))); }\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 a reference to the last element of the list.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ reference back() \r
+ { return *ValueTraits::to_value_ptr(node_traits::get_previous(const_node_ptr(&root))); }\r
+\r
+ //! <b>Effects</b>: Returns a const_reference to the last element of the list.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ const_reference back() const \r
+ { return *ValueTraits::to_value_ptr(uncast(node_traits::get_previous(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(const_node_ptr(&root))); }\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(const_node_ptr(&root))); }\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(node_ptr(&root)); }\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(const_node_ptr(&root)); }\r
+\r
+ //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning \r
+ //! of the reversed list. \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ reverse_iterator rbegin()\r
+ { return reverse_iterator(end()); }\r
+\r
+ //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning \r
+ //! of the reversed list. \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ const_reverse_iterator rbegin() const \r
+ { return const_reverse_iterator(end()); }\r
+\r
+ //! <b>Effects</b>: Returns a reverse_iterator pointing to the end\r
+ //! of the reversed list. \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ reverse_iterator rend()\r
+ { return reverse_iterator(begin()); }\r
+\r
+ //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end\r
+ //! of the reversed list. \r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant.\r
+ const_reverse_iterator rend() const\r
+ { return const_reverse_iterator(begin()); }\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(const_node_ptr(&root)); }\r
+\r
+ //! <b>Effects</b>: Swaps the elements of x and *this.\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 swap(ilist& other)\r
+ {\r
+ node_algorithms::swap_nodes(node_ptr(&root), node_ptr(&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>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>: Constant.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators (but not the references) to the\r
+ //! erased element.\r
+ iterator erase(iterator i)\r
+ {\r
+ iterator erase = i;\r
+ ++i;\r
+ node_ptr to_erase = erase.list_node();\r
+ node_algorithms::unlink(to_erase);\r
+ size_traits::decrement();\r
+ if(safemode_or_autounlink)\r
+ node_algorithms::init(to_erase);\r
+ return i;\r
+ }\r
+\r
+ //! <b>Requires</b>: first and last must be valid iterator to elements in *this.\r
+ //!\r
+ //! <b>Effects</b>: Erases the element 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 if it's a safe-mode\r
+ //! or auto-unlink value. Constant time otherwise.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators (but not the references) to the \r
+ //! erased elements.\r
+ iterator erase(iterator b, iterator e)\r
+ {\r
+ if(safemode_or_autounlink || ConstantTimeSize){\r
+ while(b != e){\r
+ b = this->erase(b);\r
+ }\r
+ return b;\r
+ }\r
+ else{\r
+ node_algorithms::unlink(b.list_node(), e.list_node());\r
+ return e;\r
+ }\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>: Constant.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators to the erased element.\r
+ template <class Destroyer>\r
+ iterator erase_and_destroy(iterator i, Destroyer destroyer)\r
+ {\r
+ iterator erase = i;\r
+ ++i;\r
+ node_ptr to_erase = erase.list_node();\r
+ node_algorithms::unlink(to_erase);\r
+ size_traits::decrement();\r
+ if(safemode_or_autounlink)\r
+ node_algorithms::init(to_erase);\r
+ destroyer(ValueTraits::to_value_ptr(to_erase));\r
+ return i;\r
+ }\r
+\r
+ //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
+ //!\r
+ //! <b>Effects</b>: Erases the element 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.\r
+ //! \r
+ //! <b>Note</b>: Invalidates the iterators to the erased elements.\r
+ template <class Destroyer>\r
+ iterator erase_and_destroy(iterator b, iterator e, Destroyer destroyer)\r
+ {\r
+ while(b != e){\r
+ b = this->erase_and_destroy(b, destroyer);\r
+ }\r
+ return b;\r
+ }\r
+\r
+ //! <b>Effects</b>: Erases all the elements of the container.\r
+ //! No destructors are called.\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(this->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
+ //! No destructors 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 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_and_destroy(this->begin(), this->end(), destroyer); }\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. Basic guarantee.\r
+ template <class Cloner, class Destroyer>\r
+ void clone_from(const ilist &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_back(*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 p must be a valid iterator of *this.\r
+ //!\r
+ //! <b>Effects</b>: Inserts the value before the position pointed by p.\r
+ //!\r
+ //! <b>Returns</b>: An iterator to the inserted element.\r
+ //! \r
+ //! <b>Throws</b>: Nothing.\r
+ //! \r
+ //! <b>Complexity</b>: Constant time. No copy constructors are called.\r
+ //! \r
+ //! <b>Note</b>: Does not affect the validity of iterators and references.\r
+ iterator insert(iterator p, 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_before(p.list_node(), to_insert);\r
+ size_traits::increment();\r
+ return iterator(to_insert);\r
+ }\r
+\r
+ //! <b>Requires</b>: Dereferencing iterator must yield \r
+ //! an lvalue of type value_type and p must be a valid iterator of *this.\r
+ //! \r
+ //! <b>Effects</b>: Inserts the range pointed by b and e before the position p.\r
+ //! No copy constructors are called.\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(iterator p, Iterator b, Iterator e)\r
+ {\r
+ for (; b != e; ++b)\r
+ this->insert(p, *b);\r
+ }\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(this->end(), 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(destroyer);\r
+ this->insert(this->end(), b, e);\r
+ }\r
+\r
+ //! <b>Requires</b>: p must be a valid iterator of *this.\r
+ //!\r
+ //! <b>Effects</b>: Transfers all the elements of list x to this list, before the\r
+ //! the element pointed by p. 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\r
+ //! this list. Iterators of this list and all the references are not invalidated.\r
+ void splice(iterator p, ilist& x)\r
+ {\r
+ if(!x.empty()){\r
+ node_algorithms::transfer\r
+ (p.list_node(), x.begin().list_node(), x.end().list_node());\r
+ size_traits::set_size(size_traits::get_size() + x.get_size());\r
+ x.set_size(size_type(0));\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: p must be a valid iterator of *this.\r
+ //! new_ele must point to an element contained in list x.\r
+ //! \r
+ //! <b>Effects</b>: Transfers the value pointed by new_ele, from list x to this list, \r
+ //! before the the element pointed by p. No destructors or copy constructors are called.\r
+ //! If p == new_ele or p == ++new_ele, this function is a null operation. \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(iterator p, ilist&x, iterator new_ele)\r
+ {\r
+ node_algorithms::transfer(p.list_node(), new_ele.list_node());\r
+ x.decrement();\r
+ size_traits::increment();\r
+ }\r
+\r
+ //! <b>Requires</b>: p must be a valid iterator of *this.\r
+ //! start and end must point to elements contained in list x.\r
+ //! \r
+ //! <b>Effects</b>: Transfers the range pointed by start and end from list x to this list, \r
+ //! before the the element pointed by p. 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(iterator p, ilist&x, iterator start, iterator end)\r
+ {\r
+ if(start != end){\r
+ if(ConstantTimeSize){\r
+ size_type increment = std::distance(start, end);\r
+ node_algorithms::transfer(p.list_node(), start.list_node(), end.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(p.list_node(), start.list_node(), end.list_node());\r
+ }\r
+ }\r
+ }\r
+\r
+ //! <b>Requires</b>: p must be a valid iterator of *this.\r
+ //! start and end must point to elements contained in list x.\r
+ //! n == std::distance(start, end)\r
+ //! \r
+ //! <b>Effects</b>: Transfers the range pointed by start and end from list x to this list, \r
+ //! before the the element pointed by p. 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(iterator p, ilist&x, iterator start, iterator end, difference_type n)\r
+ {\r
+ if(n){\r
+ if(ConstantTimeSize){\r
+ BOOST_ASSERT(n == std::distance(start, end));\r
+ node_algorithms::transfer(p.list_node(), start.list_node(), end.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(p.list_node(), start.list_node(), end.list_node());\r
+ }\r
+ }\r
+ }\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 std::less<value_type> throws. Basic guarantee.\r
+ //!\r
+ //! <b>Notes</b>: Iterators and references are not invalidated.\r
+ //! \r
+ //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N\r
+ //! is the list's size.\r
+ void sort() \r
+ { sort(std::less<value_type>()); }\r
+\r
+ //! <b>Requires</b>: p must be a comparison function that induces a strict weak ordering\r
+ //! \r
+ //! <b>Effects</b>: This function sorts the list *this according to p. The sort is \r
+ //! 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>Notes</b>: This won't throw if ilist_base_hook<>::value_traits or\r
+ //! ilist_member_hook::::value_traits are used as value traits.\r
+ //! Iterators and references are not invalidated.\r
+ //! \r
+ //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N\r
+ //! is the list's size.\r
+ template<class Predicate>\r
+ void sort(Predicate p)\r
+ {\r
+ if(node_traits::get_next(const_node_ptr(&root)) \r
+ != node_traits::get_previous(const_node_ptr(&root))){\r
+ ilist carry;\r
+ ilist counter[64];\r
+ int fill = 0;\r
+ while(!this->empty()){\r
+ carry.splice(carry.begin(), *this, this->begin());\r
+ int i = 0;\r
+ while(i < fill && !counter[i].empty()) {\r
+ carry.merge(counter[i++], p);\r
+ }\r
+ carry.swap(counter[i]);\r
+ if(i == fill)\r
+ ++fill;\r
+ }\r
+ for (int i = 1; i < fill; ++i)\r
+ counter[i].merge(counter[i-1], p);\r
+ this->swap(counter[fill-1]);\r
+ }\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(ilist& x)\r
+ { merge(x, 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>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
+ void merge(ilist& x, Predicate p)\r
+ {\r
+ iterator e = this->end();\r
+ iterator bx = x.begin();\r
+ iterator ex = x.end();\r
+\r
+ for (iterator b = this->begin(); b != e; ++b) {\r
+ size_type n(0);\r
+ iterator ix(bx);\r
+ while(ix != ex && p(*ix, *b)){\r
+ ++ix; ++n;\r
+ }\r
+ this->splice(b, x, bx, ix, n);\r
+ bx = ix;\r
+ }\r
+ //Now transfer the rest at the end of the container\r
+ this->splice(e, x);\r
+ }\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 time.\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.\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 first = begin();\r
+ iterator last = end();\r
+ while(first != last) {\r
+ iterator next = first;\r
+ ++next;\r
+ if(pred(*first)){\r
+ pointer p = first.operator->();\r
+ this->erase(first);\r
+ destroyer(p);\r
+ }\r
+ first = next;\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 pred 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 are equal 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_and_destroy(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 pred 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
+ if(!this->empty()) {\r
+ iterator first = begin();\r
+ iterator after = first;\r
+ ++after;\r
+ while(after != this->end()) {\r
+ if(pred(*first, *after)) {\r
+ pointer p = after.operator->();\r
+ after = erase(after);\r
+ destroyer(p);\r
+ }\r
+ else {\r
+ first = after++;\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
+\r
+template <class V, bool C, class S>\r
+inline bool operator==(const ilist<V, C, S>& x, const ilist<V, C, S>& y)\r
+{\r
+ if(C && x.size() != y.size()){\r
+ return false;\r
+ }\r
+ typedef typename ilist<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 ilist<V, C, S>& x,\r
+ const ilist<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 ilist<V, C, S>& x, const ilist<V, C, S>& y) \r
+{ return !(x == y); }\r
+\r
+template <class V, bool C, class S>\r
+inline bool operator>(const ilist<V, C, S>& x, const ilist<V, C, S>& y) \r
+{ return y < x; }\r
+\r
+template <class V, bool C, class S>\r
+inline bool operator<=(const ilist<V, C, S>& x, const ilist<V, C, S>& y) \r
+{ return !(y < x); }\r
+\r
+template <class V, bool C, class S>\r
+inline bool operator>=(const ilist<V, C, S>& x, const ilist<V, C, S>& y) \r
+{ return !(x < y); }\r
+\r
+template <class V, bool C, class S>\r
+inline void swap(ilist<V, C, S>& x, ilist<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_ILIST_HPP\r
projects / senf.git / blobdiff