The Tree Container Library

The ordered iterators are used only for unique_tree, and allow the traversal of child nodes in an alternate order than the standard order. They are declared/defined in ordered_iterator.h/inl. Like the child and descendant iterators, there is a const and non-const variety of the ordered iterators.

• const_unique_tree_ordered_iterator
• unique_tree_ordered_iterator

The ordered iterators are template classes, like the child and descendant iterators. The ordered iterators accept the same three template parameters as are specified for unique_tree. Also like the child and descendant iterators, the ordered iterators are declared in the value class (in this case, unique_tree) using typedefs. The following typedef declarations declare the ordered iterators in unique_tree.

typedef const_unique_tree_ordered_iterator<stored_type, node_compare_type, node_order_compare_type> const_ordered_iterator;
typedef unique_tree_ordered_iterator<stored_type, node_compare_type, node_order_compare_type> ordered_iterator;

The ordered_iterators work much like the child iterators. The main difference is that while the child iterators iterate over the main container which holds the child nodes (children), the ordered iterators iterate over an alternate container, ordered_children, which is a member of unique_tree. This container contains pointers to the child nodes. Although this set container, ordered_children, will contain the same child pointers which are contained in basic_tree's children member, ordered_children does not manage the pointers. So, unique_tree must insure that when ever a node is inserted, and a new node is created and it's pointer is inserted into basic_tree's children, that same pointer is inserted in unique_tree's ordered_children. unique_tree must also insure that when nodes are deleted and the pointers removed from basic_tree's children, the pointers are also removed from ordered_children. Note that ordered_children is defined as a multiset, rather than set. At first consideration, this may seem odd, since the unique_tree must maintain that every node in the tree is unique. This is only true, however, for the node_compare operation, which is the standard comparison operation. ordered_children uses an alternate ordering mechanism, so it is possible than every node not be unique in this alternate ordering.

The ordered iterators are driven by a single data member, which is a multiset iterator for the container ordered_children. All operations in the ordered_iterator classes delegate to this member. The main thing to remember in how the ordered iterators work, is that the ordered_children container in unique_tree always maintains the same pointer elements as those contained in basic_tree's children, but may be in a different order, dictated by the third parameter for unique_tree.