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