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>< 23 <b>typename</b> Key, 24 <b>typename</b> Mapped, 25 <b>typename</b> Cmp_Fn = std::less<Key>, 26 <b>typename</b> Tag = <a href="rb_tree_tag.html">rb_tree_tag</a>, 27 <b>template</b>< 28 <b>typename</b> Const_Node_Iterator, 29 <b>typename</b> Node_Iterator, 30 <b>typename</b> Cmp_Fn_, 31 <b>typename</b> Allocator_> 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<<b>char</b>> > 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 "http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc%2B%2B-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc"><tt>tree_order_statistics.cc</tt></a> 90 and <a href= 91 "http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc%2B%2B-v3/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> 359