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

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
   2     "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
   3
   4 <html xmlns="http://www.w3.org/1999/xhtml">
   5 <head>
   6   <meta name="generator" content=
   7   "HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" />
   8
   9   <title>Tutorial</title>
  10   <meta http-equiv="Content-Type" content=
  11   "text/html; charset=us-ascii" />
  12   </head>
  13
  14 <body>
  15   <div id="page">
  16     <h1>Short Tutorial</h1>
  17
  18     <p>Following is a short tutorial illustrating the main points
  19     of <tt>pb_ds</tt>. <a href="concepts.html">Concepts</a>
  20     describes and summarizes some concepts.</p>
  21
  22     <h2><a name="assoc_main" id="assoc_main">Associative
  23     Containers</a></h2>
  24
  25     <h3><a name="assoc_basic" id="assoc_basic">Basic Use</a></h3>
  26
  27     <p>For the most part, <tt>pb_ds</tt>'s containers have the same
  28     interface as the STL's, except for the names used for the
  29     container classes themselves. For example, this shows basic
  30     operations on a collision-chaining hash-based container:</p>
  31
  32     <pre>
  33 <a href=
  34 "cc_hash_table.html">cc_hash_table</a>&lt;<b>int</b>, <b>char</b>&gt; c;
  35
  36 c[2] = 'b';
  37
  38 assert(c.find(1) == c.end());
  39 </pre>
  40
  41     <p>The container is called <a href=
  42     "cc_hash_table.html"><tt>cc_hash_table</tt></a> as
  43     opposed to <tt>unordered_map</tt>, since "unordered map" does
  44     not necessarily mean a hash-based map (as the STL implicitly
  45     implies). For example, list-based associative containers, which
  46     are very useful for the construction of "multimaps" (see
  47     <a href=
  48     "assoc_performance_tests.html#msc">Associative-Container
  49     Performance Tests::Observations::Mapping-Semantics
  50     Considerations</a>), are also unordered. It is also not called
  51     <tt>hash_map</tt> since there are more ways than one to
  52     implement hash tables.</p>
  53
  54     <p>This snippet shows a red-black tree based container:</p>
  55     <pre>
  56 <a href=
  57 "tree.html">tree</a>&lt;<b>int</b>, <b>char</b>&gt; c;
  58
  59 c[2] = 'b';
  60
  61 assert(c.find(2) != c.end());
  62 </pre>
  63
  64     <p>The container is called <a href=
  65     "tree.html"><tt>tree</tt></a>
  66     as opposed to <tt>map</tt>, since "map" doesn't say that
  67     much.</p>
  68
  69     <p>Most of the STL's familiar methods are unchanged.
  70     <i>E.g.</i>, <tt>being</tt>, <tt>end</tt>, <tt>size</tt>,
  71     <tt>empty</tt>, and <tt>clear</tt>, do just the same as is
  72     customary. <a href=
  73     "assoc_examples.html#basic_usage">Associative-Container
  74     Examples::Basic use</a>, and especially <a href=
  75     "http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc%2B%2B-v3/testsuite/ext/pb_ds/example/basic_map.cc"><tt>basic_map.cc</tt></a>,
  76     show examples of this.</p>
  77
  78 <p>This isn't to say that things are exactly as one would expect,
  79 given the container requirments and interfaces in the C++
  80 standard.</p>
  81
  82
  83     <p>The names of containers' policies and policy accessors are
  84     different than those of the STL. For example, if <tt>C</tt> is
  85     some type of hash-based container, then</p>
  86     <pre>
  87 C::hash_fn
  88 </pre>gives the type of its hash functor, and if <tt>c</tt> is some
  89 hash-based container object, then
  90     <pre>
  91 c.get_hash_fn()
  92 </pre>
  93
  94     <p>will return a reference to its hash-functor object.</p>
  95
  96     <p>Similarly, if <tt>C</tt> is some type of tree-based
  97     container, then</p>
  98     <pre>
  99 C::cmp_fn
 100 </pre>gives the type of its comparison functor, and if <tt>c</tt>
 101 is some tree-based container object, then
 102     <pre>
 103 c.get_cmp_fn()
 104 </pre>
 105
 106     <p>will return a reference to its comparison-functor
 107     object.</p>
 108
 109     <p>It would be nice to give names consistent with those in the
 110     existing C++ standard (inclusive of TR1). Unfortunately, these
 111     standard containers don't consistently name types and
 112     methods. For example, <tt>std::tr1::unordered_map</tt> uses
 113     <tt>hasher</tt> for the hash functor, but <tt>std::map</tt> uses
 114     <tt>key_compare</tt> for the comparison functor. Also, we could
 115     not find an accessor for <tt>std::tr1::unordered_map</tt>'s hash
 116     functor, but <tt>std::map</tt> uses <tt>compare</tt> for accessing
 117     the comparison functor.</p>
 118
 119 <p>Instead, <tt>pb_ds</tt> attempts to be internally consistent, and
 120 uses standard-derived terminology if possible.
 121 </p>
 122
 123     <p>Another source of difference is in scope: <tt>pb_ds</tt>
 124     contains more types of associative containers than the STL, and
 125     more opportunities to configure these new containers, since
 126     different types of associative containers are useful in different
 127     settings (see <a href=
 128     "assoc_performance_tests.html#dss_family_choice">Associative-Container
 129     Performance Tests::Observations::Underlying Data-Structure
 130     Families</a>).</p>
 131
 132     <p><tt>pb_ds</tt> contains different classes for hash-based containers,
 133     tree-based containers, trie-based containers, and list-based
 134     containers. <a href=
 135     "interface.html#containers_assoc">Inteface::Containers::Associative
 136     Containers</a> lists the containers. <a href=
 137     "hash_based_containers.html">Design::Associative
 138     Containers::Hash-Based Containers</a>, <a href=
 139     "tree_based_containers.html">Design::Associative
 140     Containers::Tree-Based Containers</a>, <a href=
 141     "trie_based_containers.html">Design::Associative
 142     Containers::Trie-Based Containers</a>, and <a href=
 143     "lu_based_containers.html">Design::Associative
 144     Containers::List-Based Containers</a>, explain some more about
 145     these types of containers, respectively.</p>
 146
 147     <p>Since associative containers share parts of their interface,
 148     they are organized as a class hierarchy; it is shown in Figure
 149     <a href="#cd">Class hierarchy</a>.</p>
 150
 151     <h6 class="c1"><a name="cd" id="cd"><img src="container_cd.png" alt=
 152     "no image" /></a></h6>
 153
 154     <h6 class="c1">Class hierarchy.</h6>
 155
 156     <p>Each type or method is defined in the most-common ancestor
 157     in which it makes sense:
 158   <a href=
 159     "http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc%2B%2B-v3/testsuite/ext/pb_ds/example/basic_map.cc"><tt>basic_map.cc</tt></a>
 160     shows an example of most of the associative-container
 161     types.</p>
 162
 163
 164     <p>For example, all associative containers support iteration.
 165     Consequently, <a href=
 166     "container_base.html"><tt>container_base</tt></a> has the
 167     interface:</p>
 168     <pre>
 169 <b>template</b>&lt;...&gt;
 170 <b>class</b> <a href="container_base.html">container_base</a>
 171 {
 172     ...
 173
 174 <b>public</b>:
 175     ...
 176
 177     const_iterator
 178     begin() <b>const</b>;
 179
 180     iterator
 181     begin();
 182
 183     const_iterator
 184     end() <b>const</b>;
 185
 186     iterator
 187     end();
 188
 189     ...
 190 };
 191 </pre>
 192
 193     <p>and so all associative containers inherent this method.
 194     Conversely, both collision-chaining and (general) probing
 195     hash-based associative containers have a hash functor, so
 196     <a href=
 197     "basic_hash_table.html"><tt>basic_hash_table</tt></a>
 198     has the interface:</p>
 199     <pre>
 200 <b>template</b>&lt;...&gt;
 201 <b>class</b> <a href="basic_hash_table.html">basic_hash_table</a> : <b>public</b> <a href="container_base.html">container_base</a>
 202 {
 203     ...
 204
 205 <b>public</b>:
 206     ...
 207
 208     const hash_fn&amp;
 209     get_hash_fn() const;
 210
 211     hash_fn&amp;
 212     get_hash_fn();
 213     ...
 214 };
 215 </pre>
 216
 217     <p>and so all hash-based associative containers inherit the
 218     same hash-functor accessor methods.</p>
 219
 220     <p>This is discussed further in <a href=
 221     "ds_gen.html">Design::Associative Containers::Data-Structure
 222     Genericity</a>.</p>
 223
 224     <h3><a name="assoc_policies" id="assoc_policies">Configuring
 225     Associative Containers</a></h3>
 226
 227     <p>In general, each of <tt>pb_ds</tt>'s containers is
 228     parametrized by more policies than those of the STL's. For
 229     example, the STL's hash-based container is parametrized as
 230     follows:</p>
 231     <pre>
 232 <b>template</b>&lt;
 233     <b>typename</b> Key,
 234     <b>typename</b> Mapped,
 235     <b>typename</b> Hash,
 236     <b>typename</b> Pred,
 237     <b>typename</b> Allocator,
 238     <b>bool</b> Cache_Hashe_Code&gt;
 239 <b>class</b> unordered_map;
 240 </pre>
 241
 242     <p>and so can be configured by key type, mapped type, a functor
 243     that translates keys to unsigned integral types, an equivalence
 244     predicate, an allocator, and an indicator whether to store hash
 245     values with each entry. <tt>pb_ds</tt>'s collision-chaining
 246     hash-based container is parametrized as</p>
 247     <pre>
 248 <b>template</b>&lt;
 249     <b>typename</b> Key,
 250     <b>typename</b> Mapped,
 251     <b>typename</b> Hash_Fn,
 252     <b>typename</b> Eq_Fn,
 253     <b>typename</b> Comb_Hash_Fn,
 254     <b>typename</b> Resize_Policy
 255     <b>bool</b> Store_Hash
 256     <b>typename</b> Allocator&gt;
 257 <b>class</b> <a href=
 258 "cc_hash_table.html">cc_hash_table</a>;
 259 </pre>
 260
 261     <p>and so can be configured by the first four types of
 262     <tt>std::tr1::unordered_map</tt>, then a policy for translating
 263     the key-hash result into a position within the table, then a
 264     policy by which the table resizes, an indicator whether to
 265     store hash values with each entry, and an allocator (which is
 266     typically the last template parameter in STL containers).</p>
 267
 268     <p>Nearly all policy parameters have default values, so this
 269     need not be considered for casual use. It is important to note,
 270     however, that hash-based containers' policies can dramatically
 271     alter their performance in different settings, and that
 272     tree-based containers' policies can make them useful for other
 273     purposes than just look-up.</p>
 274
 275     <p><a href="hash_based_containers.html">Design::Associative
 276     Containers::Hash-Based Containers</a>, <a href=
 277     "tree_based_containers.html">Design::Associative
 278     Containers::Tree-Based Containers</a>, <a href=
 279     "trie_based_containers.html">Design::Associative
 280     Containers::Trie-Based Containers</a>, and <a href=
 281     "lu_based_containers.html">Design::Associative
 282     Containers::List-Based Containers</a>, explain some more about
 283     configuring hash based, tree based, trie based, and list base
 284     containers, respectively. <a href=
 285     "interface.html#ds_policy_classes">Interface::Container Policy
 286     Classes</a> shows the different policy classes for configuring
 287     associative containers. <a href=
 288     "assoc_examples.html#hash_based">Examples::Hash-Based
 289     Containers</a>, <a href=
 290     "assoc_examples.html#tree_like_based">Examples::Tree-Like-Based
 291     Containers</a>, and <a href=
 292     "assoc_examples.html#trie_based">Examples::Trie-Based
 293     Containers</a> show examples for this.</p>
 294
 295     <h3><a name="assoc_ds_gen" id="assoc_ds_gen">Determining
 296     Containers' Attributes</a></h3>
 297
 298     <p>Associative-containers' underlying data structures obviously
 299     affect their performance; Unfortunately, they can also affect
 300     their interface. When manipulating generically associative
 301     containers, it is often useful to be able to statically
 302     determine what they can support and what the cannot. (This was
 303     discussed in <a href=
 304     "motivation.html#assoc_ds_genericity">Motivation::Associative
 305     Containers::Data-Structure Genericity</a>.)</p>
 306
 307     <p>Happily, the STL provides a good solution to a similar
 308     problem - that of the different behavior of iterators. If
 309     <tt>It</tt> is an iterator, then</p>
 310     <pre>
 311 <b>typename</b> std::iterator_traits&lt;It&gt;::iterator_category
 312 </pre>
 313
 314     <p>is one of a small number of pre-defined
 315     <tt><b>struct</b></tt>s, and,</p>
 316     <pre>
 317 <b>typename</b> std::iterator_traits&lt;It&gt;::value_type
 318 </pre>
 319
 320     <p>is the value type to which the iterator "points".</p>
 321
 322     <p>Similarly, in <tt>pb_ds</tt>, if <tt>C</tt> is an
 323     associative container, then</p>
 324     <pre>
 325 <b>typename</b> <a href=
 326 "assoc_container_traits.html"><tt>container_traits</tt></a>&lt;C&gt;::container_category
 327 </pre>is one of a small number of pre-defined
 328 <tt><b>struct</b></tt>s, each one corresponding to a class in
 329 Figure <a href="#cd">Class hierarchy</a>. These tags are listed in
 330 <a href="interface.html#ds_ts_assoc">Interface::Associative
 331 Containers::Data-Structure Tags and Traits::Data-Structure
 332 Tags::Associative-Containers</a>; <a href="ds_gen.html#container_traits">
 333     Design::Associative Containers::Data-Structure Tags and
 334     Traits</a> explains this further; <a href=
 335     "ds_gen.html#tag_cd">Design::Associative
 336     Containers::Data-Structure Tags and Traits::Data-structure tag
 337     class hierarchy</a> shows a class diagram.
 338
 339     <p>In most cases, however, the exact underlying data structure
 340     is not really important, but only one of its attributes:
 341     whether it guarantees storing elements by key order, for
 342     example. For this one can use</p>
 343     <pre>
 344 <b>typename</b> <a href=
 345 "assoc_container_traits.html"><tt>container_traits</tt></a>&lt;C&gt;::order_preserving
 346 </pre>
 347
 348     <p>This is described further in <a href=
 349     "ds_gen.html">Design::Data-Structure Genericity</a>; <a href=
 350     "http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc%2B%2B-v3/testsuite/ext/pb_ds/example/assoc_container_traits.cc"><tt>assoc_container_traits.cc</tt></a>
 351     shows an example of querying containers' attributes.</p>
 352
 353     <h3><a name="assoc_find_range" id="assoc_find_range">Point-Type
 354     and Range-Type Methods and Iterators</a></h3>(This subsection
 355     addresses points from <a href=
 356     "motivation.html#assoc_diff_it">Motivation::Associative
 357     Containers::Differentiating between Iterator Types</a>.)
 358
 359     <p><tt>pb_ds</tt> differentiates between two types of methods
 360     and iterators: point-type, and range-type. For example,
 361     <tt>find</tt> and <tt>insert</tt> are point-type methods, since
 362     they each deal with a specific element; their returned
 363     iterators are point-type iterators. <tt>begin</tt> and
 364     <tt>end</tt> are range-type methods, since they are not used to
 365     find a specific element, but rather to go over all elements in
 366     a container object; their returned iterators are range-type
 367     iterators.</p>
 368
 369     <p>Most containers store elements in an order that is
 370     determined by their interface. Correspondingly, it is fine that
 371     their point-type iterators are synonymous with their range-type
 372     iterators. For example, in the following snippet</p>
 373     <pre>
 374 std::for_each(c.find(1), c.find(5), foo);
 375 </pre>two point-type iterators (returned by <tt>find</tt>) are used
 376 for a range-type purpose - going over all elements whose key is
 377 between 1 and 5.
 378
 379     <p>Conversely, the above snippet makes no sense for
 380     self-organizing containers - ones that order (and reorder)
 381     their elements by implementation. It would be nice to have a
 382     uniform iterator system that would allow the above snippet to
 383     compile only if it made sense.</p>
 384
 385     <p>This could trivially be done by specializing
 386     <tt>std::for_each</tt> for the case of iterators returned by
 387     <tt>std::tr1::unordered_map</tt>, but this would only solve the
 388     problem for one algorithm and one container. Fundamentally, the
 389     problem is that one can loop using a self-organizing
 390     container's point-type iterators.</p>
 391
 392     <p><tt>pb_ds</tt>'s containers define two families of
 393     iterators: <tt>const_point_iterator</tt> and
 394     <tt>point_iterator</tt> are the iterator types returned by
 395     point-type methods; <tt>const_iterator</tt> and
 396     <tt>iterator</tt> are the iterator types returned by range-type
 397     methods.</p>
 398     <pre>
 399 <b>class</b> <i>&lt;- some container -&gt;</i>
 400 {
 401 <b>public</b>:
 402     ...
 403
 404     <b>typedef</b> <i>&lt;- something -&gt;</i> const_iterator;
 405
 406     <b>typedef</b> <i>&lt;- something -&gt;</i> iterator;
 407
 408     <b>typedef</b> <i>&lt;- something -&gt;</i> const_point_iterator;
 409
 410     <b>typedef</b> <i>&lt;- something -&gt;</i> point_iterator;
 411
 412     ...
 413
 414 <b>public</b>:
 415     ...
 416
 417     const_iterator begin () <b>const</b>;
 418
 419     iterator begin();
 420
 421     const_point_iterator find(...) <b>const</b>;
 422
 423     point_iterator find(...);
 424 };
 425 </pre>
 426
 427     <p><a href="ds_gen.html#find_range">Design::Associative
 428     Containers::Data-Structure Genericity::Point-Type and
 429     Range-Type Methods and Iterators</a> discusses the relationship
 430     between point-type and range-type iterators in general; for
 431     containers whose interface defines sequence order, however, it
 432     is very simple: point-type and range-type iterators are exactly
 433     the same, which means that the above snippet will compile if it
 434     is used for an order-preserving associative container.</p>
 435
 436     <p>For self-organizing containers, however, (hash-based
 437     containers as a special example), the preceding snippet will
 438     not compile, because their point-type iterators do not support
 439     <tt><b>operator</b>++</tt>.</p>
 440
 441     <p>In any case, both for order-preserving and self-organizing
 442     containers, the following snippet will compile:</p>
 443     <pre>
 444 <b>typename</b> Cntnr::point_iterator it = c.find(2);
 445 </pre>
 446
 447     <p>because a range-type iterator can always be converted to a
 448     point-type iterator.</p>
 449
 450     <p><a href="ds_gen.html#find_range">Design::Associative
 451     Containers::Data-Structure Genericity::Point-Type and
 452     Range-Type Methods and Iterators</a> discusses this
 453     further.</p>
 454
 455     <p><a href=
 456     "motivation.html#assoc_diff_it">Motivation::Associative
 457     Containers::Differentiating between Iterator Types</a> also
 458     raised the point that a container's iterators might have
 459     different invalidation rules concerning their de-referencing
 460     abilities and movement abilities. This now corresponds exactly
 461     to the question of whether point-type and range-type iterators
 462     are valid. As explained in <a href="#assoc_ds_gen">Determining
 463     Containers' Attributes</a>, <a href=
 464     "assoc_container_traits.html"><tt>container_traits</tt></a> allows
 465     querying a container for its data structure attributes. The
 466     iterator-invalidation guarantees are certainly a property of
 467     the underlying data structure, and so</p>
 468     <pre>
 469 <a href=
 470 "assoc_container_traits.html">container_traits</a>&lt;C&gt;::invalidation_guarantee
 471 </pre>
 472
 473     <p>gives one of three pre-determined types that answer this
 474     query. This is explained further in <a href=
 475     "ds_gen.html#find_range">Design::Associative
 476     Containers::Data-Structure Genericity::Point-Type and
 477     Range-Type Methods and Iterators</a>.</p>
 478
 479     <h3><a name="assoc_ms" id="assoc_ms">Distinguishing between Maps and Sets</a></h3>
 480
 481     <p>Anyone familiar with the STL knows that there are four kinds
 482     of associative containers: maps, sets, multimaps, and
 483     multisets. <a href="#assoc_basic">Basic Use</a> discussed how
 484     to use maps, <i>i.e.</i> containers that associate each key to
 485     some data.</p>
 486
 487     <p>Sets are associative containers that simply store keys -
 488     they do not map them to anything. In the STL, each map class
 489     has a corresponding set class. <i>E.g.</i>,
 490     <tt>std::map&lt;<b>int</b>, <b>char</b>&gt;</tt> maps each
 491     <tt><b>int</b></tt> to a <tt><b>char</b></tt>, but
 492     <tt>std::set&lt;<b>int</b>, <b>char</b>&gt;</tt> simply stores
 493     <tt><b>int</b></tt>s. In <tt>pb_ds</tt>, however, there are no
 494     distinct classes for maps and sets. Instead, an associative
 495     container's <tt>Mapped</tt> template parameter is a policy: if
 496     it is instantiated by <a href=
 497     "null_mapped_type.html"><tt>null_mapped_type</tt></a>, then it
 498     is a "set"; otherwise, it is a "map". <i>E.g.</i>,</p>
 499     <pre>
 500 <a href="cc_hash_table.html">cc_hash_table</a>&lt;<b>int</b>, <b>char</b>&gt;
 501 </pre>is a "map" mapping each <tt><b>int</b></tt> value to a <tt>
 502     <b>char</b></tt>, but
 503     <pre>
 504 <a href="cc_hash_table.html">cc_hash_table</a>&lt;<b>int</b>, <a href="null_mapped_type.html">null_mapped_type</a>&gt;
 505 </pre>is a type that uniquely stores <tt><b>int</b></tt> values.
 506
 507     <p>Once the <tt>Mapped</tt> template parameter is instantiated
 508     by <a href="null_mapped_type.html">null_mapped_type</a>, then
 509     the "set" acts very similarly to the STL's sets - it does not
 510     map each key to a distinct <a href=
 511     "null_mapped_type.html">null_mapped_type</a> object. Also,
 512    , the container's <tt>value_type</tt> is essentially
 513     its <tt>key_type</tt> - just as with the STL's sets. For a simple example, see <a href=
 514     "http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc%2B%2B-v3/testsuite/ext/pb_ds/example/basic_set.cc"><tt>basic_set.cc</tt></a>
 515    .</p>
 516
 517     <p>The STL's multimaps and multisets allow, respectively,
 518     non-uniquely mapping keys and non-uniquely storing keys. As
 519     discussed in <a href=
 520     "motivation.html#assoc_mapping_semantics">Motivation::Associative
 521     Containers::Alternative to Multiple Equivalent Keys</a>, the
 522     reasons why this might be necessary are 1) that a key might be
 523     decomposed into a primary key and a secondary key, 2) that a
 524     key might appear more than once, or 3) any arbitrary
 525     combination of 1)s and 2)s. Correspondingly,
 526     one should use 1) "maps" mapping primary keys to secondary
 527     keys, 2) "maps" mapping keys to size types, or 3) any arbitrary
 528     combination of 1)s and 2)s. Thus, for example, an
 529     <tt>std::multiset&lt;<b>int</b>&gt;</tt> might be used to store
 530     multiple instances of integers, but using <tt>pb_ds</tt>'s
 531     containers, one might use</p>
 532     <pre>
 533 <a href=
 534 "tree.html">tree</a>&lt;<b>int</b>, size_t&gt;
 535 </pre><i>i.e.</i>, a "map" of <tt><b>int</b></tt>s to
 536 <tt>size_t</tt>s.
 537
 538     <p><a href="assoc_examples.html#mmaps">Associative-Container
 539     Examples::"Multimaps" and "Multisets"</a> shows some simple
 540     examples.</p>
 541
 542     <p>These "multimaps" and "multisets" might be confusing to
 543     anyone familiar with the STL's <tt>std::multimap</tt> and
 544     <tt>std::multiset</tt>, because there is no clear
 545     correspondence between the two. For example, in some cases
 546     where one uses <tt>std::multiset</tt> in the STL, one might use
 547     in <tt>pb_ds</tt> a "multimap" of "multisets" - <i>i.e.</i>, a
 548     container that maps primary keys each to an associative
 549     container that maps each secondary key to the number of times
 550     it occurs.</p>
 551
 552     <p>When one uses a "multimap," one should choose with care the
 553     type of container used for secondary keys. This is further
 554     explained in <a href=
 555     "assoc_performance_tests.html#msc">Associative-Container
 556     Performance Tests::Observations::Mapping-Semantics
 557     Considerations</a>.</p>
 558
 559 <hr>
 560     <h2><a name="pq" id="pq">Priority Queues</a></h2>
 561
 562     <h3><a name="pq_basic" id="pq_basic">Basic Use</a></h3>
 563
 564     <p><tt>pb_ds</tt>'s priority_queue container is
 565     similar to the STL's in interface. For example:</p>
 566     <pre>
 567 <a href=
 568 "priority_queue.html">priority_queue</a>&lt;<b>int</b>&gt; p;
 569
 570 p.push(2);
 571 p.push(4);
 572 p.push(1);
 573
 574 assert(p.top() == 4);
 575
 576 p.pop();
 577
 578 assert(p.top() == 2);
 579
 580 assert(p.size() == 2);
 581 assert(!p.empty());
 582 </pre>
 583
 584     <h3><a name="pq_policies" id="pq_policies">Configuring Priority
 585     Queues</a></h3>
 586
 587     <p>As opposed to associative containers, priority queues have
 588     relatively few configuration options. The priority queue is
 589     parametrized as follows:</p>
 590     <pre>
 591 <b>template</b>&lt;
 592     <b>typename</b> Value_Type,
 593     <b>typename</b> Cmp_Fn,
 594     <b>typename</b> Tag,
 595     <b>typename</b> Allocator&gt;
 596 <b>class</b> <a href="priority_queue.html">priority_queue</a>;
 597 </pre>
 598
 599     <p>The <tt>Value_Type</tt>, <tt>Cmp_Fn</tt>, and
 600     <tt>Allocator</tt> parameters are the container's value type,
 601     comparison-functor type, and allocator type, respectively;
 602     these are very similar to the STL's priority queue. The
 603     <tt>Tag</tt> parameter is different: there are a number of
 604     pre-defined tag types corresponding to binary heaps, binomial
 605     heaps, <i>etc.</i>, and <tt>Tag</tt> should be instantiated
 606     by one of them. <a href=
 607     "interface.html#ds_ts_pq">Interface::Data-Structure Tags and
 608     Traits::Data Structure Tags::Priority-Queues</a> lists the
 609     possible types, <a href="pq_design.html">Priority-Queue
 610     Design</a> explains this further, and <a href=
 611     "http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc%2B%2B-v3/testsuite/ext/pb_ds/example/basic_priority_queue.cc"><tt>basic_priority_queue.cc</tt></a>
 612     shows an example.</p>
 613
 614     <p>Note that as opposed to the STL's priority queue, <a href=
 615     "priority_queue.html"><tt>priority_queue</tt></a> is not a
 616     sequence-adapter; it is a regular container.</p>
 617
 618     <h3><a name="pq_ds_more_ops" id="pq_ds_more_ops">Supporting
 619     More Operations</a></h3>
 620
 621     <p><a href="priority_queue.html"><tt>priority_queue</tt></a>'s
 622     <tt>push</tt> method returns a point-type iterator, which can
 623     be used for modifying or erasing arbitrary values. For
 624     example:</p>
 625     <pre>
 626 <a href=
 627 "priority_queue.html">priority_queue</a>&lt;<b>int</b>&gt; p;
 628
 629 <a href=
 630 "priority_queue.html">priority_queue</a>&lt;<b>int</b>&gt;::point_iterator it = p.push(3);
 631
 632 p.modify(it, 4);
 633 </pre>
 634
 635     <p>These types of operations are necessary for making priority
 636     queues useful for different applications, especially graph
 637     applications. <a href="pq_examples.html#xref">Priority-Queue
 638     Examples::Cross-Referencing</a> gives some examples.</p>
 639
 640     <h3><a name="pq_ds_gen" id="pq_ds_gen">Determining Container
 641     Attributes</a></h3>
 642
 643     <p>Similarly to <a href=
 644     "assoc_container_traits.html"><tt>container_traits</tt></a> (described
 645     in <a href="#assoc_ds_gen">Associative Containers::Determining
 646     Containers' Attributes</a>), <a href=
 647     "pq_container_traits.html"><tt>container_traits</tt></a> can be used to
 648     statically determine priority-queues' attributes:</p>
 649     <pre>
 650 <a href=
 651 "pq_container_traits.html">container_traits</a>&lt;C&gt;::container_category
 652 </pre>is one of a small number of predefined tag structures that
 653 identifies the underlying data structure, and
 654     <pre>
 655 <a href=
 656 "pq_container_traits.html">container_traits</a>&lt;C&gt;::invalidation_guarantee
 657 </pre>
 658
 659     <p>is its invalidation guarantee. Invalidation guarantees are
 660     especially important regarding priority queues, since in
 661     <tt>pb_ds</tt>'s design, iterators are practically the only way
 662     to manipulate them.</p>
 663
 664     <p><a href="pq_design.html#pq_traits">Design::Priority
 665     Queues::Traits</a> discusses this further. <a href=
 666     "pq_examples.html#generics">Priority-Queue
 667     Examples::Generics</a> shows an example.</p>
 668   </div>
 669 </body>
 670 </html>