The Tree Container Library

The descendant node iterators, pre_order_node_iterator, const_pre_order_node_iterator, post_order_node_iterator, const_post_order_node_iterator, level_order_node_iterator, and const_level_order_node_iterator were introduced to the TCL with version 4.00. These iterators were introduced as a necessity for working with particular STL algorithms, as described below.

The descendant node iterators are almost identical in operation to the descendant element iterators. The primary difference between the two types is that the descendant node iterators expose the underlying node, while the descendant element iterators expose the underlying element. This means that the * and -> operations of the descendant node iterators return a pointer and reference (respecitively) to underlying node, or tree_type object. The descendant element iterator, on the other hand, returns a pointer and reference to a dfn>stored_type object, which is the element which resides in the node.

The signatures of these two operators are as follows.

• tree_type& operator *()
  As described above, the * operator returns a reference to the underlying node. For the const_node_iterator, this operator returns a const reference to the node object, for node_iterator the operator returns a plain reference.
  Complexity: Constant
• tree_type* operator ->()
  Also described above, this operator returns a pointer to the underlying node. For the const_node_iterator, this operator returns a pointer to const, for the iterator the operator returns a plain pointer.
  Complexity: Constant

The only other difference between the two types of iterators, is that the node() operation is not available to the descendant node iterators. Since the descendant node iterators expose the node with the dereference and pointer operators, there is no need for a node() operation.

Just as the descendant element iterator has access to the underlying node with the node() operation, the descendant node iterators can access the underlying element, with the node's get() operation. Note that this is an operation of the node, or tree_type, not an operation of the descendant node iterator.

Except for the differences described above, the descendant node iterator perform identically to the descendant element iterator, so see the discussion on the descendant element iterator for information on the descendant node iterator.

The reason for introducing the descendant node iterator in version 4.00, is to be able to use the descendant node iterators for particular STL algorithms. Certain STL algorithms, such as std::remove() need an iterator which exposes the underlying node rather than exposing the underlying element, to work properly. Other STL algorithms can take either type of iterator, but will behave differently depending on the type of iterator used.

The operations below, which are available for all four trees in the TCL, allow you to obtain a descendant node iterator from any node.

• pre_order_node_terator pre_order_node_begin()
const_pre_order_node_iterator pre_order_node_begin() const
  Returns a descendant pre-order node iterator which points to the first pre-order descendant of the node in which it's called. If the node which the operation is called has no children, returns pre_order_node_end().
  Complexity: Constant
• pre_order_node_iterator pre_order_node_end()
const_pre_order_node_iterator pre_order_node_end() const
  Returns a descendant pre-order node iterator which points the the pre-order open end of the descendant nodes.
  Complexity: Constant
• post_order_node_terator post_order_node_begin()
const_post_order_node_iterator post_order_node_begin() const
  Returns a descendant post-order node iterator which points to the first post-order descendant of the node in which it's called. If the node which the operation is called has no children, returns post_order_node_end().
  Complexity: Constant
• post_order_node_iterator post_order_node_end()
const_post_order_node_iterator post_order_node_end() const
  Returns a descendant post-order node iterator which points the the post-order open end of the descendant nodes.
  Complexity: Constant
• level_order_node_terator level_order_node_begin()
const_level_order_node_iterator level_order_node_begin() const
  Returns a descendant level-order node iterator which points to the first level-order descendant of the node in which it's called. If the node which the operation is called has no children, returns level_order_node_end().
  Complexity: Constant
• level_order_node_iterator level_order_node_end()
const_level_order_node_iterator level_order_node_end() const
  Returns a descendant level-order node iterator which points the the level-order open end of the descendant nodes.
  Complexity: Constant