list(const value_traits & v_traits = value_traits());

Effects: constructs an empty list.

Complexity: Constant

Throws: If real_value_traits::node_traits::node constructor throws (this does not happen with predefined Boost.Intrusive hooks).

template<typename Iterator> 
  list(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 the range [first,last).

Complexity: Linear in std::distance(b, e). No copy constructors are called.

Throws: If real_value_traits::node_traits::node constructor throws (this does not happen with predefined Boost.Intrusive hooks).

list(BOOST_RV_REF(list) x);

Effects: to-do

list& operator=(BOOST_RV_REF(list) x);

Effects: to-do

~list();

Effects: 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 are called), but the hooks according to the ValueTraits 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.

const real_value_traits & get_real_value_traits() const;

real_value_traits & get_real_value_traits();

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.

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 pop_back();

Effects: Erases the last 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_back_and_dispose(Disposer disposer);

Requires: Disposer::operator()(pointer) shouldn't throw.

Effects: Erases the last element of the list. No destructors are called. Disposer::operator()(pointer) is called for the removed element.

Throws: Nothing.

Complexity: Constant.

Note: Invalidates the iterators to the erased element.

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. No destructors are called. 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.

const_reference back() const;

Effects: Returns a const_reference to the last element of the list.

Throws: Nothing.

Complexity: Constant.

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 constant iterator to the end of the list.

Throws: Nothing.

Complexity: Constant.

reverse_iterator rbegin();

Effects: Returns a reverse_iterator pointing to the beginning of the reversed list.

Throws: Nothing.

Complexity: Constant.

const_reverse_iterator rbegin() const;

Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed list.

Throws: Nothing.

Complexity: Constant.

const_reverse_iterator crbegin() const;

Effects: Returns a const_reverse_iterator pointing to the beginning of the reversed list.

Throws: Nothing.

Complexity: Constant.

reverse_iterator rend();

Effects: Returns a reverse_iterator pointing to the end of the reversed list.

Throws: Nothing.

Complexity: Constant.

const_reverse_iterator rend() const;

Effects: Returns a const_reverse_iterator pointing to the end of the reversed list.

Throws: Nothing.

Complexity: Constant.

const_reverse_iterator crend() const;

Effects: Returns a const_reverse_iterator pointing to the end of the reversed list.

Throws: Nothing.

Complexity: Constant.

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 option is disabled. 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(list & other);

Effects: Swaps the elements of x and *this.

Throws: Nothing.

Complexity: Constant.

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 shifts.

Note: 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 shifts.

Note: Does not affect the validity of iterators and references.

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: Constant.

Note: Invalidates the iterators (but not the references) to the erased element.

iterator erase(const_iterator b, const_iterator e);

Requires: b and e must be valid iterators to elements in *this.

Effects: Erases the element 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 number of erased elements if it's a safe-mode or auto-unlink value, or constant-time size is enabled. Constant-time otherwise.

Note: Invalidates the iterators (but not the references) to the erased elements.

iterator erase(const_iterator b, const_iterator e, difference_type n);

Requires: b and e must be valid iterators to elements in *this. n must be std::distance(b, e).

Effects: Erases the element 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 number of erased elements if it's a safe-mode or auto-unlink value is enabled. Constant-time otherwise.

Note: Invalidates the iterators (but not the references) to the erased elements.

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: Constant.

Note: Invalidates the iterators to the erased element.

template<typename Disposer> 
  iterator erase_and_dispose(const_iterator b, const_iterator e, 
                             Disposer disposer);

Requires: Disposer::operator()(pointer) shouldn't throw.

Effects: Erases the element 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 elements erased.

Note: Invalidates the iterators to the erased elements.

void clear();

Effects: Erases all the elements of the container. No destructors are called.

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. No destructors are called. 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.

template<typename Cloner, typename Disposer> 
  void clone_from(const list & 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. Basic guarantee.

iterator insert(const_iterator p, reference value);

Requires: value must be an lvalue and p must be a valid iterator of *this.

Effects: Inserts the value before the position pointed by p.

Returns: An iterator to the inserted element.

Throws: Nothing.

Complexity: Constant time. No copy constructors are called.

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 be a valid iterator of *this.

Effects: Inserts the range pointed by b and e before the position p. No copy constructors are called.

Throws: Nothing.

Complexity: Linear to the number of elements inserted.

Note: Does not affect the validity of iterators and references.

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(const_iterator p, list & x);

Requires: p must be a valid iterator of *this.

Effects: Transfers all the elements of list x to this list, before the the element pointed by p. 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(const_iterator p, list & x, const_iterator new_ele);

Requires: p must be a valid iterator of *this. new_ele must point to an element contained in list x.

Effects: 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.

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(const_iterator p, list & x, const_iterator start, 
            const_iterator end);

Requires: p must be a valid iterator of *this. start and end must point to elements contained in list x.

Effects: 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.

Throws: Nothing.

Complexity: Linear to the number of elements transferred if constant-time size option is enabled. 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(const_iterator p, list & x, const_iterator start, 
            const_iterator end, difference_type n);

Requires: p must be a valid iterator of *this. start and end must point to elements contained in list x. n == std::distance(start, end)

Effects: 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.

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 sort();

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

Notes: Iterators and references are not invalidated.

Complexity: The number of comparisons is approximately N log N, where N is the list's size.

template<typename Predicate> void sort(Predicate p);

Requires: p must be a comparison function that induces a strict weak ordering

Effects: This function sorts the list *this according to p. The sort is stable, that is, the relative order of equivalent elements is preserved.

Throws: If real_value_traits::node_traits::node constructor throws (this does not happen with predefined Boost.Intrusive hooks) or the predicate throws. Basic guarantee.

Notes: This won't throw if list_base_hook<> or list_member_hook are used. Iterators and references are not invalidated.

Complexity: The number of comparisons is approximately N log N, where N is the list's size.

void merge(list & 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

template<typename Predicate> void merge(list & x, Predicate p);

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

void reverse();

Effects: Reverses the order of elements in the list.

Throws: Nothing.

Complexity: This function is linear time.

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.

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 pred 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 are equal 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 pred 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.

static list & container_from_end_iterator(iterator end_iterator);

Precondition: end_iterator must be a valid end iterator of list.

Effects: Returns a const reference to the list associated to the end iterator

Throws: Nothing.

Complexity: Constant.

static const list & container_from_end_iterator(const_iterator end_iterator);

Precondition: end_iterator must be a valid end const_iterator of list.

Effects: Returns a const reference to the list 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.