The Tree Container Library

The two child element iterators, iterator and const_iterator, are available for all four tree containers. The child element iterators do as their name implies, iterate over the a parent's children. as opposed to it's descendants. The associative tree child iterators are bi-directional iterators. The sequential_tree child iterators are random access iterators.

The child element iterators expose the underlying element, and are normally preferable over the child node iterators which expose the underlying node. If you do need access to the underlying node with a child element iterator, the node() operation is provided, as described further below.

Many of the operations in the tree containers return iterators. Almost all operations which return iterators return child element iterators, except for the operations which which are clearly named to return a different type of iterator. In addition to being returned from certain operations, the begin() and end() operations return the begin and end element iterators for the node which they are called.

The child element iterators work very much like the iterators in the STL. They are declared in the same manner, as shown in the following examples.

tree<int>::iterator tree_it = mytree.begin();
multitree<std::string>::const_iterator multitree_it = myuniquetree.find("Mitch");
unique_tree<CEmplyee>::iterator uniquetree_it = myuniquetree.find_deep(CEmployee(3455));
sequential_tree<std::string>::const_iterator seq_tree_it = mysequentialtree.find("Haas");

Element iterator * and -> overloaded operations return a reference and pointer (respectively) to the element within the node which an element iterator points to. This allows all element iterators to be used with most of the standard STL algorithms. The following examples illustrate the use of these two element iterator operators.

int myint = *tree_it;
std::string substr = multitree_it->substr(1, 3);
std::string name = uniquetree_it->get_employee_name()
std::string name = *seq_tree_it;

Element terators can access the node they point to with the node() operation, where the node is of the same tree type in which it resides, or tree_type. Below are examples of how these operations are used. Once you have a pointer or reference to a node, or have an element iterator that points to a node, you can call any of the tree's operations on that node or iterator, remembering that all descendant nodes of the tree are actually tree's (subtrees) themselves.

tree<int>* tree_node_ptr = tree_it.node();
tree<int>& tree_node = *tree_it.node();
multitree<std::string>* multitree_node_ptr = multitree_it.node();
multitree<std::string>& multitree_node = *multitree_it.node();
unique_tree<CEmployee>* unique_tree_ptr = uniquetree_it.node()
unique_tree<CEmployee>& unique_tree_node = *uniquetree_it.node();

Since element iterators expose the underlying node interface with the node() operation, it's very easy to insert nodes in other nodes using element iterators. Since many of the operations of nodes return element iterators themselves, element iterators are a handy way to do most of the insertions in the tree containers, as shown below.

tree_it.node()->insert(34);
multitree_it.node()->find("Mitch Jr");
multitree_it.node()->clear();
uniquetree_it.node()->find_deep(6456);
seq_tree_it.node()->insert("HaasJr");

The list below displays the tree/node operations available from iterator and const_iterator.

Incrementing/decrementing

• iterator operator ++()
const_iterator operator ++()
iterator operator --()
const_iterator operator --()
  The pre increment and decrement operators are all available to the child iterators.
  Complexity: Constant
• iterator operator ++(int)
const_iterator operator ++(int)
iterator operator --(int)
const_iterator operator --(int)
  The post increment and decrement operators are all available to the child iterators.
  Complexity: Constant

Equality/Inequality

• bool operator ==(iterator rhs)
bool operator !=(iterator rhs)
  The equality/inequality operators are available for both iterator and const_iterator. These operations check the equality/inequality of the iterators (iterator position). To be considered equal, two iterators must have the same parent node, and must point to the same child node.
  Complexity: Constant

Node access

• tree_type* node()
  Described briefly further above, this operation returns a pointer to the underlying node which the iterator is currently pointing to. All tree operations can be performed on this node object, because node objects are actually tree objects. For const_iterator this operation returns a pointer to const, for iterator this operation returns a plain pointer.
  Complexity: Constant
• store_type& operator *()
  As described above, the * operator returns a reference to the underlying element. For the const_iterator, this operator returns a const reference to the element, for iterator the operator returns a plain reference.
  Complexity: Constant
• stored_type* operator ->()
  Also described above, this operator returns a pointer to the underlying element. For the const_iterator, this operator returns a pointer to const, for the iterator the operator returns a plain pointer.
  Complexity: Constant

Additional operations for sequential_tree child iterators

Because sequential_tree child element iterators are random access iterators, they offer a few more operations than the associative tree bi-directional element iterators. These additional operations are exclusive to random access iterators, and are listed below.

• bool operator <(const const_sequential_iterator& rhs)
bool operator <=(const const_sequential_iterator& rhs)
bool operator >(const const_sequential_iterator& rhs)
bool operator >=(const const_sequential_iterator& rhs)
  Additional comparison operations for the iterators. Note, like with the STL, under most circumstances, the == and != operators of the iterators is advised to be used rather than the other comparison operators.
  Complexity: Constant
• const_iterator operator +=(size_type n)
iterator operator +=(size_type n)
  Adds n to the specified iterator. Caller must insure that the end result is within a valid range.
  Complexity: Constant
• const_iterator operator -=(size_type n)
iterator operator -=(size_type n)
  Subtracts n from the specified iterator. Caller must insure that the end result is within a valid range.
  Complexity: Constant
• difference_type operator -(const_iterator rhs)
  Subtracts one iterator from another. Caller must insure that the end result is in a valid range.
  Complexity: Constant
• friend const_iterator operator +(const_iterator lhs, size_type n)
friend const_iterator operator +(size_type n, const_iterator rhs)
friend iterator operator +(iterator lhs, size_type n)
friend iterator operator +(size_type n, iterator rhs)
  Adds n to the specified iterator and returns the result. Caller must insure the end result is within a valid range.
  Complexity: Constant
• friend const_iterator operator -(const_iterator lhs, size_type n)
friend iterator operator -(iterator lhs, size_type n)
  Subtracts n from the specified iterator, and returns the result. Caller must insure the end result is within a valid range.
  Complexity: Constant