![]() |
Home | Libraries | People | FAQ | More |
boost::intrusive::linear_slist_algorithms
// In header: <boost/intrusive/linear_slist_algorithms.hpp> template<typename NodeTraits> class linear_slist_algorithms { public: // types typedef ; typedef ; typedef ; typedef ; typedef ; // public static functions () ; () ; () ; () ; (, ) ; (, ) ; (, , ) ; () ; () ; () ; () ; () ; (, ) ; () ; (, ) ; () ; (, ) ; (, ) ; (, ) ; template<typename Disposer> (, ) ; };
linear_slist_algorithms provides basic algorithms to manipulate nodes forming a linear singly linked list.
linear_slist_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 linear list
node_ptr
: A pointer to a node
const_node_ptr
: A pointer to a const node
Static functions:
static node_ptr get_next(const_node_ptr n);
static void set_next(node_ptr n, node_ptr next);
linear_slist_algorithms
public static functions( this_node) ;
Effects: Constructs an non-used list element, putting the next pointer to null: NodeTraits::get_next(this_node) == node_ptr()
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: or it's a not inserted node: return node_ptr() == NodeTraits::get_next(this_node) || NodeTraits::get_next(this_node) == this_node
Complexity: Constant
Throws: Nothing.
( this_node) ;
Effects: Returns true is "this_node" has the same state as if it was inited using "init(node_ptr)"
Complexity: Constant
Throws: Nothing.
( prev_node) ;
Requires: prev_node must be in a circular list or be an empty circular list.
Effects: Unlinks the next node of prev_node from the circular list.
Complexity: Constant
Throws: Nothing.
( prev_node, last_node) ;
Requires: prev_node and last_node must be in a circular list or be an empty circular list.
Effects: Unlinks the range (prev_node, last_node) from the linear list.
Complexity: Constant
Throws: Nothing.
( prev_node, this_node) ;
Requires: prev_node must be a node of a linear list.
Effects: Links this_node after prev_node in the linear list.
Complexity: Constant
Throws: Nothing.
( p, b, e) ;
Requires: b and e must be nodes of the same linear list or an empty range. and p must be a node of a different linear list.
Effects: Removes the nodes from (b, e] range from their linear list and inserts them after p in p's linear list.
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) == this_node
.
Complexity: Constant
Throws: Nothing.
() ;
Requires: 'p' is the first node of a list.
Effects: Returns a pointer to a node that represents the "end" (one past end) node
Complexity: Constant time.
Throws: Nothing.
( this_node) ;
Effects: Returns true if this_node_points to an empty list.
Complexity: Constant
Throws: Nothing.
( this_node) ;
Effects: Returns true if this_node points to a sentinel node.
Complexity: Constant
Throws: Nothing.
( this_node) ;
Effects: Marks this node as a "sentinel" node, a special state that is different from "empty", that can be used to mark a special state of the list
Complexity: Constant
Throws: Nothing.
( prev_init_node, this_node) ;
Requires: this_node and prev_init_node must be in the same linear list.
Effects: Returns the previous node of this_node in the linear list starting. the search from prev_init_node. The first node checked for equality is NodeTraits::get_next(prev_init_node).
Complexity: Linear to the number of elements between prev_init_node and this_node.
Throws: Nothing.
( this_node) ;
Requires: this_node must be in a linear list or be an empty linear list.
Effects: Returns the number of nodes in a linear list. If the linear list is empty, returns 1.
Complexity: Linear
Throws: Nothing.
( this_node, other_node) ;
Requires: this_node and other_node must be nodes inserted in linear lists or be empty linear lists.
Effects: Moves all the nodes previously chained after this_node after other_node and vice-versa.
Complexity: Constant
Throws: Nothing.
( p) ;
Effects: Reverses the order of elements in the list.
Returns: The new first node of the list.
Throws: Nothing.
Complexity: This function is linear to the contained elements.
( p, n) ;
Effects: Moves the first n nodes starting at p to the end of the list.
Returns: A pair containing the new first and last node of the list or if there has been any movement, a null pair if n leads to no movement.
Throws: Nothing.
Complexity: Linear to the number of elements plus the number moved positions.
( p, n) ;
Effects: Moves the first n nodes starting at p to the beginning of the list.
Returns: A pair containing the new first and last node of the list or if there has been any movement, a null pair if n leads to no movement.
Throws: Nothing.
Complexity: Linear to the number of elements plus the number moved positions.
( p, other) ;
Requires: other must be a list and p must be a node of a different linear list.
Effects: Transfers all nodes from other after p in p's linear list.
Complexity: Linear
Throws: Nothing.
template<typename Disposer> ( p, disposer) ;
Requires: "disposer" must be an object function taking a node_ptr parameter and shouldn't throw.
Effects: Unlinks all nodes reachable from p (but not p) and calls void disposer::operator()(node_ptr)
for every node of the list where p is linked.
Returns: The number of disposed nodes
Complexity: Linear to the number of element of the list.
Throws: Nothing.