Tree Container Library: General Overview

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. There have been a few attempts to design and implement generic tree container classes over the last decade. Most that I have found do not reflect the spirit and usage of the STL. The Tree Container Library (TCL), presented here, is my attempt to create a generic tree container library which works much like the STL. The latest version of the TCL can be downloaded from the TCL download page.

The TCL consists of three templatized container classes, similar to those found in the STL. These classes allow storage of basic data types or user defined types to be stored as nodes within a tree structure. Each node of the tree is considered a tree itself, having all the properties of a tree container. So, any 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 transversal of the tree nodes. Insert and find operations, as well as various other operations, are also provided.

The TCL provides three 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. Non-sibling nodes need not be unique. Because the tree can contain non-unique nodes, there is no find_deep() operation for tree containers.
  • multitree
    The multitree container is used for tree structures in which siblings need not be unique. As with the tree container, non-sibling nodes also need not be unique. The multitree, like the tree, does not offer the find_deep() operation.
  • 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.

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 much more features, since each node in the tree is unique. For example, the find() operation is available to all three tree containers, which searches for a matching 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. For example, all three trees offer the insert(child) operation, in which a child is inserted in the parent issuing the insert operation. The unique_tree offers an extension to this and other operations. So, the unique_tree provides another insert operation insert(parent, child), which inserts the child in the specified parent node (if found).

Like the STL, the TCL uses iterators in most of it’s operations. Not only can iterators be used to traverse the tree structures in various ways, many of the operations performed on the trees returns an iterator, such as the find() and insert() operations. The most common iterators in the library are the iterator and const_iterator. These iterators are created using the same syntax as iterators in the STL. If a tree container contains objects of the type CMyClass, an iterator would be created as tree<CMyClass>::iterator it;, or tree<CMyClass>::const_iterator it;. These two standard iterators traverse only a parents immediate children.

To traverse a parents descendants as well as it’s children, there are three more iterators provided, pre_order_iterator, post_order_iterator, and level_order_iterator. The creation of these iterators uses the same syntax as the standard iterators mentioned above.

Like the iterators of STL, the * and -> operators are overridden to return the ref/ptr to the underlying node. Because of this, the underlying node operations are available to the iterator, such as insert() and find(). All node's have the same interface as the declared tree with the node's reside. (remember, nodes are themselves trees). This is a very important concept in the TCL. Every node in a tree structure has the same operations of the tree itself, since nodes are in fact the same type as the declared tree it's in. 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).

This is my third attempt to develop a tree container library. Previous attempts have been somewhat successful for the project I was currently working on, but only this attempt is ready for open source use. I would like to give some credit to a couple of my past comrades, Brock Peabody and Mike Pace, for introducing me to the world of STL, templates, and generic programming. Also thanks to those who have given me help and suggestions from newgroups, in which some are mentioned in the version history.