...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
boost::intrusive::slist
// In header: <boost/intrusive/slist.hpp> template<typename T, class... Options> class slist { public: // types typedef Config::value_traits value_traits; typedef real_value_traits::pointer pointer; typedef real_value_traits::const_pointer const_pointer; typedef std::iterator_traits< pointer >::value_type value_type; typedef std::iterator_traits< pointer >::reference reference; typedef std::iterator_traits< const_pointer >::reference const_reference; typedef std::iterator_traits< pointer >::difference_type difference_type; typedef Config::size_type size_type; typedef slist_iterator< slist, false > iterator; typedef slist_iterator< slist, true > const_iterator; typedef real_value_traits::node_traits node_traits; typedef node_traits::node node; typedef node_traits::node_ptr node_ptr; typedef node_traits::const_node_ptr const_node_ptr; typedef unspecified node_algorithms; // construct/copy/destruct slist(const value_traits & = value_traits()); template<typename Iterator> slist(Iterator, Iterator, const value_traits & = value_traits()); slist(BOOST_RV_REF(slist)); slist& operator=(BOOST_RV_REF(slist)); ~slist(); // public member functions const real_value_traits & get_real_value_traits() const; real_value_traits & get_real_value_traits(); void clear(); template<typename Disposer> void clear_and_dispose(Disposer); void push_front(reference); void push_back(reference); void pop_front(); template<typename Disposer> void pop_front_and_dispose(Disposer); reference front(); const_reference front() const; reference back(); const_reference back() const; iterator begin(); const_iterator begin() const; const_iterator cbegin() const; iterator end(); const_iterator end() const; const_iterator cend() const; iterator before_begin(); const_iterator before_begin() const; const_iterator cbefore_begin() const; iterator last(); const_iterator last() const; const_iterator clast() const; size_type size() const; bool empty() const; void swap(slist &); void shift_backwards(size_type = 1); void shift_forward(size_type = 1); template<typename Cloner, typename Disposer> void clone_from(const slist &, Cloner, Disposer); iterator insert_after(const_iterator, reference); template<typename Iterator> void insert_after(const_iterator, Iterator, Iterator); iterator insert(const_iterator, reference); template<typename Iterator> void insert(const_iterator, Iterator, Iterator); iterator erase_after(const_iterator); iterator erase_after(const_iterator, const_iterator); iterator erase_after(const_iterator, const_iterator, difference_type); iterator erase(const_iterator); iterator erase(const_iterator, const_iterator); iterator erase(const_iterator, const_iterator, difference_type); template<typename Disposer> iterator erase_after_and_dispose(const_iterator, Disposer); template<typename Disposer> iterator erase_after_and_dispose(const_iterator, const_iterator, Disposer); template<typename Disposer> iterator erase_and_dispose(const_iterator, Disposer); template<typename Disposer> iterator erase_and_dispose(const_iterator, const_iterator, Disposer); template<typename Iterator> void assign(Iterator, Iterator); template<typename Iterator, typename Disposer> void dispose_and_assign(Disposer, Iterator, Iterator); void splice_after(const_iterator, slist &, const_iterator * = 0); void splice_after(const_iterator, slist &, const_iterator); void splice_after(const_iterator, slist &, const_iterator, const_iterator); void splice_after(const_iterator, slist &, const_iterator, const_iterator, difference_type); void splice(const_iterator, slist &, const_iterator * = 0); void splice(const_iterator, slist &, const_iterator); void splice(const_iterator, slist &, const_iterator, const_iterator); void splice(const_iterator, slist &, const_iterator, const_iterator, difference_type); template<typename Predicate> void sort(Predicate); void sort(); template<typename Predicate> void merge(slist &, Predicate, const_iterator * = 0); void merge(slist &); void reverse(); void remove(const_reference); template<typename Disposer> void remove_and_dispose(const_reference, Disposer); template<typename Pred> void remove_if(Pred); template<typename Pred, typename Disposer> void remove_and_dispose_if(Pred, Disposer); void unique(); template<typename BinaryPredicate> void unique(BinaryPredicate); template<typename Disposer> void unique_and_dispose(Disposer); template<typename BinaryPredicate, typename Disposer> void unique_and_dispose(BinaryPredicate, Disposer); iterator iterator_to(reference); const_iterator iterator_to(const_reference) const; iterator previous(iterator); const_iterator previous(const_iterator) const; iterator previous(const_iterator, iterator); const_iterator previous(const_iterator, const_iterator) const; void incorporate_after(const_iterator, node_ptr, node_ptr); void incorporate_after(const_iterator, node_ptr, node_ptr, difference_type); // public static functions static slist & container_from_end_iterator(iterator); static const slist & container_from_end_iterator(const_iterator); static iterator s_iterator_to(reference); static const_iterator s_iterator_to(const_reference); // private member functions void priv_splice_after(node_ptr, slist &, node_ptr, node_ptr); void priv_incorporate_after(node_ptr, node_ptr, node_ptr); void priv_reverse(unspecified); void priv_reverse(unspecified); void priv_shift_backwards(size_type, unspecified); void priv_shift_backwards(size_type, unspecified); void priv_shift_forward(size_type, unspecified); void priv_shift_forward(size_type, unspecified); // private static functions static void priv_swap_cache_last(slist *, slist *); static void priv_swap_lists(node_ptr, node_ptr, unspecified); static void priv_swap_lists(node_ptr, node_ptr, unspecified); static slist & priv_container_from_end_iterator(const const_iterator &); // public data members static const bool constant_time_size; static const bool stateful_value_traits; static const bool linear; static const bool cache_last; };
The class template slist is an intrusive container, that encapsulates a singly-linked list. You can use such a list to squeeze the last bit of performance from your application. Unfortunately, the little gains come with some huge drawbacks. A lot of member functions can't be implemented as efficiently as for standard containers. To overcome this limitation some other member functions with rather unusual semantics have to be introduced.
The template parameter T
is the type to be managed by the container. The user can specify additional options and if no options are provided default options are used.
The container supports the following options: base_hook<>/member_hook<>/value_traits<>
, constant_time_size<>
, size_type<>
, linear<>
and cache_last<>
.
The iterators of slist are forward iterators. slist provides a static function called "previous" to compute the previous iterator of a given iterator. This function has linear complexity. To improve the usability esp. with the '*_after' functions, ++end() == begin() and previous(begin()) == end() are defined. An new special function "before_begin()" is defined, which returns an iterator that points one less the beginning of the list: ++before_begin() == begin()
slist
public
construct/copy/destructslist(const value_traits & v_traits = value_traits());
Effects: constructs an empty list.
Complexity: Constant
Throws: If value_traits::node_traits::node constructor throws (this does not happen with predefined Boost.Intrusive hooks).
template<typename Iterator> slist(Iterator b, Iterator e, const value_traits & v_traits = value_traits());
Requires: Dereferencing iterator must yield an lvalue of type value_type.
Effects: Constructs a list equal to [first,last).
Complexity: Linear in std::distance(b, e). No copy constructors are called.
Throws: If value_traits::node_traits::node constructor throws (this does not happen with predefined Boost.Intrusive hooks).
slist(BOOST_RV_REF(slist) x);
Effects: to-do
slist& operator=(BOOST_RV_REF(slist) x);
Effects: to-do
~slist();
Effects: If it's a safe-mode or auto-unlink value, 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 are called), but the hooks according to the value_traits
template parameter are set to their default value.
Complexity: Linear to the number of elements in the list, if it's a safe-mode or auto-unlink value. Otherwise constant.
slist
public member functionsconst real_value_traits & get_real_value_traits() const;
real_value_traits & get_real_value_traits();
void clear();
Effects: Erases all the elements of the container.
Throws: Nothing.
Complexity: Linear to the number of elements of the list. if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
Note: Invalidates the iterators (but not the references) to the erased elements.
template<typename Disposer> void clear_and_dispose(Disposer disposer);
Requires: Disposer::operator()(pointer) shouldn't throw.
Effects: Erases all the elements of the container Disposer::operator()(pointer) is called for the removed elements.
Throws: Nothing.
Complexity: Linear to the number of elements of the list.
Note: Invalidates the iterators to the erased elements.
void push_front(reference value);
Requires: value must be an lvalue.
Effects: Inserts the value in the front of the list. No copy constructors are called.
Throws: Nothing.
Complexity: Constant.
Note: Does not affect the validity of iterators and references.
void push_back(reference value);
Requires: value must be an lvalue.
Effects: Inserts the value in the back of the list. No copy constructors are called.
Throws: Nothing.
Complexity: Constant.
Note: Does not affect the validity of iterators and references. This function is only available is cache_last<> is true.
void pop_front();
Effects: Erases the first element of the list. No destructors are called.
Throws: Nothing.
Complexity: Constant.
Note: Invalidates the iterators (but not the references) to the erased element.
template<typename Disposer> void pop_front_and_dispose(Disposer disposer);
Requires: Disposer::operator()(pointer) shouldn't throw.
Effects: Erases the first element of the list. Disposer::operator()(pointer) is called for the removed element.
Throws: Nothing.
Complexity: Constant.
Note: Invalidates the iterators to the erased element.
reference front();
Effects: Returns a reference to the first element of the list.
Throws: Nothing.
Complexity: Constant.
const_reference front() const;
Effects: Returns a const_reference to the first element of the list.
Throws: Nothing.
Complexity: Constant.
reference back();
Effects: Returns a reference to the last element of the list.
Throws: Nothing.
Complexity: Constant.
Note: Does not affect the validity of iterators and references. This function is only available is cache_last<> is true.
const_reference back() const;
Effects: Returns a const_reference to the last element of the list.
Throws: Nothing.
Complexity: Constant.
Note: Does not affect the validity of iterators and references. This function is only available is cache_last<> is true.
iterator begin();
Effects: Returns an iterator to the first element contained in the list.
Throws: Nothing.
Complexity: Constant.
const_iterator begin() const;
Effects: Returns a const_iterator to the first element contained in the list.
Throws: Nothing.
Complexity: Constant.
const_iterator cbegin() const;
Effects: Returns a const_iterator to the first element contained in the list.
Throws: Nothing.
Complexity: Constant.
iterator end();
Effects: Returns an iterator to the end of the list.
Throws: Nothing.
Complexity: Constant.
const_iterator end() const;
Effects: Returns a const_iterator to the end of the list.
Throws: Nothing.
Complexity: Constant.
const_iterator cend() const;
Effects: Returns a const_iterator to the end of the list.
Throws: Nothing.
Complexity: Constant.
iterator before_begin();
Effects: Returns an iterator that points to a position before the first element. Equivalent to "end()"
Throws: Nothing.
Complexity: Constant.
const_iterator before_begin() const;
Effects: Returns an iterator that points to a position before the first element. Equivalent to "end()"
Throws: Nothing.
Complexity: Constant.
const_iterator cbefore_begin() const;
Effects: Returns an iterator that points to a position before the first element. Equivalent to "end()"
Throws: Nothing.
Complexity: Constant.
iterator last();
Effects: Returns an iterator to the last element contained in the list.
Throws: Nothing.
Complexity: Constant.
Note: This function is present only if cached_last<> option is true.
const_iterator last() const;
Effects: Returns a const_iterator to the first element contained in the list.
Throws: Nothing.
Complexity: Constant.
Note: This function is present only if cached_last<> option is true.
const_iterator clast() const;
Effects: Returns a const_iterator to the first element contained in the list.
Throws: Nothing.
Complexity: Constant.
Note: This function is present only if cached_last<> option is true.
size_type size() const;
Effects: Returns the number of the elements contained in the list.
Throws: Nothing.
Complexity: Linear to the number of elements contained in the list. if constant_time_size
is false. Constant time otherwise.
Note: Does not affect the validity of iterators and references.
bool empty() const;
Effects: Returns true if the list contains no elements.
Throws: Nothing.
Complexity: Constant.
Note: Does not affect the validity of iterators and references.
void swap(slist & other);
Effects: Swaps the elements of x and *this.
Throws: Nothing.
Complexity: Linear to the number of elements of both lists. Constant-time if linear<> and/or cache_last<> options are used.
Note: Does not affect the validity of iterators and references.
void shift_backwards(size_type n = 1);
Effects: 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.
Throws: Nothing.
Complexity: Linear to the number of elements plus the number shifts.
Note: Iterators Does not affect the validity of iterators and references.
void shift_forward(size_type n = 1);
Effects: 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.
Throws: Nothing.
Complexity: Linear to the number of elements plus the number shifts.
Note: Does not affect the validity of iterators and references.
template<typename Cloner, typename Disposer> void clone_from(const slist & src, Cloner cloner, Disposer disposer);
Requires: Disposer::operator()(pointer) shouldn't throw. Cloner should yield to nodes equivalent to the original nodes.
Effects: Erases all the elements from *this 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).
Complexity: Linear to erased plus inserted elements.
Throws: If cloner throws.
iterator insert_after(const_iterator prev_p, reference value);
Requires: value must be an lvalue and prev_p must point to an element contained by the list or to end().
Effects: Inserts the value after the position pointed by prev_p. No copy constructor is called.
Returns: An iterator to the inserted element.
Throws: Nothing.
Complexity: Constant.
Note: Does not affect the validity of iterators and references.
template<typename Iterator> void insert_after(const_iterator prev_p, Iterator first, Iterator last);
Requires: Dereferencing iterator must yield an lvalue of type value_type and prev_p must point to an element contained by the list or to the end node.
Effects: Inserts the [first, last) after the position prev_p.
Throws: Nothing.
Complexity: Linear to the number of elements inserted.
Note: Does not affect the validity of iterators and references.
iterator insert(const_iterator p, reference value);
Requires: value must be an lvalue and p must point to an element contained by the list or to end().
Effects: Inserts the value before the position pointed by p. No copy constructor is called.
Throws: Nothing.
Complexity: Linear to the number of elements before p. Constant-time if cache_last<> is true and p == end().
Note: Does not affect the validity of iterators and references.
template<typename Iterator> void insert(const_iterator p, Iterator b, Iterator e);
Requires: Dereferencing iterator must yield an lvalue of type value_type and p must point to an element contained by the list or to the end node.
Effects: Inserts the pointed by b and e before the position p. No copy constructors are called.
Throws: Nothing.
Complexity: Linear to the number of elements inserted plus linear to the elements before b. Linear to the number of elements to insert if cache_last<> option is true and p == end().
Note: Does not affect the validity of iterators and references.
iterator erase_after(const_iterator prev);
Effects: Erases the element after the element pointed by prev of the list. No destructors are called.
Returns: the first element remaining beyond the removed elements, or end() if no such element exists.
Throws: Nothing.
Complexity: Constant.
Note: Invalidates the iterators (but not the references) to the erased element.
iterator erase_after(const_iterator before_first, const_iterator last);
Effects: Erases the range (before_first, last) from the list. No destructors are called.
Returns: the first element remaining beyond the removed elements, or end() if no such element exists.
Throws: Nothing.
Complexity: Linear to the number of erased elements if it's a safe-mode , auto-unlink value or constant-time size is activated. Constant time otherwise.
Note: Invalidates the iterators (but not the references) to the erased element.
iterator erase_after(const_iterator before_first, const_iterator last, difference_type n);
Effects: Erases the range (before_first, last) from the list. n must be std::distance(before_first, last) - 1. No destructors are called.
Returns: the first element remaining beyond the removed elements, or end() if no such element exists.
Throws: Nothing.
Complexity: constant-time if link_mode
is normal_link. Linear to the elements (last - before_first) otherwise.
Note: Invalidates the iterators (but not the references) to the erased element.
iterator erase(const_iterator i);
Effects: Erases the element pointed by i of the list. No destructors are called.
Returns: the first element remaining beyond the removed element, or end() if no such element exists.
Throws: Nothing.
Complexity: Linear to the elements before i.
Note: Invalidates the iterators (but not the references) to the erased element.
iterator erase(const_iterator first, const_iterator last);
Requires: first and last must be valid iterator to elements in *this.
Effects: Erases the range pointed by b and e. No destructors are called.
Returns: the first element remaining beyond the removed elements, or end() if no such element exists.
Throws: Nothing.
Complexity: Linear to the elements before last.
Note: Invalidates the iterators (but not the references) to the erased elements.
iterator erase(const_iterator first, const_iterator last, difference_type n);
Effects: Erases the range [first, last) from the list. n must be std::distance(first, last). No destructors are called.
Returns: the first element remaining beyond the removed elements, or end() if no such element exists.
Throws: Nothing.
Complexity: linear to the elements before first if link_mode
is normal_link and constant_time_size
is activated. Linear to the elements before last otherwise.
Note: Invalidates the iterators (but not the references) to the erased element.
template<typename Disposer> iterator erase_after_and_dispose(const_iterator prev, Disposer disposer);
Requires: Disposer::operator()(pointer) shouldn't throw.
Effects: Erases the element after the element pointed by prev of the list. Disposer::operator()(pointer) is called for the removed element.
Returns: the first element remaining beyond the removed elements, or end() if no such element exists.
Throws: Nothing.
Complexity: Constant.
Note: Invalidates the iterators to the erased element.
template<typename Disposer> iterator erase_after_and_dispose(const_iterator before_first, const_iterator last, Disposer disposer);
Requires: Disposer::operator()(pointer) shouldn't throw.
Effects: Erases the range (before_first, last) from the list. Disposer::operator()(pointer) is called for the removed elements.
Returns: the first element remaining beyond the removed elements, or end() if no such element exists.
Throws: Nothing.
Complexity: Lineal to the elements (last - before_first + 1).
Note: Invalidates the iterators to the erased element.
template<typename Disposer> iterator erase_and_dispose(const_iterator i, Disposer disposer);
Requires: Disposer::operator()(pointer) shouldn't throw.
Effects: Erases the element pointed by i of the list. No destructors are called. Disposer::operator()(pointer) is called for the removed element.
Returns: the first element remaining beyond the removed element, or end() if no such element exists.
Throws: Nothing.
Complexity: Linear to the elements before i.
Note: Invalidates the iterators (but not the references) to the erased element.
template<typename Disposer> iterator erase_and_dispose(const_iterator first, const_iterator last, Disposer disposer);
Requires: first and last must be valid iterator to elements in *this. Disposer::operator()(pointer) shouldn't throw.
Effects: Erases the range pointed by b and e. No destructors are called. Disposer::operator()(pointer) is called for the removed elements.
Returns: the first element remaining beyond the removed elements, or end() if no such element exists.
Throws: Nothing.
Complexity: Linear to the number of erased elements plus linear to the elements before first.
Note: Invalidates the iterators (but not the references) to the erased elements.
template<typename Iterator> void assign(Iterator b, Iterator e);
Requires: Dereferencing iterator must yield an lvalue of type value_type.
Effects: Clears the list and inserts the range pointed by b and e. No destructors or copy constructors are called.
Throws: Nothing.
Complexity: 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.
Note: Invalidates the iterators (but not the references) to the erased elements.
template<typename Iterator, typename Disposer> void dispose_and_assign(Disposer disposer, Iterator b, Iterator e);
Requires: Disposer::operator()(pointer) shouldn't throw.
Requires: Dereferencing iterator must yield an lvalue of type value_type.
Effects: 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.
Throws: Nothing.
Complexity: Linear to the number of elements inserted plus linear to the elements contained in the list.
Note: Invalidates the iterators (but not the references) to the erased elements.
void splice_after(const_iterator prev, slist & x, const_iterator * last = 0);
Requires: prev is an iterator to an element or x.end()/x.before_begin() in x.
Effects: Transfers all the elements of list x to this list, after the the element pointed by prev. No destructors or copy constructors are called.
Returns: Nothing.
Throws: Nothing.
Complexity: In general, linear to the elements contained in x. Constant-time if cache_last<> option is true and also constant-time if linear<> option is true "this" is empty and "last" is not used.
Note: 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.
Additional note: If the optional parameter "last" is provided, it will be assigned to the last spliced element or prev if x is empty. This iterator can be used as new "prev" iterator for a new splice_after call. that will splice new values after the previously spliced values.
void splice_after(const_iterator prev_pos, slist & x, const_iterator prev_ele);
Requires: prev must point to an element contained by this list or to the before_begin() element. prev_ele must point to an element contained in list x or must be x.before_begin().
Effects: Transfers the element after prev_ele, from list x to this list, after the element pointed by prev. No destructors or copy constructors are called.
Throws: Nothing.
Complexity: Constant.
Note: 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_after(const_iterator prev_pos, slist & x, const_iterator before_first, const_iterator before_last);
Requires: prev_pos must be a dereferenceable iterator in *this or be before_begin(), and before_first and before_last belong to x and ++before_first != x.end() && before_last != x.end().
Effects: Transfers the range (before_first, before_last] from list x to this list, after the element pointed by prev_pos. No destructors or copy constructors are called.
Throws: Nothing.
Complexity: Linear to the number of elements transferred if constant_time_size
is true. Constant-time otherwise.
Note: 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_after(const_iterator prev_pos, slist & x, const_iterator before_first, const_iterator before_last, difference_type n);
Requires: prev_pos must be a dereferenceable iterator in *this or be before_begin(), and before_first and before_last belong to x and ++before_first != x.end() && before_last != x.end() and n == std::distance(before_first, before_last).
Effects: Transfers the range (before_first, before_last] from list x to this list, after the element pointed by p. No destructors or copy constructors are called.
Throws: Nothing.
Complexity: Constant time.
Note: 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 it, slist & x, const_iterator * last = 0);
Requires: it is an iterator to an element in x.
Effects: Transfers all the elements of list x to this list, before the the element pointed by it. No destructors or copy constructors are called.
Returns: Nothing.
Throws: Nothing.
Complexity: Linear to the elements contained in x plus linear to the elements before it. Linear to the elements before it if cache_last<> option is true. Constant-time if cache_last<> option is true and it == end().
Note: 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.
Additional note: If the optional parameter "last" is provided, it will be assigned to the last spliced element or prev if x is empty. This iterator can be used as new "prev" iterator for a new splice_after call. that will splice new values after the previously spliced values.
void splice(const_iterator pos, slist & x, const_iterator elem);
Requires: it p must be a valid iterator of *this. elem must point to an element contained in list x.
Effects: Transfers the element elem, from list x to this list, before the element pointed by pos. No destructors or copy constructors are called.
Throws: Nothing.
Complexity: Linear to the elements before pos and before elem. Linear to the elements before elem if cache_last<> option is true and pos == end().
Note: 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 pos, slist & x, const_iterator first, const_iterator last);
Requires: pos must be a dereferenceable iterator in *this and first and last belong to x and first and last a valid range on x.
Effects: Transfers the range [first, last) from list x to this list, before the element pointed by pos. No destructors or copy constructors are called.
Throws: Nothing.
Complexity: Linear to the sum of elements before pos, first, and last plus linear to the number of elements transferred if constant_time_size
is true. Linear to the sum of elements before first, and last plus linear to the number of elements transferred if constant_time_size
is true if cache_last<> is true and pos == end()
Note: 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 pos, slist & x, const_iterator first, const_iterator last, difference_type n);
Requires: pos must be a dereferenceable iterator in *this and first and last belong to x and first and last a valid range on x. n == std::distance(first, last).
Effects: Transfers the range [first, last) from list x to this list, before the element pointed by pos. No destructors or copy constructors are called.
Throws: Nothing.
Complexity: Linear to the sum of elements before pos, first, and last. Linear to the sum of elements before first and last if cache_last<> is true and pos == end().
Note: 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.
template<typename Predicate> void sort(Predicate p);
Effects: 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.
Throws: If value_traits::node_traits::node constructor throws (this does not happen with predefined Boost.Intrusive hooks) or the predicate throws. Basic guarantee.
Complexity: The number of comparisons is approximately N log N, where N is the list's size.
Note: Iterators and references are not invalidated
void sort();
Requires: 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.
Effects: 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.
Throws: If value_traits::node_traits::node constructor throws (this does not happen with predefined Boost.Intrusive hooks) or std::less<value_type> throws. Basic guarantee.
Complexity: This function is linear time: it performs at most size() + x.size() - 1 comparisons.
Note: Iterators and references are not invalidated.
template<typename Predicate> void merge(slist & x, Predicate p, const_iterator * last = 0);
Requires: 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.
Effects: 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.
Returns: Nothing.
Throws: If the predicate throws. Basic guarantee.
Complexity: This function is linear time: it performs at most size() + x.size() - 1 comparisons.
Note: Iterators and references are not invalidated.
Additional note: If optional "last" argument is passed, it is assigned to an iterator to the last transferred value or end() is x is empty.
void merge(slist & x);
Effects: 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.
Throws: if std::less<value_type> throws. Basic guarantee.
Complexity: This function is linear time: it performs at most size() + x.size() - 1 comparisons.
Note: Iterators and references are not invalidated
void reverse();
Effects: Reverses the order of elements in the list.
Throws: Nothing.
Complexity: This function is linear to the contained elements.
Note: Iterators and references are not invalidated
void remove(const_reference value);
Effects: Removes all the elements that compare equal to value. No destructors are called.
Throws: If std::equal_to<value_type> throws. Basic guarantee.
Complexity: Linear time. It performs exactly size() comparisons for equality.
Note: The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly size() comparisons for equality.
template<typename Disposer> void remove_and_dispose(const_reference value, Disposer disposer);
Requires: Disposer::operator()(pointer) shouldn't throw.
Effects: Removes all the elements that compare equal to value. Disposer::operator()(pointer) is called for every removed element.
Throws: If std::equal_to<value_type> throws. Basic guarantee.
Complexity: Linear time. It performs exactly size() comparisons for equality.
Note: The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid.
template<typename Pred> void remove_if(Pred pred);
Effects: Removes all the elements for which a specified predicate is satisfied. No destructors are called.
Throws: If pred throws. Basic guarantee.
Complexity: Linear time. It performs exactly size() calls to the predicate.
Note: The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid.
template<typename Pred, typename Disposer> void remove_and_dispose_if(Pred pred, Disposer disposer);
Requires: Disposer::operator()(pointer) shouldn't throw.
Effects: Removes all the elements for which a specified predicate is satisfied. Disposer::operator()(pointer) is called for every removed element.
Throws: If pred throws. Basic guarantee.
Complexity: Linear time. It performs exactly size() comparisons for equality.
Note: The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid.
void unique();
Effects: Removes adjacent duplicate elements or adjacent elements that are equal from the list. No destructors are called.
Throws: If std::equal_to<value_type> throws. Basic guarantee.
Complexity: Linear time (size()-1) comparisons calls to pred()).
Note: The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid.
template<typename BinaryPredicate> void unique(BinaryPredicate pred);
Effects: Removes adjacent duplicate elements or adjacent elements that satisfy some binary predicate from the list. No destructors are called.
Throws: If the predicate throws. Basic guarantee.
Complexity: Linear time (size()-1) comparisons equality comparisons.
Note: The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid.
template<typename Disposer> void unique_and_dispose(Disposer disposer);
Requires: Disposer::operator()(pointer) shouldn't throw.
Effects: Removes adjacent duplicate elements or adjacent elements that satisfy some binary predicate from the list. Disposer::operator()(pointer) is called for every removed element.
Throws: If std::equal_to<value_type> throws. Basic guarantee.
Complexity: Linear time (size()-1) comparisons equality comparisons.
Note: The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid.
template<typename BinaryPredicate, typename Disposer> void unique_and_dispose(BinaryPredicate pred, Disposer disposer);
Requires: Disposer::operator()(pointer) shouldn't throw.
Effects: Removes adjacent duplicate elements or adjacent elements that satisfy some binary predicate from the list. Disposer::operator()(pointer) is called for every removed element.
Throws: If the predicate throws. Basic guarantee.
Complexity: Linear time (size()-1) comparisons equality comparisons.
Note: The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid.
iterator iterator_to(reference value);
Requires: value must be a reference to a value inserted in a list.
Effects: This function returns a const_iterator pointing to the element
Throws: Nothing.
Complexity: Constant time.
Note: Iterators and references are not invalidated.
const_iterator iterator_to(const_reference value) const;
Requires: value must be a const reference to a value inserted in a list.
Effects: This function returns an iterator pointing to the element.
Throws: Nothing.
Complexity: Constant time.
Note: Iterators and references are not invalidated.
iterator previous(iterator i);
Returns: The iterator to the element before i in the list. Returns the end-iterator, if either i is the begin-iterator or the list is empty.
Throws: Nothing.
Complexity: Linear to the number of elements before i. Constant if cache_last<> is true and i == end().
const_iterator previous(const_iterator i) const;
Returns: The const_iterator to the element before i in the list. Returns the end-const_iterator, if either i is the begin-const_iterator or the list is empty.
Throws: Nothing.
Complexity: Linear to the number of elements before i. Constant if cache_last<> is true and i == end().
iterator previous(const_iterator prev_from, iterator i);
Returns: The iterator to the element before i in the list, starting the search on element after prev_from. Returns the end-iterator, if either i is the begin-iterator or the list is empty.
Throws: Nothing.
Complexity: Linear to the number of elements before i. Constant if cache_last<> is true and i == end().
const_iterator previous(const_iterator prev_from, const_iterator i) const;
Returns: The const_iterator to the element before i in the list, starting the search on element after prev_from. Returns the end-const_iterator, if either i is the begin-const_iterator or the list is empty.
Throws: Nothing.
Complexity: Linear to the number of elements before i. Constant if cache_last<> is true and i == end().
void incorporate_after(const_iterator prev_from, node_ptr first, node_ptr before_last);
Requires: prev_pos must be a dereferenceable iterator in *this or be before_begin(), and before_first and before_last belong to x and ++before_first != x.end() && before_last != x.end().
Effects: Transfers the range (before_first, before_last] to this list, after the element pointed by prev_pos. No destructors or copy constructors are called.
Throws: Nothing.
Complexity: Linear to the number of elements transferred if constant_time_size
is true. Constant-time otherwise.
Note: 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 incorporate_after(const_iterator prev_pos, node_ptr first, node_ptr before_last, difference_type n);
Requires: prev_pos must be a dereferenceable iterator in *this or be before_begin(), and before_first and before_last belong to x and ++before_first != x.end() && before_last != x.end() and n == std::distance(first, before_last) + 1.
Effects: Transfers the range (before_first, before_last] from list x to this list, after the element pointed by p. No destructors or copy constructors are called.
Throws: Nothing.
Complexity: Constant time.
Note: 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.
slist
public static functionsstatic slist & container_from_end_iterator(iterator end_iterator);
Precondition: end_iterator must be a valid end iterator of slist.
Effects: Returns a const reference to the slist associated to the end iterator
Throws: Nothing.
Complexity: Constant.
static const slist & container_from_end_iterator(const_iterator end_iterator);
Precondition: end_iterator must be a valid end const_iterator of slist.
Effects: Returns a const reference to the slist associated to the end iterator
Throws: Nothing.
Complexity: Constant.
static iterator s_iterator_to(reference value);
Requires: value must be a reference to a value inserted in a list.
Effects: This function returns a const_iterator pointing to the element
Throws: Nothing.
Complexity: Constant time.
Note: Iterators and references are not invalidated. This static function is available only if the value traits is stateless.
static const_iterator s_iterator_to(const_reference value);
Requires: value must be a const reference to a value inserted in a list.
Effects: This function returns an iterator pointing to the element.
Throws: Nothing.
Complexity: Constant time.
Note: Iterators and references are not invalidated. This static function is available only if the value traits is stateless.
slist
private member functionsvoid priv_splice_after(node_ptr prev_pos_n, slist & x, node_ptr before_first_n, node_ptr before_last_n);
void priv_incorporate_after(node_ptr prev_pos_n, node_ptr first_n, node_ptr before_last_n);
void priv_reverse(unspecified);
void priv_reverse(unspecified);
void priv_shift_backwards(size_type n, unspecified);
void priv_shift_backwards(size_type n, unspecified);
void priv_shift_forward(size_type n, unspecified);
void priv_shift_forward(size_type n, unspecified);
slist
private static functionsstatic void priv_swap_cache_last(slist * this_impl, slist * other_impl);
static void priv_swap_lists(node_ptr this_node, node_ptr other_node, unspecified);
static void priv_swap_lists(node_ptr this_node, node_ptr other_node, unspecified);
static slist & priv_container_from_end_iterator(const const_iterator & end_iterator);