gcc/libstdc++-v3/doc/html/ext/pb_ds/tutorial.html - Issue 3050029: [gcc] GCC 4.5.0=>4.5.1

Unified Diff: gcc/libstdc++-v3/doc/html/ext/pb_ds/tutorial.html

Issue 3050029: [gcc] GCC 4.5.0=>4.5.1 (Closed) Base URL: ssh://git@gitrw.chromium.org:9222/nacl-toolchain.git

Patch Set: Created 10 years, 5 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

View side-by-side diff with in-line comments

« no previous file with comments | « gcc/libstdc++-v3/doc/html/ext/pb_ds/trivial_iterator_tag.html ('k') | gcc/libstdc++-v3/doc/html/ext/pb_ds/update_policy_cd.png » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Hide Comments ('s')

Index: gcc/libstdc++-v3/doc/html/ext/pb_ds/tutorial.html

diff --git a/gcc/libstdc++-v3/doc/html/ext/pb_ds/tutorial.html b/gcc/libstdc++-v3/doc/html/ext/pb_ds/tutorial.html

deleted file mode 100644

index 152cd57b1ab7b3042f79fc62446114fd30c1fb99..0000000000000000000000000000000000000000

--- a/gcc/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>

- 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.

- <h2><a name="assoc_main" id="assoc_main">Associative

- Containers</a></h2>

- <h3><a name="assoc_basic" id="assoc_basic">Basic Use</a></h3>

- 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:

- <pre>

-<a href=

-"cc_hash_table.html">cc_hash_table</a><int, char> c;

-c[2] = 'b';

-assert(c.find(1) == c.end());

-</pre>

- 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.

- This snippet shows a red-black tree based container:

- <pre>

-<a href=

-"tree.html">tree</a><int, char> c;

-c[2] = 'b';

-assert(c.find(2) != c.end());

-</pre>

- 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.

- Most of the STL's familiar methods are unchanged.

- E.g., <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.

-This isn't to say that things are exactly as one would expect,

-given the container requirments and interfaces in the C++

-standard.

- 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

- <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>

- will return a reference to its hash-functor object.

- Similarly, if <tt>C</tt> is some type of tree-based

- container, then

- <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>

- will return a reference to its comparison-functor

- object.

- 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.

-Instead, <tt>pb_ds</tt> attempts to be internally consistent, and

-uses standard-derived terminology if possible.

-

- 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>).

- <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.

- 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>.

- <h6 class="c1"><a name="cd" id="cd"><img src="container_cd.png" alt=

- "no image" /></a></h6>

- <h6 class="c1">Class hierarchy.</h6>

- 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.

- For example, all associative containers support iteration.

- Consequently, <a href=

- "container_base.html"><tt>container_base</tt></a> has the

- interface:

- <pre>

-template<...>

-class <a href="container_base.html">container_base</a>

- ...

-public:

- ...

- const_iterator

- begin() const;

- iterator

- begin();

- const_iterator

- end() const;

- iterator

- end();

- ...

-};

-</pre>

- 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:

- <pre>

-template<...>

-class <a href="basic_hash_table.html">basic_hash_table</a> : public <a href="container_base.html">container_base</a>

- ...

-public:

- ...

- const hash_fn&

- get_hash_fn() const;

- hash_fn&

- get_hash_fn();

- ...

-};

-</pre>

- and so all hash-based associative containers inherit the

- same hash-functor accessor methods.

- This is discussed further in <a href=

- "ds_gen.html">Design::Associative Containers::Data-Structure

- Genericity</a>.

- <h3><a name="assoc_policies" id="assoc_policies">Configuring

- Associative Containers</a></h3>

- 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:

- <pre>

-template<

- typename Key,

- typename Mapped,

- typename Hash,

- typename Pred,

- typename Allocator,

- bool Cache_Hashe_Code>

-class unordered_map;

-</pre>

- 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

- <pre>

-template<

- typename Key,

- typename Mapped,

- typename Hash_Fn,

- typename Eq_Fn,

- typename Comb_Hash_Fn,

- typename Resize_Policy

- bool Store_Hash

- typename Allocator>

-class <a href=

-"cc_hash_table.html">cc_hash_table</a>;

-</pre>

- 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).

- 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.

- <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.

- <h3><a name="assoc_ds_gen" id="assoc_ds_gen">Determining

