diff options
Diffstat (limited to 'gcc-4.4.3/libstdc++-v3/doc/html/ext/pb_ds/tutorial.html')
| -rw-r--r-- | gcc-4.4.3/libstdc++-v3/doc/html/ext/pb_ds/tutorial.html | 670 |
1 files changed, 670 insertions, 0 deletions
diff --git a/gcc-4.4.3/libstdc++-v3/doc/html/ext/pb_ds/tutorial.html b/gcc-4.4.3/libstdc++-v3/doc/html/ext/pb_ds/tutorial.html new file mode 100644 index 000000000..152cd57b1 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/doc/html/ext/pb_ds/tutorial.html @@ -0,0 +1,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> |