1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<title>Non-Unique Mapping Containers</title>
<meta name="GENERATOR" content="Microsoft Visual Studio .NET 7.1">
<meta name="vs_targetSchema" content="http://schemas.microsoft.com/intellisense/ie5">
</head>
<body bgcolor="white">
<h1>Non-Unique Mapping Containers</h1>
<p>
This section describes the design of non-unique mapping containers
(multimaps and multisets). It is organized as follows:
</p>
<ol>
<li> The <a href = "#general">Main Points</a> Section describes the main points.
</li>
<li>
The <a href = "#types">Mapped Data Types and Mapped Value Types</a> Section
describes some additional types that each associative container defines.
</li>
<li> The <a href = "generics">Generics</a> Section describes some classes for
generic programming.
</li>
<li> The <a href = "#compound_keys">Compound Keys</a> Section describes an
alternative to the STL's design of using equivalent, non-identical, keys.
</li>
</ol>
<h2><a name = "general">Main Points</a></h2>
<p>
In <tt>pb_assoc</tt>, all associative containers have a unique-key design;
each container can have at most one entry for any given key. Multimaps
are designed as maps from keys to sets; multisets are designed as maps from
keys to non-negative integral types.
</p>
<h2><a name = "types">Mapped Data Types and Mapped Value Types</a></h2>
<p>
The STL's design of associative containers elegantly allows
generic manipulation of containers: each container defines
<tt>data_type</tt> as the domain of its data;
<tt>value_type</tt> as the domain of its relationship. This is not
directly applicable in <tt>pb_assoc</tt>. Consider
a multimap mapping <tt>Key</tt> objects to
<tt>Data_Coll</tt> objects, where
<tt>Data_Coll</tt> is some set-type of <tt>Data</tt>.
Then should the multimap's <tt>value_type</tt> should be
<tt>std::pair<Key, Data></tt> or
<tt>std::pair<Key, Data_Coll></tt>, for example?.
</p>
<p>
<tt>pb_assoc</tt> addresses this by differentiating
between the <i>domain</i> and the <i>type</i> of relationship.
All associative containers define <tt>value_type</tt> as
the relationship's <i>domain</i>, and <tt>mapped_value_type</tt> as its
<i>type</i>. <i>E.g.</i>, both
map types and multimap types may share the same <tt>value_type</tt>,
if they map from the same key domain to
the same data domain. In this case, however, they will not share
the same <tt>mapped_value_type</tt>, since the multimap type maps from the
key domain to the domain of collections of data. The same
differentiation exists between the domain and type of mapped data.
</p>
<p>
In general, the following types describe the relationships
of each associative container:
</p>
<ol>
<li>
<tt>key_type</tt>- This describes the domain of the keys of the container. All
associative containers define this type.
</li>
<li>
<tt>data_type</tt>- This describes the <i>domain</i> of the data mapped by a
key. It is identical to the <tt>data_type</tt> defined by <tt>std::map</tt>, <tt>std::set</tt>,
<tt>std::multimap</tt>, and <tt>std::multiset</tt>. Sets and multisets do not
define this type, since they map each key to the abstract fact that the key is
stored by them.
</li>
<li>
<tt>mapped_data_type</tt>- This describes the <i>type</i> of the data mapped by
a key. For maps, this is the same as <tt>data_type</tt>. For multimaps, this is
not the same as <tt>data_type</tt>; The <tt>mapped_data_type</tt> describes the
collection of <tt>data_type</tt>s used. Sets do not define this type. For
multisets, the <tt>mapped_data_type</tt> describes the unsigned integral type
used to indicate the number of occurrences of a key.
</li>
<li>
<tt>value_type</tt>- This describes the <i>domain</i> of relationships store in
a container. It is identical to the <tt>value_type</tt> defined by <tt>std::map</tt>,
<tt>std::set</tt>, <tt>std::multimap</tt>, and <tt>std::multiset</tt>.
</li>
<li>
<tt>mapped_value_type</tt>- This describes the <i>type</i> of relationships
store in a container. It consists of information on the <tt>key_type</tt> and <tt>mapped_data_type</tt>
(except for sets).
</li>
</ol>
<p>
The following table defines the above types for a map
mapping from <tt>Key</tt> types to <tt>Data</tt> types:
</p>
<TABLE WIDTH="100%" BORDER="1" ID="Table1">
<TR>
<TD Width="50%" ALIGN="left"><b>type</b></TD>
<TD Width="50%" ALIGN="left"><b>Description / Definition</b></TD>
</TR>
<TR>
<TD ALIGN="left"><pre>key_type</pre>
</TD>
<TD ALIGN="left"><pre>Key</pre>
</TD>
</TR>
<TR>
<TD ALIGN="left"><pre>data_type</pre>
</TD>
<TD ALIGN="left"><pre>Data</pre>
</TD>
</TR>
<TR>
<TD ALIGN="left"><pre>mapped_data_type</pre>
</TD>
<TD ALIGN="left"><pre>Data</pre>
</TD>
</TR>
<TR>
<TD ALIGN="left"><pre>value_type</pre>
</TD>
<TD ALIGN="left"><pre>std::pair<<b>const</b> Key, Data></pre>
</TD>
</TR>
<TR>
<TD ALIGN="left"><pre>mapped_value_type</pre>
</TD>
<TD ALIGN="left"><pre>std::pair<<b>const</b> Key, Data></pre>
</TD>
</TR>
</TABLE>
<p>The following table defines the above types for a
set storing <tt>Key</tt> types:</p>
<TABLE WIDTH="100%" BORDER="1" ID="Table2">
<TR>
<TD Width="50%" ALIGN="left"><b>type</b></TD>
<TD Width="50%" ALIGN="left"><b>Description / Definition</b></TD>
</TR>
<TR>
<TD ALIGN="left"><pre>key_type</pre>
</TD>
<TD ALIGN="left"><pre>Key</pre>
</TD>
</TR>
<TR>
<TD ALIGN="left"><pre>data_type</pre>
</TD>
<TD ALIGN="left">-</TD>
</TR>
<TR>
<TD ALIGN="left"><pre>mapped_data_type</pre>
</TD>
<TD ALIGN="left">-</TD>
</TR>
<TR>
<TD ALIGN="left"><pre>value_type</pre>
</TD>
<TD ALIGN="left"><pre><b>const</b> Key</pre>
</TD>
</TR>
<TR>
<TD ALIGN="left"><pre>mapped_value_type</pre>
</TD>
<TD ALIGN="left"><pre><b>const</b> Key</pre>
</TD>
</TR>
</TABLE>
<p>The following table defines the above types for a multimap
mapping from <tt>Key</tt> types to <tt>Data_Coll<Data></tt>
types, where <tt>Data_Coll<Data></tt>
is a set of <tt>Data</tt> types:</p>
<TABLE WIDTH="100%" BORDER="1" ID="Table3">
<TR>
<TD Width="50%" ALIGN="left"><b>type</b></TD>
<TD Width="50%" ALIGN="left"><b>Description / Definition</b></TD>
</TR>
<TR>
<TD ALIGN="left"><pre>key_type</pre>
</TD>
<TD ALIGN="left"><pre>Key</pre>
</TD>
</TR>
<TR>
<TD ALIGN="left"><pre>data_type</pre>
</TD>
<TD ALIGN="left"><pre>Data</pre>
</TD>
</TR>
<TR>
<TD ALIGN="left"><pre>mapped_data_type</pre>
</TD>
<TD ALIGN="left"><pre>Data_Coll<Data></pre>
</TD>
</TR>
<TR>
<TD ALIGN="left"><pre>value_type</pre>
</TD>
<TD ALIGN="left"><pre>std::pair<<b>const</b> Key, Data></pre>
</TD>
</TR>
<TR>
<TD ALIGN="left"><pre>mapped_value_type</pre>
</TD>
<TD ALIGN="left"><pre>std::pair<<b>const</b> Key, Data_Coll<Data> ></pre>
</TD>
</TR>
</TABLE>
<p>The following table defines the above types for a multiset
storing <tt>Key</tt> types:</p>
<TABLE WIDTH="100%" BORDER="1" ID="Table4">
<TR>
<TD Width="50%" ALIGN="left"><b>type</b></TD>
<TD Width="50%" ALIGN="left"><b>Description / Definition</b></TD>
</TR>
<TR>
<TD ALIGN="left"><pre>key_type</pre>
</TD>
<TD ALIGN="left"><pre>Key</pre>
</TD>
</TR>
<TR>
<TD ALIGN="left"><pre>data_type</pre>
</TD>
<TD ALIGN="left">-</TD>
</TR>
<TR>
<TD ALIGN="left"><pre>mapped_data_type</pre>
</TD>
<TD ALIGN="left"><pre>size_type</pre>
</TD>
</TR>
<TR>
<TD ALIGN="left"><pre>value_type</pre>
</TD>
<TD ALIGN="left"><pre>std::pair<<b>const</b> Key, size_type></pre>
</TD>
</TR>
<TR>
<TD ALIGN="left"><pre>mapped_value_type</pre>
</TD>
<TD ALIGN="left"><pre><b>const</b> Key</pre>
</TD>
</TR>
</TABLE>
<p>
The above types allow to define simple invariants on the interfaces of
containers. For example, each container defines both an <tt>insert</tt> method
which takes a const reference to a <tt>value_type</tt>, and an <tt>insert</tt> method
which takes a const reference to a <tt>mapped_value_type</tt>. Containers for
which both these types are synonymous (<i>i.e.</i>, maps and sets), consequently
have a
single <tt>insert</tt> method. Containers for which these types are distinct (<i>i.e.</i>,
multimaps and multisets), use overloading.
</p>
<h2><a name="generics">Generics</a></h2>
<p>
<tt>pb_assoc</tt> contains a number of utility classes to ease generic
programming.
</p>
<p>
There are four container-type identifiers, <a href="is_map_type.html"><tt>is_map_type</tt></a>,
<a href="is_set_type.html"><tt>is_set_type</tt></a>, <a href="is_multimap_type.html">
<tt>is_multimap_type</tt></a>, and <a href="is_multiset_type.html"><tt>is_multiset_type</tt></a>.
Given a container <tt>T</tt>, for example, it is possible to query at compile
time whether it is a a multimap type by writing <tt>is_multimap_type<T>::value</tt>.
(This is probably very similar to [<a href="references.html#boost_concept_check">boost_concept_check</a>]
and [<a href="references.html#boost_type_traits">boost_type_traits</a>].)
</p>
<p>
In some cases, it is necessary, given a container and an iterator, to query the
iterator' <tt>value_type</tt> to the container's <tt>value_type</tt> and <tt>mapped_value_type</tt>.
The classes
<a href="is_mapped_value_iterator.html"><tt>is_mapped_value_iterator</tt></a>
and <a href="iterator_key.html"><tt>iterator_key</tt></a> can be used for this.
</p>
<p>
The STL's <tt>std::multimap</tt> and <tt>std::multiset</tt> allow iterating
over all <tt>value_type</tt>s stored in them, which is convenient. The library
provides a <a href="value_iterators.html"><tt>value_iterator</tt></a> for this.
This is an iterator adapter over the containers' native iterators.
</p>
<h2><a name = "compound_keys">Compound Keys</a></h2>
<p>
The STL allows using equivalent, non-identical, keys.
For example, let <tt>interval</tt> be a line-interval class,
<tt>color</tt> be a
color type, <tt>thickness</tt> be a thickness type, and <tt>colored_interval</tt>
be a class composed of an <tt>interval</tt> and a <tt>color</tt>.
</p>
<p>
Suppose one wants to store <tt>colored_interval</tt>
objects using a comparison predicate ignoring colors. Then
in the STL's design, one would use
<tt>multiset<colored_interval></tt>; in <tt>pb_assoc</tt>'s design,
one would use one of the following:
</p>
<ol>
<li>
A map mapping <tt>interval</tt> objects to
<tt>color</tt> objects. This, however, assumes that
<tt>colored_interval</tt> is decomposable to, and constructible from,
<tt>interval</tt> and <tt>color</tt>.
</li>
<li>
A map mapping <tt>colored_interval</tt> objects to
<tt>color</tt> objects. In this (less efficient) case, a <tt>colored_interval</tt> object
is a "representative" of all colored intervals with the same endpoints.
</li>
</ol>
<p>
Suppose one wants to map <tt>colored_interval</tt>
objects to <tt>thickness</tt> objects
using a comparison predicate ignoring colors. Then
in the STL's design, one would use
<tt>multimap<colored_interval, thickness></tt>; in <tt>pb_assoc</tt>'s design,
one would use one of the following:
</p>
<ol>
<li> A map mapping <tt>interval</tt> objects to
<tt>std::pair<color, thickness></tt> objects. This, however, assumes that
<tt>colored_interval</tt> is decomposable to, and constructible from,
<tt>interval</tt> and <tt>color</tt>.
</li>
<li> A map mapping <tt>colored_interval</tt> objects to
<tt>std::pair<color, thickness></tt> objects. In this (less efficient) case, a <tt>colored_interval</tt> object
is a "representative" of all colored intervals with the same endpoints.
</li>
</ol>
<p>
(From the above, it is apparent that the STL's design has an advantage
over <tt>pb_assoc</tt>'s design in terms of convenience. Nonethless, there
are efficiency limitation in the STL's design (see
<a href = "motivation.html#unique_key">Unique-Key Design for Multimaps and Multisets</a>).)
</p>
<p>
The above example, using intervals, colors and thicknesses, can be generalized.
Let
<tt>key_unique_part</tt> be a unique part of some key
(<i>e.g.</i>, <tt>interval</tt> in the above),
<tt>key_non_unique_part</tt> be a non-unique part of some key
(<i>e.g.</i>, <tt>color</tt> in the above),
<tt>key</tt> be some key composed of unique and non-uniqe parts
(<i>e.g.</i>, <tt>colored_interval</tt> in the above),
and
<tt>data</tt> be some data
(<i>e.g.</i>, <tt>thickness</tt> in the above).
Then the <a href = "#stl_to_pb_assoc_non_unique_mapping">
figure shows some
STL containers and the <tt>pb_assoc</tt> counterparts.
</a>
</p>
<h6 align = "center">
<a name = "stl_to_pb_assoc_non_unique_mapping">
<img src = "stl_to_pb_assoc_non_unique_mapping.jpg" alt = "no-image" width = "60%">
</a>
</h6>
<h6 align = "center">
STL containers and <tt>pb_assoc</tt> counterparts.
</h6>
</body>
</html>
|
