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
|
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!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
other libraries except the standard C++ library . All classes are
defined in namespace <code class="code">__gnu_pbds</code>. The library internally
uses macros beginning with <code class="code">PB_DS</code>, but
<code class="code">#undef</code>s anything it <code class="code">#define</code>s (except for
header guards). Compiling the library in an environment where macros
beginning in <code class="code">PB_DS</code> are defined, may yield unpredictable
results in compilation, execution, or both.</p><p>
Further dependencies are necessary to create the visual output
for the performance tests. To create these graphs, an
additional package is needed: <span class="command"><strong>pychart</strong></span>.
</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>
The various data structures are organized as follows.
</p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p>
Branch-Based
</p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; "><li class="listitem"><p>
<code class="classname">basic_branch</code>
is an abstract base class for branched-based
associative-containers
</p></li><li class="listitem"><p>
<code class="classname">tree</code>
is a concrete base class for tree-based
associative-containers
</p></li><li class="listitem"><p>
<code class="classname">trie</code>
is a concrete base class trie-based
associative-containers
</p></li></ul></div></li><li class="listitem"><p>
Hash-Based
</p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; "><li class="listitem"><p>
<code class="classname">basic_hash_table</code>
is an abstract base class for hash-based
associative-containers
</p></li><li class="listitem"><p>
<code class="classname">cc_hash_table</code>
is a concrete collision-chaining hash-based
associative-containers
</p></li><li class="listitem"><p>
<code class="classname">gp_hash_table</code>
is a concrete (general) probing hash-based
associative-containers
</p></li></ul></div></li><li class="listitem"><p>
List-Based
</p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; "><li class="listitem"><p>
<code class="classname">list_update</code>
list-based update-policy associative container
</p></li></ul></div></li><li class="listitem"><p>
Heap-Based
</p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; "><li class="listitem"><p>
<code class="classname">priority_queue</code>
A priority queue.
</p></li></ul></div></li></ul></div><p>
The hierarchy is composed naturally so that commonality is
captured by base classes. Thus <code class="function">operator[]</code>
is defined at the base of any hierarchy, since all derived
containers support it. Conversely <code class="function">split</code> is
defined in <code class="classname">basic_branch</code>, since only
tree-like containers support it.
</p><p>
In addition, there are the following diagnostics classes,
used to report errors specific to this library's data
structures.
</p><div class="figure"><a id="idm269889461728"></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>
For the most part, the policy-based containers containers in
namespace <code class="literal">__gnu_pbds</code> have the same interface as
the equivalent containers in the standard C++ library, 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 class="programlisting">
#include <ext/pb_ds/assoc_container.h>
int main()
{
__gnu_pbds::cc_hash_table<int, char> c;
c[2] = 'b';
assert(c.find(1) == c.end());
};
</pre><p>
The container is called
<code class="classname">__gnu_pbds::cc_hash_table</code> instead of
<code class="classname">std::unordered_map</code>, since <span class="quote">“<span class="quote">unordered
map</span>”</span> does not necessarily mean a hash-based map as implied by
the C++ library (C++11 or TR1). For example, list-based associative
containers, which are very useful for the construction of
"multimaps," are also unordered.
</p><p>This snippet shows a red-black tree based container:</p><pre class="programlisting">
#include <ext/pb_ds/assoc_container.h>
int main()
{
__gnu_pbds::tree<int, char> c;
c[2] = 'b';
assert(c.find(2) != c.end());
};
</pre><p>The container is called <code class="classname">tree</code> instead of
<code class="classname">map</code> since the underlying data structures are
being named with specificity.
</p><p>
The member function naming convention is to strive to be the same as
the equivalent member functions in other C++ standard library
containers. The familiar methods are unchanged:
<code class="function">begin</code>, <code class="function">end</code>,
<code class="function">size</code>, <code class="function">empty</code>, and
<code class="function">clear</code>.
</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 then the usual. For example, if <span class="type">hash_type</span> is
some type of hash-based container, then</p><pre class="programlisting">
hash_type::hash_fn
</pre><p>
gives the type of its hash functor, and if <code class="varname">obj</code> is
some hash-based container object, then
</p><pre class="programlisting">
obj.get_hash_fn()
</pre><p>will return a reference to its hash-functor object.</p><p>
Similarly, if <span class="type">tree_type</span> is some type of tree-based
container, then
</p><pre class="programlisting">
tree_type::cmp_fn
</pre><p>
gives the type of its comparison functor, and if
<code class="varname">obj</code> is some tree-based container object,
then
</p><pre class="programlisting">
obj.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,
<code class="classname">std::tr1::unordered_map</code> uses
<span class="type">hasher</span> for the hash functor, but
<code class="classname">std::map</code> uses <span class="type">key_compare</span> for
the comparison functor. Also, we could not find an accessor for
<code class="classname">std::tr1::unordered_map</code>'s hash functor, but
<code class="classname">std::map</code> uses <code class="classname">compare</code>
for accessing the comparison functor.
</p><p>
Instead, <code class="literal">__gnu_pbds</code> attempts to be internally
consistent, and uses standard-derived terminology if possible.
</p><p>
Another source of difference is in scope:
<code class="literal">__gnu_pbds</code> contains more types of associative
containers than the standard C++ library, and more opportunities
to configure these new containers, since different types of
associative containers are useful in different settings.
</p><p>
Namespace <code class="literal">__gnu_pbds</code> contains different classes for
hash-based containers, tree-based containers, trie-based containers,
and list-based containers.
</p><p>
Since associative containers share parts of their interface, they
are organized as a class hierarchy.
</p><p>Each type or method is defined in the most-common ancestor
in which it makes sense.
</p><p>For example, all associative containers support iteration
expressed in the following form:
</p><pre class="programlisting">
const_iterator
begin() const;
iterator
begin();
const_iterator
end() const;
iterator
end();
</pre><p>
But not all containers contain or use hash functors. Yet, both
collision-chaining and (general) probing hash-based associative
containers have a hash functor, so
<code class="classname">basic_hash_table</code> contains the interface:
</p><pre class="programlisting">
const hash_fn&
get_hash_fn() const;
hash_fn&
get_hash_fn();
</pre><p>
so all hash-based associative containers inherit the same
hash-functor accessor methods.
</p></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.using.tutorial.configuring"></a>
Configuring via Template Parameters
</h4></div></div></div><p>
In general, each of this library's containers is
parametrized by more policies than those of the standard library. For
example, the standard hash-based container is parametrized as
follows:
</p><pre class="programlisting">
template<typename Key, typename Mapped, typename Hash,
typename Pred, typename Allocator, bool Cache_Hashe_Code>
class 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. this library's collision-chaining
hash-based container is parametrized as
</p><pre class="programlisting">
template<typename Key, typename Mapped, typename Hash_Fn,
typename Eq_Fn, typename Comb_Hash_Fn,
typename Resize_Policy, bool Store_Hash
typename Allocator>
class cc_hash_table;
</pre><p>
and so can be configured by the first four types of
<code class="classname">std::tr1::unordered_map</code>, 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 standard 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>As opposed to associative containers, priority queues have
relatively few configuration options. The priority queue is
parametrized as follows:</p><pre class="programlisting">
template<typename Value_Type, typename Cmp_Fn,typename Tag,
typename Allocator>
class priority_queue;
</pre><p>The <code class="classname">Value_Type</code>, <code class="classname">Cmp_Fn</code>, and
<code class="classname">Allocator</code> parameters are the container's value type,
comparison-functor type, and allocator type, respectively;
these are very similar to the standard's priority queue. The
<code class="classname">Tag</code> parameter is different: there are a number of
pre-defined tag types corresponding to binary heaps, binomial
heaps, etc., and <code class="classname">Tag</code> should be instantiated
by one of them.</p><p>Note that as opposed to the
<code class="classname">std::priority_queue</code>,
<code class="classname">__gnu_pbds::priority_queue</code> is not a
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>
Querying Container Attributes
</h4></div></div></div><p></p><p>A containers underlying data structure
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.
</p><p>Happily, the standard provides a good solution to a similar
problem - that of the different behavior of iterators. If
<code class="classname">It</code> is an iterator, then
</p><pre class="programlisting">
typename std::iterator_traits<It>::iterator_category
</pre><p>is one of a small number of pre-defined tag classes, and
</p><pre class="programlisting">
typename std::iterator_traits<It>::value_type
</pre><p>is the value type to which the iterator "points".</p><p>
Similarly, in this library, if <span class="type">C</span> is a
container, then <code class="classname">container_traits</code> is a
trait class that stores information about the kind of
container that is implemented.
</p><pre class="programlisting">
typename container_traits<C>::container_category
</pre><p>
is one of a small number of predefined tag structures that
uniquely identifies the type of underlying data structure.
</p><p>In most cases, however, the exact underlying data
structure is not really important, but what is important is
one of its other attributes: whether it guarantees storing
elements by key order, for example. For this one can
use</p><pre class="programlisting">
typename container_traits<C>::order_preserving
</pre><p>
Also,
</p><pre class="programlisting">
typename container_traits<C>::invalidation_guarantee
</pre><p>is the container's invalidation guarantee. Invalidation
guarantees are especially important regarding priority queues,
since in this library's design, iterators are practically the
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>
Point and Range Iteration
</h4></div></div></div><p></p><p>This library differentiates between two types of methods
and iterators: point-type, and range-type. For example,
<code class="function">find</code> and <code class="function">insert</code> are point-type methods, since
they each deal with a specific element; their returned
iterators are point-type iterators. <code class="function">begin</code> and
<code class="function">end</code> 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 class="programlisting">
std::for_each(c.find(1), c.find(5), foo);
</pre><p>
two point-type iterators (returned by <code class="function">find</code>) are used
for a range-type purpose - going over all elements whose key is
between 1 and 5.
</p><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
<code class="function">std::for_each</code> for the case of iterators returned by
<code class="classname">std::tr1::unordered_map</code>, 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>
This library's containers define two families of
iterators: <span class="type">point_const_iterator</span> and
<span class="type">point_iterator</span> are the iterator types returned by
point-type methods; <span class="type">const_iterator</span> and
<span class="type">iterator</span> are the iterator types returned by range-type
methods.
</p><pre class="programlisting">
class <- some container ->
{
public:
...
typedef <- something -> const_iterator;
typedef <- something -> iterator;
typedef <- something -> point_const_iterator;
typedef <- something -> point_iterator;
...
public:
...
const_iterator begin () const;
iterator begin();
point_const_iterator find(...) const;
point_iterator find(...);
};
</pre><p>For
containers whose interface defines sequence order , 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
<code class="function">operator++</code>.
</p><p>In any case, both for order-preserving and self-organizing
containers, the following snippet will compile:
</p><pre class="programlisting">
typename 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>Distingushing between iterator types also
raises 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 above, <code class="classname">container_traits</code> 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 class="programlisting">
container_traits<C>::invalidation_guarantee
</pre><p>
gives one of three pre-determined types that answer this
query.
</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>
Additional code examples are provided in the source
distribution, as part of the regression and performance
testsuite.
</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>
Basic use of maps:
<code class="filename">basic_map.cc</code>
</p></li><li class="listitem"><p>
Basic use of sets:
<code class="filename">basic_set.cc</code>
</p></li><li class="listitem"><p>
Conditionally erasing values from an associative container object:
<code class="filename">erase_if.cc</code>
</p></li><li class="listitem"><p>
Basic use of multimaps:
<code class="filename">basic_multimap.cc</code>
</p></li><li class="listitem"><p>
Basic use of multisets:
<code class="filename">basic_multiset.cc</code>
</p></li><li class="listitem"><p>
Basic use of priority queues:
<code class="filename">basic_priority_queue.cc</code>
</p></li><li class="listitem"><p>
Splitting and joining priority queues:
<code class="filename">priority_queue_split_join.cc</code>
</p></li><li class="listitem"><p>
Conditionally erasing values from a priority queue:
<code class="filename">priority_queue_erase_if.cc</code>
</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>
Using <code class="classname">container_traits</code> to query
about underlying data structure behavior:
<code class="filename">assoc_container_traits.cc</code>
</p></li><li class="listitem"><p>
A non-compiling example showing wrong use of finding keys in
hash-based containers: <code class="filename">hash_find_neg.cc</code>
</p></li><li class="listitem"><p>
Using <code class="classname">container_traits</code>
to query about underlying data structure behavior:
<code class="filename">priority_queue_container_traits.cc</code>
</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>
Setting the initial size of a hash-based container
object:
<code class="filename">hash_initial_size.cc</code>
</p></li><li class="listitem"><p>
A non-compiling example showing how not to resize a
hash-based container object:
<code class="filename">hash_resize_neg.cc</code>
</p></li><li class="listitem"><p>
Resizing the size of a hash-based container object:
<code class="filename">hash_resize.cc</code>
</p></li><li class="listitem"><p>
Showing an illegal resize of a hash-based container
object:
<code class="filename">hash_illegal_resize.cc</code>
</p></li><li class="listitem"><p>
Changing the load factors of a hash-based container
object: <code class="filename">hash_load_set_change.cc</code>
</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>
Using a modulo range-hashing function for the case of an
unknown skewed key distribution:
<code class="filename">hash_mod.cc</code>
</p></li><li class="listitem"><p>
Writing a range-hashing functor for the case of a known
skewed key distribution:
<code class="filename">shift_mask.cc</code>
</p></li><li class="listitem"><p>
Storing the hash value along with each key:
<code class="filename">store_hash.cc</code>
</p></li><li class="listitem"><p>
Writing a ranged-hash functor:
<code class="filename">ranged_hash.cc</code>
</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>
Joining two tree-based container objects:
<code class="filename">tree_join.cc</code>
</p></li><li class="listitem"><p>
Splitting a PATRICIA trie container object:
<code class="filename">trie_split.cc</code>
</p></li><li class="listitem"><p>
Order statistics while joining two tree-based container
objects:
<code class="filename">tree_order_statistics_join.cc</code>
</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>
Using trees for order statistics:
<code class="filename">tree_order_statistics.cc</code>
</p></li><li class="listitem"><p>
Augmenting trees to support operations on line
intervals:
<code class="filename">tree_intervals.cc</code>
</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>
Using a PATRICIA trie for DNA strings:
<code class="filename">trie_dna.cc</code>
</p></li><li class="listitem"><p>
Using a PATRICIA
trie for finding all entries whose key matches a given prefix:
<code class="filename">trie_prefix_search.cc</code>
</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>
Cross referencing an associative container and a priority
queue: <code class="filename">priority_queue_xref.cc</code>
</p></li><li class="listitem"><p>
Cross referencing a vector and a priority queue using a
very simple version of Dijkstra's shortest path
algorithm:
<code class="filename">priority_queue_dijkstra.cc</code>
</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>
|
