Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Class template list

boost::intrusive::list

Synopsis

// In header: <boost/intrusive/list.hpp>

template<typename T,  Options> 
class list {
public:
  // types
  typedef                                           ;          
  typedef                                 ;               
  typedef                           ;         
  typedef pointer_traits<               ;            
  typedef pointer_traits<                  ;             
  typedef pointer_traits<            ;       
  typedef pointer_traits<            ;       
  typedef                                              ;             
  typedef                  ;              
  typedef                   ;        
  typedef        ;      
  typedef  ;
  typedef                             ;           
  typedef                                     ;                  
  typedef                                 ;              
  typedef                           ;        
  typedef circular_list_algorithms<               ;       
  typedef                                           ;    

  // construct/copy/destruct
  ();
  ();
  template<typename Iterator> 
    (, ,  = );
  (list &&);
  list & (list &&);
  ~();

  // public member functions
   () ;
   () ;
   () ;
  template<typename Disposer>  () ;
   () ;
  template<typename Disposer>  () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   () ;
   (list &) ;
   ( = ) ;
   ( = ) ;
   () ;
   (, ) ;
   (, , ) ;
  template<typename Disposer> 
     (, ) ;
  template<typename Disposer> 
     (, , ) ;
   () ;
  template<typename Disposer>  () ;
  template<typename Cloner, typename Disposer> 
     (list &, , );
  template<typename Cloner, typename Disposer> 
     (list &&, , );
   (, ) ;
  template<typename Iterator> 
     (, , ) ;
  template<typename Iterator>  (, ) ;
  template<typename Iterator, typename Disposer> 
     (, , ) ;
   (, list &) ;
   (, list &, ) ;
   (, list &, , ) ;
   (, list &, , , 
              ) ;
   ();
  template<typename Predicate>  ();
   (list &);
  template<typename Predicate>  (list &, );
   () ;
   () ;
  template<typename Disposer> 
     (, ) ;
  template<typename Pred>  ();
  template<typename Pred, typename Disposer> 
     (, );
   ();
  template<typename BinaryPredicate>  ();
  template<typename Disposer>  ();
  template<typename BinaryPredicate, typename Disposer> 
     (, );
   () ;
   () ;
   () ;

  // public static functions
  list & () ;
  list & () ;
   () ;
   () ;

  // public data members
  static  constant_time_size;
  static  stateful_value_traits;
  static  has_container_from_iterator;
};

Description

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

list public construct/copy/destruct

  1. ();

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

  2. ( v_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).

  3. template<typename Iterator> 
      ( b,  e,  v_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 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).

  4. (list && x);

    Effects: Constructs a container moving resources from another container. Internal value traits are move constructed and nodes belonging to x (except the node representing the "end") are linked to *this.

    Complexity: Constant.

    Throws: If value_traits::node_traits::node's move constructor throws (this does not happen with predefined Boost.Intrusive hooks) or the move constructor of value traits throws.

  5. list & (list && x);

    Effects: Equivalent to swap

  6. ~();

    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.

    Throws: Nothing.

    Complexity: Linear to the number of elements in the list, if it's a safe-mode or auto-unlink value . Otherwise constant.

list public member functions

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

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

  3.  () ;

    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.

  4. template<typename 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.

  5.  () ;

    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.

  6. template<typename 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.

  7.  () ;

    Effects: Returns a reference to the first element of the list.

    Throws: Nothing.

    Complexity: Constant.

  8.  () ;

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

    Throws: Nothing.

    Complexity: Constant.

  9.  () ;

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

    Throws: Nothing.

    Complexity: Constant.

  10.  () ;

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

    Throws: Nothing.

    Complexity: Constant.

  11.  () ;

    Effects: Returns an iterator to the first element contained in the list.

    Throws: Nothing.

    Complexity: Constant.

  12.  () ;

    Effects: Returns a const_iterator to the first element contained in the list.

    Throws: Nothing.

    Complexity: Constant.

  13.  () ;

    Effects: Returns a const_iterator to the first element contained in the list.

    Throws: Nothing.

    Complexity: Constant.

  14.  () ;

    Effects: Returns an iterator to the end of the list.

    Throws: Nothing.

    Complexity: Constant.

  15.  () ;

    Effects: Returns a const_iterator to the end of the list.

    Throws: Nothing.

    Complexity: Constant.

  16.  () ;

    Effects: Returns a constant iterator to the end of the list.

    Throws: Nothing.

    Complexity: Constant.

  17.  () ;

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

    Throws: Nothing.

    Complexity: Constant.

  18.  () ;

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

    Throws: Nothing.

    Complexity: Constant.

  19.  () ;

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

    Throws: Nothing.

    Complexity: Constant.

  20.  () ;

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

    Throws: Nothing.

    Complexity: Constant.

  21.  () ;

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

    Throws: Nothing.

    Complexity: Constant.

  22.  () ;

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

    Throws: Nothing.

    Complexity: Constant.

  23.  () ;

    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.

  24.  () ;

    Effects: Returns true if the list contains no elements.

    Throws: Nothing.

    Complexity: Constant.

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

  25.  (list & other) ;

    Effects: Swaps the elements of x and *this.

    Throws: Nothing.

    Complexity: Constant.

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

  26.  ( n = ) ;

    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.

  27.  ( n = ) ;

    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.

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

  29.  ( b,  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.

  30.  ( b,  e,  n) ;

    Requires: b and e must be valid iterators to elements in *this. n must be 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.

  31. template<typename Disposer> 
       ( i,  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.

  32. template<typename Disposer> 
       ( b,  e, 
                                  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.

  33.  () ;

    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.

  34. template<typename 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.

  35. template<typename Cloner, typename Disposer> 
       (list & src,  cloner,  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.

  36. template<typename Cloner, typename Disposer> 
       (list && src,  cloner,  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()(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.

  37.  ( p,  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.

  38. template<typename Iterator> 
       ( p,  b,  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.

  39. template<typename Iterator>  ( b,  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.

  40. template<typename Iterator, typename Disposer> 
       ( disposer,  b,  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.

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

  42.  ( p, list & x,  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 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.

  43.  ( p, list & x,  f,  e) ;

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

    Effects: Transfers the range pointed by f and e from list x to this list, before 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.

  44.  ( p, list & x,  f,  e, 
                 n) ;

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

    Effects: Transfers the range pointed by f and e from list x to this list, before 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.

  45.  ();

    Effects: This function sorts the list *this according to operator <. 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 operator < 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.

  46. template<typename 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 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.

  47.  (list & x);

    Effects: This function removes all of x's elements and inserts them in order into *this according to operator <. 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 operator < 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

  48. template<typename Predicate>  (list & x,  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.

  49.  () ;

    Effects: Reverses the order of elements in the list.

    Throws: Nothing.

    Complexity: This function is linear time.

    Note: Iterators and references are not invalidated

  50.  ( value) ;

    Effects: Removes all the elements that compare equal to value. No destructors are called.

    Throws: If operator == 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.

  51. template<typename Disposer> 
       ( value,  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 operator == 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.

  52. template<typename 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.

  53. template<typename Pred, typename Disposer> 
       ( pred,  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.

  54.  ();

    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.

  55. template<typename 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.

  56. template<typename 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.

  57. template<typename BinaryPredicate, typename Disposer> 
       ( pred,  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.

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

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

  60.  () ;

    Effects: Asserts the integrity of the container.

    Complexity: Linear time.

    Note: The method has no effect when asserts are turned off (e.g., with NDEBUG). Experimental function, interface might change in future versions.

list public static functions

  1. list & ( 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.

  2. list & 
    ( 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.

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

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


PrevUpHomeNext