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

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
   2 <html>
   3     <head>
   4         <title>List Updates</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
   9 <body bgcolor = "white">
  10
  11 <h1>List-Update Containers</h1>
  12
  13
  14 <p>
  15         This section describes list-based containers. It is organized as follows.
  16 </p>
  17
  18 <ol>
  19         <li> <a href = "#overview">Overview</a> is an overview.</li>
  20         <li> <a href = "#list_updates">List Updates</a> describes updating lists
  21 as elements are accessed.</li>
  22 </ol>
  23
  24
  25 <h2><a name = "overview">Overview</a></h2>
  26
  27 <p>
  28     Associative containers typically use some attributes of the keys of which they store: tree-based
  29 containers use the ability to compare keys; hash-based containers use the ability to map
  30 keys into numbers.
  31 </p>
  32
  33 <p>
  34         In some cases it is better to avoid this:
  35 </p>
  36
  37 <ol>
  38         <li>
  39                 Hash-based and tree-based containers typically require additional memory
  40         for time efficiency.
  41         </li>
  42         <li>
  43                 Hash-based and tree-based containers require extra information
  44                 about keys: hash-based containers need hash functors, tree-based containers need
  45                 comparison functors. In some (rare) cases, a key might be encapsulated to the extent that it is not possible to supply these functors.
  46         </li>
  47 </ol>
  48
  49 <p>
  50         In such cases, storing the entries in a unique-key list is a reasonable solution.
  51 This uses the minimal amount of memory, and requires only an equivalence functor.
  52 Clearly, the order of the elements within the list affects performance; ideally, frequently accessed elements
  53 should be at the front of the list.
  54 </p>
  55
  56 <p>
  57     Many remarkable (online competitive
  58 [<a href = "references.html#motwani95random">motwani95random</a>])
  59 algorithms exist for reordering lists to reflect access prediction
  60 [<a href = "references.html#andrew04mtf">andrew04mtf</a>].
  61 </p>
  62
  63 <p>
  64         Figure
  65 <a href = "#lu_cd">List-update containers</a>
  66         shows the container-hierarchy; the list-based container is circled.
  67 </p>
  68
  69 <h6 align = "center">
  70 <a name = "lu_cd">
  71 <img src = "lu_cd.jpg" width = "70%" alt = "no image">
  72 </h6>
  73 <h6 align = "center">
  74 </a>
  75 List-update containers.
  76 </h6>
  77
  78
  79 <p>
  80         The list-based container has the following declaration:
  81 </p>
  82
  83 <pre>
  84 <b>template</b>&lt;
  85         <b>typename</b> Key,
  86         <b>typename</b> Data,
  87         <b>class</b> Eq_Fn = std::equal_to&lt;Key&gt;,
  88         <b>class</b> Update_Policy =
  89                 <a href = "move_to_front_lu_policy.html">move_to_front_lu_policy&lt;&gt;</a>,
  90         <b>class</b> Allocator =
  91                 std::allocator&lt;<b>char</b>&gt; &gt;
  92 <b>class</b> <a href = "lu_assoc_cntnr.html">lu_assoc_cntnr</a>;
  93 </pre>
  94
  95
  96 <p>
  97         The parameters have the following meaning:
  98 </p>
  99 <ol>
 100         <li> <tt>Key</tt> is the key type.
 101         </li>
 102         <li> <tt>Data</tt> is the data-policy, and is explained in
 103 <a href = "ms_gen.html#ds_policy">Mapping-Semantics Genericity::Data Types as a Policy</a>.
 104         </li>
 105         <li> <tt>Eq_Fn</tt> is a key equivalence functor.</li>
 106         <li> <tt>Update_Policy</tt> is a policy updating
 107         positions in the list based on access patterns. It is described in
 108         the following subsection.
 109         </li>
 110         <li> <tt>Allocator</tt> is (surprisingly) an allocator type.
 111         </li>
 112 </ol>
 113
 114
 115
 116
 117
 118 <h2><a name = "list_updates">List Updates</a></h2>
 119
 120 <p>
 121     This subsection describes list-update policies. It is organized as follows.
 122 </p>
 123
 124 <ol>
 125     <li> <a href = "#general">General Terms</a> describes general
 126         terms.
 127     </li>
 128     <li> <a href = "#imp_pb_assoc">Implementation in <tt>pb_assoc</tt></a>
 129          describes the implementation of these concepts in <tt>pb_assoc</tt>.
 130     </li>
 131 </ol>
 132
 133
 134
 135
 136 <h3><a name = "general">General Terms</a></h3>
 137
 138
 139 <p>
 140     For example, Figure
 141 <a href = "#lu">-A
 142 The counter algorithm
 143 </a>
 144 shows the counter algorithm. Each node contains both a key and a count metadata (shown in bold).
 145 When an element is accessed (<i>e.g.</i> 6)
 146 its count is incremented, as shown in
 147 Figure
 148 <a href = "#lu">
 149 The counter algorithm
 150 </a>-B.
 151 If the count reaches some predetermined value, say 10, as shown in
 152 Figure
 153 <a href = "#lu">
 154 The counter algorithm
 155 </a>-C,
 156 the count is set to 0
 157 and the node is moved to the front of the list,  as in
 158 Figure
 159 <a href = "#lu">
 160 The counter algorithm
 161 </a>-D.
 162
 163
 164 </p>
 165
 166 <h6 align = "center">
 167 <a name = "lu">
 168 <img src = "lu_ops.jpg" width = "65%">
 169 </a>
 170 </h6>
 171 <h6 align = "center">
 172 The counter algorithm.
 173 </h6>
 174
 175
 176
 177 <h3><a name = "imp_pb_assoc">Implementation in <tt>pb_assoc</tt></a></h3>
 178
 179 <p>
 180     The <tt>pb_assoc</tt> library allows instantiating lists with policies
 181 implementing any algorithm moving nodes to the front of the list (policies implementing
 182 algorithms interchanging nodes are currently unsupported).
 183 </p>
 184
 185 <p>
 186     Associative containers based on lists are parameterized by a <tt>Update_Policy</tt> parameter.
 187 This parameter defines the type of metadata each node contains, how to create the metadata, and how to
 188 decide, using this metadata, whether to move a node to the front of the list.
 189     A list-based associative container object derives (publicly) from its update policy.
 190 </p>
 191
 192 <p>
 193     An instantiation of <tt>Update_Policy</tt> must define internally <tt>update_metadata</tt> as the metadata
 194 it requires. Internally, each node of the list contains, besides the usual key and data, an instance
 195 of <tt><b>typename</b> Update_Policy::update_metadata</tt>.
 196 </p>
 197
 198 <p>
 199     An instantiation of <tt>Update_Policy</tt> must define internally two operators:
 200 </p>
 201 <pre>
 202 update_metadata
 203   <b>operator</b>()
 204   ();
 205
 206 <b>bool</b>
 207   <b>operator</b>()
 208   (update_metadata &);
 209 </pre>
 210
 211 <p>
 212     The first is called by the container object, when creating a new node, to create the node's metadata. The
 213 second is called by the container object, when a node is accessed (<i>e.g.</i>, when a find operation's key
 214 is equivalent to the key of the node), to determine whether to move the node to the front of the list.
 215 </p>
 216
 217 <p>
 218     Additionally, the library contains implementations of the move-to-front and counter policies. These
 219 are described in
 220 <a href="interface.html#policy_classes">Policy Classes</a>.
 221 </p>
 222
 223 </body>
 224
 225 </html>