The Tree Container Library

tree<> and multitree<> are almost identical in operation and implementation. The main difference between the two is that tree uses a std::set to contain child nodes, while multiset uses std::multiset. The following explanation applies to both tree and multitree. In fact, if you compare the declarations of tree and multitree side by side, you will see that they are almost exactly alike, if you substitute tree for multitree, and set for multiset.

The first bit of code in tree.h and multitree.h, is a forward declaration for tree/multitree, which is for the function object that follows. The following function object is used for a comparison operation which compares two pointers to tree/multitree nodes. This comparison operator will be used for the internal container which will store child nodes. This container is a member of basic_tree, called children. The functor overloads the call operator, passing two arguments which are pointers to the tree_type. The call operator simply dereference's the pointers, and compares the stored_type object in the nodes. This function object is used in the third template parameter of the base class (basic_tree) derivation declaration, discussed immediately below.

The declaration of tree/multitree takes two template parameters. The first template parameter, stored_type, defines the object type which will be stored in each node in the tree. The second template parameter, node_compare_type, provides the comparison operation to be used to compare two nodes, or rather, the stored_type within two nodes. It's this operation which determines the order of the child nodes within their parent As shown in the declaration, this second template parameter, if not provided, defaults to std::less<stored_type>. For basic types, (int, double, long) the less than operator is already defined. For user defined types, (classes, structs), you must define this operation by overloading the less_than (<) operator for the class.

The interesting part of the class declaration is the derivation declaration.
Both tree and multitree derive publicly from associative_tree. associative_tree takes three template parameters, supplied by tree and multitree.

• stored_type
  The stored type which is the first template parameter for tree and multitree is passed on as the first template parameter for associative_tree, and then to basic_tree.
• tree<stored_type, node_compare_type> for tree
  multitree<stored_type, node_compare_type> for multitree
  This is the actual fully specified tree/multitree, to inform associative_tree and basic_tree the type of class that is deriving from them.
• std::set<tree<stored_type, node_compare_type>*, tree_deref_less<stored_type, node_compare_type> > for tree
  std::multiset<multitree<stored_type, node_compare_type>*, multitree_deref_less<stored_type, node_compare_type> > for multitree
  This is the third template parameter for basic_tree. It defines the container used to store the child nodes. As shown, the container is a set for tree, and a multiset for multitree. There are two internal template parameters in these declarations for set and multiset. The first parameter for the container is the element type for the set/multiset, and the second template parameter is the comparison operation to be used for the container, which is the comparison operation function object discussed further above.

Inside the tree/multitree declaration, a few typedefs are first encountered. The first typedef declares itself, the fully specified tree_type, (tree or multitree). The second and third typedef, declare key_compare and value_compare for STL container compatibility. The forth typedef declares the fully specified basic_tree type, basic_tree_type, which is the final base class. The fifth typedef declares the fully specified associative_tree type, which is the immediate base class. The next line declares the base class, basic tree, to be a friend class.

The constructors and destructor are declared next. The first (default) constructor delegates to it's immediate base classes (associative_tree) default constructor. The second constructor takes a reference to a stored_type object, which is forwarded to associative_tree, which forwards it to basic_tree, which it uses to initialize the stored_type pointer, pElement, for the node. The third constructor is the copy constructor. The destructor is very simple, and merely calls the clear() operation.

The assignment operation (=) is defined next, and is implemented in the accompanied inl file. The public interface to the class is then defined. It is implemented in the inl file. The public interface is very small, since most of the interface is declared and defined in the base classes. The interface operations include a number of insert operations and the swap() operation. The insert operations are very simple, as they all delegate to associative_tree. The swap() operation is also very simple, and is implemented in the inl file.