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

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
   2 <html>
   3     <head>
   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">
   7     </head>
   8 <body bgcolor = "white">
   9
  10
  11 <h1>Mapping-Semantics</h1>
  12
  13 <p>
  14         This section describes genericity over different mapping-semantics. It is organized as follows.
  15 </p>
  16 <ol>
  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>
  23 </ol>
  24
  25
  26 <h2><a name = "intro">Introduction</a></h2>
  27
  28 <p>
  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.
  30 </p>
  31
  32 <p>
  33         In <tt>pb_assoc</tt>, all containers have unique-key semantics. Each key is uniquely mapped to &quot;something&quot;.
  34 </p>
  35
  36
  37 <h2><a name = "ds_policy">Data Types as a Policy</a></h2>
  38
  39 <p>
  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
  42 </p>
  43 <pre>
  44 <b>template</b>&lt;
  45         <b>typename</b> Key,
  46         <b>typename</b> Data,
  47         ...&gt;
  48 <b>class</b> <a href = "cc_hash_assoc_cntnr.html">cc_hash_assoc_cntnr</a>;
  49 </pre>
  50
  51 <p>
  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.
  53 </p>
  54
  55 <ol>
  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 &quot;map&quot; - it maps each <tt>Key</tt> object to a <tt>Data</tt> object.
  58         </li>
  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 &quot;set&quot; - 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).
  62         </li>
  63         <li>
  64         If <tt>Data</tt> is
  65 <a href = "compound_data_type.html">compound_data_type</a><tt>&lt;Cntnr&gt;</tt>,
  66 then the container is a &quot;multimap&quot; - it maps each <tt>Key</tt> object into a <tt>Cntnr</tt> object. This structure is recursive - <tt>Cntnr</tt> itself can be a &quot;map&quot;, &quot;set&quot;, &quot;multimap&quot;, and so forth.
  67         </li>
  68 </ol>
  69
  70 <p>
  71         Each container derives from one of the three containers
  72 in the oval of Figure
  73 <a href = "#ms_cd">
  74 Data-types as a policy
  75 </a>.
  76 </p>
  77
  78                 <ol>
  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>.
  83                         </li>
  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>&lt;Cntnr&gt;</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.
  92                 </ol>
  93
  94
  95 <h6 align = "center">
  96 <a name = "ms_cd">
  97 <img src = "ms_cd.jpg" width = "70%" alt = "no image">
  98 </h6>
  99 </a>
 100 <h6 align = "center">
 101 Data-types as a policy.
 102 </h6>
 103
 104
 105 <h2><a name = "problem">The Basic Problem</a></h2>
 106
 107 <p>
 108         Consider a <tt>pb_assoc</tt> &quot;multimap&quot; mapping integers to characters.
 109 Since a <tt>pb_assoc</tt> &quot;multimap&quot; is a &quot;map&quot; of &quot;sets&quot;,
 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.
 113 </p>
 114
 115 <p>
 116         Put differently, while the <tt>pb_assoc</tt> &quot;multimap&quot; can be viewed logically as the collection
 117 </p>
 118 <p>
 119         { <tt><b>int</b></tt> &rarr; {<tt><b>char</b></tt>} },
 120 </p>
 121 <p>
 122         It would be nice if it could simultaneously be viewed as the collection
 123 </p>
 124 <p>
 125         { (<tt><b>int</b></tt>, <tt><b>char</b></tt>) },
 126 </p>
 127 <p><i>i.e.</i>, a &quot;set&quot; of pairs.</p>
 128
 129 <p>
 130         In more general terms, it would be nice to be able to simultaneously
 131 view a collection
 132 </p>
 133 <p>
 134 { key_type_0 &rarr; { key_type_1 &rarr; { key_type_2 &rarr; { key_type_3 &rarr; { ... }}}}}
 135 </p>
 136 <p>
 137 as each of the following:
 138 </p>
 139 <p>
 140 { (key_type_0, key_type_1) &rarr; { key_type_2 &rarr { key_type_e &rarr; { ... }}}},
 141 </p>
 142 <p>
 143 { (key_type_0, key_type_1, key_type_2) &rarr { key_type_3 &rarr; { ... }}}
 144 </p>
 145 <p>
 146 { (key_type_0, key_type_1, key_type_2, key_type_3 ) &rarr { }}
 147 </p>
 148 <p>
 149 ...
 150 </p>
 151
 152
 153 <p>
 154 <a href = #mapping_level">Mapping_Levels</a> discusses the mechanism
 155 for these multiple views in <tt>pb_assoc</tt>
 156 </p>
 157
 158
 159
 160 <h2><a name = "mapping_level">Mapping Levels</a></h2>
 161
 162 <p>
 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>
 166 parameter:
 167 </p>
 168
 169 <ol>
 170         <li> If the <tt>Data</tt> parameter is instantiated
 171 by
 172 <a href = "null_data_type.html"><tt>null_data_type</tt></a> (<i>i.e.</i>,
 173 the container is a &quot;set&quot;), then the mapping level is 1.
 174         </li>
 175         <li> If the <tt>Data</tt> parameter is instantiated
 176 by
 177 <a href = "compound_data_type.html">compound_data_type</a><tt>&lt;Cntnr&gt;</tt>
 178 (<i>i.e.</i>, the container is a &quot;multimap&quot;), then the mapping level
 179 is 1 + the mapping level of <tt>Cntnr</tt>.
 180         </li>
 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 &quot;map&quot;), then the mapping level is 1.
 184         </li>
 185 </ol>
 186
 187 <p>
 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>
 190 defines internally
 191 </p>
 192 <pre>
 193 <b>template</b>&lt;
 194         <b>int</b> Mapping_Level&gt;
 195 <b>struct</b> rebind
 196 {
 197         <b>typedef</b>
 198                 ...
 199                 other;
 200 };
 201 </pre>
 202
 203 <p>
 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
 207 to <tt>other</tt>.
 208 </p>
 209
 210 <p>
 211         As an example, consider the type
 212 </p>
 213
 214 <pre>
 215 <b>typedef</b>
 216         <a href = "cc_hash_assoc_cntnr.html">cc_hash_assoc_cntnr</a>&lt;
 217                 <b>int</b>,
 218                 <a href = "compound_data_type.html">compound_data_type</a>&lt;
 219                         <a href = "tree_assoc_cntnr.html">tree_assoc_cntnr</a>&lt;
 220                                 <b>char</b>,
 221                                 <a href = "null_data_type.html"><tt>null_data_type</tt></a>&gt; &gt; &gt;
 222         cntnr_t;
 223 </pre>
 224 <p>
 225         which is a &quot;map&quot; mapping each <tt><b>int</b></tt> to
 226 a &quot;set&quot; of <tt><b>char</b></tt>s. In this case, <tt>cntnr_t</tt> has mapping level 2.
 227 </p>
 228
 229 <p>
 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:
 231 </p>
 232
 233 <pre>
 234 cntnr_t c;
 235
 236 <b>typedef</b>
 237         t::rebind<1>::other
 238         t_;
 239
 240 ((t_ &)c).insert(std::make_pair(2, 'b'));
 241 </pre>
 242
 243
 244 <p>
 245 <a href = "../example/mapping_level_example.cpp"><tt>mapping_level_example.cpp</tt></a> shows a more detailed example.
 246 </p>
 247
 248
 249
 250 <h2><a name = "ms_traits">Tags and Traits</a></h2>
 251
 252 <p>
 253         It is, of course, beneficial to query types for their mapping semantics.
 254 </p>
 255
 256 <p>
 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
 260
 261 are the following:
 262 </p>
 263
 264 <ol>
 265         <li>
 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 &quot;set&quot;s.
 268         </li>
 269         <li>
 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 &quot;map&quot;s.
 272         </li>
 273         <li>
 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 &quot;multimap&quot;s.
 276         </li>
 277 </ol>
 278
 279 <p>
 280         Additionally, a container's mapping semantics can be queried by traits. For any
 281 container <tt>Cntnr</tt>,
 282 </p>
 283
 284 <pre>
 285 <a href = "ms_traits.html">ms_traits</a>&lt;Cntnr&gt;::mapping_level
 286 </pre>
 287
 288 <p>
 289         indicates the mapping level of the container, for example.
 290 </p>
 291
 292
 293
 294 <h2><a name = "drawbacks">Drawbacks</a></h2>
 295
 296 <tt>pb_assoc</tt>'s mapping-semantics design has some drawbacks compared to that of the STL.
 297
 298
 299 <h3>Equivalent, Non-Identical Keys</h3>
 300
 301 <p>
 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:
 304 </p>
 305
 306 <pre>
 307 <i>// Name type.</i>
 308 <b>typedef</b>
 309         std::string
 310         name;
 311
 312 <i>// Account-id type.</i>
 313 <b>typedef</b>
 314         <b>unsigned long</b>
 315         account_id;
 316
 317 <i>// Association between a name and an account id.</i>
 318 <b>class</b> opened_info
 319 {
 320 <b>public</b>:
 321         ...
 322
 323         <i>// Comparison operator.</i>
 324         <b>bool</b>
 325                 <b></b>operator&lt;</b>
 326                 (<b>const</b> opened_info &r_other)
 327         {
 328                 <i>Comparison is defined as the comparison of the names.</i>
 329                 <b>return</b> m_name < r_other.m_name;
 330         }
 331
 332
 333 <b>private</b>:
 334         name m_name;
 335
 336         account_id m_acc_id;
 337 };
 338
 339 <i>// A multiset of opened accounts.</i>
 340 <b>typedef</b>
 341         std::multiset&lt;
 342                 opened_info&gt;
 343         all_opened_info;
 344 </pre>
 345
 346 <p>
 347         <tt>std::multiset</tt> can accomodate multiple equivalent, non-identical <tt>opened_info</tt> - those with the same name but different account id.
 348 </p>
 349
 350 <p>
 351         In <tt>pb_assoc</tt>, however, non-unique mapping is unsupported. The equivalent to the above could be
 352 </p>
 353
 354 <pre>
 355 <b>typedef</b>
 356         tree_assoc_cntnr&lt;
 357                 name,
 358                 compound_data_type&lt;
 359                         cc_hash_assoc_cntnr&lt;
 360                                 account_id&gt; &gt; &gt;
 361         all_opened_info;
 362 </pre>
 363
 364 <p>
 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>
 370 object.
 371 </p>
 372
 373 <p>
 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.
 376 </p>
 377
 378 <h3>Definition of <tt>value_type</tt></h3>
 379
 380 <p>
 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&lt;<b>const</b> key, data&gt;</tt>;
 385 for example, the <tt>value_type</tt> of <tt>std::map&lt;<b>int</b>, <b>char</b>&gt;</tt> is
 386 <tt>std::pair&lt;<b>const int</b>, <b>char</b>&gt;</tt>. Futhermore, the <tt>value_type</tt> of a container and the <tt>value_type</tt> of the container's iterators are identical.
 387 </p>
 388
 389 <p>
 390         In <tt>pb_assoc</tt>, conversely, the rules are more complex.
 391 </p>
 392
 393 <p> For one, a container's
 394 <tt>value_type</tt> is, in general
 395 <tt>std::pair&lt;<b>const</b> Key, Data&gt;</tt>,
 396 but if <tt>Data</tt> is <tt>null_data_type</tt>, then the <tt>value_type</tt>
 397 is
 398 <tt>Key</tt>,
 399 and if
 400 <tt>Data</tt> is
 401 <tt>compound_data_type&lt;Cntnr&gt;</tt>, then the <tt>value_type</tt> is
 402 <tt>std::pair&lt;<b>const</b> Key, Cntnr&gt;</tt>.
 403 </p>
 404
 405 <p>
 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
 407 </p>
 408
 409 <pre>
 410 <b>typedef</b>
 411         <b>typename</b> Cntnr::<b>template</b> rebind&lt;i&gt;::other</tt>
 412         Cntnr_;
 413 </pre>
 414 <p>
 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.
 420 </p>
 421
 422 <h6 align = "center">
 423 <a name = "reference_iterator">
 424 <img src = "reference_iterator.jpg" width = "70%" alt = "no image">
 425 </h6>
 426 </a>
 427 <h6 align = "center">
 428 Iterator of a rebound type.
 429 </h6>
 430
 431
 432 <h3>Multisets</h3>
 433
 434 <p>
 435         <tt>pb_assoc</tt> does not contain a &quot;multiset&quot; type. The closest equivalent is mapping keys to non-negative integral types, <i>e.g.</i>, <tt>size_t</tt>.
 436 </p>
 437
 438 </body>
 439
 440 </html>