The tree-based container has the following declaration:
template< typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>, typename Tag = rb_tree_tag, template< typename Const_Node_Iterator, typename Node_Iterator, typename Cmp_Fn_, typename Allocator_> class Node_Update = null_tree_node_update, typename Allocator = std::allocator<char> > class tree;
The parameters have the following meaning:
The Tag parameter specifies which underlying data structure to use. Instantiating it by rb_tree_tag, splay_tree_tag, or ov_tree_tag, specifies an underlying red-black tree, splay tree, or ordered-vector tree, respectively; any other tag is illegal. Note that containers based on the former two contain more types and methods than the latter (e.g., reverse_iterator and rbegin), and different exception and invalidation guarantees.
Consider the two trees in Figures Some node invariants A and B. The first is a tree of floats; the second is a tree of pairs, each signifying a geometric line interval. Each element in a tree is refered to as a node of the tree. Of course, each of these trees can support the usual queries: the first can easily search for 0.4; the second can easily search for std::make_pair(10, 41).
Each of these trees can efficiently support other queries. The first can efficiently determine that the 2rd key in the tree is 0.3; the second can efficiently determine whether any of its intervals overlaps std::make_pair(29,42) (useful in geometric applications or distributed file systems with leases, for example). (See tree_order_statistics.cc and tree_intervals.cc for examples.) It should be noted that an std::set can only solve these types of problems with linear complexity.
In order to do so, each tree stores some metadata in each node, and maintains node invariants clrs2001]. The first stores in each node the size of the sub-tree rooted at the node; the second stores at each node the maximal endpoint of the intervals at the sub-tree rooted at the node.
Supporting such trees is difficult for a number of reasons:
These problems are solved by a combination of two means: node iterators, and template-template node updater parameters.
Each tree-based container defines two additional iterator types, const_node_iterator and node_iterator. These iterators allow descending from a node to one of its children. Node iterator allow search paths different than those determined by the comparison functor. tree supports the methods:
const_node_iterator node_begin() const; node_iterator node_begin(); const_node_iterator node_end() const; node_iterator node_end();
The first pairs return node iterators corresponding to the root node of the tree; the latter pair returns node iterators corresponding to a just-after-leaf node.
The tree-based containers are parametrized by a Node_Update template-template parameter. A tree-based container instantiates Node_Update to some node_update class, and publicly subclasses node_update. Figure A tree and its update policy shows this scheme, as well as some predefined policies (which are explained below).
node_update (an instantiation of Node_Update) must define metadata_type as the type of metadata it requires. For order statistics, e.g., metadata_type might be size_t. The tree defines within each node a metadata_type object.
node_update must also define the following method for restoring node invariants:
void operator()(node_iterator nd_it, const_node_iterator end_nd_it)
In this method, nd_it is a node_iterator corresponding to a node whose A) all descendants have valid invariants, and B) its own invariants might be violated; end_nd_it is a const_node_iterator corresponding to a just-after-leaf node. This method should correct the node invariants of the node pointed to by nd_it. For example, say node x in Figure Restoring node invariants-A has an invalid invariant, but its' children, y and z have valid invariants. After the invocation, all three nodes should have valid invariants, as in Figure Restoring node invariants-B.
When a tree operation might invalidate some node invariant, it invokes this method in its node_update base to restore the invariant. For example, Figure Insert update sequence diagram shows an insert operation (point A); the tree performs some operations, and calls the update functor three times (points B, C, and D). (It is well known that any insert, erase, split or join, can restore all node invariants by a small number of node invariant updates [clrs2001].)
To complete the description of the scheme, three questions need to be answered:
The first two questions are answered by the fact that node_update (an instantiation of Node_Update) is a public base class of the tree. Consequently:
The cyclic dependency is solved through template-template parameters. Node_Update is parametrized by the tree's node iterators, its comparison functor, and its allocator type. Thus, instantiations of Node_Update have all information required.
pb_ds assumes that constructing a metadata object and modifying it are exception free. Suppose that during some method, say insert, a metadata-related operation (e.g., changing the value of a metadata) throws an exception. Ack! Rolling back the method is unusually complex.
In Interface::Concepts::Null Policy Classes a distinction was made between redundant policies and null policies. Node invariants show a case where null policies are required.
Assume a regular tree is required, one which need not support order statistics or interval overlap queries. Seemingly, in this case a redundant policy - a policy which doesn't affect nodes' contents would suffice. This, would lead to the following drawbacks:
A null policy class, null_tree_node_update solves both these problems. The tree detects that node invariants are irrelevant, and defines all accordingly.
Tree-based containers support split and join methods. It is possible to split a tree so that it passes all nodes with keys larger than a given key to a different tree. These methods have the following advantages over the alternative of externally inserting to the destination tree and erasing from the source tree: