The Tree Container Library

The associative_tree was created to give the three associative_trees a common class from which to derive, to offer a common interface for operations specific to associative trees. associative_tree inherits from basic_tree, and simply forwards the template parameters it receives from it's derived value classes to basic_tree. All three associative tree value classes, tree, multitree, and unique_tree are then derived from associative_tree. These value classes pass the appropriate template parameters to associative tree.

The associative_tree defines an interface particular only to the associative trees. This interface includes operations which can only be performed on tree containers which use an STL associative container (set or multiset) to contain the child nodes. The child_iterators and descendant_iterator for the associative tree value classes are also declared (via typedefs) in associative_tree.

In the following discussion, please refer to the source code in associative_tree.h.
Associative tree is a class template much the same as basic_tree. It accepts three template parameters, which are the same template parameters for basic_tree. associative_tree then uses these three template parameters in the declaration of it's derivation of basic_tree. In effect, it 'passes through' it's template arguments to basic_tree.

associative_tree first makes a typedef, for convenience, of the fully specified basic_tree, basic_tree_type. It then defines two constructors and a destructor. The first constructor is a default constructor, and the second accepts a reference to a stored_type, which it delegates to basic_tree's constructor. The destructor performs no needed action. Both constructors and destructor are given protected access, since there is no reason for users of the library to instantiate an instance of this class.

The next line in the class declaration creates a typedef, for convenience, of itself. Then, two typedefs are provided for size_type and key_type, to insure STL container comparability. Next, three friend declarations are provided for the three const descendant iterators. These friendship operations are needed by the descendant iterators to allow them access to specific protected and private operations in associative_tree.

Next, as mentioned further above, typedef's are supplied to define the child and descendant iterators for associative_tree (and it's derived value tree container classes). These typedefs are as follows:

typedef const_associative_iterator<stored_type, tree_type, container_type> const_iterator;
typedef associative_iterator<stored_type, tree_type, container_type> iterator;
typedef const_pre_order_descendant_iterator<stored_type, tree_type, container_type, associative_tree_type> const_pre_order_iterator;
typedef pre_order_descendant_iterator<stored_type, tree_type, container_type, associative_tree_type>  pre_order_iterator;
typedef const_post_order_descendant_iterator<stored_type, tree_type, container_type, associative_tree_type> const_post_order_iterator;
typedef post_order_descendant_iterator<stored_type, tree_type, container_type, associative_tree_type> post_order_iterator;
typedef const_level_order_descendant_iterator<stored_type, tree_type, container_type, associative_tree_type>  const_level_order_iterator;
typedef level_order_descendant_iterator<stored_type, tree_type, container_type, associative_tree_type> level_order_iterator;

Following these typedef declarations, are the child and descendant iterator accessors for begin() and end().

Next, the public interface is provided for associative trees (and it's derived tree value classes). I will not go into detail of the implementation of these operations here. The code is apparent for most of these operations, and if not already provided, and code comments are provided to detail implementation which may not be apparent. I would like to mention, however, that the operations provided in the interface of associative_tree are those which are required to meet standard STL associative container requirements.