node_ordered_class_doc

st_tree Home / st_tree Documentation

tree<Data, ordered<Compare>, Alloc>::node_type

This node type automatically maintains each node’s children in sorted order, by data. This node type models a multiset<> interface. The ordering relation is given by Compare, which defaults to std::less<Data>.

tree_type – the type of the tree that contains this node
node_type – data type of nodes contained by the node. This is a recursive definition, as a node is a container for child nodes of same type.
data_type – alias for the Data template param: the data payload type at each node
allocator_type – the allocator type used by the node

key_type – data type of ordering key. (equivalent to data_type for this storage category)
key_compare – type of ordering class. Alias for Compare template param.
value_type – data type contained by the node container class. The value type of a node is its node_type.
pointer – pointer to value_type
reference – reference to value_type
const_pointer – pointer to constant value_type
const_reference – reference to constant value_type
size_type – represents size (unsigned) values
difference_type – represents difference (signed) values

iterator – iterates over child nodes (forward iterator)
const_iterator

bf_iterator – iterates over subtree starting at this node as root, breadth first traversal
const_bf_iterator
df_pre_iterator – iterates over subtree, depth-first preorder traversal
const_df_pre_iterator
df_post_iterator – iterates over subtree, depth-first postorder traversal
const_df_post_iterator

node_type() – default constructor: typically only used internally
~node_type() – destructor

node_raw(const node_raw& src) – copy constructor: typically used internally
node_raw& operator=(const node_raw& rhs) – deep assignment: data() and children of (rhs) are copied to the node. Node maintains its position in its parent’s child container. Throws cycle_exception if assignment would create a cycle in the tree (if (rhs) is ancestor of the node).

const data_type& data() const – return reference to data payload of the node. Only ‘const’ version is available for ordered storage model, since data() is the ordering key and is immutable.

size_type ply() const – return the node’s ply in the tree. The ply of root node is 0. The ply of the root’s children is 1, etc.
size_type depth() const – the depth of the node’s subtree
size_type subtree_size() – the number of nodes in the node’s subtree
bool is_root() const – true if the node has no parent

node_type& parent() – return reference to node’s parent (throw parent_exception if no parent)
const node_type& parent() const

tree_type& tree() – return reference to the tree that the node is a member of.
const tree_type& tree() const

bool is_ancestor(const node_type& n) const – true if the node is an ancestor of (n)

size_type size() const – returns the number of the node’s children
bool empty() const – true if the node has no children

iterator insert(const data_type& data) – insert a new child node with data payload (data). returns iterator that points to new child.
iterator insert(const node_type& src) – insert a deep-copy of (src) to the node’s children. returns iterator that points to new child.
iterator insert(const tree_type& src) – insert a deep-copy of (src).root() to the node’s children. returns iterator that points to new child.

size_type erase(const data_type& data) – erase all children with data equal to (data). Returns number of children erased.
void erase(const iterator& j) – erase the child node at (j)
void erase(const iterator& F, const iterator& L) – erase node’s children on the iterator interval [F, L)
void erase() – erase the node from its parent

void clear() – erase all the node’s children: reset to empty.

size_type count(const data_type& data) const – return the number of child nodes whose data member is equal to (data).

iterator find(const data_type& data) – returns iterator pointing to a node whose data member is equal to (data). If no such node exists, returns end().
const_iterator find(const data_type& data) const

iterator lower_bound(const data_type& data) – return iterator pointing to first child whose data member is not less than (data).
const_iterator lower_bound(const data_type& data) const
iterator upper_bound(const data_type& data) – return iterator pointing to first child whose data member is greater than (data).
const_iterator upper_bound(const data_type& data) const
pair<iterator, iterator> equal_range(const data_type& data) – return iterator range of children whose data member is (data).
pair<const_iterator, const_iterator> equal_range(const data_type& data) const

void swap(node_type& b) – swap data and children with node (b). throws cycle_exception if swap would create a cycle in tree (e.g. if node is ancestor of (b))

void graft(node_type& src) – removes (src) from its current location and inserts to the nodes children. Throws cycle_exception if operation would create cycle in the tree.
void graft(tree_type& src) – graft (src).root()

bool operator==(const node_type& rhs) const – true if node is equal to (rhs). Two nodes are equal if their data instances are equal, and if their child nodes are lexicographically equal (as defined by iterating begin() to end()).
bool operator!=(const node_type& rhs) const

bool operator<(const node_type& rhs) const – true if node is less than (rhs). Node (a) is less than (b) if a.data() < b.data(), otherwise if the children of (a) are lexicographically less than children of (b) (iterating begin() to end()).
bool operator>(const node_type& rhs) const
bool operator<=(const node_type& rhs) const
bool operator>=(const node_type& rhs) const

iterator begin() – iteration over child nodes
const_iterator begin() const
iterator end()
const_iterator end() const

bf_iterator bf_begin() – iteration over nodes of subtree: breadth first traversal
const_bf_iterator bf_begin() const
bf_iterator bf_end()
const_bf_iterator bf_end() const

df_pre_iterator df_pre_begin() – iteration over nodes of subtree: depth first pre order traversal
const_df_pre_iterator df_pre_begin() const
df_pre_iterator df_pre_end()
const_df_pre_iterator df_pre_end() const

df_post_iterator df_post_begin() – iteration over nodes of subtree: depth first post order traversal
const_df_post_iterator df_post_begin() const
df_post_iterator df_post_end()
const_df_post_iterator df_post_end() const