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