- Containers' Attributes</a></h3>

- 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>.)

- 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

- <pre>

-typename std::iterator_traits<It>::iterator_category

-</pre>

- is one of a small number of pre-defined

- <tt>struct</tt>s, and,

- <pre>

-typename std::iterator_traits<It>::value_type

-</pre>

- is the value type to which the iterator "points".

- Similarly, in <tt>pb_ds</tt>, if <tt>C</tt> is an

- associative container, then

- <pre>

-typename <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>struct</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.

- 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

- <pre>

-typename <a href=

-"assoc_container_traits.html"><tt>container_traits</tt></a><C>::order_preserving

-</pre>

- 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.

- <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>.)

- <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.

- 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

- <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.

- 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.

- 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.

- <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.

- <pre>

-class <- some container ->

-public:

- ...

- typedef <- something -> const_iterator;

- typedef <- something -> iterator;

- typedef <- something -> const_point_iterator;

- typedef <- something -> point_iterator;

- ...

-public:

- ...

- const_iterator begin () const;

- iterator begin();

- const_point_iterator find(...) const;

- point_iterator find(...);

-};

-</pre>

- <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.

- 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>operator++</tt>.

- In any case, both for order-preserving and self-organizing

- containers, the following snippet will compile:

- <pre>

-typename Cntnr::point_iterator it = c.find(2);

-</pre>

- because a range-type iterator can always be converted to a

- point-type iterator.

- <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.

- <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

- <pre>

-<a href=

-"assoc_container_traits.html">container_traits</a><C>::invalidation_guarantee

-</pre>

- 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>.

- <h3><a name="assoc_ms" id="assoc_ms">Distinguishing between Maps and Sets</a></h3>

- 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.e. containers that associate each key to

- some data.

- 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. E.g.,

- <tt>std::map<int, char></tt> maps each

- <tt>int</tt> to a <tt>char</tt>, but

- <tt>std::set<int, char></tt> simply stores

- <tt>int</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". E.g.,

- <pre>

-<a href="cc_hash_table.html">cc_hash_table</a><int, char>

-</pre>is a "map" mapping each <tt>int</tt> value to a <tt>

- char</tt>, but

- <pre>

-<a href="cc_hash_table.html">cc_hash_table</a><int, <a href="null_mapped_type.html">null_mapped_type</a>>

-</pre>is a type that uniquely stores <tt>int</tt> values.

- 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>

- .

- 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<int></tt> might be used to store

- multiple instances of integers, but using <tt>pb_ds</tt>'s

- containers, one might use

- <pre>

-<a href=

-"tree.html">tree</a><int, size_t>

-</pre>i.e., a "map" of <tt>int</tt>s to

-<tt>size_t</tt>s.

- <a href="assoc_examples.html#mmaps">Associative-Container

- Examples::"Multimaps" and "Multisets"</a> shows some simple

- examples.

- 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.e., a

- container that maps primary keys each to an associative

- container that maps each secondary key to the number of times

- it occurs.

- 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>.

-<hr>

- <h2><a name="pq" id="pq">Priority Queues</a></h2>

- <h3><a name="pq_basic" id="pq_basic">Basic Use</a></h3>

- <tt>pb_ds</tt>'s priority_queue container is

- similar to the STL's in interface. For example:

- <pre>

-<a href=

-"priority_queue.html">priority_queue</a><int> 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>

- As opposed to associative containers, priority queues have

- relatively few configuration options. The priority queue is

- parametrized as follows:

- <pre>

-template<

- typename Value_Type,

- typename Cmp_Fn,

- typename Tag,

- typename Allocator>

-class <a href="priority_queue.html">priority_queue</a>;

-</pre>

- 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, etc., 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.

- 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.

- <h3><a name="pq_ds_more_ops" id="pq_ds_more_ops">Supporting

- More Operations</a></h3>

- <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:

- <pre>

-<a href=

-"priority_queue.html">priority_queue</a><int> p;

-<a href=

-"priority_queue.html">priority_queue</a><int>::point_iterator it = p.push(3);

-p.modify(it, 4);

-</pre>

- 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.

- <h3><a name="pq_ds_gen" id="pq_ds_gen">Determining Container

- Attributes</a></h3>

- 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:

- <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>

- 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.

- <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.

- </div>

-</body>

-</html>