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:
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
The unique_tree also offers extensions to the common interface for the three tree types. For example, all three
trees offer the
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
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
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.