Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is the documentation for an old version of Boost. Click here to view this page for the latest version.
PrevUpHomeNext

Class template linear_slist_algorithms

boost::intrusive::linear_slist_algorithms

Synopsis

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

template<typename NodeTraits> 
class linear_slist_algorithms {
public:
  // types
  typedef NodeTraits::node           node;          
  typedef NodeTraits::node_ptr       node_ptr;      
  typedef NodeTraits::const_node_ptr const_node_ptr;
  typedef NodeTraits                 node_traits;   
  typedef twin< node_ptr >           node_pair;     

  // public static functions
  static void init(node_ptr) noexcept;
  static bool unique(const_node_ptr) noexcept;
  static bool inited(const_node_ptr) noexcept;
  static void unlink_after(node_ptr) noexcept;
  static void unlink_after(node_ptr, node_ptr) noexcept;
  static void link_after(node_ptr, node_ptr) noexcept;
  static void transfer_after(node_ptr, node_ptr, node_ptr) noexcept;
  static void init_header(node_ptr) noexcept;
  static node_ptr end_node(const_node_ptr) noexcept;
  static bool is_empty(const_node_ptr) noexcept;
  static bool is_sentinel(const_node_ptr) noexcept;
  static void set_sentinel(node_ptr) noexcept;
  static node_ptr get_previous_node(node_ptr, node_ptr) noexcept;
  static std::size_t count(const_node_ptr) noexcept;
  static void swap_trailing_nodes(node_ptr, node_ptr) noexcept;
  static node_ptr reverse(node_ptr) noexcept;
  static node_pair move_first_n_backwards(node_ptr, std::size_t) noexcept;
  static node_pair move_first_n_forward(node_ptr, std::size_t) noexcept;
  static void transfer_after(node_ptr, node_ptr) noexcept;
  template<typename Disposer> 
    static std::size_t detach_and_dispose(node_ptr, Disposer) noexcept;
};

Description

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

  1. static void init(node_ptr this_node) noexcept;

    Effects: Constructs an non-used list element, putting the next pointer to null: NodeTraits::get_next(this_node) == node_ptr()

    Complexity: Constant

    Throws: Nothing.

  2. static bool unique(const_node_ptr this_node) noexcept;

    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.

  3. static bool inited(const_node_ptr this_node) noexcept;

    Effects: Returns true is "this_node" has the same state as if it was inited using "init(node_ptr)"

    Complexity: Constant

    Throws: Nothing.

  4. static void unlink_after(node_ptr prev_node) noexcept;

    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.

  5. static void unlink_after(node_ptr prev_node, node_ptr last_node) noexcept;

    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.

  6. static void link_after(node_ptr prev_node, node_ptr this_node) noexcept;

    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.

  7. static void transfer_after(node_ptr p, node_ptr b, node_ptr e) noexcept;

    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.

  8. static void init_header(node_ptr this_node) noexcept;

    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.

  9. static node_ptr end_node(const_node_ptr) noexcept;

    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.

  10. static bool is_empty(const_node_ptr this_node) noexcept;

    Effects: Returns true if this_node_points to an empty list.

    Complexity: Constant

    Throws: Nothing.

  11. static bool is_sentinel(const_node_ptr this_node) noexcept;

    Effects: Returns true if this_node points to a sentinel node.

    Complexity: Constant

    Throws: Nothing.

  12. static void set_sentinel(node_ptr this_node) noexcept;

    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.

  13. static node_ptr 
    get_previous_node(node_ptr prev_init_node, node_ptr this_node) noexcept;

    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.

  14. static std::size_t count(const_node_ptr this_node) noexcept;

    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.

  15. static void swap_trailing_nodes(node_ptr this_node, node_ptr other_node) noexcept;

    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.

  16. static node_ptr reverse(node_ptr p) noexcept;

    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.

  17. static node_pair move_first_n_backwards(node_ptr p, std::size_t n) noexcept;

    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.

  18. static node_pair move_first_n_forward(node_ptr p, std::size_t n) noexcept;

    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.

  19. static void transfer_after(node_ptr p, node_ptr other) noexcept;

    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.

  20. template<typename Disposer> 
      static std::size_t 
      detach_and_dispose(node_ptr p, Disposer disposer) noexcept;

    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.


PrevUpHomeNext