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

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