The Tree Container Library

The sequential_tree offers all of the operations in the standard interface, and also those listed specifically in the sequential_tree interface.

The sequential_tree uses a std::vector internally to store the child nodes, whereas the associative trees use std::set for the same purpose. For this reason, the child nodes of sequential_tree are not naturally ordered, and will remain in the order in which they are inserted, unless a sort() operation is performed on the node(s). The sort operations are available only to sequential_tree, and not to the associative trees, since their nodes are ordered naturally. The sequential_tree also offers extra insert() operations to insert children nodes at a particular position amongst the other children. See the sequential_tree example for more info.

The sequential_tree accepts a single template parameter, which represents the type which will be stored in each node, which is called the stored_type. Objects of this type are referred to as elements. Instantiating the sequential_tree is as easy as
sequential_tree<std::string> my_tree;

Inserting nodes is just as easy.

my_tree.insert("E node");
my_tree.insert("A node");
my_tree.insert("C node");
sequential_tree<std::string>::iterator it = my_tree.insert("B node");
it.node()->insert("D node");
my_tree.insert(it, "F node");

In the code snippet above, nodes E, A, and C are inserted in the root node. Then node B is inserted, and the return iterator from the newly inserted node is saved to it. After node B is inserted in the root, node D being inserted into node B, via the iterator which points to node B. Then node F is inserted before node B using the operation insert( iterator, stored_type&) operation.

Since the stored_type, std::string, has a less-than operator defined, a sort() operation which takes no parameters can be performed on the tree object. my_tree.sort();

This will sort the children in the root nodes in ascending order. To sort the nodes in a different order, say, descending, we must either create a binary predicate function or a function object to pass to the sort operation. A binary predicate operation for my_tree is shown below.

bool pred(const std::string& lhs, const std::string& rhs)
{
     return lhs > rhs;
}

A function object which will perform the same functionality is shown below.

struct comp_functor
{
   bool operator() (const std::string& lhs, const std::string& rhs)
   {
      return lhs > rhs;
   }
}

The root node of my_tree can now be sorted using the binary predicate:
my_tree.sort(pred);

or by using the function object:
my_tree.sort<comp_functor>();

The example above shows the root node being sorted using the three sort operations. Any node in the tree can be sorted in the same way. Also, using the three descendant sort operations, which has identical syntax to the child sort operations given above, every descendant of the node which sort_descendant is called will have it's children sorted, not just the nodes immediate children.