1 <!DOCTYPE HTML PUBLIC
"-//W3C//DTD HTML 4.0 Transitional//EN">
4 <title>Mapping-Semantics Genericity
</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">
11 <h1>Mapping-Semantics
</h1>
14 This section describes genericity over different mapping-semantics. It is organized as follows.
17 <li><a href =
"#intro">Introduction
</a></li>
18 <li><a href =
"#ds_policy">Data Types as a Policy
</a></li>
19 <li><a href =
"#problem">The Basic Problem
</a></li>
20 <li><a href =
"#mapping_level">Mapping Levels
</a></li>
21 <li><a href =
"#ms_traits">Tags and Traits
</a></li>
22 <li><a href =
"#drawbacks">Drawbacks
</a></li>
26 <h2><a name =
"intro">Introduction
</a></h2>
29 <a href =
"motivation.html#mapping_semantics">Motivation::Mapping Semantics
</a> discussed scalability issues with the STL's non-unique-mapping associative containers; non-unique association inherently embeds linked-lists in associative containers resulting in scalability problems and other problems.
33 In
<tt>pb_assoc
</tt>, all containers have unique-key semantics. Each key is uniquely mapped to
"something
".
37 <h2><a name =
"ds_policy">Data Types as a Policy
</a></h2>
40 All associative-containers in
<tt>pb_assoc
</tt> are parameterized by a data type.
41 <i>E.g.,
</i> <a href =
"cc_hash_assoc_cntnr.html">cc_hash_assoc_cntnr
</a> is parameterized as
48 <b>class
</b> <a href =
"cc_hash_assoc_cntnr.html">cc_hash_assoc_cntnr
</a>;
52 There are no separate classes for maps, sets, multimaps, and multisets (as the STL has). Rather, the mapping-semantic is set by specifying the
<tt>Key
</tt> parameter.
56 <li> If
<tt>Data
</tt> is any type (
<i>e.g.
</i>,
<tt><b>int
</b></tt> or
57 <tt>std::string
</tt>), then the container is a
"map
" - it maps each
<tt>Key
</tt> object to a
<tt>Data
</tt> object.
59 <li> If
<tt>Data
</tt> is
60 <a href =
"null_data_type.html"><tt>null_data_type
</tt></a>,
61 then the container is a
"set
" - it stores each
<tt>Key
</tt> object. In this case, each
<tt>Key
</tt> object is not really mapped to anything (except, implicitly, to the fact that it is stored in the container object).
65 <a href =
"compound_data_type.html">compound_data_type
</a><tt><Cntnr
></tt>,
66 then the container is a
"multimap
" - it maps each
<tt>Key
</tt> object into a
<tt>Cntnr
</tt> object. This structure is recursive -
<tt>Cntnr
</tt> itself can be a
"map
",
"set
",
"multimap
", and so forth.
71 Each container derives from one of the three containers
74 Data-types as a policy
79 <li><a href =
"basic_assoc_cntnr.html"><tt>basic_assoc_cntnr
</tt></a>
80 is the base for most instantiations of a container's
<tt>Data
</tt> paramter. This
81 base includes the definition of
<tt>data_type
</tt>, and supports
82 <tt><b>operator
</b>[]
</tt>.
84 <li><a href =
"basic_assoc_cntnr_no_data.html"><tt>basic_assoc_cntnr
</tt></a> is the base for a
85 <a href =
"null_data_type"><tt>null_data_type
</tt></a> instantiation of a container's
<tt>Data
</tt> paramter. This
86 base lacks the definition of
<tt>data_type
</tt>, and does not support
87 <tt><b>operator
</b>[]
</tt>.
88 <li><a href =
"basic_assoc_cntnr_compound_data.html"><tt>basic_assoc_cntnr
</tt></a> is the base for a
89 <a href =
"compound_data_type.html"><tt>compound_data_type
</tt></a><tt><Cntnr
></tt> instantiation of a container's
<tt>Data
</tt> paramter. This
90 base includes the definition of
<tt>data_type
</tt>, and supports
91 <tt><b>operator
</b>[]
</tt>. It further supports some advanced functionality described in the remainder of this section.
97 <img src =
"ms_cd.jpg" width =
"70%" alt =
"no image">
100 <h6 align =
"center">
101 Data-types as a policy.
105 <h2><a name =
"problem">The Basic Problem
</a></h2>
108 Consider a
<tt>pb_assoc
</tt> "multimap
" mapping integers to characters.
109 Since a
<tt>pb_assoc
</tt> "multimap
" is a
"map
" of
"sets
",
110 if
<tt>m
</tt> is an object of this type, it is not possible to directly use
111 <tt>m.insert(std::make_pair(
2, 'b')
</tt> (however, it is possible to directly use
112 <tt>m[
2].insert('b')
</tt>). In would be nice if this method whould be supported.
116 Put differently, while the
<tt>pb_assoc
</tt> "multimap
" can be viewed logically as the collection
119 {
<tt><b>int
</b></tt> → {
<tt><b>char
</b></tt>} },
122 It would be nice if it could simultaneously be viewed as the collection
125 { (
<tt><b>int
</b></tt>,
<tt><b>char
</b></tt>) },
127 <p><i>i.e.
</i>, a
"set
" of pairs.
</p>
130 In more general terms, it would be nice to be able to simultaneously
134 { key_type_0
→ { key_type_1
→ { key_type_2
→ { key_type_3
→ { ... }}}}}
137 as each of the following:
140 { (key_type_0, key_type_1)
→ { key_type_2 &rarr { key_type_e
→ { ... }}}},
143 { (key_type_0, key_type_1, key_type_2) &rarr { key_type_3
→ { ... }}}
146 { (key_type_0, key_type_1, key_type_2, key_type_3 ) &rarr { }}
154 <a href = #mapping_level
">Mapping_Levels</a> discusses the mechanism
155 for these multiple views in <tt>pb_assoc</tt>
160 <h2><a name = "mapping_level
">Mapping Levels</a></h2>
163 Each associative container in <tt>pb_assoc</tt> has
164 a <i>mapping level</i>. The mapping level is defined by
165 the instantiation of a container's <tt>Data</tt>
170 <li> If the <tt>Data</tt> parameter is instantiated
172 <a href = "null_data_type.html
"><tt>null_data_type</tt></a> (<i>i.e.</i>,
173 the container is a "set"), then the mapping level is 1.
175 <li> If the <tt>Data</tt> parameter is instantiated
177 <a href = "compound_data_type.html
">compound_data_type</a><tt><Cntnr></tt>
178 (<i>i.e.</i>, the container is a "multimap"), then the mapping level
179 is 1 + the mapping level of <tt>Cntnr</tt>.
181 <li> If the <tt>Data</tt> parameter is instantiated
182 by any other type, <i>e.g.</i>, <tt><b>char</b></tt> (<i>i.e.</i>,
183 the container is a "map"), then the mapping level is 1.
188 Containers can be rebound, at compile time, to different mapping levels.
189 The compound data-type specialization <a href = "basic_assoc_cntnr_compound_data.html
"><tt>basic_assoc_cntnr</tt></a>
194 <b>int</b> Mapping_Level>
204 (which is similar to the STL's allocator rebind mechanism).
205 the type <tt>other</tt> is the view of the container with mapping
206 level <tt>Mapping_Level</tt>. The container can be safely cast
211 As an example, consider the type
216 <a href = "cc_hash_assoc_cntnr.html
">cc_hash_assoc_cntnr</a><
218 <a href = "compound_data_type.html
">compound_data_type</a><
219 <a href = "tree_assoc_cntnr.html
">tree_assoc_cntnr</a><
221 <a href = "null_data_type.html
"><tt>null_data_type</tt></a>> > >
225 which is a "map" mapping each <tt><b>int</b></tt> to
226 a "set" of <tt><b>char</b></tt>s. In this case, <tt>cntnr_t</tt> has mapping level 2.
230 An object of type <tt>cntnr_t</tt> cannot support <tt>insert(std::make_pair(2, 'b'));</tt>. On the other hand, the following code snippet shows how to do so:
240 ((t_ &)c).insert(std::make_pair(2, 'b'));
245 <a href = "../example/mapping_level_example.cpp
"><tt>mapping_level_example.cpp</tt></a> shows a more detailed example.
250 <h2><a name = "ms_traits
">Tags and Traits</a></h2>
253 It is, of course, beneficial to query types for their mapping semantics.
257 Each container defines internally the type <tt>ms_category</tt>
258 as its mapping-semantics tag (hopefully this name is not copyrighted
259 by some major corporation). The possible tags, shown in Figure
266 <a href = "basic_ms_tag.html
"><tt>basic_ms_tag</tt></a>
267 is a basic mapping-semantics tag. It is the type defined by "set"s.
270 <a href = "data_enabled_ms_tag.html
"><tt>data_enabled_ms_tag</tt></a>
271 is a mapping-semantics tag of types that have data. It is the type defined by "map"s.
274 <a href = "compound_data_enabled_ms_tag.html
"><tt>compound_data_enabled_ms_tag</tt></a>
275 is a mapping-semantics tag of types that have compound data. It is the type defined by "multimap"s.
280 Additionally, a container's mapping semantics can be queried by traits. For any
281 container <tt>Cntnr</tt>,
285 <a href = "ms_traits.html
">ms_traits</a><Cntnr>::mapping_level
289 indicates the mapping level of the container, for example.
294 <h2><a name = "drawbacks
">Drawbacks</a></h2>
296 <tt>pb_assoc</tt>'s mapping-semantics design has some drawbacks compared to that of the STL.
299 <h3>Equivalent, Non-Identical Keys</h3>
302 The STL's multimaps and multisets allow storing equivalent, non-identical keys
303 [<a href = "references.html#kleft00sets
">kleft00sets</a>]. For example, assume a bank maintains a data structure monitoring the accounts opened by each person. This could be modeled as the following:
312 <i>// Account-id type.</i>
317 <i>// Association between a name and an account id.</i>
318 <b>class</b> opened_info
323 <i>// Comparison operator.</i>
325 <b></b>operator<</b>
326 (<b>const</b> opened_info &r_other)
328 <i>Comparison is defined as the comparison of the names.</i>
329 <b>return</b> m_name < r_other.m_name;
339 <i>// A multiset of opened accounts.</i>
347 <tt>std::multiset</tt> can accomodate multiple equivalent, non-identical <tt>opened_info</tt> - those with the same name but different account id.
351 In <tt>pb_assoc</tt>, however, non-unique mapping is unsupported. The equivalent to the above could be
358 compound_data_type<
359 cc_hash_assoc_cntnr<
360 account_id> > >
365 The drawback lies in the fact that the data stored in
366 <tt>all_opened_info</tt> is less encapsulated - an <tt>opened_info</tt>
367 object needs to be constructed when a specific name and account are found, and
368 an <tt>opened_info</tt> object needs to be decomposed into <tt>name</tt> and
369 <tt>account_id</tt> objects when it is inserted into a <tt>all_opened_info</tt>
374 It should be noticed however, that the above drawbacks - construction and decomposition are constant-time additive drawbacks. The drawbacks of the
375 STL's associative containers are in terms of orders of growth.
378 <h3>Definition of <tt>value_type</tt></h3>
381 The STL's associative containers contain a pleasingly uniform definition of
382 the <tt>value_type</tt> of a container.
383 If a container is parameterized by <tt>key</tt> as its <tt>Key</tt>, and <tt>data</tt> as its <tt>Data</tt>, then its <tt>value_type</tt> is
384 <tt>std::pair<<b>const</b> key, data></tt>;
385 for example, the <tt>value_type</tt> of <tt>std::map<<b>int</b>, <b>char</b>></tt> is
386 <tt>std::pair<<b>const int</b>, <b>char</b>></tt>. Futhermore, the <tt>value_type</tt> of a container and the <tt>value_type</tt> of the container's iterators are identical.
390 In <tt>pb_assoc</tt>, conversely, the rules are more complex.
393 <p> For one, a container's
394 <tt>value_type</tt> is, in general
395 <tt>std::pair<<b>const</b> Key, Data></tt>,
396 but if <tt>Data</tt> is <tt>null_data_type</tt>, then the <tt>value_type</tt>
401 <tt>compound_data_type<Cntnr></tt>, then the <tt>value_type</tt> is
402 <tt>std::pair<<b>const</b> Key, Cntnr></tt>.
406 Futhermore, assume that <tt>Cntnr</tt> is an associative container with more than a single mapping level, and let <tt>Cntnr_</tt> be defined as
411 <b>typename</b> Cntnr::<b>template</b> rebind<i>::other</tt>
415 <i>i.e.</i>, the container rebound to a different mapping level.
416 In this case, the <tt>value_type</tt> of the rebound container is not the <tt>value_type</tt>
417 of the rebound container's iterators. <i>I.e.</i>, it is <emph>not</emph> true that
418 <tt><b>typename</b> Cntnr_::value_type</tt> is the same as
419 <tt><b>typename</b> Cntnr_::iterator::value_type</tt>. This complication never exists for the STL's container.
422 <h6 align = "center
">
423 <a name = "reference_iterator
">
424 <img src = "reference_iterator.jpg
" width = "70%
" alt = "no image
">
427 <h6 align = "center
">
428 Iterator of a rebound type.
435 <tt>pb_assoc</tt> does not contain a "multiset" type. The closest equivalent is mapping keys to non-negative integral types, <i>e.g.</i>, <tt>size_t</tt>.