| 1 |
20 |
jlechner |
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
|
| 2 |
|
|
<html>
|
| 3 |
|
|
<head>
|
| 4 |
|
|
<title>Concepts</title>
|
| 5 |
|
|
<meta name="GENERATOR" content="Microsoft Visual Studio .NET 7.1">
|
| 6 |
|
|
<meta name="vs_targetSchema" content="http://schemas.microsoft.com/intellisense/ie5">
|
| 7 |
|
|
</head>
|
| 8 |
|
|
<body bgcolor = "white">
|
| 9 |
|
|
<h1>Concepts</h1>
|
| 10 |
|
|
|
| 11 |
|
|
<p>
|
| 12 |
|
|
Following are some concepts used throughout the documentation.
|
| 13 |
|
|
</p>
|
| 14 |
|
|
|
| 15 |
|
|
<ol>
|
| 16 |
|
|
<li><a href = "#concepts_null_policies">Null Policy Classes</a></li>
|
| 17 |
|
|
<li><a href = "#concepts_find_and_range_iterators">Find and Range Iterators</a></li>
|
| 18 |
|
|
<li><a href = "#concepts_mapping_levels">Mapping Levels</a></li>
|
| 19 |
|
|
</ol>
|
| 20 |
|
|
|
| 21 |
|
|
<h2><a name = "concepts_null_policies">Null Policy Classes</a></h2>
|
| 22 |
|
|
|
| 23 |
|
|
<p>
|
| 24 |
|
|
Associative containers are typically parameterized by various policies.
|
| 25 |
|
|
For example, a hash-based associative
|
| 26 |
|
|
container is parameterized by a hash-functor, transforming each key into an non-negative numerical type. Each such value is then further mapped into a position within the table.
|
| 27 |
|
|
The mapping of a key into a position within the table is therefore a two-step process.
|
| 28 |
|
|
</p>
|
| 29 |
|
|
|
| 30 |
|
|
<p>
|
| 31 |
|
|
In some
|
| 32 |
|
|
cases, instantiations are <i>redundant</i>. For example, when the keys are integers, it is possible to use a <i>redundant</i>
|
| 33 |
|
|
hash policy, which transforms each key into its value.
|
| 34 |
|
|
</p>
|
| 35 |
|
|
|
| 36 |
|
|
<p>
|
| 37 |
|
|
In some other cases, these policies are <i>irrelevent</i>. For example,
|
| 38 |
|
|
a hash-based associative container might transform keys into positions within
|
| 39 |
|
|
a table by a different method than the two-step method described above. In such a case, the hash functor is simply irrelevent.
|
| 40 |
|
|
</p>
|
| 41 |
|
|
|
| 42 |
|
|
<p>
|
| 43 |
|
|
<tt>pb_assoc</tt> uses special pre-defined "null policies" classes
|
| 44 |
|
|
for these cases. Some null policies in <tt>pb_assoc</tt>
|
| 45 |
|
|
are:
|
| 46 |
|
|
</p>
|
| 47 |
|
|
<ol>
|
| 48 |
|
|
<li <a href = "null_data_type.html"><tt>null_data_type</tt></a></li>
|
| 49 |
|
|
<li><a href = "null_node_updator.html"><tt>null_node_updator</tt></a></li>
|
| 50 |
|
|
<li><a href = "null_hash_fn.html"><tt>null_hash_fn</tt></a></li>
|
| 51 |
|
|
<li><a href = "null_probe_fn.html"><tt>null_probe_fn</tt></a></li>
|
| 52 |
|
|
</ol>
|
| 53 |
|
|
|
| 54 |
|
|
<p>
|
| 55 |
|
|
A "set" in <tt>pb_assoc</tt> is an associative container with its <tt>Data_Parameter</tt> instantiated by
|
| 56 |
|
|
<a href = "null_data_type.html"><tt>null_data_type</tt></a>.
|
| 57 |
|
|
<a href = "tree_based_containers.html#node_invariants.html">Tree-Based Containers::Node Invariants</a>
|
| 58 |
|
|
explains another case where a null policy is needed.
|
| 59 |
|
|
</p>
|
| 60 |
|
|
|
| 61 |
|
|
|
| 62 |
|
|
|
| 63 |
|
|
<h2><a name = "concepts_find_and_range_iterators">Find and Range Methods and Iterators</a></h2>
|
| 64 |
|
|
|
| 65 |
|
|
<p>
|
| 66 |
|
|
Associative containers allow access to their elements via iterators. <i>E.g.</i>,
|
| 67 |
|
|
<tt>find</tt> returns an iterator to an element with a given key and
|
| 68 |
|
|
<tt>begin</tt> returns an iterator to the first element in the container.
|
| 69 |
|
|
</p>
|
| 70 |
|
|
|
| 71 |
|
|
<p>
|
| 72 |
|
|
In general, there are two types of methods: <i>find types</i>, and <i>range types</i>.
|
| 73 |
|
|
Find-type
|
| 74 |
|
|
methods return iterators corresponding to elements which have been found in some sense, as
|
| 75 |
|
|
the container searched for them in order to access them (<i>i.e.</i>, via the
|
| 76 |
|
|
<tt>find</tt> method) or searched for their location in order to insert them
|
| 77 |
|
|
(<i>i.e.</i>, via the <tt>insert</tt> method). Range-type methods return iterators
|
| 78 |
|
|
which can be used to traverse the range of all stored elements, (<i>i.e.</i>, via the
|
| 79 |
|
|
<tt>begin</tt> and <tt>end</tt> methods).
|
| 80 |
|
|
</p>
|
| 81 |
|
|
|
| 82 |
|
|
<p>Correspondingly, in <tt>pb_assoc</tt> there are two types of iterators: <i>find type</i>
|
| 83 |
|
|
iterators are returned by find methods, and range iterators are returned by range methods. For example,
|
| 84 |
|
|
if <tt>T</tt> is any associative container with integer keys, and <tt>t</tt>
|
| 85 |
|
|
is a container of type <tt>T</tt>,
|
| 86 |
|
|
then the following snippet is valid:
|
| 87 |
|
|
</p>
|
| 88 |
|
|
|
| 89 |
|
|
<pre>
|
| 90 |
|
|
<b>typename</b> T::find_iterator it0 = t.find(3);
|
| 91 |
|
|
<b>typename</b> T::const_find_iterator it0 = t.find(3);
|
| 92 |
|
|
|
| 93 |
|
|
<b>typename</b> T::iterator it0 = t.begin();
|
| 94 |
|
|
<b>typename</b> T::const_iterator it0 = t.begin();
|
| 95 |
|
|
</pre>
|
| 96 |
|
|
|
| 97 |
|
|
|
| 98 |
|
|
<p>
|
| 99 |
|
|
This is motivated and explained further in
|
| 100 |
|
|
<a href = "ds_gen.html#find_range">Data-Structure Genericity::Find-Type and Range-Type Methods and Iterators</a>, which also explains the relationship between find-type and range-type iterators.
|
| 101 |
|
|
</p>
|
| 102 |
|
|
|
| 103 |
|
|
<h2><a href = "#concepts_mapping_levels">Mapping Levels</a></h2>
|
| 104 |
|
|
|
| 105 |
|
|
<p>
|
| 106 |
|
|
In <tt>pb_assoc</tt> "multimaps" are
|
| 107 |
|
|
"maps" of "sets". While this design allows efficient
|
| 108 |
|
|
operations, it makes for cumbersome use at points. For example a
|
| 109 |
|
|
"multimap" of integers to characters does not
|
| 110 |
|
|
directly support <tt>inser(std::make_pair(2, 'b')</tt>, since 2 is mapped
|
| 111 |
|
|
to a "set" of characters, and not to a character.
|
| 112 |
|
|
</p>
|
| 113 |
|
|
|
| 114 |
|
|
<p>
|
| 115 |
|
|
Consequently, <tt>pb_assoc</tt> contains a rebind-like mechanism so that
|
| 116 |
|
|
containers can support such operations. To dispel ambiguity, container types are
|
| 117 |
|
|
assigned mapping levels. "Maps" and "sets" have
|
| 118 |
|
|
a mapping level 1, since they use a single association level. The "multimap"
|
| 119 |
|
|
above has a mapping level 2, since it uses two association levels: one for integers, and one for characters. The rebind mechanism can be used to alter the association level. This is described in
|
| 120 |
|
|
<a href = "ms_gen.html">Mapping Semantics</a>.
|
| 121 |
|
|
</p>
|
| 122 |
|
|
|
| 123 |
|
|
</body>
|
| 124 |
|
|
</html>
|
