old-autovect-branch/libstdc++-v3/docs/html/ext/pb_assoc/non_unique_mapping.html

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