l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.1.0/docs/html/ext/pb_assoc/concepts.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
   2 <html>
   3 <head>
   4 <title>Concepts</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 <h1>Concepts</h1>
  10
  11 <p>
  12 Following are some concepts used throughout the documentation.
  13 </p>
  14
  15 <ol>
  16     <li><a href = "#concepts_null_policies">Null Policy Classes</a></li>
  17     <li><a href = "#concepts_find_and_range_iterators">Find and Range Iterators</a></li>
  18     <li><a href = "#concepts_mapping_levels">Mapping Levels</a></li>
  19 </ol>
  20
  21 <h2><a name = "concepts_null_policies">Null Policy Classes</a></h2>
  22
  23 <p>
  24     Associative containers are typically parameterized by various policies.
  25 For example, a hash-based associative
  26 container is parameterized by a hash-functor, transforming each key into an non-negative numerical type. Each such value is then further mapped into a position within the table.
  27 The mapping of a key into a position within the table is therefore a two-step process.
  28 </p>
  29
  30 <p>
  31 In some
  32 cases, instantiations are <i>redundant</i>. For example, when the keys are integers, it is possible to use a <i>redundant</i>
  33 hash policy, which transforms each key into its value.
  34 </p>
  35
  36 <p>
  37     In some other cases, these policies are <i>irrelevent</i>. For example,
  38 a hash-based associative container might transform keys into positions within
  39 a table by a different method than the two-step method described above. In such a case, the hash functor is simply irrelevent.
  40 </p>
  41
  42 <p>
  43         <tt>pb_assoc</tt> uses special pre-defined &quot;null policies&quot; classes
  44 for these cases. Some null policies in <tt>pb_assoc</tt>
  45 are:
  46 </p>
  47 <ol>
  48         <li <a href = "null_data_type.html"><tt>null_data_type</tt></a></li>
  49     <li><a href = "null_node_updator.html"><tt>null_node_updator</tt></a></li>
  50     <li><a href = "null_hash_fn.html"><tt>null_hash_fn</tt></a></li>
  51     <li><a href = "null_probe_fn.html"><tt>null_probe_fn</tt></a></li>
  52 </ol>
  53
  54 <p>
  55 A &quot;set&quot; in <tt>pb_assoc</tt> is an associative container with its <tt>Data_Parameter</tt> instantiated by
  56 <a href = "null_data_type.html"><tt>null_data_type</tt></a>.
  57 <a href = "tree_based_containers.html#node_invariants.html">Tree-Based Containers::Node Invariants</a>
  58 explains another case where a null policy is needed.
  59 </p>
  60
  61
  62
  63 <h2><a name = "concepts_find_and_range_iterators">Find and Range Methods and Iterators</a></h2>
  64
  65 <p>
  66     Associative containers allow access to their elements via iterators. <i>E.g.</i>,
  67 <tt>find</tt> returns an iterator to an element with a given key and
  68 <tt>begin</tt> returns an iterator to the first element in the container.
  69 </p>
  70
  71 <p>
  72 In general, there are two types of methods: <i>find types</i>, and <i>range types</i>.
  73     Find-type
  74 methods return iterators corresponding to elements which have been found in some sense, as
  75 the container searched for them in order to access them (<i>i.e.</i>, via the
  76 <tt>find</tt> method) or searched for their location in order to insert them
  77 (<i>i.e.</i>, via the <tt>insert</tt> method). Range-type methods return iterators
  78 which can be used to traverse the range of all stored elements, (<i>i.e.</i>, via the
  79 <tt>begin</tt> and <tt>end</tt> methods).
  80 </p>
  81
  82 <p>Correspondingly, in <tt>pb_assoc</tt> there are two types of iterators: <i>find type</i>
  83 iterators are returned by find methods, and range iterators are returned by range methods. For example,
  84 if <tt>T</tt> is any associative container with integer keys, and <tt>t</tt>
  85 is a container of type <tt>T</tt>,
  86 then the following snippet is valid:
  87 </p>
  88
  89 <pre>
  90 <b>typename</b> T::find_iterator it0 = t.find(3);
  91 <b>typename</b> T::const_find_iterator it0 = t.find(3);
  92
  93 <b>typename</b> T::iterator it0 = t.begin();
  94 <b>typename</b> T::const_iterator it0 = t.begin();
  95 </pre>
  96
  97
  98 <p>
  99     This is motivated and explained further in
 100 <a href = "ds_gen.html#find_range">Data-Structure Genericity::Find-Type and Range-Type Methods and Iterators</a>, which also explains the relationship between find-type and range-type iterators.
 101 </p>
 102
 103 <h2><a href = "#concepts_mapping_levels">Mapping Levels</a></h2>
 104
 105 <p>
 106         In <tt>pb_assoc</tt> &quot;multimaps&quot; are
 107 &quot;maps&quot; of &quot;sets&quot;. While this design allows efficient
 108 operations, it makes for cumbersome use at points. For example a
 109 &quot;multimap&quot; of integers to characters does not
 110 directly support <tt>inser(std::make_pair(2, 'b')</tt>, since 2 is mapped
 111 to a &quot;set&quot; of characters, and not to a character.
 112 </p>
 113
 114 <p>
 115         Consequently, <tt>pb_assoc</tt> contains a rebind-like mechanism so that
 116 containers can support such operations. To dispel ambiguity, container types are
 117 assigned mapping levels. &quot;Maps&quot; and &quot;sets&quot; have
 118 a mapping level 1, since they use a single association level. The &quot;multimap&quot;
 119 above has a mapping level 2, since it uses two association levels: one for integers, and one for characters. The rebind mechanism can be used to alter the association level. This is described in
 120 <a href = "ms_gen.html">Mapping Semantics</a>.
 121 </p>
 122
 123 </body>
 124 </html>