OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [libstdc++-v3/] [doc/] [html/] [ext/] [pb_ds/] [tutorial.html] - Blame information for rev 424

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 424 jeremybenn 
<!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>

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.