libstdc++-v3/doc/html/ext/pb_ds/concepts.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
   2     "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
   3
   4 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
   5 <head>
   6   <meta name="generator" content=
   7   "HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" />
   8
   9   <title>Concepts</title>
  10   <meta http-equiv="Content-Type" content=
  11   "text/html; charset=us-ascii" />
  12   </head>
  13
  14 <body>
  15   <div id="page">
  16     <h1>Concepts</h1>
  17
  18     <h2><a name="concepts_find_and_range_iterators" id=
  19     "concepts_find_and_range_iterators">Point and Range Methods and
  20     Iterators</a></h2>
  21
  22     <p>A point-type iterator is an iterator that refers to a
  23     specific element, <i>e.g.</i> as returned through an
  24     associative-container's <tt>find</tt> method; a range-type
  25     iterator is an iterator that is used to go over a sequence of
  26     elements, <i>e.g.</i>, as returned by a container's
  27     <tt>find</tt> method. A point-type method is a method that
  28     returns a point-type iterator; a range-type method is a method
  29     that returns a range-type iterator.</p>
  30
  31     <p>For most containers, these types are synonymous; for
  32     self-organizing containers, such as hash-based containers or
  33     priority queues, these are inherently different (in any
  34     implementation, including that of the STL), but in
  35     <tt>pb_ds</tt> this is made explicit - they are distinct
  36     types.</p>
  37
  38
  39     <h2><a name="invalidation_guarantees" id=
  40     "invalidation_guarantees">Invalidation Guarantees</a></h2>
  41
  42     <p>If one manipulates a container object, then iterators
  43     previously obtained from it can be invalidated. In some cases a
  44     previously-obtained iterator cannot be de-referenced; in other
  45     cases, the iterator's next or previous element might have
  46     changed unpredictably. This corresponds exactly to the question
  47     whether a point-type or range-type iterator (see previous
  48     concept) is valid or not. In <tt>pb_ds</tt> one can query a
  49     container (in compile time) what are its invalidation
  50     guarantees.</p>
  51
  52      <h2><a name="prm_sec" id="prm_sec">Primary and Secondary Keys
  53     and Associative Containers</a></h2>
  54
  55     <p>In <tt>pb_ds</tt> there are no associative containers which
  56     allow multiple values with equivalent keys (such as the STL's
  57     <tt>std::multimap</tt>, for example). Instead, one maps the
  58     unique part of a key - the primary key, into an
  59     associative-container of the (originally) non-unique parts of
  60     the key - the secondary key. A primary associative-container is
  61     an associative container of primary keys; a secondary
  62     associative-container is an associative container of secondary
  63     keys.</p>
  64
  65
  66     <h2><a name="concepts_null_policies" id=
  67     "concepts_null_policies">Null Policy Classes</a></h2>
  68
  69     <p>Associative containers are typically parametrized by
  70     various policies. For example, a hash-based associative
  71     container is parametrized by a hash-functor, transforming each
  72     key into an non-negative numerical type. Each such value is
  73     then further mapped into a position within the table. The
  74     mapping of a key into a position within the table is therefore
  75     a two-step process.</p>
  76
  77     <p>In some cases, instantiations are <i>redundant</i>. For
  78     example, when the keys are integers, it is possible to use a
  79     <i>redundant</i> hash policy, which transforms each key into
  80     its value.</p>
  81
  82     <p>In some other cases, these policies are <i>irrelevant</i>.
  83     For example, a hash-based associative container might transform
  84     keys into positions within a table by a different method than
  85     the two-step method described above. In such a case, the hash
  86     functor is simply irrelevant.</p>
  87
  88     <p><tt>pb_ds</tt> uses special pre-defined "null policies"
  89     classes for these cases. Some null policies in <tt>pb_ds</tt>
  90     are:</p>
  91
  92     <ol>
  93       <li><a href=
  94       "null_mapped_type.html"><tt>null_mapped_type</tt></a></li>
  95
  96       <li><a href=
  97       "null_tree_node_update.html"><tt>null_tree_node_update</tt></a></li>
  98
  99       <li><a href=
 100       "null_trie_node_update.html"><tt>null_trie_node_update</tt></a></li>
 101
 102       <li><a href=
 103       "null_hash_fn.html"><tt>null_hash_fn</tt></a></li>
 104
 105       <li><a href=
 106       "null_probe_fn.html"><tt>null_probe_fn</tt></a></li>
 107     </ol>
 108
 109     <p>A "set" in <tt>pb_ds</tt>, for example, is an associative
 110     container with its <tt>Data_Parameter</tt> instantiated by
 111     <a href="null_mapped_type.html"><tt>null_mapped_type</tt></a>.
 112     <a href=
 113     "tree_based_containers.html#invariants">Design::Tree-Based
 114     Containers::Node Invariants</a> explains another case where a
 115     null policy is needed.</p>
 116   </div>
 117 </body>
 118 </html>