Introduction
The Standard Template Library (STL) supplies C++ developers with many useful generic container classes. One type of container not found in the STL is the tree container. The Tree Container Library (TCL), presented here, is a generic tree container library which, not only works much like the STL, but is also compatible with the STL algorithms. This library and all examples presented 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 complete library is available in the source code download above. Also provided in the second download above is the complete documentation of the TCL, as a CHM file. This documentation includes hundreds of pages, and examples which clearly describe the usage of the TCL. A detailed explanation and example are given for every operation of each container in the TCL, and other examples (and the source code files) are included in the documentation.
The TCL consists of four container class templates, similar to those found in the STL. These containers 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 (or subtree) itself, having all the properties of the tree container which it's a part of. Thus, 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 in addition to those found tree and multitree.
- sequential_tree
The sequential_tree container is used for tree structures in which the tree nodes are not naturally ordered. Child nodes may be sorted after insertion, if desired. The sort order may be determined by a binary predicate, function object, or by default, the < operator of the element.
This simple class diagram below shows the relationships between the base classes and the value classes (tree container classes). basic_tree is the base tree for all tree containers, and includes basic operations common to all trees. sequential_tree derives directly from basic_tree. associative_tree also serves as a base class to the associative trees. This class contains operations common only to those trees, tree, multitree, and unique_tree.
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 than the tree and multitree, since each node in the tree is unique. For example, the find() operation is available for the 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.
In the TCL, iterators are used to traverse the breadth and depth of the tree containers. There are a couple different categories of iterators in the TCL. The main way to categorize the iterators is by the way they iterate over the nodes in the trees. In this respect, there are four types of iterators, listed below.
- Child Iterators
Used to iterate over the immediate children of a node.
- Reverse Child Iterators
Used to iterate over the immediate children of a node in reverse order.
- Descendant Iterators
Used to iterate over the descendants of a tree or subtree. The descendant iterators traverse the breadth and depth of a tree/subtree. There are three popular methods for traversing a tree structure, and three types of descendant iterators to provide these traversals:
- Pre Order
In this traversal, the parent node is visited first, followed immediately by any children of that node, from left to right.
- Post Order
In this traversal, all children are visited first from left to right, then the children's parent.
- Level Order
In this traversal, each level of the tree structure is visited in order, from top to bottom.
- Ordered Iterators
These iterators are available only for unique_tree. They offer an alternate ordering scheme for the child nodes within their parent.
The TCL iterators can also be categorized by what they expose. To understand this concept, a good understanding is needed to differentiate between a 'node' and an 'element'. In the TCL, a node is considered to part of the tree structure itself. A node is used to contain the data, or elements, in the tree container. Each node in a tree structure has the same property of the tree itself. In fact, any operation which can be performed on the tree structure can also be performed (with a few exceptions) on any node in the tree structure. The nodes are in fact, subtrees within the structure.
Elements, on the other hand, are the data which is stored in the tree container. Each node in the tree structure contains an element. You decide what the elements will be in your own tree structures. The elements can be a basic type, such as and int or double, or can be a user defined type.
Now, the child, reverse, and descendant iterators all come in two varieties, which depends on what the iterators expose. Both iterator types iterate in the same fashion. The only difference is what is returned by the iterators dereference operator and pointer operator.
- Element Iterators
Element iterators return a pointer/reference to the underlying element, with the -> and * operators, respectively.
- Node Iterators
Node iterators return a pointer/reference to the underlying node, with the -> and * operators, respectively.
The child, reverse, and descendant iterators all come in the two varieties listed above. Thus, the TCL provides child 'element' iterators, reverse 'element' iterators, descendant 'element' iterators, and also child 'node' iterators, reverse 'node' iterators, and descendant 'node' iterators.
Normally, you will use the element iterators for most of your needs. The child element iterators are those that the TCL uses as return values from many of it's operations, like find(). These iterators are used so much more than the node iterators, that they are not given an element prefix, like the node iterators and operations are given.
And, of course, all the iterators come both the const and non-const varieties.
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 child 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.
Both 'child' and 'descendant' iterators can be used with the STL algorithms, as well as both 'element' and 'node' iterators. 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). 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).
Points of Interest
In developing this library, I learned about the difficulties encountered when developing container classes. Looking through the implementation of STL gave me many of the ideas I needed to develop this library.
History
The latest version (4.08) of the TCL has all tree containers enclosed in the namespace 'tcl'.
More information on the design and operations, can be found here.
