The Tree Container Library
A C++ generic tree container library which, not only works much like the STL, but is also compatible with the STL algorithms. The Tree Container Library is used worldwide in thousands of industries and organizations. It is completely free to use, and is licensed under the zlib/libpng license.
The purpose of this page is threefold.
- To give much deserved credit to those that have contributed to the TCL.
- To document the current and past focus of issues and needed changes.
- To show TCL users the latest direction and expected changes in the TCL.
The TCL would not be where it is now without the suggestions, insight, corrections, and hard work from other developers. I'll try my best to list their contributions on this page, and also in the credits page. I'll also try to keep this page updated with the current focus of the TCL, and expected changes and enhancements you can expect.
| April 2, 2008 |
Version 5.1.0 sees many changes to all iterator class templates in the TCL. The first changes is that there are no longer two separate classes
for const and non-const varieties of the iterators. Using a technique from Matt Austern, the const type information is passed to the class
templates as a template parameter. This avoids many of the awkward const_casts which were needed for the non-const variety which
was derived from the const variety. Another major change is the addition of a base() operation for the descendant iterators, which
returns a child iterator pointing to the same element/node. This operation will be very useful, since many operations in the TCL require a
child iterator, and previously, there was no easy way to obtain a child iterator from a descendant iterator. The need of this operation became
apparent with conversations from Neville Franks, who has offered many good suggestions for the TCL.
|
| Jan 1, 2008 | In December of 2007, Adrian Secord contacted me regarding a const correctness issue with the dereference operators in the iterators. Adrian had made contributions earlier in the year to the TCL, and after looking into the matter, discovered he was correct with this finding. He also discussed how the descendant iterators were not working as expected, as it is standard practice for descendant tree iterators to traverse the called, or top, node of the traversal. Doing some research on my own, I soon found out that Adrian was correct in this regards also. Since this change will affect the behavior of the descendant iterators, I was a little hesitant on making the change at all. Adrian suggested making this change a major version change (from 4 to 5) warning current users of the changed behavior. Taking Adrian's advice on this matter also, the new version is a major revision, and labeled version 5.0.3. Current users are advised that the descendant iterators have changed in behavior, in that they now visit the top node, or node which created the descendant iterator. More specifically, the pre_order_iterator and level_order_iterator will be positioned on the called node initially, and the post_order_iterator will be positioned on the called node just before reaching the end of it's traversal. Another impact of this change is that there will always be at least one node/element visited in a descendant iterator traversal. Previously, calling a descendant begin() operation could return descendant end() if the called nodes contained no children, but that isn't the case any longer. If the called node has no children, and a descendant begin() is called on that node, a valid iterator will still be returned, pointing to the called node. Current users of the TCL which use the descendant iterators may need to modify their code to comply with the new behavior in all library versions going forward. |
| Jan 11, 2007 |
Version 4.00 of the TCL has just been released. This major version introduces the concept of the node iterator.
Earlier in the design of the TCL, I encountered a design dilemma, with the problem of deciding if the various iterator types
should expose the underlying element
or expose the underlying node.
I decided to have the all the iterators, child, reverse, and descendant expose the underlying element,
as it was more natural to iterator behavior, and more compatible with what the STL algorithms expect. There are some STL
algorithms, however, which require that the underlying node be exposed rather than the underlying element,
such as the standard algorithm std::remove(). To make the TCL even more compatible with the STL algorithms,
and to give the TCL more versatility, the concept of node iterators is introduced. The normal iterator types,
now known as element iterators are still available and use the same interface and syntax. In addition to the element
iterators, there will be node iterator counterparts. The node iterators and accessors will have the same name as their
element iterator counterparts with a 'node' prefix. For example, node_iterator is the node iterator counterpart
of iterator, pre_order_node_iterator is the counterpart of pre_order_iterator,
post_order_node_begin() is the counterpart of post_order_begin(), etc. With this major release,
all backwards compatibility to the normal element iterators and tree containers is maintained. There is also an updated
TCL test suite with also tests the new mode iterators.
|
| July 27 2006 | Version 3.50 of the TCL has just been released. Unlike previous releases, this release isn't quite backwards compatible with previous versions. The interface to the tree containers themselves has not changed, only the design and interface of the iterator classes. For all iterators, the */-> operations now return a reference/pointer to the underlying stored_type object. Previously, these operations returned a reference/pointer to the underlying tree_type. Changing the interface of all iterators was a decision that I did not take lightly, since many TCL users might have to modify their code for it to remain compatible with the latest version. If it were possible to support both earlier versions and the needed change to the iterators, I would have done that, but the only way to implement the needed changes involved changing the iterator interface. There are two main reasons for the change: STL compatibility, and conformance. To be compatible with the STL algorithms, the iterator classes need to have the */-> operators return a reference/pointer to the underlying stored_type object within the node. This is especially true for STL generic copy() operations and range insertion operations. Having those iterator operations return stored_type ref/ptr allows the STL algorithms to copy/insert stored_type objects, not tree_type objects. Also, all STL algorithms will perform on stored_type objects rather than tree_type objects, which is the norm. Previously, when those iterator operations returned a ref/ptr to the underlying tree_type object, performing a stl::copy() operation to an STL container would copy tree_type objects to the STL container, rather than the desired stored_type objects. Copying tree's tree_type objects to a STL container would cause problems, because most of the object's operations would not be applicable or make sense in a linear container, such as parent(), begin(), end(), or any other child node operations. This is because the tree_type elements in the STL container would no longer have children or parents. The only solution to this problem was to change the design of the iterator classes, and have their */-> operations return a ref/ptr to the underlying stored_type object, which resolves all these issues when using the iterators with STL algorithms. I hope that changing the iterator interface does not cause too much hardship on current users of the TCL. Please feel free to email me with any questions, concerns, rants, or suggestions. |
| July 7 2006 |
Having completed and stabilized TCL's sibling project xhtml_gen, I'm turning
my attention again to the TCL. Expect a major version release (3.00) sometime this month. This new version of the TCL
will be mostly STL compatible. STL compatibility is a large benefit to the TCL, and something
I've been hoping to accomplish since it's creation. This means you will be able to use any of the tree iterators (child and descendant)
for any of the trees in the STL algorithms. STL compatibility also means you can transfer tree nodes
to and from STL containers very easily, as well as perform operations on whole trees using STL algorithms
with descendant iterators. Another major change is that all iterators will be defined
outside of their classes. All iterator classes (child, descendant, and ordered) will be defined in a new
source file, tree_iterators.h. Then, the iterators will be composed within the class by using typedefs. This will
make both the iterators and basic_tree, much less cluttered and easier to understand. There will be one small change
to the interface of the TCL, which is the removal of the set() operation from the associative trees.
The set() operation should never have been part of the interface for associative trees, since it breaks the rules
of associative containers. Since there may be some projects in the field which depend on this operation, a link
will be provided to the current version, although previous versions will not be supported.
|
| Apr 31 2006 |
It has been a while since the last update to the TCL. I've been looking into a number of suggestions from Martin Wirth
and Shen Lei.
One of Martins suggestions was to take advantage of the underlying vector to contain child nodes of the sequential_tree,
and expose many of those benefits to the user. Martin actually
had many more significant changes to make sequential_tree more adaptable, but problems with certain compiler compatibility with templates
are preventing me from implementing many of these suggestions. I did, however, make a correction to the derivation of the iterator
classes, which now derive from std::iterator<std::bidirectional_iterator_tag, tree_type*>. I feel this is a first step in
making the TCL iterators compatible with many of the STL algorithms, which Martin was also hinting at.
Shen Lei has also been suggesting some changes to the TCL. He has taken the time to implement a mapped base tree class,
which differs in the philosophy of the TCL. His mapped tree implementation uses value semantics rather than reference semantics,
which has some advantages and some disadvantages over the TCL implementation. You can contact
Shen Lei for more information on his implementation
of the mapped tree container. Thanks to Martin Wirth and Shen Lei for their ideas and work. |
| Apr 11, 2006 |
Martin Wirth has submitted suggestions for TCL's sequential_tree, to take advantage of it's sequential
nature, and the fact that it uses a vector for it's underlying node containment. Random access of a node's
children is one of Martin's suggestions which I'll be testing in the next few weeks. The ability to use TCL's
iterators in std::algorithm routines is another of Martin's suggestions. Although a very good idea, and would
make the TCL more generic and compatible with the standard library, the iterator classes would need to be redesigned.
It may be possible, however, to make the iterator classes work with some of the bidirectional STL algorithms. Thanks to Martin for identifying the need and ideas for generalizing the functionality of the TCL's iterators. |
| Mar 25, 2006 |
Mark Sandler has submitted code for serializing the node structure within the TCL containers. After updating the site for the recent addition of sequential_tree, I'll be looking into the code further, and will give consideration to adding it to the TCL. Thanks to Mark for coming up with the serialization idea and accompanied code. |
| Mar 22, 2006 |
After giving the various solutions for allowing the use of custom allocators some more thought,
I concluded that the best solution was the one which was given by Bjorn Madsen,
who had come up with the original idea of adding custom allocators to the TCL.
His solution worked very well, and was standard compliant. Unfortunately, the solution
was incompatible with VC6 due to VC6's incomplete support of advanced template functionality.
After discussing the problem with Bjorn, we decided on an alternate and compromising solution,
which is to create custom allocation/deallocation operations in the base class, which all
classes will use for all allocation of
stored_type
and tree_type.
These operations would then use two new allocator members introduced in basic_tree.
This should make changing any TCL container to using a custom allocator a simple matter of changing
these two allocator member variables in basic_tree. Thanks again to Bjorn for coming up with the concept and original solution for the use of custom allocators in the TCL. |
| Mar 16, 2006 | Bjorn Madsen of Rare Ltd has made a modification to the TCL for allowing the use of a custom allocator. These changes will soon be worked into a special version of the TCL, or will be available as wrapper classes to the TCL, in which future fixes and enhancements to the TCL will automatically be available to the custom wrapper classes. |
| Mar 16, 2006 |
For the last month, I've been working on adding the latest tree container member to the TCL, sequential_tree<>.
Where the original three tree containers, tree, multitree, and unique_tree use a std::set to contain the child
nodes, sequential_tree uses a std::vector. So, the nodes remain in the same order they are added (or inserted).
Multiple sort() operations are also provided, to change the order of the child nodes if so inclined. A re-design
of the TCL was necessary, to remove operations particular to the original three trees, and place them into
a new class which sits between the original three trees and basic_tree. This new class, which inherits from basic_tree, is named
associative_tree, accordingly, because the three 'associative' containers derive from it. With the std::set specific
operations removed from basic_tree and placed into associative_tree, the new tree container member, sequential_tree
was free to inherit from basic_tree. Updates to the web-site to reflect the design changes, and the addition of sequential_tree, will occur over the next couple weeks. |
| Feb 16, 2006 |
Volker Bijewitz has been testing the TCL in Visual Studio 2005, and has discovered some problems both
with the compilation and with the runtime. The compilation errors seem to be coming in the non-const descendant
iterator constructors, which accept an iterator parameter. Since their base classes are derived from
std::iterator<category, type>, the std namespace is being added to the descendant iterator classes.
The iterator class in the constructors is then being seen incorrectly as std::iterator. The solution
involved creating a typedef for basic_tree::iterator after its definition, and using the typedef
in the descendant iterator constructors. The runtime errors were a little tougher problem. VC8's implementation of the STL does not allow the comparison of iterators of different containers, which is done with the descendant iterators. Normally, this action is undefined, but allowed (in VC6, VC7, and gcc). It's not considered good practice, however, and VC8 probably has the rights to assert in that situation. The resolution was to add the parent pointer to each iterator and const_iterator. Then have the iterators == operator check first if the parent classes are equal. If not, don't perform an equality check on the internal iterators, and if so return the result of the internal (set<>) iterator comparison. These fixes have been made, and are implemented in Version 1.20, which is now available. Thanks to Volker for discovering these issues in the VC8 (Studio 2005) compiler. |
| Feb 9, 2006 |
I've made some crude benchmark examples (soon to be posted) and came up with some pretty good results.
The examples included inserting one million very basic class objects in all three trees.
I used a random algorithm, and a level_order_iterator to insert the nodes. The trees ended up
being about 2000 levels deep. Below are the average results of the tests.
|
| Jan 26, 2006 |
Quynh Nguyen has been working with me to resolve a couple of issues he has discovered in the TCL.
Thanks again to Quynh for the suggestions and fixes to issues he has discovered in the TCL. |
| Jan 1, 2006 | A new year, and thanks to John Potter and Roland Pibinger for conveying the need to have TCL be compatible with many of the standard compilers such as gcc. My close friend, Santhosh Shetty has been helping getting me up to speed with the installation and setup of gcc and cygwin, as well as giving other suggestions and insights to better the TCL. I've also been toying around with the recently added C++ capabilities of Eclipse, and using it with the gcc compiler. It will take some work to get the TCL fully gcc compliant, which is the current focus. |