node_keyed_class_doc

st_tree Home / st_tree Documentation

tree<Data, keyed<Key, Compare>, Alloc>::node_type

This node type maintains each node’s children keyed by Key. This node type models a map<> interface. The key ordering relation is given by Compare, which defaults to std::less<Key>.

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. Alias for Key template param
key_compare – type of ordering class. Alias for Compare template param.
kv_pair – a key-value pair type for map-style insertion: pair<key_type, data_type>
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).

data_type& data() – return reference to data payload of the node.
const data_type& data() const

const key_type& key() const – return reference to a node’s key. Key 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

pair<iterator, bool> insert(const kv_pair& kv) – insert key/value pair. returns iterator that points to child with key (key), and bool that is true if insertion happened.
pair<iterator, bool> insert(const key_type& key, const data_type& data) – insert a new child node with data payload (data).
pair<iterator, bool> insert(const key_type& key, const node_type& src) – insert a deep-copy of (src) to the node’s children.
pair<iterator, bool> insert(const key_type& key, const tree_type& src) – insert a deep-copy of (src).root() to the node’s children.

size_type erase(const key_type& key) – erase all children with key equal to (key). 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 key_type& key) const – return the number of child nodes whose key is equal to (key). (will be either zero or one).

node_type& operator[](const key_type& key) – returns the node whose key is (key). If no such node exists, it is inserted first.
const node_type& operator[](const key_type& key) const – returns the node whose key is (key). Throws missing_exception if no such node exists.

iterator find(const key_type& key) – returns iterator pointing to a node whose key is equal to (key). If no such node exists, returns end().
const_iterator find(const key_type& datakey const

iterator lower_bound(const key_type& key) – return iterator pointing to first child whose key is not less than (key).
const_iterator lower_bound(const key_type& key) const
iterator upper_bound(const key_type& key) – return iterator pointing to first child whose key is greater than (key).
const_iterator upper_bound(const key_type& key) const
pair<iterator, iterator> equal_range(const key_type& key) – return iterator range of children whose key is (key).
pair<const_iterator, const_iterator> equal_range(const key_type& key) 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(const key_type& key, 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(const key_type& key, 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