The Tree Container Library

The unique_tree offers the same operations as tree and multitree, plus a few extra operations. Because every node in the tree is guaranteed to be unique, unique_tree offers deep find operations and operations to insert nodes in a given parent.

The unique_tree is the most powerful of the tree containers. It allows a find_deep() operation which can find any node within the descendants of the node which it's called. The tree and multitree offer only the find() operation, which can only find a node within the children from which called. Also, unique tree offers an insert operation which can insert a child node in any parent. These two operations will be discussed in the unique_tree example.

The unique_tree accepts three template arguments, with the second two being optional. The first two parameters, stored_type and node_compare_type, are the same two template parameters used in tree and multitree. The general usage page describes these two parameters in detail. The third template parameter, node_order_compare_type is needed only by unique_tree. This optional parameter supplies an alternative comparison operation to be used to compare nodes, which order child nodes within their parent. The use for this optional template parameter can best be described with an example. Suppose you wanted to store family tree information in the unique_tree. We'll call the class of objects being stored in the nodes, CFamilyMember. Class data members may include many pieces of information, including name, age, gender, birth date, spouse, etc. A key field (data member) will be necessary, which will guarantee that every node will be unique. A good candidate data member would be SSN, since all SSN's are unique. The best way to implement the use of the SSN field being used as the 'key' field, (or node_compare_type), is to define a less-than operator in the class, which compares the SSN's of two objects.

friend bool operator <(const CFamilyMember& lhs, const CFamilyMember& rhs)
{
   return lhs.ssn < rhs.ssn;
}

If not supplied, the second template parameter of unique_tree defaults to std::less<stored_type>, which uses the defined less-then operation defined in the class, as the one above. If you wish to supply the third template parameter for unique_tree, however, you must explicitly supply the second template parameter. In this case, we wish to make it the same as the default.

Using standard child iterators with this unique_tree as it's currently defined, child nodes will be traversed within a given parent starting with the node with the lowest SSN to the node with the highest SSN. But, what if we wanted to be able to traverse the child nodes in another order, say by the age field in the child node. This would be very practical, since the child nodes represent children of the parent in the parent node. In order to have an alternate order to traverse the child nodes, we will supply a third template parameter. Before doing that though, we must define a comparison operation that we can use for the third template parameter. The following function object should do nicely.

struct CAgeCompare
{
   bool operator ()(const CFamilyMember& lhs, const CFamilyMember& rhs)
   {
      return lhs.age < rhs.age;
   }
}

With this function object defined, we are ready to declare our unique tree as shown below.

unique_tree<CFamilyMember, std::less<CFamilyMember>, CAgeCompare> myFamilyTree;

In the declaration, we make use of all three template parameters. As mentioned earlier, if the second template parameter is not supplied, it defaults to std::less<stored_type>. If std::less<stored_type> is used in declaring unique_tree, then the less-than operator must be defined for stored_type. The third template parameter for unique_tree defaults to the same as the default for the second template parameter, std::less<stored_type>.

The declaration of unique tree above has no affect on the standard child iterator traversal of child nodes. The order of child node traversal is set by the second template parameter, node_compare_type, which can also be considered the key type, because it establishes uniqueness within the tree. There is another set of iterators available specifically available for the unique tree, called ordered_iterators. These are the iterators that are used as the alternate traversal mechanism, which are controlled by the third template parameter for unique_tree. If the third parameter is not declared, it defaults to the same type which is used for the second parameter.

The unique_tree has some very powerful advantages over the tree and multitree, made possible because of the fact that every node in the tree is guaranteed to be unique. Because of this, any node can be found in the tree from the root node. Another advantage of the unique_tree, is that if allow_orphans is turned on, nodes can be inserted in parents, before the parents themselves are inserted. In this case, a temporary parent node is created in unique_tree for the parent, which will be updated when the parent is later inserted. Since every node is guaranteed to be unique, trying to insert a node in the tree that matches an existing node, however, will fail, and return the end iterator to the parent.

If storing class objects in the unique_tree, it may be convenient to supply a constructor to the class which will accept an argument which sets the 'key' member of the class. This 'key' member is the member which is compared for many internal node operations as directed by the node_compare_type A constructor such as this would allow the easy creation of an element for many of the unique_tree operations. As an example, we will use our CFamilyMember class. We can create a class constructor which accepts an integer which is used to set the 'key' class member ssn, as below.

CFamilyMember(int ssn_) : ssn(ssn_) {}

Since the find(), find_deep(), and insert() operations use this key field as the comparison operation internally, then this is the only field that needs set in the element for these operations. Therefore, when doing a find() or find_deep() operation, we need only be concerned about setting this member in the class object that is used for the argument for these operations. This is illustrated below.

it = node.find(CFamilyMember(814));
it = Tree.find_deep(CFamilyMember(694));
it = Tree.insert(CFamilyMember(694), CFamilyMember(749, "Nick Palmer", 17));

Another advantage to having this particular constructor, is that the constructor can be used implicitely, in a function which accepts a stored_type object (element). In this case, you only need to specify the 'key' value, instead of constructing an element object with the key value. This is illustrated below in the following examples, which have the same behavior as those above.

it = node.find(814);
it = Tree.find_deep(694);
it = Tree.insert(694, CFamilyMember(749, "Nick Palmer", 17));

The example presented here is used in the full example described in the unique_tree example, which gives more insight to the usage and operations of unique_tree.