The Tree Container Library

The sequential_tree is TCL's latest addition. It was created for the need to store child node objects in their parent nodes in the order in which they were inserted. sequential_tree's child nodes can also be sorted at any time, using the sort() operation on a specific node, or on the whole tree. Child nodes can also be sorted using the STL various sort algorithms.

sequential_tree is the only tree of the four tree containers, which derive directly from basic_tree. The other three trees, which are associative trees derive from associative_tree. The main difference between sequential_tree and the associative trees is that sequential_tree uses a std::vector internally to store the child nodes, while the associative trees use either std::set or std::multiset for the same reason. Please refer to the source code for sequential_tree.h in the following discussion.

In the class declaration, sequential_tree accepts a single template parameter, for the stored_type. Since the child nodes will not be naturally ordered, as in the associative trees, there is no need for a second template parameter to specify the node_compare_type. In the declaration, sequential_tree inherits from basic_tree, passing, or forming the three template arguments needed for basic_tree. See basic_tree implementation for a detailed description for the three template parameters it accepts.

Within the class definition, sequential_tree first defines a number of typedefs. The first typedef declares the type of itself, the fully specified tree_type.
The second typedef declares itself again, as sequential_tree_type. This typedef is used in the declarations of the descendant Iterators further below, to distinguish the last template parameter. The third typedef declares the fully specified container_type.
The forth typedef defines the fully specified base class, basic_tree_type.
The fifth typedef defines a predicate function pointer type, for a couple of the sort() operations, described below.

Next the descendant iterators are declared as friends to sequential_tree, to allow them access to specific operations in the tree.

The child and descendant iterators are declared next, via typdefs. These typedefs are identical to those declared in associative_tree, except the last template parameter for the descendant iterators is specified as sequential_tree_type rather than associative_tree_type. The typedefs are as follows.

typedef const_sequential_iterator<stored_type, tree_type, container_type> const_iterator;
typedef sequential_iterator<stored_type, tree_type, container_type> iterator;
typedef const_pre_order_descendant_iterator<stored_type, tree_type, container_type, sequential_tree_type> const_pre_order_iterator;
typedef pre_order_descendant_iterator<stored_type, tree_type, container_type, sequential_tree_type> pre_order_iterator;
typedef const_post_order_descendant_iterator<stored_type, tree_type, container_type, sequential_tree_type> const_post_order_iterator;
typedef post_order_descendant_iterator<stored_type, tree_type, container_type, sequential_tree_type>  post_order_iterator;
typedef const_level_order_descendant_iterator<stored_type, tree_type, container_type, sequential_tree_type> const_level_order_iterator;
typedef level_order_descendant_iterator<stored_type, tree_type, container_type, sequential_tree_type> level_order_iterator;

The constructors and destructor are then declared/defined. The first constructor is the default constructor, which passes a newly created default stored_type object to basic_tree's constructor. As with all contained types, the stored_type must have a default constructor defined. The second constructor accepts a size_type argument, sz, which inserts sz child nodes into the tree, using stored_type's default constructor. The third constructor accepts a size_type sz, and a stored_type object, and inserts sz copies of the stored_type object into the newly constructed tree. The forth constructor accepts a reference to a stored_type object, which is used to set the stored_type for the root node. The fifth constructor is the copy constructor. The sixth constructor accepts a range of input iterators, where the stored_type objects in that range will be added to the newly constructed tree. The destructor simply calls the clear operation for the node.

The assignment operator is then declared, followed by the accessors for the child and descendant iterators. Then the public interface is declared/defined. I won't go into detail on the public interface operations. Many of them are quite simple, and are defined inline. See the sequential_tree interface for info on these operations. The implementation for the more complex of these operations are commented in the inl file.

The subscript, [], operators are declared next, and implemented in the inl file. Then the overloaded operators are declared. The < and == are implemented in the inl file. All the rest are defined according using these two.

The sort operations follow. There are two groups of sort operations. The standard sort() operations sort the immediate children within the node in which it's called. The sort_descendants() operations sort the descendants of the node in which it's called. There are three variations in which the sort operations can be called.

• With no arguments, in which case the sort operations uses the less-than operator defined for stored_type. The less-than operation must be defined for stored_type to use this form of sort() and sort_descending().
• With a predicate function pointer argument, which uses the predicate function to sort the nodes.
• With a function object argument, which uses the function object to sort the nodes.

The function object sort() and sort_descending() operations are defined inline. Next, some function objects are defined inline, as private, which are used as de-referencing operations for the sort() and sort_descending() operations. Since pointers to the nodes are stored in the vector containers as the children, de-referencing operations are needed for all of the sort operations defined above.