diff options
Diffstat (limited to 'boost/intrusive/list.hpp')
| -rw-r--r-- | boost/intrusive/list.hpp | 520 |
1 files changed, 260 insertions, 260 deletions
diff --git a/boost/intrusive/list.hpp b/boost/intrusive/list.hpp index dbbf7c93f5..5450bc5d81 100644 --- a/boost/intrusive/list.hpp +++ b/boost/intrusive/list.hpp @@ -1,7 +1,7 @@ ///////////////////////////////////////////////////////////////////////////// // // (C) Copyright Olaf Krzikalla 2004-2006. -// (C) Copyright Ion Gaztanaga 2006-2009 +// (C) Copyright Ion Gaztanaga 2006-2012 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -59,7 +59,7 @@ struct list_defaults /// @endcond -//! The class template list is an intrusive container that mimics most of the +//! The class template list is an intrusive container that mimics most of the //! interface of std::list as described in the C++ standard. //! //! The template parameter \c T is the type to be managed by the container. @@ -118,12 +118,12 @@ class list_impl //noncopyable BOOST_MOVABLE_BUT_NOT_COPYABLE(list_impl) - enum { safemode_or_autounlink = + enum { safemode_or_autounlink = (int)real_value_traits::link_mode == (int)auto_unlink || (int)real_value_traits::link_mode == (int)safe_link }; //Constant-time size is incompatible with auto-unlink hooks! - BOOST_STATIC_ASSERT(!(constant_time_size && + BOOST_STATIC_ASSERT(!(constant_time_size && ((int)real_value_traits::link_mode == (int)auto_unlink) )); @@ -196,25 +196,25 @@ class list_impl real_value_traits &get_real_value_traits() { return this->get_real_value_traits(detail::bool_<external_value_traits>()); } - //! <b>Effects</b>: constructs an empty list. - //! - //! <b>Complexity</b>: Constant - //! + //! <b>Effects</b>: constructs an empty list. + //! + //! <b>Complexity</b>: Constant + //! //! <b>Throws</b>: If real_value_traits::node_traits::node //! constructor throws (this does not happen with predefined Boost.Intrusive hooks). list_impl(const value_traits &v_traits = value_traits()) : data_(v_traits) - { + { this->priv_size_traits().set_size(size_type(0)); - node_algorithms::init_header(this->get_root_node()); + node_algorithms::init_header(this->get_root_node()); } //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type. - //! + //! //! <b>Effects</b>: Constructs a list equal to the range [first,last). - //! - //! <b>Complexity</b>: Linear in std::distance(b, e). No copy constructors are called. - //! + //! + //! <b>Complexity</b>: Linear in std::distance(b, e). No copy constructors are called. + //! //! <b>Throws</b>: If real_value_traits::node_traits::node //! constructor throws (this does not happen with predefined Boost.Intrusive hooks). template<class Iterator> @@ -227,43 +227,43 @@ class list_impl } //! <b>Effects</b>: to-do - //! + //! list_impl(BOOST_RV_REF(list_impl) x) : data_(::boost::move(x.priv_value_traits())) { this->priv_size_traits().set_size(size_type(0)); - node_algorithms::init_header(this->get_root_node()); + node_algorithms::init_header(this->get_root_node()); this->swap(x); } //! <b>Effects</b>: to-do - //! - list_impl& operator=(BOOST_RV_REF(list_impl) x) + //! + list_impl& operator=(BOOST_RV_REF(list_impl) x) { this->swap(x); return *this; } - //! <b>Effects</b>: If it's not a safe-mode or an auto-unlink value_type + //! <b>Effects</b>: If it's not a safe-mode or an auto-unlink value_type //! the destructor does nothing - //! (ie. no code is generated). Otherwise it detaches all elements from this. - //! In this case the objects in the list are not deleted (i.e. no destructors + //! (ie. no code is generated). Otherwise it detaches all elements from this. + //! In this case the objects in the list are not deleted (i.e. no destructors //! are called), but the hooks according to the ValueTraits template parameter //! are set to their default value. - //! - //! <b>Complexity</b>: Linear to the number of elements in the list, if - //! it's a safe-mode or auto-unlink value . Otherwise constant. - ~list_impl() + //! + //! <b>Complexity</b>: Linear to the number of elements in the list, if + //! it's a safe-mode or auto-unlink value . Otherwise constant. + ~list_impl() {} //! <b>Requires</b>: value must be an lvalue. - //! + //! //! <b>Effects</b>: Inserts the value in the back of the list. //! No copy constructors are called. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - //! + //! //! <b>Note</b>: Does not affect the validity of iterators and references. - void push_back(reference value) + void push_back(reference value) { node_ptr to_insert = get_real_value_traits().to_node_ptr(value); if(safemode_or_autounlink) @@ -273,31 +273,31 @@ class list_impl } //! <b>Requires</b>: value must be an lvalue. - //! + //! //! <b>Effects</b>: Inserts the value in the front of the list. //! No copy constructors are called. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - //! + //! //! <b>Note</b>: Does not affect the validity of iterators and references. - void push_front(reference value) + void push_front(reference value) { node_ptr to_insert = get_real_value_traits().to_node_ptr(value); if(safemode_or_autounlink) BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::inited(to_insert)); - node_algorithms::link_before(node_traits::get_next(this->get_root_node()), to_insert); + node_algorithms::link_before(node_traits::get_next(this->get_root_node()), to_insert); this->priv_size_traits().increment(); } //! <b>Effects</b>: Erases the last element of the list. //! No destructors are called. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - //! + //! //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased element. void pop_back() { return this->pop_back_and_dispose(detail::null_disposer()); } @@ -307,11 +307,11 @@ class list_impl //! <b>Effects</b>: Erases the last element of the list. //! No destructors are called. //! Disposer::operator()(pointer) is called for the removed element. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - //! + //! //! <b>Note</b>: Invalidates the iterators to the erased element. template<class Disposer> void pop_back_and_dispose(Disposer disposer) @@ -326,11 +326,11 @@ class list_impl //! <b>Effects</b>: Erases the first element of the list. //! No destructors are called. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - //! + //! //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased element. void pop_front() { return this->pop_front_and_dispose(detail::null_disposer()); } @@ -340,15 +340,15 @@ class list_impl //! <b>Effects</b>: Erases the first element of the list. //! No destructors are called. //! Disposer::operator()(pointer) is called for the removed element. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - //! + //! //! <b>Note</b>: Invalidates the iterators to the erased element. template<class Disposer> void pop_front_and_dispose(Disposer disposer) - { + { node_ptr to_erase = node_traits::get_next(this->get_root_node()); node_algorithms::unlink(to_erase); this->priv_size_traits().decrement(); @@ -358,197 +358,197 @@ class list_impl } //! <b>Effects</b>: Returns a reference to the first element of the list. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - reference front() + reference front() { return *get_real_value_traits().to_value_ptr(node_traits::get_next(this->get_root_node())); } //! <b>Effects</b>: Returns a const_reference to the first element of the list. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_reference front() const + const_reference front() const { return *get_real_value_traits().to_value_ptr(uncast(node_traits::get_next(this->get_root_node()))); } //! <b>Effects</b>: Returns a reference to the last element of the list. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - reference back() + reference back() { return *get_real_value_traits().to_value_ptr(node_traits::get_previous(this->get_root_node())); } //! <b>Effects</b>: Returns a const_reference to the last element of the list. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_reference back() const + const_reference back() const { return *get_real_value_traits().to_value_ptr(uncast(node_traits::get_previous(this->get_root_node()))); } //! <b>Effects</b>: Returns an iterator to the first element contained in the list. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - iterator begin() + iterator begin() { return iterator(node_traits::get_next(this->get_root_node()), this); } //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_iterator begin() const + const_iterator begin() const { return this->cbegin(); } //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_iterator cbegin() const + const_iterator cbegin() const { return const_iterator(node_traits::get_next(this->get_root_node()), this); } //! <b>Effects</b>: Returns an iterator to the end of the list. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - iterator end() + iterator end() { return iterator(this->get_root_node(), this); } //! <b>Effects</b>: Returns a const_iterator to the end of the list. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_iterator end() const + const_iterator end() const { return this->cend(); } //! <b>Effects</b>: Returns a constant iterator to the end of the list. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. const_iterator cend() const { return const_iterator(uncast(this->get_root_node()), this); } - //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning - //! of the reversed list. - //! + //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning + //! of the reversed list. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. reverse_iterator rbegin() { return reverse_iterator(this->end()); } - //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning - //! of the reversed list. - //! + //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning + //! of the reversed list. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_reverse_iterator rbegin() const + const_reverse_iterator rbegin() const { return this->crbegin(); } - //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning - //! of the reversed list. - //! + //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning + //! of the reversed list. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_reverse_iterator crbegin() const + const_reverse_iterator crbegin() const { return const_reverse_iterator(end()); } //! <b>Effects</b>: Returns a reverse_iterator pointing to the end - //! of the reversed list. - //! + //! of the reversed list. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - reverse_iterator rend() + reverse_iterator rend() { return reverse_iterator(begin()); } //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end - //! of the reversed list. - //! + //! of the reversed list. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_reverse_iterator rend() const + const_reverse_iterator rend() const { return this->crend(); } //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end - //! of the reversed list. - //! + //! of the reversed list. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - const_reverse_iterator crend() const + const_reverse_iterator crend() const { return const_reverse_iterator(this->begin()); } //! <b>Precondition</b>: end_iterator must be a valid end iterator //! of list. - //! + //! //! <b>Effects</b>: Returns a const reference to the list associated to the end iterator - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. static list_impl &container_from_end_iterator(iterator end_iterator) { return list_impl::priv_container_from_end_iterator(end_iterator); } //! <b>Precondition</b>: end_iterator must be a valid end const_iterator //! of list. - //! + //! //! <b>Effects</b>: Returns a const reference to the list associated to the end iterator - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. static const list_impl &container_from_end_iterator(const_iterator end_iterator) { return list_impl::priv_container_from_end_iterator(end_iterator); } //! <b>Effects</b>: Returns the number of the elements contained in the list. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Linear to the number of elements contained in the list. //! if constant-time size option is disabled. Constant time otherwise. - //! + //! //! <b>Note</b>: Does not affect the validity of iterators and references. size_type size() const { if(constant_time_size) return this->priv_size_traits().get_size(); else - return node_algorithms::count(this->get_root_node()) - 1; + return node_algorithms::count(this->get_root_node()) - 1; } //! <b>Effects</b>: Returns true if the list contains no elements. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - //! + //! //! <b>Note</b>: Does not affect the validity of iterators and references. bool empty() const { return node_algorithms::unique(this->get_root_node()); } //! <b>Effects</b>: Swaps the elements of x and *this. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - //! + //! //! <b>Note</b>: Does not affect the validity of iterators and references. void swap(list_impl& other) { - node_algorithms::swap_nodes(this->get_root_node(), other.get_root_node()); + node_algorithms::swap_nodes(this->get_root_node(), other.get_root_node()); if(constant_time_size){ size_type backup = this->priv_size_traits().get_size(); this->priv_size_traits().set_size(other.priv_size_traits().get_size()); @@ -559,11 +559,11 @@ class list_impl //! <b>Effects</b>: Moves backwards all the elements, so that the first //! element becomes the second, the second becomes the third... //! the last element becomes the first one. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Linear to the number of shifts. - //! + //! //! <b>Note</b>: Does not affect the validity of iterators and references. void shift_backwards(size_type n = 1) { node_algorithms::move_forward(this->get_root_node(), n); } @@ -571,11 +571,11 @@ class list_impl //! <b>Effects</b>: Moves forward all the elements, so that the second //! element becomes the first, the third becomes the second... //! the first element becomes the last one. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Linear to the number of shifts. - //! + //! //! <b>Note</b>: Does not affect the validity of iterators and references. void shift_forward(size_type n = 1) { node_algorithms::move_backwards(this->get_root_node(), n); } @@ -587,9 +587,9 @@ class list_impl //! or end() if no such element exists. //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - //! + //! //! <b>Note</b>: Invalidates the iterators (but not the references) to the //! erased element. iterator erase(const_iterator i) @@ -602,13 +602,13 @@ class list_impl //! //! <b>Returns</b>: the first element remaining beyond the removed elements, //! or end() if no such element exists. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Linear to the number of erased elements if it's a safe-mode //! or auto-unlink value, or constant-time size is enabled. Constant-time otherwise. - //! - //! <b>Note</b>: Invalidates the iterators (but not the references) to the + //! + //! <b>Note</b>: Invalidates the iterators (but not the references) to the //! erased elements. iterator erase(const_iterator b, const_iterator e) { @@ -629,13 +629,13 @@ class list_impl //! //! <b>Returns</b>: the first element remaining beyond the removed elements, //! or end() if no such element exists. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Linear to the number of erased elements if it's a safe-mode //! or auto-unlink value is enabled. Constant-time otherwise. - //! - //! <b>Note</b>: Invalidates the iterators (but not the references) to the + //! + //! <b>Note</b>: Invalidates the iterators (but not the references) to the //! erased elements. iterator erase(const_iterator b, const_iterator e, difference_type n) { @@ -662,9 +662,9 @@ class list_impl //! or end() if no such element exists. //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - //! + //! //! <b>Note</b>: Invalidates the iterators to the erased element. template <class Disposer> iterator erase_and_dispose(const_iterator i, Disposer disposer) @@ -693,11 +693,11 @@ class list_impl //! //! <b>Returns</b>: the first element remaining beyond the removed elements, //! or end() if no such element exists. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Linear to the number of elements erased. - //! + //! //! <b>Note</b>: Invalidates the iterators to the erased elements. template <class Disposer> iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) @@ -717,17 +717,17 @@ class list_impl //! <b>Effects</b>: Erases all the elements of the container. //! No destructors are called. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Linear to the number of elements of the list. //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise. - //! + //! //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased elements. void clear() { if(safemode_or_autounlink){ - this->clear_and_dispose(detail::null_disposer()); + this->clear_and_dispose(detail::null_disposer()); } else{ node_algorithms::init_header(this->get_root_node()); @@ -740,11 +740,11 @@ class list_impl //! <b>Effects</b>: Erases all the elements of the container. //! No destructors are called. //! Disposer::operator()(pointer) is called for the removed elements. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Linear to the number of elements of the list. - //! + //! //! <b>Note</b>: Invalidates the iterators to the erased elements. template <class Disposer> void clear_and_dispose(Disposer disposer) @@ -765,15 +765,15 @@ class list_impl //! Cloner should yield to nodes equivalent to the original nodes. //! //! <b>Effects</b>: Erases all the elements from *this - //! calling Disposer::operator()(pointer), clones all the + //! calling Disposer::operator()(pointer), clones all the //! elements from src calling Cloner::operator()(const_reference ) //! and inserts them on *this. //! //! If cloner throws, all cloned elements are unlinked and disposed //! calling Disposer::operator()(pointer). - //! + //! //! <b>Complexity</b>: Linear to erased plus inserted elements. - //! + //! //! <b>Throws</b>: If cloner throws. Basic guarantee. template <class Cloner, class Disposer> void clone_from(const list_impl &src, Cloner cloner, Disposer disposer) @@ -793,11 +793,11 @@ class list_impl //! <b>Effects</b>: Inserts the value before the position pointed by p. //! //! <b>Returns</b>: An iterator to the inserted element. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant time. No copy constructors are called. - //! + //! //! <b>Note</b>: Does not affect the validity of iterators and references. iterator insert(const_iterator p, reference value) { @@ -809,16 +809,16 @@ class list_impl return iterator(to_insert, this); } - //! <b>Requires</b>: Dereferencing iterator must yield + //! <b>Requires</b>: Dereferencing iterator must yield //! an lvalue of type value_type and p must be a valid iterator of *this. - //! + //! //! <b>Effects</b>: Inserts the range pointed by b and e before the position p. //! No copy constructors are called. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Linear to the number of elements inserted. - //! + //! //! <b>Note</b>: Does not affect the validity of iterators and references. template<class Iterator> void insert(const_iterator p, Iterator b, Iterator e) @@ -827,19 +827,19 @@ class list_impl this->insert(p, *b); } - //! <b>Requires</b>: Dereferencing iterator must yield + //! <b>Requires</b>: Dereferencing iterator must yield //! an lvalue of type value_type. - //! + //! //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e. //! No destructors or copy constructors are called. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Linear to the number of elements inserted plus //! linear to the elements contained in the list if it's a safe-mode //! or auto-unlink value. //! Linear to the number of elements inserted in the list otherwise. - //! + //! //! <b>Note</b>: Invalidates the iterators (but not the references) //! to the erased elements. template<class Iterator> @@ -851,18 +851,18 @@ class list_impl //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. //! - //! <b>Requires</b>: Dereferencing iterator must yield + //! <b>Requires</b>: Dereferencing iterator must yield //! an lvalue of type value_type. - //! + //! //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e. //! No destructors or copy constructors are called. //! Disposer::operator()(pointer) is called for the removed elements. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Linear to the number of elements inserted plus //! linear to the elements contained in the list. - //! + //! //! <b>Note</b>: Invalidates the iterators (but not the references) //! to the erased elements. template<class Iterator, class Disposer> @@ -880,7 +880,7 @@ class list_impl //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - //! + //! //! <b>Note</b>: Iterators of values obtained from list x now point to elements of //! this list. Iterators of this list and all the references are not invalidated. void splice(const_iterator p, list_impl& x) @@ -897,15 +897,15 @@ class list_impl //! <b>Requires</b>: p must be a valid iterator of *this. //! new_ele must point to an element contained in list x. - //! - //! <b>Effects</b>: Transfers the value pointed by new_ele, from list x to this list, + //! + //! <b>Effects</b>: Transfers the value pointed by new_ele, from list x to this list, //! before the the element pointed by p. No destructors or copy constructors are called. - //! If p == new_ele or p == ++new_ele, this function is a null operation. - //! + //! If p == new_ele or p == ++new_ele, this function is a null operation. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - //! + //! //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this //! list. Iterators of this list and all the references are not invalidated. void splice(const_iterator p, list_impl&x, const_iterator new_ele) @@ -917,15 +917,15 @@ class list_impl //! <b>Requires</b>: p must be a valid iterator of *this. //! start and end must point to elements contained in list x. - //! - //! <b>Effects</b>: Transfers the range pointed by start and end from list x to this list, + //! + //! <b>Effects</b>: Transfers the range pointed by start and end from list x to this list, //! before the the element pointed by p. No destructors or copy constructors are called. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Linear to the number of elements transferred //! if constant-time size option is enabled. Constant-time otherwise. - //! + //! //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this //! list. Iterators of this list and all the references are not invalidated. void splice(const_iterator p, list_impl&x, const_iterator start, const_iterator end) @@ -939,14 +939,14 @@ class list_impl //! <b>Requires</b>: p must be a valid iterator of *this. //! start and end must point to elements contained in list x. //! n == std::distance(start, end) - //! - //! <b>Effects</b>: Transfers the range pointed by start and end from list x to this list, + //! + //! <b>Effects</b>: Transfers the range pointed by start and end from list x to this list, //! before the the element pointed by p. No destructors or copy constructors are called. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant. - //! + //! //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this //! list. Iterators of this list and all the references are not invalidated. void splice(const_iterator p, list_impl&x, const_iterator start, const_iterator end, difference_type n) @@ -966,25 +966,25 @@ class list_impl } } - //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. + //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. //! The sort is stable, that is, the relative order of equivalent elements is preserved. - //! + //! //! <b>Throws</b>: If real_value_traits::node_traits::node //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) //! or std::less<value_type> throws. Basic guarantee. //! //! <b>Notes</b>: Iterators and references are not invalidated. - //! + //! //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N //! is the list's size. - void sort() + void sort() { this->sort(std::less<value_type>()); } //! <b>Requires</b>: p must be a comparison function that induces a strict weak ordering - //! - //! <b>Effects</b>: This function sorts the list *this according to p. The sort is + //! + //! <b>Effects</b>: This function sorts the list *this according to p. The sort is //! stable, that is, the relative order of equivalent elements is preserved. - //! + //! //! <b>Throws</b>: If real_value_traits::node_traits::node //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) //! or the predicate throws. Basic guarantee. @@ -992,13 +992,13 @@ class list_impl //! <b>Notes</b>: This won't throw if list_base_hook<> or //! list_member_hook are used. //! Iterators and references are not invalidated. - //! + //! //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N //! is the list's size. template<class Predicate> void sort(Predicate p) { - if(node_traits::get_next(this->get_root_node()) + if(node_traits::get_next(this->get_root_node()) != node_traits::get_previous(this->get_root_node())){ list_impl carry(this->priv_value_traits()); detail::array_initializer<list_impl, 64> counter(this->priv_value_traits()); @@ -1021,32 +1021,32 @@ class list_impl } //! <b>Effects</b>: This function removes all of x's elements and inserts them - //! in order into *this according to std::less<value_type>. The merge is stable; - //! that is, if an element from *this is equivalent to one from x, then the element - //! from *this will precede the one from x. - //! + //! in order into *this according to std::less<value_type>. The merge is stable; + //! that is, if an element from *this is equivalent to one from x, then the element + //! from *this will precede the one from x. + //! //! <b>Throws</b>: If std::less<value_type> throws. Basic guarantee. - //! + //! //! <b>Complexity</b>: This function is linear time: it performs at most //! size() + x.size() - 1 comparisons. - //! + //! //! <b>Note</b>: Iterators and references are not invalidated void merge(list_impl& x) { this->merge(x, std::less<value_type>()); } //! <b>Requires</b>: p must be a comparison function that induces a strict weak //! ordering and both *this and x must be sorted according to that ordering - //! The lists x and *this must be distinct. - //! + //! The lists x and *this must be distinct. + //! //! <b>Effects</b>: This function removes all of x's elements and inserts them - //! in order into *this. The merge is stable; that is, if an element from *this is - //! equivalent to one from x, then the element from *this will precede the one from x. - //! + //! in order into *this. The merge is stable; that is, if an element from *this is + //! equivalent to one from x, then the element from *this will precede the one from x. + //! //! <b>Throws</b>: If the predicate throws. Basic guarantee. - //! + //! //! <b>Complexity</b>: This function is linear time: it performs at most //! size() + x.size() - 1 comparisons. - //! + //! //! <b>Note</b>: Iterators and references are not invalidated. template<class Predicate> void merge(list_impl& x, Predicate p) @@ -1073,23 +1073,23 @@ class list_impl } } - //! <b>Effects</b>: Reverses the order of elements in the list. - //! + //! <b>Effects</b>: Reverses the order of elements in the list. + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: This function is linear time. - //! + //! //! <b>Note</b>: Iterators and references are not invalidated void reverse() { node_algorithms::reverse(this->get_root_node()); } //! <b>Effects</b>: Removes all the elements that compare equal to value. //! No destructors are called. - //! + //! //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee. - //! + //! //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality. - //! + //! //! <b>Note</b>: The relative order of elements that are not removed is unchanged, //! and iterators to elements that are not removed remain valid. void remove(const_reference value) @@ -1101,9 +1101,9 @@ class list_impl //! Disposer::operator()(pointer) is called for every removed element. //! //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee. - //! + //! //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality. - //! + //! //! <b>Note</b>: The relative order of elements that are not removed is unchanged, //! and iterators to elements that are not removed remain valid. template<class Disposer> @@ -1112,11 +1112,11 @@ class list_impl //! <b>Effects</b>: Removes all the elements for which a specified //! predicate is satisfied. No destructors are called. - //! + //! //! <b>Throws</b>: If pred throws. Basic guarantee. - //! + //! //! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate. - //! + //! //! <b>Note</b>: The relative order of elements that are not removed is unchanged, //! and iterators to elements that are not removed remain valid. template<class Pred> @@ -1130,7 +1130,7 @@ class list_impl //! Disposer::operator()(pointer) is called for every removed element. //! //! <b>Throws</b>: If pred throws. Basic guarantee. - //! + //! //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality. //! //! <b>Note</b>: The relative order of elements that are not removed is unchanged, @@ -1150,26 +1150,26 @@ class list_impl } } - //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent + //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent //! elements that are equal from the list. No destructors are called. - //! + //! //! <b>Throws</b>: If std::equal_to<value_type throws. Basic guarantee. - //! + //! //! <b>Complexity</b>: Linear time (size()-1 comparisons calls to pred()). - //! + //! //! <b>Note</b>: The relative order of elements that are not removed is unchanged, //! and iterators to elements that are not removed remain valid. void unique() { this->unique_and_dispose(std::equal_to<value_type>(), detail::null_disposer()); } - //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent + //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent //! elements that satisfy some binary predicate from the list. //! No destructors are called. - //! + //! //! <b>Throws</b>: If pred throws. Basic guarantee. - //! + //! //! <b>Complexity</b>: Linear time (size()-1 comparisons equality comparisons). - //! + //! //! <b>Note</b>: The relative order of elements that are not removed is unchanged, //! and iterators to elements that are not removed remain valid. template<class BinaryPredicate> @@ -1178,14 +1178,14 @@ class list_impl //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. //! - //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent + //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent //! elements that are equal from the list. //! Disposer::operator()(pointer) is called for every removed element. - //! + //! //! <b>Throws</b>: If std::equal_to<value_type throws. Basic guarantee. - //! + //! //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons. - //! + //! //! <b>Note</b>: The relative order of elements that are not removed is unchanged, //! and iterators to elements that are not removed remain valid. template<class Disposer> @@ -1194,14 +1194,14 @@ class list_impl //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. //! - //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent + //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent //! elements that satisfy some binary predicate from the list. //! Disposer::operator()(pointer) is called for every removed element. - //! + //! //! <b>Throws</b>: If pred throws. Basic guarantee. - //! + //! //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons. - //! + //! //! <b>Note</b>: The relative order of elements that are not removed is unchanged, //! and iterators to elements that are not removed remain valid. template<class BinaryPredicate, class Disposer> @@ -1226,13 +1226,13 @@ class list_impl } //! <b>Requires</b>: value must be a reference to a value inserted in a list. - //! + //! //! <b>Effects</b>: This function returns a const_iterator pointing to the element - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant time. - //! + //! //! <b>Note</b>: Iterators and references are not invalidated. //! This static function is available only if the <i>value traits</i> //! is stateless. @@ -1244,17 +1244,17 @@ class list_impl } //! <b>Requires</b>: value must be a const reference to a value inserted in a list. - //! + //! //! <b>Effects</b>: This function returns an iterator pointing to the element. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant time. - //! + //! //! <b>Note</b>: Iterators and references are not invalidated. //! This static function is available only if the <i>value traits</i> //! is stateless. - static const_iterator s_iterator_to(const_reference value) + static const_iterator s_iterator_to(const_reference value) { BOOST_STATIC_ASSERT((!stateful_value_traits)); BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(real_value_traits::to_node_ptr(const_cast<reference> (value)))); @@ -1262,13 +1262,13 @@ class list_impl } //! <b>Requires</b>: value must be a reference to a value inserted in a list. - //! + //! //! <b>Effects</b>: This function returns a const_iterator pointing to the element - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant time. - //! + //! //! <b>Note</b>: Iterators and references are not invalidated. iterator iterator_to(reference value) { @@ -1277,13 +1277,13 @@ class list_impl } //! <b>Requires</b>: value must be a const reference to a value inserted in a list. - //! + //! //! <b>Effects</b>: This function returns an iterator pointing to the element. - //! + //! //! <b>Throws</b>: Nothing. - //! + //! //! <b>Complexity</b>: Constant time. - //! + //! //! <b>Note</b>: Iterators and references are not invalidated. const_iterator iterator_to(const_reference value) const { @@ -1434,7 +1434,7 @@ struct make_list { /// @cond typedef typename pack_options - < list_defaults<T>, + < list_defaults<T>, #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) O1, O2, O3 #else @@ -1466,7 +1466,7 @@ template<class T, class O1, class O2, class O3> template<class T, class ...Options> #endif class list - : public make_list<T, + : public make_list<T, #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) O1, O2, O3 #else @@ -1475,7 +1475,7 @@ class list >::type { typedef typename make_list - <T, + <T, #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) O1, O2, O3 #else @@ -1517,8 +1517,8 @@ class list #endif -} //namespace intrusive -} //namespace boost +} //namespace intrusive +} //namespace boost #include <boost/intrusive/detail/config_end.hpp> |