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, 0 insertions, 670 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 deleted file mode 100644 index 152cd57b1..000000000 --- a/gcc-4.4.3/libstdc++-v3/doc/html/ext/pb_ds/tutorial.html +++ /dev/null @@ -1,670 +0,0 @@ -<!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> |