libstdc++-v3/doc/html/manual/policy_data_structures_using.html

   1 <html><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><title>Using</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.76.1"><meta name="keywords" content="
   2         ISO C++
   3       ,
   4         policy
   5       ,
   6         container
   7       ,
   8         data
   9       ,
  10         structure
  11       ,
  12         associated
  13       ,
  14         tree
  15       ,
  16         trie
  17       ,
  18         hash
  19       ,
  20         metaprogramming
  21       "><meta name="keywords" content="
  22       ISO C++
  23     ,
  24       library
  25     "><meta name="keywords" content="
  26       ISO C++
  27     ,
  28       runtime
  29     ,
  30       library
  31     "><link rel="home" href="../index.html" title="The GNU C++ Library"><link rel="up" href="policy_data_structures.html" title="Chapter 22. Policy-Based Data Structures"><link rel="prev" href="policy_data_structures.html" title="Chapter 22. Policy-Based Data Structures"><link rel="next" href="policy_data_structures_design.html" title="Design"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Using</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="policy_data_structures.html">Prev</a> </td><th width="60%" align="center">Chapter 22. Policy-Based Data Structures</th><td width="20%" align="right"> <a accesskey="n" href="policy_data_structures_design.html">Next</a></td></tr></table><hr></div><div class="section" title="Using"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="containers.pbds.using"></a>Using</h2></div></div></div><div class="section" title="Prerequisites"><div class="titlepage"><div><div><h3 class="title"><a name="pbds.using.prereq"></a>Prerequisites</h3></div></div></div><p>The library contains only header files, and does not require any
  32       other libraries except the standard C++ library . All classes are
  33       defined in namespace <code class="code">__gnu_pbds</code>. The library internally
  34       uses macros beginning with <code class="code">PB_DS</code>, but
  35       <code class="code">#undef</code>s anything it <code class="code">#define</code>s (except for
  36       header guards). Compiling the library in an environment where macros
  37       beginning in <code class="code">PB_DS</code> are defined, may yield unpredictable
  38       results in compilation, execution, or both.</p><p>
  39         Further dependencies are necessary to create the visual output
  40         for the performance tests. To create these graphs, an
  41         additional package is needed: <span class="command"><strong>pychart</strong></span>.
  42       </p></div><div class="section" title="Organization"><div class="titlepage"><div><div><h3 class="title"><a name="pbds.using.organization"></a>Organization</h3></div></div></div><p>
  43         The various data structures are organized as follows.
  44       </p><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p>
  45             Branch-Based
  46           </p><div class="itemizedlist"><ul class="itemizedlist" type="circle"><li class="listitem"><p>
  47                 <code class="classname">basic_branch</code>
  48                 is an abstract base class for branched-based
  49                 associative-containers
  50               </p></li><li class="listitem"><p>
  51                 <code class="classname">tree</code>
  52                 is a concrete base class for tree-based
  53                 associative-containers
  54               </p></li><li class="listitem"><p>
  55                 <code class="classname">trie</code>
  56                 is a concrete base class trie-based
  57                 associative-containers
  58               </p></li></ul></div></li><li class="listitem"><p>
  59             Hash-Based
  60           </p><div class="itemizedlist"><ul class="itemizedlist" type="circle"><li class="listitem"><p>
  61                 <code class="classname">basic_hash_table</code>
  62                 is an abstract base class for hash-based
  63                 associative-containers
  64               </p></li><li class="listitem"><p>
  65                 <code class="classname">cc_hash_table</code>
  66                 is a concrete collision-chaining hash-based
  67                 associative-containers
  68               </p></li><li class="listitem"><p>
  69                 <code class="classname">gp_hash_table</code>
  70                 is a concrete (general) probing hash-based
  71                 associative-containers
  72               </p></li></ul></div></li><li class="listitem"><p>
  73             List-Based
  74           </p><div class="itemizedlist"><ul class="itemizedlist" type="circle"><li class="listitem"><p>
  75                 <code class="classname">list_update</code>
  76                 list-based update-policy associative container
  77               </p></li></ul></div></li><li class="listitem"><p>
  78             Heap-Based
  79           </p><div class="itemizedlist"><ul class="itemizedlist" type="circle"><li class="listitem"><p>
  80                 <code class="classname">priority_queue</code>
  81                 A priority queue.
  82               </p></li></ul></div></li></ul></div><p>
  83         The hierarchy is composed naturally so that commonality is
  84         captured by base classes. Thus <code class="function">operator[]</code>
  85         is defined at the base of any hierarchy, since all derived
  86         containers support it. Conversely <code class="function">split</code> is
  87         defined in <code class="classname">basic_branch</code>, since only
  88         tree-like containers support it.
  89       </p><p>
  90         In addition, there are the following diagnostics classes,
  91         used to report errors specific to this library's data
  92         structures.
  93       </p><div class="figure"><a name="id641972"></a><p class="title"><b>Figure 22.7. Exception Hierarchy</b></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_exception_hierarchy.png" align="middle" alt="Exception Hierarchy"></div></div></div><br class="figure-break"></div><div class="section" title="Tutorial"><div class="titlepage"><div><div><h3 class="title"><a name="pbds.using.tutorial"></a>Tutorial</h3></div></div></div><div class="section" title="Basic Use"><div class="titlepage"><div><div><h4 class="title"><a name="pbds.using.tutorial.basic"></a>Basic Use</h4></div></div></div><p>
  94           For the most part, the policy-based containers containers in
  95           namespace <code class="literal">__gnu_pbds</code> have the same interface as
  96           the equivalent containers in the standard C++ library, except for
  97           the names used for the container classes themselves. For example,
  98           this shows basic operations on a collision-chaining hash-based
  99           container:
 100         </p><pre class="programlisting">
 101           #include &lt;ext/pb_ds/assoc_container.h&gt;
 102
 103           int main()
 104           {
 105           __gnu_pbds::cc_hash_table&lt;int, char&gt; c;
 106           c[2] = 'b';
 107           assert(c.find(1) == c.end());
 108           };
 109         </pre><p>
 110           The container is called
 111           <code class="classname">__gnu_pbds::cc_hash_table</code> instead of
 112           <code class="classname">std::unordered_map</code>, since <span class="quote">“<span class="quote">unordered
 113           map</span>”</span> does not necessarily mean a hash-based map as implied by
 114           the C++ library (C++11 or TR1). For example, list-based associative
 115           containers, which are very useful for the construction of
 116           "multimaps," are also unordered.
 117         </p><p>This snippet shows a red-black tree based container:</p><pre class="programlisting">
 118           #include &lt;ext/pb_ds/assoc_container.h&gt;
 119
 120           int main()
 121           {
 122           __gnu_pbds::tree&lt;int, char&gt; c;
 123           c[2] = 'b';
 124           assert(c.find(2) != c.end());
 125           };
 126         </pre><p>The container is called <code class="classname">tree</code> instead of
 127         <code class="classname">map</code> since the underlying data structures are
 128         being named with specificity.
 129         </p><p>
 130           The member function naming convention is to strive to be the same as
 131           the equivalent member functions in other C++ standard library
 132           containers. The familiar methods are unchanged:
 133           <code class="function">begin</code>, <code class="function">end</code>,
 134           <code class="function">size</code>, <code class="function">empty</code>, and
 135           <code class="function">clear</code>.
 136         </p><p>
 137           This isn't to say that things are exactly as one would expect, given
 138           the container requirments and interfaces in the C++ standard.
 139         </p><p>
 140           The names of containers' policies and policy accessors are
 141           different then the usual. For example, if <span class="type">hash_type</span> is
 142         some type of hash-based container, then</p><pre class="programlisting">
 143           hash_type::hash_fn
 144         </pre><p>
 145           gives the type of its hash functor, and if <code class="varname">obj</code> is
 146           some hash-based container object, then
 147         </p><pre class="programlisting">
 148           obj.get_hash_fn()
 149         </pre><p>will return a reference to its hash-functor object.</p><p>
 150           Similarly, if <span class="type">tree_type</span> is some type of tree-based
 151           container, then
 152         </p><pre class="programlisting">
 153           tree_type::cmp_fn
 154         </pre><p>
 155           gives the type of its comparison functor, and if
 156           <code class="varname">obj</code> is some tree-based container object,
 157           then
 158         </p><pre class="programlisting">
 159           obj.get_cmp_fn()
 160         </pre><p>will return a reference to its comparison-functor object.</p><p>
 161           It would be nice to give names consistent with those in the existing
 162           C++ standard (inclusive of TR1). Unfortunately, these standard
 163           containers don't consistently name types and methods. For example,
 164           <code class="classname">std::tr1::unordered_map</code> uses
 165           <span class="type">hasher</span> for the hash functor, but
 166           <code class="classname">std::map</code> uses <span class="type">key_compare</span> for
 167           the comparison functor. Also, we could not find an accessor for
 168           <code class="classname">std::tr1::unordered_map</code>'s hash functor, but
 169           <code class="classname">std::map</code> uses <code class="classname">compare</code>
 170           for accessing the comparison functor.
 171         </p><p>
 172           Instead, <code class="literal">__gnu_pbds</code> attempts to be internally
 173           consistent, and uses standard-derived terminology if possible.
 174         </p><p>
 175           Another source of difference is in scope:
 176           <code class="literal">__gnu_pbds</code> contains more types of associative
 177           containers than the standard C++ library, and more opportunities
 178           to configure these new containers, since different types of
 179           associative containers are useful in different settings.
 180         </p><p>
 181           Namespace <code class="literal">__gnu_pbds</code> contains different classes for
 182           hash-based containers, tree-based containers, trie-based containers,
 183           and list-based containers.
 184         </p><p>
 185           Since associative containers share parts of their interface, they
 186           are organized as a class hierarchy.
 187         </p><p>Each type or method is defined in the most-common ancestor
 188         in which it makes sense.
 189         </p><p>For example, all associative containers support iteration
 190         expressed in the following form:
 191         </p><pre class="programlisting">
 192           const_iterator
 193           begin() const;
 194
 195           iterator
 196           begin();
 197
 198           const_iterator
 199           end() const;
 200
 201           iterator
 202           end();
 203         </pre><p>
 204           But not all containers contain or use hash functors. Yet, both
 205           collision-chaining and (general) probing hash-based associative
 206           containers have a hash functor, so
 207           <code class="classname">basic_hash_table</code> contains the interface:
 208         </p><pre class="programlisting">
 209           const hash_fn&amp;
 210           get_hash_fn() const;
 211
 212           hash_fn&amp;
 213           get_hash_fn();
 214         </pre><p>
 215           so all hash-based associative containers inherit the same
 216           hash-functor accessor methods.
 217         </p></div><div class="section" title="Configuring via Template Parameters"><div class="titlepage"><div><div><h4 class="title"><a name="pbds.using.tutorial.configuring"></a>
 218             Configuring via Template Parameters
 219           </h4></div></div></div><p>
 220           In general, each of this library's containers is
 221           parametrized by more policies than those of the standard library. For
 222           example, the standard hash-based container is parametrized as
 223           follows:
 224         </p><pre class="programlisting">
 225           template&lt;typename Key, typename Mapped, typename Hash,
 226           typename Pred, typename Allocator, bool Cache_Hashe_Code&gt;
 227           class unordered_map;
 228         </pre><p>
 229           and so can be configured by key type, mapped type, a functor
 230           that translates keys to unsigned integral types, an equivalence
 231           predicate, an allocator, and an indicator whether to store hash
 232           values with each entry. this library's collision-chaining
 233           hash-based container is parametrized as
 234         </p><pre class="programlisting">
 235           template&lt;typename Key, typename Mapped, typename Hash_Fn,
 236           typename Eq_Fn, typename Comb_Hash_Fn,
 237           typename Resize_Policy, bool Store_Hash
 238           typename Allocator&gt;
 239           class cc_hash_table;
 240         </pre><p>
 241           and so can be configured by the first four types of
 242           <code class="classname">std::tr1::unordered_map</code>, then a
 243           policy for translating the key-hash result into a position
 244           within the table, then a policy by which the table resizes,
 245           an indicator whether to store hash values with each entry,
 246           and an allocator (which is typically the last template
 247           parameter in standard containers).
 248         </p><p>
 249           Nearly all policy parameters have default values, so this
 250           need not be considered for casual use. It is important to
 251           note, however, that hash-based containers' policies can
 252           dramatically alter their performance in different settings,
 253           and that tree-based containers' policies can make them
 254           useful for other purposes than just look-up.
 255         </p><p>As opposed to associative containers, priority queues have
 256         relatively few configuration options. The priority queue is
 257         parametrized as follows:</p><pre class="programlisting">
 258           template&lt;typename Value_Type, typename Cmp_Fn,typename Tag,
 259           typename Allocator&gt;
 260           class priority_queue;
 261         </pre><p>The <code class="classname">Value_Type</code>, <code class="classname">Cmp_Fn</code>, and
 262         <code class="classname">Allocator</code> parameters are the container's value type,
 263         comparison-functor type, and allocator type, respectively;
 264         these are very similar to the standard's priority queue. The
 265         <code class="classname">Tag</code> parameter is different: there are a number of
 266         pre-defined tag types corresponding to binary heaps, binomial
 267         heaps, etc., and <code class="classname">Tag</code> should be instantiated
 268         by one of them.</p><p>Note that as opposed to the
 269         <code class="classname">std::priority_queue</code>,
 270         <code class="classname">__gnu_pbds::priority_queue</code> is not a
 271         sequence-adapter; it is a regular container.</p></div><div class="section" title="Querying Container Attributes"><div class="titlepage"><div><div><h4 class="title"><a name="pbds.using.tutorial.traits"></a>
 272             Querying Container Attributes
 273           </h4></div></div></div><p></p><p>A containers underlying data structure
 274         affect their performance; Unfortunately, they can also affect
 275         their interface. When manipulating generically associative
 276         containers, it is often useful to be able to statically
 277         determine what they can support and what the cannot.
 278         </p><p>Happily, the standard provides a good solution to a similar
 279         problem - that of the different behavior of iterators. If
 280         <code class="classname">It</code> is an iterator, then
 281         </p><pre class="programlisting">
 282           typename std::iterator_traits&lt;It&gt;::iterator_category
 283         </pre><p>is one of a small number of pre-defined tag classes, and
 284         </p><pre class="programlisting">
 285           typename std::iterator_traits&lt;It&gt;::value_type
 286         </pre><p>is the value type to which the iterator "points".</p><p>
 287           Similarly, in this library, if <span class="type">C</span> is a
 288           container, then <code class="classname">container_traits</code> is a
 289           trait class that stores information about the kind of
 290           container that is implemented.
 291         </p><pre class="programlisting">
 292           typename container_traits&lt;C&gt;::container_category
 293         </pre><p>
 294           is one of a small number of predefined tag structures that
 295           uniquely identifies the type of underlying data structure.
 296         </p><p>In most cases, however, the exact underlying data
 297         structure is not really important, but what is important is
 298         one of its other attributes: whether it guarantees storing
 299         elements by key order, for example. For this one can
 300         use</p><pre class="programlisting">
 301           typename container_traits&lt;C&gt;::order_preserving
 302         </pre><p>
 303           Also,
 304         </p><pre class="programlisting">
 305           typename container_traits&lt;C&gt;::invalidation_guarantee
 306         </pre><p>is the container's invalidation guarantee. Invalidation
 307         guarantees are especially important regarding priority queues,
 308         since in this library's design, iterators are practically the
 309         only way to manipulate them.</p></div><div class="section" title="Point and Range Iteration"><div class="titlepage"><div><div><h4 class="title"><a name="pbds.using.tutorial.point_range_iteration"></a>
 310             Point and Range Iteration
 311           </h4></div></div></div><p></p><p>This library differentiates between two types of methods
 312         and iterators: point-type, and range-type. For example,
 313         <code class="function">find</code> and <code class="function">insert</code> are point-type methods, since
 314         they each deal with a specific element; their returned
 315         iterators are point-type iterators. <code class="function">begin</code> and
 316         <code class="function">end</code> are range-type methods, since they are not used to
 317         find a specific element, but rather to go over all elements in
 318         a container object; their returned iterators are range-type
 319         iterators.
 320         </p><p>Most containers store elements in an order that is
 321         determined by their interface. Correspondingly, it is fine that
 322         their point-type iterators are synonymous with their range-type
 323         iterators. For example, in the following snippet
 324         </p><pre class="programlisting">
 325           std::for_each(c.find(1), c.find(5), foo);
 326         </pre><p>
 327           two point-type iterators (returned by <code class="function">find</code>) are used
 328           for a range-type purpose - going over all elements whose key is
 329           between 1 and 5.
 330         </p><p>
 331           Conversely, the above snippet makes no sense for
 332           self-organizing containers - ones that order (and reorder)
 333           their elements by implementation. It would be nice to have a
 334           uniform iterator system that would allow the above snippet to
 335           compile only if it made sense.
 336         </p><p>
 337           This could trivially be done by specializing
 338           <code class="function">std::for_each</code> for the case of iterators returned by
 339           <code class="classname">std::tr1::unordered_map</code>, but this would only solve the
 340           problem for one algorithm and one container. Fundamentally, the
 341           problem is that one can loop using a self-organizing
 342           container's point-type iterators.
 343         </p><p>
 344           This library's containers define two families of
 345           iterators: <span class="type">point_const_iterator</span> and
 346           <span class="type">point_iterator</span> are the iterator types returned by
 347           point-type methods; <span class="type">const_iterator</span> and
 348           <span class="type">iterator</span> are the iterator types returned by range-type
 349           methods.
 350         </p><pre class="programlisting">
 351           class &lt;- some container -&gt;
 352           {
 353           public:
 354           ...
 355
 356           typedef &lt;- something -&gt; const_iterator;
 357
 358           typedef &lt;- something -&gt; iterator;
 359
 360           typedef &lt;- something -&gt; point_const_iterator;
 361
 362           typedef &lt;- something -&gt; point_iterator;
 363
 364           ...
 365
 366           public:
 367           ...
 368
 369           const_iterator begin () const;
 370
 371           iterator begin();
 372
 373           point_const_iterator find(...) const;
 374
 375           point_iterator find(...);
 376           };
 377         </pre><p>For
 378         containers whose interface defines sequence order , it
 379         is very simple: point-type and range-type iterators are exactly
 380         the same, which means that the above snippet will compile if it
 381         is used for an order-preserving associative container.
 382         </p><p>
 383           For self-organizing containers, however, (hash-based
 384           containers as a special example), the preceding snippet will
 385           not compile, because their point-type iterators do not support
 386           <code class="function">operator++</code>.
 387         </p><p>In any case, both for order-preserving and self-organizing
 388         containers, the following snippet will compile:
 389         </p><pre class="programlisting">
 390           typename Cntnr::point_iterator it = c.find(2);
 391         </pre><p>
 392           because a range-type iterator can always be converted to a
 393           point-type iterator.
 394         </p><p>Distingushing between iterator types also
 395         raises the point that a container's iterators might have
 396         different invalidation rules concerning their de-referencing
 397         abilities and movement abilities. This now corresponds exactly
 398         to the question of whether point-type and range-type iterators
 399         are valid. As explained above, <code class="classname">container_traits</code> allows
 400         querying a container for its data structure attributes. The
 401         iterator-invalidation guarantees are certainly a property of
 402         the underlying data structure, and so
 403         </p><pre class="programlisting">
 404           container_traits&lt;C&gt;::invalidation_guarantee
 405         </pre><p>
 406           gives one of three pre-determined types that answer this
 407           query.
 408         </p></div></div><div class="section" title="Examples"><div class="titlepage"><div><div><h3 class="title"><a name="pbds.using.examples"></a>Examples</h3></div></div></div><p>
 409         Additional code examples are provided in the source
 410         distribution, as part of the regression and performance
 411         testsuite.
 412       </p><div class="section" title="Intermediate Use"><div class="titlepage"><div><div><h4 class="title"><a name="pbds.using.examples.basic"></a>Intermediate Use</h4></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p>
 413               Basic use of maps:
 414               <code class="filename">basic_map.cc</code>
 415             </p></li><li class="listitem"><p>
 416               Basic use of sets:
 417               <code class="filename">basic_set.cc</code>
 418             </p></li><li class="listitem"><p>
 419               Conditionally erasing values from an associative container object:
 420               <code class="filename">erase_if.cc</code>
 421             </p></li><li class="listitem"><p>
 422               Basic use of multimaps:
 423               <code class="filename">basic_multimap.cc</code>
 424             </p></li><li class="listitem"><p>
 425               Basic use of multisets:
 426               <code class="filename">basic_multiset.cc</code>
 427             </p></li><li class="listitem"><p>
 428               Basic use of priority queues:
 429               <code class="filename">basic_priority_queue.cc</code>
 430             </p></li><li class="listitem"><p>
 431               Splitting and joining priority queues:
 432               <code class="filename">priority_queue_split_join.cc</code>
 433             </p></li><li class="listitem"><p>
 434               Conditionally erasing values from a priority queue:
 435               <code class="filename">priority_queue_erase_if.cc</code>
 436             </p></li></ul></div></div><div class="section" title="Querying with container_traits"><div class="titlepage"><div><div><h4 class="title"><a name="pbds.using.examples.query"></a>Querying with <code class="classname">container_traits</code> </h4></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p>
 437               Using <code class="classname">container_traits</code> to query
 438               about underlying data structure behavior:
 439               <code class="filename">assoc_container_traits.cc</code>
 440             </p></li><li class="listitem"><p>
 441               A non-compiling example showing wrong use of finding keys in
 442               hash-based containers: <code class="filename">hash_find_neg.cc</code>
 443             </p></li><li class="listitem"><p>
 444               Using <code class="classname">container_traits</code>
 445               to query about underlying data structure behavior:
 446               <code class="filename">priority_queue_container_traits.cc</code>
 447             </p></li></ul></div></div><div class="section" title="By Container Method"><div class="titlepage"><div><div><h4 class="title"><a name="pbds.using.examples.container"></a>By Container Method</h4></div></div></div><p></p><div class="section" title="Hash-Based"><div class="titlepage"><div><div><h5 class="title"><a name="pbds.using.examples.container.hash"></a>Hash-Based</h5></div></div></div><div class="section" title="size Related"><div class="titlepage"><div><div><h6 class="title"><a name="pbds.using.examples.container.hash.resize"></a>size Related</h6></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p>
 448                   Setting the initial size of a hash-based container
 449                   object:
 450                   <code class="filename">hash_initial_size.cc</code>
 451                 </p></li><li class="listitem"><p>
 452                   A non-compiling example showing how not to resize a
 453                   hash-based container object:
 454                   <code class="filename">hash_resize_neg.cc</code>
 455                 </p></li><li class="listitem"><p>
 456                   Resizing the size of a hash-based container object:
 457                   <code class="filename">hash_resize.cc</code>
 458                 </p></li><li class="listitem"><p>
 459                   Showing an illegal resize of a hash-based container
 460                   object:
 461                   <code class="filename">hash_illegal_resize.cc</code>
 462                 </p></li><li class="listitem"><p>
 463                   Changing the load factors of a hash-based container
 464                   object: <code class="filename">hash_load_set_change.cc</code>
 465                 </p></li></ul></div></div><div class="section" title="Hashing Function Related"><div class="titlepage"><div><div><h6 class="title"><a name="pbds.using.examples.container.hash.hashor"></a>Hashing Function Related</h6></div></div></div><p></p><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p>
 466                   Using a modulo range-hashing function for the case of an
 467                   unknown skewed key distribution:
 468                   <code class="filename">hash_mod.cc</code>
 469                 </p></li><li class="listitem"><p>
 470                   Writing a range-hashing functor for the case of a known
 471                   skewed key distribution:
 472                   <code class="filename">shift_mask.cc</code>
 473                 </p></li><li class="listitem"><p>
 474                   Storing the hash value along with each key:
 475                   <code class="filename">store_hash.cc</code>
 476                 </p></li><li class="listitem"><p>
 477                   Writing a ranged-hash functor:
 478                   <code class="filename">ranged_hash.cc</code>
 479                 </p></li></ul></div></div></div><div class="section" title="Branch-Based"><div class="titlepage"><div><div><h5 class="title"><a name="pbds.using.examples.container.branch"></a>Branch-Based</h5></div></div></div><div class="section" title="split or join Related"><div class="titlepage"><div><div><h6 class="title"><a name="pbds.using.examples.container.branch.split"></a>split or join Related</h6></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p>
 480                   Joining two tree-based container objects:
 481                   <code class="filename">tree_join.cc</code>
 482                 </p></li><li class="listitem"><p>
 483                   Splitting a PATRICIA trie container object:
 484                   <code class="filename">trie_split.cc</code>
 485                 </p></li><li class="listitem"><p>
 486                   Order statistics while joining two tree-based container
 487                   objects:
 488                   <code class="filename">tree_order_statistics_join.cc</code>
 489                 </p></li></ul></div></div><div class="section" title="Node Invariants"><div class="titlepage"><div><div><h6 class="title"><a name="pbds.using.examples.container.branch.invariants"></a>Node Invariants</h6></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p>
 490                   Using trees for order statistics:
 491                   <code class="filename">tree_order_statistics.cc</code>
 492                 </p></li><li class="listitem"><p>
 493                   Augmenting trees to support operations on line
 494                   intervals:
 495                   <code class="filename">tree_intervals.cc</code>
 496                 </p></li></ul></div></div><div class="section" title="trie"><div class="titlepage"><div><div><h6 class="title"><a name="pbds.using.examples.container.branch.trie"></a>trie</h6></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p>
 497                   Using a PATRICIA trie for DNA strings:
 498                   <code class="filename">trie_dna.cc</code>
 499                 </p></li><li class="listitem"><p>
 500                   Using a PATRICIA
 501                   trie for finding all entries whose key matches a given prefix:
 502                   <code class="filename">trie_prefix_search.cc</code>
 503                 </p></li></ul></div></div></div><div class="section" title="Priority Queues"><div class="titlepage"><div><div><h5 class="title"><a name="pbds.using.examples.container.priority_queue"></a>Priority Queues</h5></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p>
 504                 Cross referencing an associative container and a priority
 505                 queue: <code class="filename">priority_queue_xref.cc</code>
 506               </p></li><li class="listitem"><p>
 507                 Cross referencing a vector and a priority queue using a
 508                 very simple version of Dijkstra's shortest path
 509                 algorithm:
 510                 <code class="filename">priority_queue_dijkstra.cc</code>
 511               </p></li></ul></div></div></div></div></div><div class="navfooter"><hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="policy_data_structures.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="policy_data_structures.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="policy_data_structures_design.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter 22. Policy-Based Data Structures </td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top"> Design</td></tr></table></div></body></html>