The Tree Container Library

The Standard Template Library (STL) supplies C++ developers with many useful generic container classes. One type of container not found in the STL the tree container. The Tree Container Library (TCL), presented here, is a generic C++ tree container library which, not only works much like the STL, but is compatible with the STL algorithms and other STL containers. The latest version of the TCL can be downloaded from the TCL download page. The library and all examples are compatible with VC6, VC7, and VC8 (Visual Studio 2005), as well as gcc. Most other C++ compilers should have no problems with the library, if they are compliant with C++ template standards.

The TCL consists of four template container classes, similar to those found in the STL. These classes allow storage of basic data types or user defined types to be stored within nodes in a tree structure. Each node of the tree is considered a tree itself, having all the properties of the tree container that it's a part of. So, all operations which can be performed on the tree container can likewise be performed on any node within the tree. Iterators are provided to allow the traversal of the tree nodes. Insert and find operations, as well as various other operations, are also provided.

The TCL provides four tree containers which differ according to their intention of use:

• tree

  The tree container is used for tree structures in which every sibling node is unique, or rather, every child node of a particular parent can be uniquely distinguished. Non-sibling nodes need not be unique.

• multitree

  The multitree container is used for tree structures in which siblings need not be unique, or rather, children which have the same parent node need not be distinguishable.

• unique_tree

  The unique_tree container is used for tree structures in which every node in the tree is unique. Because every node in the tree is guaranteed to be unique, the unique tree offers a find_deep() operation, as well as other operations different from tree and multitree.

• sequential_tree

  The sequential_tree container is used for tree structures in which the tree nodes remain in the same order in which they are inserted. Any or all nodes may later be sorted, by using a binary predicate, function object, or < operator of the element.

The tree and multitree are very similar in operation and interface. The difference between the two is much like the difference between the set and multiset in the STL. The unique_tree offers many more features, since each node in the tree is unique. For example, the find() operation is available to tree, multitree, and unique_tree, which searches for a matching child node contained within a single parent node. The unique_tree offers an additional operation, find_deep() which not only searches the parent node's immediate children, but also searches it's descendants.

The unique_tree also offers extensions to the common interface for the three tree types. All four trees offer the insert(child) operation, in which a child is inserted in the parent issuing the insert operation. The unique_tree, however, offers an extension to this and other operations. For example, the unique_tree provides another insert operation, insert(parent, child), which inserts the child in the specified parent node (if found).

tree, multitree, and unique_tree are considered associative tree containers, since they all use std::set for internal child node containment. sequential_tree, however, uses a std::vector to store the child nodes. Thus, sequential_tree does not offer find() operations like the associative tree containers do. sequential_tree has it's own unique operations, however, like multiple sort() operations which can be used to sort any/all of the child nodes within their parent. The associative trees do not need sort() operations, because their nodes are ordered naturally.

To understand the structure of the tree containers in the TCL, and how the iterators work, a good understanding is needed for the concept of a node and an element. In the TCL, the term node is used to refer to an object in a tree structure which contains the stored_type element. The stored type element (elements of which you are storing in the tree) is not considered the node itself, but is contained within the node. The tree structure is, then made up of nodes, with the top node being the root node. All nodes in the tree structure (with a couple exceptions) have the same operations and properties of the tree itself. The concept of an element is to specifiy the stored_type object which is being stored within the nodes of the tree. The node and element are considered as two seperate entities. The tree structure consists of nodes. Nodes can likewise have child nodes, and those can also have their own child nodes. The elements reside in the nodes, and are the objects which the user has specified to store in the tree.

Like the STL, the TCL uses iterators in many of it’s operations. TCL iterators can be catagorized in multiple ways. For all iterators, there are the const and non-const varieties. Another way TCL iterators can be categorized, is by their traversals. child iterators are the most common type of iterators in the TCL, and traverse only the immediate children of a given parent node. There are also child reverse iterators available, which traverse in a reverse direction over the immediate children of a parent node. For traversing both breadth and depth of a tree container, there are descendant iterators available, for pre-order, post-order, and level-order traversing. The unique_tree also offers a special ordered_iterator to traverse the child nodes in an alternately defined order. The final way in which the TCL iterators can be categorized is by what they expose. In this respect, there are two types of iterators available, the element iterators, more commonly refered to as just iterators, and the node iterators. The element iterators expose the underlying element, while the node iterators expose the underlying node. Normally, the most common type of iterators used in the TCL are the element iterators. In all discussions in the TCL documentation, if the distinction is not made to element iterators or node iterators, then the element iterators is assumed. When the term iterator is used in the documentation, it could be used to represent all iterator types, only child iterators, or only child element iterators, depending on the context.

Not only can iterators be used to traverse the tree structures in various ways, many of the operations performed on the trees return an iterator, such as the find() and insert() operations. These iterators that are returned from many of the TCL tree container operations are normally chiild element iterators, unless clearly named to specify otherwise. All iterators are created using the same syntax as iterators in the STL. If a tree container contains objects of the type CMyClass, a child element iterator would be created as tree<CMyClass>::iterator it;, or tree<CMyClass>::const_iterator it;. These two child iterators traverse only a parents immediate children.

To traverse a parents descendants as well as it’s children, there are 12 descendant iterators provided, pre_order_iterator, post_order_iterator, level_order_iterator, and their node iterator counterparts, pre_order_node_iterator, post_order_node_iterator, and level_order_node_iterator. Each of these six iterators also have a const variety. The creation of these descendant iterators uses the same syntax as the child iterators mentioned above.

Both child and descendant iterators can be used with the STL algorithms, as well as both element and node iterators. (see STL Compatibility.)
This means that the elements, which reside in the nodes of the tree containers can be copied back and forth between containers in the STL using the element iterators. The nodes can be copied back and forth between containers in the STL using the node iterators. Also, virtually any STL algorithm can now be used with TCL tree containers and iterators. When used with the STL algorithms, it must be clear that the TCL element iterators expose the node's elements, while the node iterators expose the nodes.

As mentioned above, for the element iterators, the * and -> operators are overridden to return the reference/pointer to the underlying element within the node to which the iterator points. All element iterators also have a node() operation, which returns a pointer to the underlying node which contains the element. By using the element iterator's node() operation, the node's operations, such as insert() and find() are available to the element iterator. Remember that nodes have the same interface as the declared tree in which the nodes reside. (Nodes are themselves trees, or actually subtrees). The only difference between a declared tree container and one of it's nodes, is the simple fact that the declared tree container doesn't have a parent node. (It's the root node).

I would like to give some credit for the success of this library to a couple of my past comrades, Brock Peabody and Mike Pace, for introducing me to the world of STL, templates, and C++ generic programming. Also thanks to those who have given me invaluable help and suggestions, in which some are mentioned in the credits.