1 <!DOCTYPE HTML PUBLIC
"-//W3C//DTD HTML 4.0 Transitional//EN">
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">
8 <body bgcolor =
"white">
12 Following are some concepts used throughout the documentation.
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>
21 <h2><a name =
"concepts_null_policies">Null Policy Classes
</a></h2>
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.
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.
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.
43 <tt>pb_assoc
</tt> uses special pre-defined
"null policies
" classes
44 for these cases. Some null policies in
<tt>pb_assoc
</tt>
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>
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.
63 <h2><a name =
"concepts_find_and_range_iterators">Find and Range Methods and Iterators
</a></h2>
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.
72 In general, there are two types of methods:
<i>find types
</i>, and
<i>range types
</i>.
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).
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:
90 <b>typename
</b> T::find_iterator it0 = t.find(
3);
91 <b>typename
</b> T::const_find_iterator it0 = t.find(
3);
93 <b>typename
</b> T::iterator it0 = t.begin();
94 <b>typename
</b> T::const_iterator it0 = t.begin();
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.
103 <h2><a href =
"#concepts_mapping_levels">Mapping Levels
</a></h2>
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.
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>.