The Tree Container Library

Using the Tree Container Library (TCL) is much like using the container classes in the STL. The syntax and operation is very similar. First, you will need to decide which of the four tree containers will fit your needs. The difference between the tree containers is described in the overview.

The tree and multitree both accept two template arguments, the second being optional. The first template parameter represents the data type you will be storing in the container, hence forward called the stored_type. The stored_type can be either a basic data type, such as an int or a string, or a user defined type (class). Objects of stored_type are considered as elements, which are stored within the nodes of the tree. The second template parameter represents the node comparison operation, a functor, used in the searching and ordering of the nodes, hence forward called the node_compare_type. If not supplied, this template parameter defaults to std::less<stored_type>. So, if the container stores a basic type such as int's, the node_compare_type will default to std::less<int>. If the container stores class objects, then you could either supply a < operation for the class which would be used when the node_compare_type defaults to std::less<stored_type>, or, create and use a functor for the second parameter.

The unique_tree accepts three template arguments, the last two being optional. The first two template parameters are the same as with the tree and multitree described above. The third template parameter represents another node comparison operation, called the node_order_compare_type which is used for special iterators called ordered_iterators which can be used to determine an alternate ordering of nodes within their parent. An alternate ordering for child nodes can be handy if the comparison operation used to distinguish unique nodes within the unique_tree is not the desired ordering you wish to be used to traverse child nodes within a single parent.

The sequential_tree accepts a single template argument, which is required. This parameter represents the data type you will be storing in the container, stored_type, discussed above. Since this container does not naturally order the nodes within their parent, there is not a node_compare_type that is needed for sequential_tree. The nodes remain in the order in which they were inserted into the tree. This container does, however, offer sorting operations for any or all of the nodes, so the order of the nodes can be changed if desired.

Given the above information, the following are simple declarations of the four tree containers:

• tree<std::string> my_tree;
• multitree<int> my_tree
• unique_tree<CMyClass> my_tree;
• sequential_tree<std::string> my_tree;

#include "tree.h"
#include "multitree.h"
#include "unique_tree.h"
#include "sequential_tree.h"
#include <string>
class CMyClass
{
public:
  CMyClass() : key(0) {} // needs default constructor
  CMyClass(int key_, const std::string& text_)
    : key(key_), text(text_) {}
    const std::string& get_text() const { return text; }
    friend bool operator <(const CMyClass& lhs, const CMyClass& rhs)
    {
      return lhs.key < rhs.key;
    }
private:
  int key;
  std::string text;
};
struct CAltKey
{
  bool operator()(const CMyClass& lhs, const CMyClass& rhs)
  {
    return lhs.get_text() < rhs.get_text();
  }
};
int main(int argc, char* argv[])
{
  using namespace tcl;
  tree<CMyClass> my_tree;
  multitree<CMyClass, CAltKey> my_multi_tree(CMyClass(0, "Root"));
  unique_tree<CMyClass, std::less<CMyClass>, CAltKey> my_unique_tree;
  sequential_tree<CMyClass> my_sequential_tree;
  return 0;
}

The usage of class objects in the trees is shown to the right. Here, objects of the class, CMyClass, will be stored in the tree containers. Notice that MyClass defines a < operator, which is used by the default std::less<> parameter for the associative trees. This operation will be used by the default (or explicitly supplied) std::less<> parameter. If a < operation is not defined for the class, then an explicit comparison functor must be declared and supplied for the second template parameter for the associative trees.

Notice in the sample code, that the tree declaration provides no second parameter, so the < operator will be used for node comparisons. In the multitree declaration, CAltKey is supplied for the second parameter, which will be used for the node comparisons. In the unique_tree declaration, both the second and third template parameters are supplied. The second template parameter, node_compare_type is just std::less<CMyClass>, which is the default. Since the third parameter is being explicitly supplied, the second parameter must also be explicitly supplied, even though it is the default value. The third parameter supplies the comparison CAltKey which can be used to iterate the nodes within a parent in an alternate order. The sequential_tree needs no comparison operation. However, since a < operation is defined for CMyClass, this comparison operation will be used for sequential_tree's sort() operation if sort() is not supplied a parameter.

Note that in the declaration of the multitree, a newly created element is passed to the constructor. This will set the element of the root node. Normally, an element is supplied to a node during an insert operation, but the root node must have it's element set via the constructor.

Creating an iterator for the containers is much like creating an iterator for STL containers. Iterators are used for more than just iterating over the nodes in the trees. Indeed, the find(), insert(), and other operations return a child iterator. There are three types of iterators in the TCL.

• child iterators
  child iterators are available for all three tree containers. They iterate only over the children of the specified node. Child iterators traverse the breadth, not depth of the specified node.
• descendant iterators
  descendant iterators are also available for all three tree containers. Descendant iterators iterate over the breadth and depth of a specified node, and come in three flavors.
  • pre order iterator
  • post order iterator
  • level order iterator.
  Descendant iterators behave a little different then child iterators, in the fact that they traverse the called, or top node. If the called node is the root node, the descendant iterators will iterate over all the nodes in a tree structure.
• ordered iterators
  ordered iterators are available only for unique_tree. They offer an alternate order in which to traverse the children of a specified parent node.

It's helpful to think of the elements as being stored in the nodes of the trees, rather than actually being the nodes. The nodes are themselves trees of the same type, and have the same interface as trees, for finding, searching, removing, iterating, etc. The element in any node can be retrieved with the node's get() operation. This tree/node operation returns a pointer to the element contained within. All elements are created on the heap internally when inserted into the tree.

With tree, multitree, and sequential_tree, nodes must be inserted using the insert(child) operation on the parent node for the child. So, for these trees, you must have a pointer, reference, or iterator pointing to a node, before you can insert any child nodes into that node. For unique_tree, this is not the case. For unique_tree, you can insert any child node into any parent node from the root node, using the insert(parent, child) operation available only to unique_tree.

The TCL allows for polymorphic storage without the need to store pointers in the tree container. This means that you can store elements of stored_type and elements derived from stored_type, and those objects will keep their original identity. To do this, you must supply a clone function to the tree container. The container uses the clone function to copy the stored_type or objects derived from stored_type, rather than using the stored_type copy constructor. More information on this subject, as well as the standard operations for using the trees are given in Common Interface.