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