libstdc++-v3/doc/html/ext/pb_ds/tree_based_containers.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
   2     "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
   3
   4 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
   5 <head>
   6   <meta name="generator" content=
   7   "HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" />
   8
   9   <title>Tree-Based Containers</title>
  10   <meta http-equiv="Content-Type" content=
  11   "text/html; charset=us-ascii" />
  12   </head>
  13
  14 <body>
  15   <div id="page">
  16     <h1>Tree Design</h1>
  17
  18     <h2><a name="overview" id="overview">Overview</a></h2>
  19
  20     <p>The tree-based container has the following declaration:</p>
  21     <pre>
  22 <b>template</b>&lt;
  23     <b>typename</b> Key,
  24     <b>typename</b> Mapped,
  25     <b>typename</b> Cmp_Fn = std::less&lt;Key&gt;,
  26     <b>typename</b> Tag = <a href="rb_tree_tag.html">rb_tree_tag</a>,
  27     <b>template</b>&lt;
  28         <b>typename</b> Const_Node_Iterator,
  29         <b>typename</b> Node_Iterator,
  30         <b>typename</b> Cmp_Fn_,
  31         <b>typename</b> Allocator_&gt;
  32     <b>class</b> Node_Update = <a href=
  33 "null_tree_node_update.html">null_tree_node_update</a>,
  34     <b>typename</b> Allocator = std::allocator&lt;<b>char</b>&gt; &gt;
  35 <b>class</b> <a href=
  36 "tree.html">tree</a>;
  37 </pre>
  38
  39     <p>The parameters have the following meaning:</p>
  40
  41     <ol>
  42       <li><tt>Key</tt> is the key type.</li>
  43
  44       <li><tt>Mapped</tt> is the mapped-policy.</li>
  45
  46       <li><tt>Cmp_Fn</tt> is a key comparison functor</li>
  47
  48       <li><tt>Tag</tt> specifies which underlying data structure
  49       to use.</li>
  50
  51       <li><tt>Node_Update</tt> is a policy for updating node
  52       invariants. This is described in <a href="#invariants">Node
  53       Invariants</a>.</li>
  54
  55       <li><tt>Allocator</tt> is an allocator
  56       type.</li>
  57     </ol>
  58
  59     <p>The <tt>Tag</tt> parameter specifies which underlying
  60     data structure to use. Instantiating it by <a href=
  61     "rb_tree_tag.html"><tt>rb_tree_tag</tt></a>, <a href=
  62     "splay_tree_tag.html"><tt>splay_tree_tag</tt></a>, or
  63     <a href="ov_tree_tag.html"><tt>ov_tree_tag</tt></a>,
  64     specifies an underlying red-black tree, splay tree, or
  65     ordered-vector tree, respectively; any other tag is illegal.
  66     Note that containers based on the former two contain more types
  67     and methods than the latter (<i>e.g.</i>,
  68     <tt>reverse_iterator</tt> and <tt>rbegin</tt>), and different
  69     exception and invalidation guarantees.</p>
  70
  71     <h2><a name="invariants" id="invariants">Node
  72     Invariants</a></h2>
  73
  74     <p>Consider the two trees in Figures <a href=
  75     "#node_invariants">Some node invariants</a> A and B. The first
  76     is a tree of floats; the second is a tree of pairs, each
  77     signifying a geometric line interval. Each element in a tree is refered to as a node of the tree. Of course, each of
  78     these trees can support the usual queries: the first can easily
  79     search for <tt>0.4</tt>; the second can easily search for
  80     <tt>std::make_pair(10, 41)</tt>.</p>
  81
  82     <p>Each of these trees can efficiently support other queries.
  83     The first can efficiently determine that the 2rd key in the
  84     tree is <tt>0.3</tt>; the second can efficiently determine
  85     whether any of its intervals overlaps
  86     <tt>std::make_pair(29,42)</tt> (useful in geometric
  87     applications or distributed file systems with leases, for
  88     example). (See <a href=
  89     "../../../../testsuite/ext/pb_ds/example/tree_order_statistics.cc"><tt>tree_order_statistics.cc</tt></a>
  90     and <a href=
  91     "../../../../testsuite/ext/pb_ds/example/tree_intervals.cc"><tt>tree_intervals.cc</tt></a>
  92     for examples.) It should be noted that an <tt>std::set</tt> can
  93     only solve these types of problems with linear complexity.</p>
  94
  95     <p>In order to do so, each tree stores some <i>metadata</i> in
  96     each node, and maintains node invariants <a href=
  97     "references.html#clrs2001">clrs2001</a>]. The first stores in
  98     each node the size of the sub-tree rooted at the node; the
  99     second stores at each node the maximal endpoint of the
 100     intervals at the sub-tree rooted at the node.</p>
 101
 102     <h6 class="c1"><a name="node_invariants" id=
 103     "node_invariants"><img src="node_invariants.png" alt=
 104     "no image" /></a></h6>
 105
 106     <h6 class="c1">Some node invariants.</h6>
 107
 108     <p>Supporting such trees is difficult for a number of
 109     reasons:</p>
 110
 111     <ol>
 112       <li>There must be a way to specify what a node's metadata
 113       should be (if any).</li>
 114
 115       <li>Various operations can invalidate node invariants.
 116       <i>E.g.</i>, Figure <a href=
 117       "#node_invariant_invalidations">Invalidation of node
 118       invariants</a> shows how a right rotation, performed on A,
 119       results in B, with nodes <i>x</i> and <i>y</i> having
 120       corrupted invariants (the grayed nodes in C); Figure <a href=
 121       "#node_invariant_invalidations">Invalidation of node
 122       invariants</a> shows how an insert, performed on D, results
 123       in E, with nodes <i>x</i> and <i>y</i> having corrupted
 124       invariants (the grayed nodes in F). It is not feasible to
 125       know outside the tree the effect of an operation on the nodes
 126       of the tree.</li>
 127
 128       <li>The search paths of standard associative containers are
 129       defined by comparisons between keys, and not through
 130       metadata.</li>
 131
 132       <li>It is not feasible to know in advance which methods trees
 133       can support. Besides the usual <tt>find</tt> method, the
 134       first tree can support a <tt>find_by_order</tt> method, while
 135       the second can support an <tt>overlaps</tt> method.</li>
 136     </ol>
 137
 138     <h6 class="c1"><a name="node_invariant_invalidations" id=
 139     "node_invariant_invalidations"><img src=
 140     "node_invariant_invalidations.png" alt="no image" /></a></h6>
 141
 142     <h6 class="c1">Invalidation of node invariants.</h6>
 143
 144     <p>These problems are solved by a combination of two means:
 145     node iterators, and template-template node updater
 146     parameters.</p>
 147
 148     <h3><a name="node_it" id="node_it">Node Iterators</a></h3>
 149
 150     <p>Each tree-based container defines two additional iterator
 151     types, <a href=
 152     "tree_const_node_iterator.html"><tt>const_node_iterator</tt></a>
 153     and <a href=
 154     "tree_node_iterator.html"><tt>node_iterator</tt></a>.
 155     These iterators allow descending from a node to one of its
 156     children. Node iterator allow search paths different than those
 157     determined by the comparison functor. <a href=
 158     "tree.html">tree</a>
 159     supports the methods:</p>
 160     <pre>
 161     <a href="tree_const_node_iterator.html"><tt>const_node_iterator</tt></a>
 162     node_begin() <b>const</b>;
 163
 164     <a href="tree_node_iterator.html"><tt>node_iterator</tt></a>
 165     node_begin();
 166
 167     <a href="tree_const_node_iterator.html"><tt>const_node_iterator</tt></a>
 168     node_end() <b>const</b>;
 169
 170     <a href="tree_node_iterator.html"><tt>node_iterator</tt></a>
 171     node_end();
 172 </pre>
 173
 174     <p>The first pairs return node iterators corresponding to the
 175     root node of the tree; the latter pair returns node iterators
 176     corresponding to a just-after-leaf node.</p>
 177
 178     <h3><a name="node_up" id="node_up">Node Updater
 179     (Template-Template) Parameters</a></h3>
 180
 181     <p>The tree-based containers are parametrized by a
 182     <tt>Node_Update</tt> template-template parameter. A tree-based
 183     container instantiates <tt>Node_Update</tt> to some
 184     <tt>node_update</tt> class, and publicly
 185     subclasses <tt>node_update</tt>. Figure
 186     <a href="#tree_node_update_cd">A tree and its update
 187     policy</a> shows this scheme, as well as some predefined
 188     policies (which are explained below).</p>
 189
 190     <h6 class="c1"><a name="tree_node_update_cd" id=
 191     "tree_node_update_cd"><img src=
 192     "tree_node_update_policy_cd.png" alt="no image" /></a></h6>
 193
 194     <h6 class="c1">A tree and its update policy.</h6>
 195
 196     <p><tt>node_update</tt> (an instantiation of
 197     <tt>Node_Update</tt>) must define <tt>metadata_type</tt> as
 198     the type of metadata it requires. For order statistics,
 199     <i>e.g.</i>, <tt>metadata_type</tt> might be <tt>size_t</tt>.
 200     The tree defines within each node a <tt>metadata_type</tt>
 201     object.</p>
 202
 203     <p><tt>node_update</tt> must also define the following method
 204     for restoring node invariants:</p>
 205     <pre>
 206     void
 207     operator()(<a href=
 208 "tree_node_iterator.html"><tt>node_iterator</tt></a> nd_it, <a href=
 209 "tree_const_node_iterator.html"><tt>const_node_iterator</tt></a> end_nd_it)
 210 </pre>
 211
 212     <p>In this method, <tt>nd_it</tt> is a <a href=
 213     "tree_node_iterator.html"><tt>node_iterator</tt></a>
 214     corresponding to a node whose A) all descendants have valid
 215     invariants, and B) its own invariants might be violated;
 216     <tt>end_nd_it</tt> is a <a href=
 217     "tree_const_node_iterator.html"><tt>const_node_iterator</tt></a>
 218     corresponding to a just-after-leaf node. This method should
 219     correct the node invariants of the node pointed to by
 220     <tt>nd_it</tt>. For example, say node <i>x</i> in Figure
 221     <a href="#restoring_node_invariants">Restoring node
 222     invariants</a>-A has an invalid invariant, but its' children,
 223     <i>y</i> and <i>z</i> have valid invariants. After the
 224     invocation, all three nodes should have valid invariants, as in
 225     Figure <a href="#restoring_node_invariants">Restoring node
 226     invariants</a>-B.</p>
 227
 228     <h6 class="c1"><a name="restoring_node_invariants" id=
 229     "restoring_node_invariants"><img src=
 230     "restoring_node_invariants.png" alt="no image" /></a></h6>
 231
 232     <h6 class="c1">Invalidation of node invariants.</h6>
 233
 234     <p>When a tree operation might invalidate some node invariant,
 235     it invokes this method in its <tt>node_update</tt> base to
 236     restore the invariant. For example, Figure <a href=
 237     "#update_seq_diagram">Insert update sequence diagram</a> shows
 238     an <tt>insert</tt> operation (point A); the tree performs some
 239     operations, and calls the update functor three times (points B,
 240     C, and D). (It is well known that any <tt>insert</tt>,
 241     <tt>erase</tt>, <tt>split</tt> or <tt>join</tt>, can restore
 242     all node invariants by a small number of node invariant updates
 243     [<a href="references.html#clrs2001">clrs2001</a>].)</p>
 244
 245     <h6 class="c1"><a name="update_seq_diagram" id=
 246     "update_seq_diagram"><img src="update_seq_diagram.png" alt=
 247     "no image" /></a></h6>
 248
 249     <h6 class="c1">Insert update sequence diagram.</h6>
 250
 251     <p>To complete the description of the scheme, three questions
 252     need to be answered:</p>
 253
 254     <ol>
 255       <li>How can a tree which supports order statistics define a
 256       method such as <tt>find_by_order</tt>?</li>
 257
 258       <li>How can the node updater base access methods of the
 259       tree?</li>
 260
 261       <li>How can the following cyclic dependency be resolved?
 262       <tt>node_update</tt> is a base class of the tree, yet it
 263       uses node iterators defined in the tree (its child).</li>
 264     </ol>
 265
 266     <p>The first two questions are answered by the fact that
 267     <tt>node_update</tt> (an instantiation of
 268     <tt>Node_Update</tt>) is a <tt><b>public</b></tt> base class
 269     of the tree. Consequently:</p>
 270
 271     <ol>
 272       <li>Any public methods of <tt>node_update</tt> are
 273       automatically methods of the tree [<a href=
 274       "references.html#alexandrescu01modern">alexandrescu01modern</a>].
 275       Thus an order-statistics node updater, <a href=
 276       "tree_order_statistics_node_update.html"><tt>tree_order_statistics_node_update</tt></a>
 277       defines the <tt>find_by_order</tt> method; any tree
 278       instantiated by this policy consequently supports this method
 279       as well.</li>
 280
 281       <li>In C++, if a base class declares a method as
 282       <tt><b>virtual</b></tt>, it is <tt><b>virtual</b></tt> in its
 283       subclasses. If <tt>node_update</tt> needs to access one of
 284       the tree's methods, say the member function <tt>end</tt>, it simply
 285       declares that method as <tt><b>virtual</b></tt>
 286       abstract.</li>
 287     </ol>
 288
 289     <p>The cyclic dependency is solved through template-template
 290     parameters. <tt>Node_Update</tt> is parametrized by the tree's node iterators, its comparison
 291     functor, and its allocator type. Thus,
 292     instantiations of <tt>Node_Update</tt> have all information required.</p>
 293
 294     <p class="c1"><tt>pb_ds</tt> assumes that constructing a metadata object and modifying it
 295     are exception free. Suppose that during some method, say
 296     <tt>insert</tt>, a metadata-related operation
 297     (<i>e.g.</i>, changing the value of a metadata) throws an
 298     exception. Ack! Rolling back the method is unusually complex.</p>
 299
 300     <p>In <a href=
 301     "concepts.html#concepts_null_policies">Interface::Concepts::Null
 302     Policy Classes</a> a distinction was made between <i>redundant
 303     policies</i> and <i>null policies</i>. Node invariants show a
 304     case where null policies are required.</p>
 305
 306     <p>Assume a regular tree is required, one which need not
 307     support order statistics or interval overlap queries.
 308     Seemingly, in this case a redundant policy - a policy which
 309     doesn't affect nodes' contents would suffice. This, would lead
 310     to the following drawbacks:</p>
 311
 312     <ol>
 313       <li>Each node would carry a useless metadata object, wasting
 314       space.</li>
 315
 316       <li>The tree cannot know if its <tt>Node_Update</tt> policy
 317       actually modifies a node's metadata (this is halting
 318       reducible). In Figure <a href=
 319       "#rationale_null_node_update">Useless update path</a> ,
 320       assume the shaded node is inserted. The tree would have to
 321       traverse the useless path shown to the root, applying
 322       redundant updates all the way.</li>
 323     </ol>
 324
 325     <h6 class="c1"><a name="rationale_null_node_update" id=
 326     "rationale_null_node_update"><img src=
 327     "rationale_null_node_update.png" alt="no image" /></a></h6>
 328
 329     <h6 class="c1">Useless update path.</h6>
 330
 331     <p>A null policy class, <a href=
 332     "null_tree_node_update.html"><tt>null_tree_node_update</tt></a>
 333     solves both these problems. The tree detects that node
 334     invariants are irrelevant, and defines all accordingly.</p>
 335
 336     <h2><a name="add_methods" id="add_methods">Additional
 337     Methods</a></h2>
 338
 339     <p>Tree-based containers support split and join methods.
 340     It is possible to split a tree so that it passes
 341     all nodes with keys larger than a given key to a different
 342     tree. These methods have the following advantages over the
 343     alternative of externally inserting to the destination
 344     tree and erasing from the source tree:</p>
 345
 346     <ol>
 347       <li>These methods are efficient - red-black trees are split
 348       and joined in poly-logarithmic complexity; ordered-vector
 349       trees are split and joined at linear complexity. The
 350       alternatives have super-linear complexity.</li>
 351
 352       <li>Aside from orders of growth, these operations perform
 353       few allocations and de-allocations. For red-black trees, allocations are not performed,
 354       and the methods are exception-free. </li>
 355     </ol>
 356   </div>
 357 </body>
 358 </html>