The Tree Container Library

The child iterators are declared and defined in child_iterator.h. All operations of the child_iterators are defined inline. The first pair of iterators

• const_associative_iterator
• associative_iterator

are used by the associative trees. The last pair of iterators,

• const_sequential_iterator
• sequential_iterator

are used by sequential_tree.

The declaration of all the child iterators accept three template parameters, which are the same three template parameters accepted by associative_tree and basic_tree.

• stored_type
  This is the same first template parameter specified for all the tree container value classes. This type parameter informs the child iterators the stored_type which is stored in the nodes.
• tree_type
  This is the fully specified derived value class type. It can also be considered the node type.
• container_type
  This template parameter is used to specify the storage container used to store children in each node.

The first child iterator to be declared is const_associative_iterator, used for the associative trees. It derives from std::iterator<std::bidirectional_iterator_tag, stored_type>, which gives it properties of a bi-directional iterator pointing to stored_type's. This in part, helps to make const_associative_iterator compatible with STL algorithms and other STL containers. const_associative_iterator contains two data members, the first member is declared as below:
typename container_type::const_iterator it

This data member is a STL iterator which will point to elements in basic_tree's member, children. children is a STL container (set, multiset or vector) which contains the child nodes for a particular node object. The second data member, pIt_parent, is a pointer to the parent node of the iterator. It is needed when testing two iterator objects for equality. To test two iterator objects for equality, the iterator's first data member, the STL iterator, are compared. Since testing two STL iterators from different containers is undefined, basic_tree's iterator must first check the STL iterator's parent, pIt_parent, for equality before checking the STL iterators for equality.

At the top of the declaration for const_associative_iterator, associative_tree, and basic_tree are declared as friends, which will allow them access to the const_associative_iterator's two data members mentioned above. The constructors for const_associative_iterator follow. A default constructor is defined which lets users create iterators without supplying an argument. Another constructor is defined which accepts a (set, multiset, or vector) STL const_iterator as the first parameter, and a pointer to the parent node as the second parameter. This constructor is used by two operations in associative_tree, begin() and end(), which return a const_associative_iterator. The destructor, copy constructor, and assignment operation perform no specific actions, so are not declared to let the compiler generate them by default.

We now come to the overloaded operators for const_associative_iterator. The equality operator is defined, which first checks if the parent node is the same for the iterators being compared. If the parent is the same, then the STL iterator members can be compared. The inequality operator is defined with the uses the equality operator. The operators * and -> operators delegate the operations to the it member variable. Since the STL iterator, it, points to STL container elements which are pointers to nodes, (or trees), the get() operation is performed on the underlying node to return a pointer to the element in that node. For the * operator, the stored_type pointer is dereferenced. The increment and decrement operators are then defined. They simply increment/decrement the data member, and return a self reference.it.

The public interface for const_associative_iterator contains only one function:
const tree_type* node()
This function returns the pointer to the underlying node object which const_associative_iterator points to.

Next comes the definition of the class, associative_iterator. Since it's derived from const_associative_iterator, associative_iterator is able to inherit a few of the operations in const_associative_iterator. It must overload some of them, however, so it can return non-const objects instead of const object that const_associative_iterator returns. Since it's derived from const_associative_iterator, it is also a bi-directional iterator.

The declarations for sequential_tree's child iterators are much the same as the child iterators for associative_tree described above. Only the differences will be discussed.

In const_sequential_iterator, the first difference from const_associative_iterator, is that it is derived from std::iterator<std::random_access_iterator_tag, stored_type>, as this is a random access iterator, rather than a bi-directional iterator. Next, a typedef for difference_type is declared. Because of differences in compilers, this typedef is declared conditionally according to compiler.

The constructors in sequential_tree_iterator are much like the ones in const_associative_iterator. As in const_associative_iterator, the destructor, copy constructor, and assignment operator are not defined, and left for the compiler to define by default. Unlike const_associative_iterator, const_sequential_iterator defines all comparison operators, not just < and ==. The overloaded * and -> operators are defined like they are in const_associative_iterator.

The next group of arithmetic operators are also what distinguishes const_sequential_iterator from const_associative_iterator. These operations are simply defined inline, and are required to make the sequential_tree iterators true random ordered iterators.

Finally, sequential_iterator is defined, which inherits from const_sequential_iterator.