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.
This bit of code (click on the code link to the right) shows the polymorphic behavior that the TCL is capable of.
This particular example uses the
unique_tree to demonstrate the polymorphic behavior,
but all three tree containers exhibit this functionality. The code illustrates how the TCL's clone()
operation enables the containers to allow the storage of derived objects without slicing.
A source file of this example can be downloaded here.
This example is compatible with versions 3.50 and higher of the TCL. The latest version of the TCL can be downloaded from the TCL download page.
This polymorphic example, as well as the library, is now compatible with Visual C++ 6.0.
For this compiler, users need to un-check the Enable minimal rebuild option for successful compilation.
Also for VC 6.0 users, the normal
#pragma warning (disable : xxxx) directive
is necessary to avoid the compiler warnings.
In this example, I use a class hierarchy which might be used in the property rental management business.
A tree structure is to contain nodes corresponding to different rental types, such as
properties, buildings, units (apartments, suites, rooms), parking lots, parking spots, etc.
We will be building a tree structure like the one shown in a link to the right. Since we will
be creating classes for these different types, we will derive them from a common base type, CRental,
which will be the type we will store in our tree container. The example will show that no slicing will
occur when inserting nodes of the derived types.
A sample of the results to the console is also given to the right.
Line 1 is used for Visual Studio compilers. Those using MS compilers can un-comment this line.
Lines 2 - 4 include needed headers from the STL. Line 5 includes the unique_tree header file. A forward declaration of our base class, which will be our stored_type, is given in line 8. A namespace is declared in lines 10 - 15, which declare some needed functions.
Line 17 begins the definition of our base class, CRental. Line 20 defines a default constructor for the
base class. Like the STL, a default constructor must be provided for types stored in the tree containers.
The constructor in line 21 is mainly for convenience, and also to provide an implicit conversion
of an integer to a CRental Object, for the insertion operations, covered below. Lines 22 and 23 define
the constructor which the derived classes will call to set the base data members. Since this is a base
class, we need to remember to make the destructor virtual, as in line 24. Line 26 defines a virtual function
which is used to return a string indicating the object type. This will be the function we will be watching
closely, which will indicate if the tree container is indeed polymorphic. Line 27 defines our virtual clone
function, also known as a virtual constructor. This will get used indirectly by the tree container
to provide a new object of the correct type.
The use of clone functions, or virtual constructors, has become somewhat of a C++ idiom or pattern,
and you can find information on this subject in many popular C++ books. Line 29 defines the less-than operator,
which will be used to determine the node order in our unique_tree. It compares the
the CRental objects, and since we are using a unique_tree, we will need to insure that this number
is unique in every object we insert in the tree. Lines 30 - 37 provide more public interface operations
we will need for this example. Notice that we are making all operations, including the virtual operations,
const. This will allow us to access these functions with const_iterators. Lines 40 - 41 declare two
base class data members.
Lines 44 - 100 define the derived classes for our tree structure. The definition of CProperty begins on line 44. It's constructor in lines 48 - 54 is used to create property objects, and it initializes it's base class with the first two parameter, while setting it's own data members with the last two parameters. Line 57 overrides the virtual function which will show us if the tree is polymorphic. Line 58 overrides the virtual clone operation, and returns a new object of it's own type.
Lines 65 - 100 define CBuilding and CUnit, and are very similar to the definitions of CProperty, but with different data members, so I will not discuss them in detail.
Line 102 defines a function which will be passed to the tree's
The function signature of this operation is
- stored_type* clone_fcn(const stored_type&)
The function simply calls the
clone() operation on the passed object, and returns it's result.
If the tree container has this function supplied, it will use this function to create new objects
of stored_type, and avoid object slicing.
Line 107 starts the main function. Line 109 declares the unique_tree we will be using in our example, and sets it's root node. Lines 112 - 116 populate and print the unique_tree without first supplying a clone operation to unique_tree. In the display for this first output, you'll notice that all nodes are of type unknown indicating that all node objects were sliced.
Lines 118 - 124 clear, load, and print the unique_tree again, but supply a clone operation first. The display for the second tree structure shows the inserted objects did not get sliced, as they show their correct types. Stepping through the code will also show what is going on during the insertions, and that the derived clone() operations are being used to make copies of the inserted objects.
The function starting on line 129 populates the unique_tree. All insert operations use the
insert(parent, child) operation, which is available only to unique_tree. Lines 131 - 134 insert
the property objects. Lines 136 - 144 insert the building objects. Lines 147 - 173 insert the
unit objects. Since we did not allow orphans for this unique_tree, we need to insure we insert
the parents before their children and descendants. If we were to allow orphans, with the
allow_orphan() operation, it would not matter what order we perform the insertions in.
(You can try this out as an exercise).
Notice in line 132, that the first passed argument makes use of the single parameter constructor for CRental. Objects of the base class, CRental can be used for the first argument, because this parameter is used only to find the parent in which to insert the child. Also notice on all remaining insert operations in this function, that it's not necessary to explicitly use the CRental constructor. That constructor will conveniently convert an integer which is passed as the first argument to a CRental object.
The last two functions,
is_last_child() are covered in detail
in the generic example.