old-autovect-branch/libstdc++-v3/docs/html/ext/pb_assoc/tree_based_containers.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
   2 <html>
   3         <head>
   4                 <title>Tree-Based Containers</title>
   5                 <meta name="GENERATOR" content="Microsoft Visual Studio .NET 7.1">
   6                 <meta name="vs_targetSchema" content="http://schemas.microsoft.com/intellisense/ie5">
   7         </head>
   8 <body bgcolor = "white">
   9 <h1>Tree-Based Containers</h1>
  10
  11 <p>
  12         This section describes tree-based containers. It is organized as follows.
  13 </p>
  14
  15 <ol>
  16         <li> <a href = "#overview">Overview</a> describes an overview.</li>
  17         <li> <a href = "#invariants">Node Invariants</a> describes node invariants.</li>
  18         <li> <a href = "#add_methods">Additional Types and Methods</a> describes additional methods
  19 that tree-based containers support.</li>
  20 </ol>
  21
  22 <h2><a name = "overview">Overview</a></h2>
  23
  24 <p>
  25         Figure
  26 <a href = "#tree_cd">Tree-based containers</a>
  27         shows the container-hierarchy; the tree-based container is circled.
  28 </p>
  29
  30 <h6 align = "center">
  31 <a name = "tree_cd">
  32 <img src = "tree_cd.jpg" width = "70%" alt = "no image">
  33 </h6>
  34 <h6 align = "center">
  35 </a>
  36 Tree-based containers.
  37 </h6>
  38
  39
  40 <p>
  41         The tree-based container has the following declaration:
  42 </p>
  43 <pre>
  44 <b>template</b>&lt;
  45         <b>typename</b> Key,
  46         <b>typename</b> Data,
  47         <b>class</b> Cmp_Fn = std::less&lt;Key&gt;,
  48         <b>class</b> DS_Tag = <a href = "rb_tree_ds_tag.html">rb_tree_ds_tag</a>,
  49         <b>class</b> Node_Updator = <a href = "null_node_updator.html">null_node_updator</a>,
  50         <b>class</b> Allocator =
  51                 std::allocator&lt;<b>char</b>&gt; &gt;
  52 <b>class</b> <a href = "tree_assoc_cntnr.html">tree_assoc_cntnr</a>;
  53 </pre>
  54
  55
  56 <p>
  57         The parameters have the following meaning:
  58 </p>
  59 <ol>
  60         <li> <tt>Key</tt> is the key type.
  61         </li>
  62         <li> <tt>Data</tt> is the data-policy, and is explained in
  63 <a href = "ms_gen.html#ds_policy">Mapping-Semantics Genericity::Data Types as a Policy</a>.
  64         </li>
  65         <li> <tt>Cmp_Fn</tt> is a key comparison functor</li>
  66         <li> <tt>DS_Tag</tt> specifies which underlying data-structure to use, and is described shortly.
  67         <li> <tt>Node_Updator</tt> is a policy for updating node invariants.
  68 This is described in <a href = "#invariants">Node Invariants</a>.
  69         </li>
  70         <li> <tt>Allocator</tt> is (surprisingly) an allocator type.
  71         </li>
  72 </ol>
  73
  74 <p>
  75         The <tt>DS_Tag</tt> specifies which underlying data-structure to use.
  76 Instantiating it by
  77 <a href = "rb_tree_ds_tag.html">rb_tree_ds_tag</a>,
  78 <a href = "splay_tree_ds_tag.html">splay_tree_ds_tag</a>,
  79 or
  80 <a href = "ov_tree_ds_tag.html">ov_tree_ds_tag</a>,
  81 specifies an undelying
  82 red-black tree,
  83 splay tree,
  84 or
  85 ordered-vector tree.
  86         any other tag is illegal. Note that containers based on the former two contain more types and methods than the latter (<i>e.g.</i>, <tt>reverse_iterator</tt> and <tt>rbegin</tt>), and different exception and invalidation guarantees.
  87 </p>
  88
  89
  90
  91
  92 <h2><a name = "invariants">Node Invariants</a></h2>
  93
  94 <p>
  95         Figure
  96 <a href = "#node_invariants">Some node invariants</a>
  97 shows some node invariants. A shows
  98 a tree whose each node contains, asides from an <tt>double</tt> key, the number
  99 of nodes at the subtree rooted at the node; B shows a tree whose each node
 100 contains, asides from a line-interval key, the maximal endpoint of the interval
 101 of any node in the subtree rooted at the node.
 102         The first tree allows querying efficiently what is the order statistic
 103 of any element; the second tree allows querying efficiently if any, or which,
 104 intervals overlap a given interval.
 105 </p>
 106
 107 <h6 align = "center">
 108 <a name = "node_invariants">
 109 <img src = "node_invariants.jpg" width = "50%" alt = "no image">
 110 </a>
 111 </h6>
 112 <h6 align = "center">
 113 Some node invariants.
 114 </h6>
 115
 116
 117 <p>
 118         Maintaining such trees is difficult, for two reasons:
 119 </p>
 120 <ol>
 121         <li> Various operations can invalidate node invariants.
 122 <i>E.g.</i>, Figure
 123 <a href = "#node_invariant_invalidations">Invalidation of node invariants</a>
 124 shows how a right rotation, performed on A, results in B, with nodes <i>x</i>
 125 and <i>y</i> having corrupted invariants (the greyed nodes in C);
 126 Figure
 127 <a href = "#node_invariant_invalidations">Invalidation of node invariants</a>
 128 shows how an insert, performed on D, results in E, with nodes <i>x</i>
 129 and <i>y</i> having corrupted invariants (the greyed nodes in F).
 130         It is not feasible to know outside the tree the effect of an operation on the
 131 nodes of the tree.
 132         </li>
 133         <li>
 134                 Even if node invariants are maintained, it is not possible to know
 135 in advance which search paths are required (<i>e.g.</i>, searching for all
 136 line intervals overlapping some interval might require several search paths).
 137         </li>
 138 </ol>
 139
 140
 141 <h6 align = "center">
 142 <a name = "node_invariant_invalidations">
 143 <img src = "node_invariant_invalidations.jpg" width = "80%" alt = "no image">
 144 </a>
 145 </h6>
 146 <h6 align = "center">
 147 Invalidation of node invariants.
 148 </h6>
 149
 150 <p>
 151         These problems are solved by a combination of two means:
 152 </p>
 153
 154 <ol>
 155         <li>
 156                 The tree-based containers are parameterized by a <tt>Node_Updator</tt>
 157 parameter. When a tree operation might invalidate some node invariant,
 158 a <tt>Node_Updator</tt> object is invoked to restore the invariant. This object is
 159 always invoked with three nodes: some node, say <i>x</i> in
 160 Figure
 161 <a href = "#restoring_node_invariants">Invalidation of node invariants</a>-A
 162 has an invalid invariant, but its children, <i>y</i> and <i>z</i> hav valid invariants.
 163 After the invocation, all three nodes have valid invariants, as
 164 in
 165 Figure
 166 <a href = "#restoring_node_invariants">Invalidation of node invariants</a>-B.
 167 It is well known that any <tt>insert</tt>, <tt>erase</tt>,
 168 <tt>split</tt> or <tt>join</tt>, can restore
 169 all node invariants by a small number of node invariant updates
 170 [<a href = "references.html#clrs2001">clrs2001</a>].
 171 For example, Figure
 172 <a href = "#update_seq_diagram">
 173 Insert update sequence diagram
 174 </a>
 175 shows an <tt>insert</tt> operation (point A); the tree performs some operations, and
 176 calls the update functor three times (points B, C, and D).
 177         </li>
 178         <li>
 179                 The tree based containers all define internally <tt>node_iterator</tt>
 180         and <tt>const_node_iterator</tt>, iterators which can be used to traverse
 181         from a node to any of its children or parent.
 182         </li>
 183 </ol>
 184
 185 <h6 align = "center">
 186 <a name = "restoring_node_invariants">
 187 <img src = "restoring_node_invariants.jpg" width = "80%" alt = "no image">
 188 </a>
 189 </h6>
 190 <h6 align = "center">
 191 Invalidation of node invariants.
 192 </h6>
 193
 194 <h6 align = "center">
 195 <a name = "update_seq_diagram">
 196 <img src = "update_seq_diagram.jpg" width = "50%" alt = "no image">
 197 </a>
 198 </h6>
 199 <h6 align = "center">
 200 Insert update sequence diagram.
 201 </h6>
 202
 203
 204 <p>
 205         In
 206 <a href = "concepts.html#concepts_null_policies">Null Policy Classes</a>
 207 a distinction was made between <i>redundant policies</i>
 208 and <i>null policies</i>.
 209 </p>
 210
 211 <p>
 212         Seemingly, in this case a redundant policy - a policy which doesn't
 213 affect nodes' contents would suffice in this case. This, however, would
 214 lead to performance loss.
 215 Figure
 216 <a href = "#rationale_null_node_updator">
 217 Rationale for null node-invariant functors
 218 </a>
 219 shows a typical case where invariants are restored (in this case, to the
 220 shaded node). In most cases, tree operations such as rotations affect only
 221 the lower levels of the tree. A null policy allows to know that there
 222 is no need to traverse the tree to the root.
 223 </p>
 224
 225 <h6 align = "center">
 226 <a name = "rationale_null_node_updator">
 227 <img src = "rationale_null_node_updator.jpg" width = "50%" alt = "no image">
 228 </a>
 229 </h6>
 230 <h6 align = "center">
 231 Rationale for null node-invariant functors.
 232 </h6>
 233
 234
 235
 236 <h2><a name = "add_methods">Addtional Methods</a></h2>
 237
 238
 239
 240
 241
 242
 243
 244 </body>
 245
 246 </html>