![]() |
Home | Libraries | People | FAQ | More |
boost::intrusive::circular_list_algorithms
// In header: <boost/intrusive/circular_list_algorithms.hpp> template<typename NodeTraits> class circular_list_algorithms { public: // types typedef ; typedef ; typedef ; typedef ; // member classes/structs/unions struct stable_partition_info { // public data members num_1st_partition; num_2nd_partition; beg_2st_partition; }; // public static functions () ; () ; () ; () ; () ; () ; () ; (, ) ; (, ) ; (, ) ; (, ) ; (, , ) ; (, ) ; () ; (, ) ; (, ) ; (, ) ; template<typename Pred> (, , , ); // private static functions (, ) ; (, ) ; };
circular_list_algorithms provides basic algorithms to manipulate nodes forming a circular doubly linked list. An empty circular list is formed by a node whose pointers point to itself.
circular_list_algorithms is configured with a NodeTraits class, which encapsulates the information about the node to be manipulated. NodeTraits must support the following interface:
Typedefs:
node
: The type of the node that forms the circular list
node_ptr
: A pointer to a node
const_node_ptr
: A pointer to a const node
Static functions:
static node_ptr get_previous(const_node_ptr n);
static void set_previous(node_ptr n, node_ptr prev);
static node_ptr get_next(const_node_ptr n);
static void set_next(node_ptr n, node_ptr next);
circular_list_algorithms
public static functions( this_node) ;
Effects: Constructs an non-used list element, so that inited(this_node) == true
Complexity: Constant
Throws: Nothing.
( this_node) ;
Effects: Returns true is "this_node" is in a non-used state as if it was initialized by the "init" function.
Complexity: Constant
Throws: Nothing.
( this_node) ;
Effects: Constructs an empty list, making this_node the only node of the circular list: NodeTraits::get_next(this_node) == NodeTraits::get_previous(this_node) == this_node
.
Complexity: Constant
Throws: Nothing.
( this_node) ;
Effects: Returns true if this_node_points to an empty list.
Complexity: Constant
Throws: Nothing.
( this_node) ;
Requires: this_node must be in a circular list or be an empty circular list.
Effects: Returns true is "this_node" is the only node of a circular list: return NodeTraits::get_next(this_node) == this_node
Complexity: Constant
Throws: Nothing.
( this_node) ;
Requires: this_node must be in a circular list or be an empty circular list.
Effects: Returns the number of nodes in a circular list. If the circular list is empty, returns 1.
Complexity: Linear
Throws: Nothing.
( this_node) ;
Requires: this_node must be in a circular list or be an empty circular list.
Effects: Unlinks the node from the circular list.
Complexity: Constant
Throws: Nothing.
( b, e) ;
Requires: b and e must be nodes of the same circular list or an empty range.
Effects: Unlinks the node [b, e) from the circular list.
Complexity: Constant
Throws: Nothing.
( nxt_node, this_node) ;
Requires: nxt_node must be a node of a circular list.
Effects: Links this_node before nxt_node in the circular list.
Complexity: Constant
Throws: Nothing.
( prev_node, this_node) ;
Requires: prev_node must be a node of a circular list.
Effects: Links this_node after prev_node in the circular list.
Complexity: Constant
Throws: Nothing.
( this_node, other_node) ;
Requires: this_node and other_node must be nodes inserted in circular lists or be empty circular lists.
Effects: Swaps the position of the nodes: this_node is inserted in other_nodes position in the second circular list and the other_node is inserted in this_node's position in the first circular list.
Complexity: Constant
Throws: Nothing.
( p, b, e) ;
Requires: b and e must be nodes of the same circular list or an empty range. and p must be a node of a different circular list or may not be an iterator in Effects: Removes the nodes from [b, e) range from their circular list and inserts them before p in p's circular list.
Complexity: Constant
Throws: Nothing.
( p, i) ;
Requires: i must a node of a circular list and p must be a node of a different circular list.
Effects: Removes the node i from its circular list and inserts it before p in p's circular list. If p == i or p == NodeTraits::get_next(i), this function is a null operation.
Complexity: Constant
Throws: Nothing.
( p) ;
Effects: Reverses the order of elements in the list.
Throws: Nothing.
Complexity: This function is linear time.
( p, n) ;
Effects: Moves the node p n positions towards the end of the list.
Throws: Nothing.
Complexity: Linear to the number of moved positions.
( p, n) ;
Effects: Moves the node p n positions towards the beginning of the list.
Throws: Nothing.
Complexity: Linear to the number of moved positions.
( f, l) ;
Requires: f and l must be in a circular list.
Effects: Returns the number of nodes in the range [f, l).
Complexity: Linear
Throws: Nothing.
template<typename Pred> ( beg, end, pred, info);