gomp-20050608-branch/libstdc++-v3/docs/html/ext/pb_assoc/overview.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
   2 <html>
   3     <head>
   4         <title>Overview</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>Overview</h1>
  12
  13 <p>
  14         The <a href = "introduction.html">Introduction</a> Section described some challenges
  15 in designing associative containers. This section describes the <tt>pb_assoc</tt>'s solution.
  16 </p>
  17
  18
  19 <p>
  20 Figure
  21 <a href = "#cd">Class hierarchy</a>
  22 shows a class diagram of <tt>pb_assoc's associative containers.</tt>
  23 Associative container classes subclass other associative container classes such that
  24 base classes capture common types and methods
  25 [<a href = "references.html#stroustrup97cpp">stroustrup97cpp</a>]. The type <tt>hash_fn</tt> is defined in <a href = "basic_hash_assoc_cntnr.html"><tt>basic_hash_assoc_cntnr</tt></a>, for example, since all hash-based containers employ a hash function;
  26 <a href = "cc_hash_assoc_cntnr.html"><tt>cc_hash_assoc_cntnr</tt></a>
  27 and
  28 <a href = "gp_hash_assoc_cntnr.html"><tt>gp_hash_assoc_cntnr</tt></a>,
  29 subclasses encapsulating a collision-chaining and (general) probing hash table, respectively, each define other types specific for their underlying data-structure.
  30 This is described further in
  31 <a href = "ds_gen.html">Data-Structure Genericity</a>.
  32 </p>
  33
  34 <h6 align = "center">
  35 <a name = "cd">
  36 <img src = "cd.jpg" width = "70%" alt = "no image">
  37 </h6>
  38 </a>
  39 <h6 align = "center">
  40 Class hierarchy.
  41 </h6>
  42
  43 <p>
  44         It is sometimes useful to know the underlying data-structure.
  45 Associative containers internally define <tt>ds_category</tt> as a class describing this. Two classes might be different instantiations
  46 of
  47 <a href = "tree_assoc_cntnr.html"><tt>tree_assoc_cntnr</tt></a>, but one might be based on a red-black tree while another might be based on a splay tree. (This might affect the way tree objects should be manipulated.) <tt><b>typename</b> Cntnr::ds_category</tt>
  48 yields a &quot;tag&quot; class for the underlying data-structure of some type
  49 <tt>Cntnr</tt>.
  50 This is described further in
  51 <a href = "ds_gen.html">Data-Structure Genericity</a>.
  52 </p>
  53
  54 <p>
  55         When manipulating generic containers, it is useful to know which types, methods, and guarantees they support. For example, tree-based containers can support split and join operations, while containers based on most other underlying data-structures cannot.
  56 These questions can be answered in compile time through a traits mechanism.
  57 <a href = "ds_traits.html"><tt>ds_traits</tt>&lt;Cntnr&gt;::split_join</a>, for example, answers the above question.
  58 This is described further in
  59 <a href = "ds_gen.html">Data-Structure Genericity</a>;
  60 <a href = "../example/ds_traits_example.cpp"><tt>ds_traits_example.cpp</tt></a>-
  61 shows an example.
  62 </p>
  63
  64 <p>
  65         <tt>pb_assoc</tt>       does not contain separate containers for different mapping semantics,
  66 as the STL does (<i>e.g.</i>, <tt>std::map</tt> and <tt>std::multimap</tt>). Rather, containers are parameterized by a <tt>Data</tt> parameter, and this parameter is a policy for the mapping semantics.
  67 </p>
  68 <ol>
  69         <li>
  70         Instantiating a container's <tt>Data</tt> parameter by all but two distingished types, will make a &quot;map&quot;. Thus
  71 <pre>
  72 <a href = "cc_hash_assoc_cntnr.html">cc_hash_assoc_cntnr</a>&lt;
  73         <b>int</b>,
  74         <b>char</b>&gt;
  75 </pre> is a type mapping each <tt><b>int</b></tt> value to a <tt><b>char</b></tt>
  76         value.
  77         <a href = "../example/basic_map_example.cpp"><tt>basic_map_example.cpp</tt></a>
  78         shows an example.
  79         </li>
  80         <li>
  81         Instantiating a container's <tt>Data</tt> parameter by <a href = "null_data_type.html"><tt>null_data_type</tt></a> will make a &quot;set&quot;. Thus
  82 <pre>
  83 <a href = "cc_hash_assoc_cntnr.html">cc_hash_assoc_cntnr</a>&lt;
  84         <b>int</b>,
  85         <a href = "null_data_type.html">null_data_type</a>&gt;
  86 </pre>
  87 is a type storing unique <tt><b>int</b></tt> values.
  88 <a href = "../example/basic_set_example.cpp"><tt>basic_set_example.cpp</tt></a> shows an example.
  89         </li>
  90         <li>
  91         Instantiating a container's <tt>Data</tt> parameter by <a href = "compound_data_type.html"><tt>compound_data_type</tt></a><tt>&lt;Cntnr&gt;</tt>, where <tt>Cntnr</tt> is a different associative container, will make a &quot;(multi)+map&quot;. Thus
  92 <pre>
  93 <a href = "cc_hash_assoc_cntnr.html">cc_hash_assoc_cntnr</a>&lt;
  94         <b>int</b>,
  95         <a href = "compound_data_type.html">compound_data_type</a>&lt;
  96                 <a href = "cc_hash_assoc_cntnr.html">cc_hash_assoc_cntnr</a>&lt;
  97                         <b>char</b>,
  98                         <a href = "null_data_type.html">null_data_type</a>&gt; &gt; &gt;
  99 </pre>
 100  is a type
 101 mapping each <tt><b>int</b></tt> value to a &quot;set&quot; of <tt><b>char</b></tt>
 102 values.
 103 <a href = "../example/basic_multimap_example.cpp"><tt>basic_multimap_example.cpp</tt></a> shows an example.
 104 This composition is recursive, however, and more complex relationships can be built.
 105 <a href = "../example/mapping_level_example.cpp"><tt>mapping_level_example.cpp</tt></a> shows an example.
 106         </li>
 107 </ol>
 108
 109 <p>
 110         The associative-container classes derive each from one of the three
 111 <a href = "basic_assoc_cntnr.html"><tt>basic_assoc_cntnr</tt></a> classes, depending
 112 on the data policy. These three base classes define different types and methods. For example, the &quot;map&quot; specialization of
 113 <a href = "basic_assoc_cntnr.html"><tt>basic_assoc_cntnr</tt></a>
 114 defines <tt><b>operator</b>[]</tt>, wherase the &quot;set&quot; specialization does not.
 115 This is described further in
 116 <a href = "ms_gen.html">Mapping-Semantic Genericity</a>.
 117 </p>
 118
 119 <p>
 120         <tt>pb_assoc</tt>'s design contains the concept of a <i>mapping level</i>. &quot;Map&quot; and &quot;set&quot; types have a single mapping level; A container
 121 mapping integers to &quot;maps&quot; mapping characters to floats has two mapping levels, since it can be viewed as a type mapping each integer to a &quot;map&quot;, or as a type mapping each pair of integer and character to a float. <tt>pb_assoc</tt> contains traits and rebind mechanisms for querying and altering the mapping levels.
 122 This is described further in
 123 <a href = "ms_gen.html">Mapping-Semantic Genericity</a>.
 124 </p>
 125
 126 <p>
 127         The leaf classes in Figure
 128 <a href = "#cd">Class hierarchy</a>
 129 are each parameterized by policies, easing configuring containers for different settings.
 130 <a href = "hash_based_containers.html">Hash-Based Containers</a> describes the design and policies of hash-based containers,
 131         <a href = "tree_based_containers.html">Tree-Based Containers</a> describes the design and policies of tree-based containers, and
 132         <a href = "lu_based_containers.html">List-Based Containers</a> describes the design and policies of list-based containers with update policies.
 133
 134 </p>
 135
 136
 137 </body>
 138
 139 </html>