| <!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= |
| "../../../../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= |
| "../../../../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= |
| "../../../../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= |
| "../../../../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= |
| "../../../../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> |
