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

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
   2     "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.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>Data-Structure Genericity</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>Data-Structure Genericity</h1>
  17
  18     <h2><a name="problem" id="problem">The Basic Problem</a></h2>
  19
  20     <p>The design attempts to address the following problem. When
  21     writing a function manipulating a generic container object,
  22     what is the behavior of the object? <i>E.g.</i>, suppose one
  23     writes</p>
  24     <pre>
  25 <b>template</b>&lt;<b>typename</b> Cntnr&gt;
  26 <b>void</b>
  27 some_op_sequence(Cntnr &amp;r_container)
  28 {
  29     ...
  30 }
  31 </pre>then one needs to address the following questions in the body
  32 of <tt>some_op_sequence</tt>:
  33
  34     <ol>
  35       <li>Which types and methods does <tt>Cntnr</tt> support?
  36       Containers based on hash tables can be queries for the
  37       hash-functor type and object; this is meaningless for
  38       tree-based containers. Containers based on trees can be
  39       split, joined, or can erase iterators and return the
  40       following iterator; this cannot be done by hash-based
  41       containers.</li>
  42
  43       <li>What are the guarantees of <tt>Cntnr</tt>? A container
  44       based on a probing hash-table invalidates all iterators when
  45       it is modified; this is not the case for containers based on
  46       node-based trees. Containers based on a node-based tree can
  47       be split or joined without exceptions; this is not the case
  48       for containers based on vector-based trees.</li>
  49
  50       <li>How does the container maintain its elements? Tree-based
  51       and Trie-based containers store elements by key order;
  52       others, typically, do not. A container based on a splay trees
  53       or lists with update policies "cache" "frequently accessed"
  54       elements; containers based on most other underlying
  55       data structures do not.</li>
  56     </ol>
  57
  58     <p>The remainder of this section deals with these issues.</p>
  59
  60     <h2><a name="ds_hierarchy" id="ds_hierarchy">Container
  61     Hierarchy</a></h2>
  62
  63     <p>Figure <a href="#cd">Container class hierarchy</a> shows the
  64     container hierarchy.</p>
  65
  66     <h6 class="c1"><a name="cd" id="cd"><img src="container_cd.png" alt=
  67     "no image" /></a></h6>
  68
  69     <h6 class="c1">Container class hierarchy.</h6>
  70
  71     <ol>
  72       <li><a href=
  73       "container_base.html"><tt>container_base</tt></a> is an
  74       abstract base class for associative containers.</li>
  75
  76       <li>Tree-Like-Based Associative-Containers:
  77
  78         <ol>
  79           <li><a href=
  80           "basic_tree.html"><tt>basic_tree</tt></a>
  81           is an abstract base class for tree-like-based
  82           associative-containers</li>
  83
  84           <li><a href=
  85           "tree.html"><tt>tree</tt></a>
  86           is a concrete base class for tree-based
  87           associative-containers</li>
  88
  89           <li><a href=
  90           "trie.html"><tt>trie</tt></a>
  91           is a concrete base class trie-based
  92           associative-containers</li>
  93         </ol>
  94       </li>
  95
  96       <li>Hash-Based Associative-Containers:
  97
  98         <ol>
  99           <li><a href=
 100           "basic_hash_table.html"><tt>basic_hash_table</tt></a>
 101           is an abstract base class for hash-based
 102           associative-containers</li>
 103
 104           <li><a href=
 105           "cc_hash_table.html"><tt>cc_hash_table</tt></a>
 106           is a concrete collision-chaining hash-based
 107           associative-containers</li>
 108
 109           <li><a href=
 110           "gp_hash_table.html"><tt>gp_hash_table</tt></a>
 111           is a concrete (general) probing hash-based
 112           associative-containers</li>
 113         </ol>
 114       </li>
 115
 116       <li>List-Based Associative-Containers:
 117
 118         <ol>
 119           <li><a href=
 120           "list_update.html"><tt>list_update</tt></a> -
 121           list-based update-policy associative container</li>
 122         </ol>
 123       </li>
 124     </ol>
 125
 126     <p>The hierarchy is composed naturally so that commonality is
 127     captured by base classes. Thus <tt><b>operator[]</b></tt> is
 128     defined <a href=
 129     "container_base.html"><tt>container_base</tt></a>, since
 130     all containers support it. Conversely <tt>split</tt> is defined
 131     in <a href=
 132     "basic_tree.html"><tt>basic_tree</tt></a>,
 133     since only tree-like containers support it. <a href=
 134     "#container_traits">Data-Structure Tags and Traits</a> discusses how
 135     to query which types and methods each container supports.</p>
 136
 137     <h2><a name="container_traits" id="container_traits">Data-Structure Tags and
 138     Traits</a></h2>
 139
 140     <p>Tags and traits are very useful for manipulating generic
 141     types. For example, if <tt>It</tt> is an iterator class, then
 142     <tt><b>typename</b> It::iterator_category</tt> or
 143     <tt><b>typename</b>
 144     std::iterator_traits&lt;It&gt;::iterator_category</tt> will
 145     yield its category, and <tt><b>typename</b>
 146     std::iterator_traits&lt;It&gt;::value_type</tt> will yield its
 147     value type.</p>
 148
 149     <p><tt>pb_ds</tt> contains a tag hierarchy corresponding to the
 150     hierarchy in Figure <a href="#cd">Class hierarchy</a>. The tag
 151     hierarchy is shown in Figure <a href=
 152     "#tag_cd">Data-structure tag class hierarchy</a>.</p>
 153
 154     <h6 class="c1"><a name="tag_cd" id="tag_cd"><img src=
 155     "assoc_container_tag_cd.png" alt="no image" /></a></h6>
 156
 157     <h6 class="c1">Data-structure tag class hierarchy.</h6>
 158
 159     <p><a href=
 160     "container_base.html"><tt>container_base</tt></a>
 161     publicly defines <tt>container_category</tt> as one of the classes in
 162     Figure <a href="#tag_cd">Data-structure tag class
 163     hierarchy</a>. Given any container <tt>Cntnr</tt>, the tag of
 164     the underlying data structure can be found via
 165     <tt><b>typename</b> Cntnr::container_category</tt>.</p>
 166
 167     <p>Additionally, a traits mechanism can be used to query a
 168     container type for its attributes. Given any container
 169     <tt>Cntnr</tt>, then <tt><a href=
 170     "assoc_container_traits.html">__gnu_pbds::container_traits</a>&lt;Cntnr&gt;</tt>
 171     is a traits class identifying the properties of the
 172     container.</p>
 173
 174     <p>To find if a container can throw when a key is erased (which
 175     is true for vector-based trees, for example), one can
 176     use</p><a href=
 177     "assoc_container_traits.html"><tt>container_traits</tt></a><tt>&lt;Cntnr&gt;::erase_can_throw</tt>,
 178     for example.
 179
 180     <p>Some of the definitions in <a href=
 181     "assoc_container_traits.html"><tt>container_traits</tt></a> are
 182     dependent on other definitions. <i>E.g.</i>, if <a href=
 183     "assoc_container_traits.html"><tt>container_traits</tt></a><tt>&lt;Cntnr&gt;::order_preserving</tt>
 184     is <tt><b>true</b></tt> (which is the case for containers based
 185     on trees and tries), then the container can be split or joined;
 186     in this case, <a href=
 187     "assoc_container_traits.html"><tt>container_traits</tt></a><tt>&lt;Cntnr&gt;::split_join_can_throw</tt>
 188     indicates whether splits or joins can throw exceptions (which
 189     is true for vector-based trees); otherwise <a href=
 190     "assoc_container_traits.html"><tt>container_traits</tt></a><tt>&lt;Cntnr&gt;::split_join_can_throw</tt>
 191     will yield a compilation error. (This is somewhat similar to a
 192     compile-time version of the COM model [<a href=
 193     "references.html#mscom">mscom</a>]).</p>
 194
 195     <h2><a name="find_range" id="find_range">Point-Type and
 196     Range-Type Methods and Iterators</a></h2>
 197
 198     <h3><a name="it_unordered" id="it_unordered">Iterators in
 199     Unordered Container Types</a></h3>
 200
 201     <p><tt>pb_ds</tt> differentiates between two types of methods
 202     and iterators: point-type methods and iterators, and range-type
 203     methods and iterators (see <a href=
 204     "motivation.html#assoc_diff_it">Motivation::Associative
 205     Containers::Differentiating between Iterator Types</a> and
 206     <a href="tutorial.html#assoc_find_range">Tutorial::Associative
 207     Containers::Point-Type and Range-Type Methods and
 208     Iterators</a>). Each associative container's interface includes
 209     the methods:</p>
 210     <pre>
 211 const_point_iterator
 212 find(const_key_reference r_key) const;
 213
 214 point_iterator
 215 find(const_key_reference r_key);
 216
 217 std::pair&lt;point_iterator,<b>bool</b>&gt;
 218 insert(const_reference r_val);
 219 </pre>
 220
 221     <p>The relationship between these iterator types varies between
 222     container types. Figure <a href=
 223     "#point_iterators_cd">Point-type and range-type iterators</a>-A
 224     shows the most general invariant between point-type and
 225     range-type iterators: <tt>iterator</tt>, <i>e.g.</i>, can
 226     always be converted to <tt>point_iterator</tt>. Figure <a href=
 227     "#point_iterators_cd">Point-type and range-type iterators</a>-B
 228     shows invariants for order-preserving containers: point-type
 229     iterators are synonymous with range-type iterators.
 230     Orthogonally, Figure <a href="#point_iterators_cd">Point-type
 231     and range-type iterators</a>-C shows invariants for "set"
 232     containers: iterators are synonymous with const iterators.</p>
 233
 234     <h6 class="c1"><a name="point_iterators_cd" id=
 235     "point_iterators_cd"><img src="point_iterators_cd.png" alt=
 236     "no image" /></a></h6>
 237
 238     <h6 class="c1">Point-type and range-type iterators.</h6>
 239
 240     <p>Note that point-type iterators in self-organizing containers
 241     (<i>e.g.</i>, hash-based associative containers) lack movement
 242     operators, such as <tt><b>operator++</b></tt> - in fact, this
 243     is the reason why <tt>pb_ds</tt> differentiates from the STL's
 244     design on this point.</p>
 245
 246     <p>Typically, one can determine an iterator's movement
 247     capabilities in the STL using
 248     <tt>std::iterator_traits&lt;It&gt;iterator_category</tt>, which
 249     is a <tt><b>struct</b></tt> indicating the iterator's movement
 250     capabilities. Unfortunately, none of the STL's predefined
 251     categories reflect a pointer's <u>not</u> having any movement
 252     capabilities whatsoever. Consequently, <tt>pb_ds</tt> adds a
 253     type <a href=
 254     "trivial_iterator_tag.html"><tt>trivial_iterator_tag</tt></a>
 255     (whose name is taken from a concept in [<a href=
 256     "references.html#sgi_stl">sgi_stl</a>]), which is the category
 257     of iterators with no movement capabilities. All other STL tags,
 258     such as <tt>forward_iterator_tag</tt> retain their common
 259     use.</p>
 260
 261     <h3><a name="inv_guar" id="inv_guar">Invalidation
 262     Guarantees</a></h3>
 263
 264     <p><a href=
 265     "motivation.html#assoc_inv_guar">Motivation::Associative
 266     Containers::Differentiating between Iterator
 267     Types::Invalidation Guarantees</a> posed a problem. Given three
 268     different types of associative containers, a modifying
 269     operation (in that example, <tt>erase</tt>) invalidated
 270     iterators in three different ways: the iterator of one
 271     container remained completely valid - it could be de-referenced
 272     and incremented; the iterator of a different container could
 273     not even be de-referenced; the iterator of the third container
 274     could be de-referenced, but its "next" iterator changed
 275     unpredictably.</p>
 276
 277     <p>Distinguishing between find and range types allows
 278     fine-grained invalidation guarantees, because these questions
 279     correspond exactly to the question of whether point-type
 280     iterators and range-type iterators are valid. <a href=
 281     "#invalidation_guarantee_cd">Invalidation guarantees class
 282     hierarchy</a> shows tags corresponding to different types of
 283     invalidation guarantees.</p>
 284
 285     <h6 class="c1"><a name="invalidation_guarantee_cd" id=
 286     "invalidation_guarantee_cd"><img src=
 287     "invalidation_guarantee_cd.png" alt="no image" /></a></h6>
 288
 289     <h6 class="c1">Invalidation guarantees class hierarchy.</h6>
 290
 291     <ol>
 292       <li><a href=
 293       "basic_invalidation_guarantee.html"><tt>basic_invalidation_guarantee</tt></a>
 294       corresponds to a basic guarantee that a point-type iterator,
 295       a found pointer, or a found reference, remains valid as long
 296       as the container object is not modified.</li>
 297
 298       <li><a href=
 299       "point_invalidation_guarantee.html"><tt>point_invalidation_guarantee</tt></a>
 300       corresponds to a guarantee that a point-type iterator, a
 301       found pointer, or a found reference, remains valid even if
 302       the container object is modified.</li>
 303
 304       <li><a href=
 305       "range_invalidation_guarantee.html"><tt>range_invalidation_guarantee</tt></a>
 306       corresponds to a guarantee that a range-type iterator remains
 307       valid even if the container object is modified.</li>
 308     </ol>
 309
 310     <p>As shown in <a href=
 311     "tutorial.html#assoc_find_range">Tutorial::Associative
 312     Containers::Point-Type and Range-Type Methods and
 313     Iterators</a>, to find the invalidation guarantee of a
 314     container, one can use</p>
 315     <pre>
 316 <b>typename</b> <a href=
 317 "assoc_container_traits.html">container_traits</a>&lt;Cntnr&gt;::invalidation_guarantee
 318 </pre>
 319
 320     <p>which is one of the classes in Figure <a href=
 321     "#invalidation_guarantee_cd">Invalidation guarantees class
 322     hierarchy</a>.</p>
 323
 324     <p>Note that this hierarchy corresponds to the logic it
 325     represents: if a container has range-invalidation guarantees,
 326     then it must also have find invalidation guarantees;
 327     correspondingly, its invalidation guarantee (in this case
 328     <a href=
 329     "range_invalidation_guarantee.html"><tt>range_invalidation_guarantee</tt></a>)
 330     can be cast to its base class (in this case <a href=
 331     "point_invalidation_guarantee.html"><tt>point_invalidation_guarantee</tt></a>).
 332     This means that this this hierarchy can be used easily using
 333     standard metaprogramming techniques, by specializing on the
 334     type of <tt>invalidation_guarantee</tt>.</p>
 335
 336     <p>(These types of problems were addressed, in a more general
 337     setting, in [<a href=
 338     "references.html#meyers96more">meyers96more</a>] - Item 2. In
 339     our opinion, an invalidation-guarantee hierarchy would solve
 340     these problems in all container types - not just associative
 341     containers.)</p>
 342   </div>
 343 </body>
 344 </html>