l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.1.0/docs/html/ext/pb_assoc/list_updates.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 <p>
  14     This section describes policies for list updates. It is organized as follows:
  15 </p>
  16
  17 <ol>
  18     <li> The <a href = "#general">General Terms</a> Subsection describes general
  19         terms.
  20     </li>
  21     <li> The <a href = "#imp_pb_assoc">Implementation in <tt>pb_assoc</tt></a>
  22         Subsection describes the implementation of these concepts in <tt>pb_assoc</tt>.
  23     </li>
  24 </ol>
  25
  26
  27 <h2><a name = "general">General Terms</a></h2>
  28
  29 <p>
  30     Associative containers use some attributes of the keys of which they store: tree-based
  31 containers use the ability to compare keys; hash-based containers use the ability to map
  32 keys into numbers.
  33 </p>
  34
  35 <p>
  36         In the (rare) case where keys can only be checked for equivalence, these
  37 types of containers cannot be used. In such a case, storing the entries in a list is a reasonable solution.
  38 Clearly, the order of the elements within the list affects performance; ideally, frequently accessed elements
  39 should be at the front of the list.
  40 </p>
  41
  42 <p>
  43     Many remarkable (online competitive
  44 [<a href = "references.html#motwani95random">motwani95random</a>])
  45 algorithms exist for reordering lists to reflect access prediction
  46 [<a href = "references.html#andrew04mtf">andrew04mtf</a>]. Some of these algorithms require storing
  47 metadata with each key, while others do not. Some of these algorithms require only the ability to
  48 move an element to the front of the list, while others require the ability to interchange an element and
  49 its predecessor.
  50 </p>
  51
  52 <p>
  53     For example, Figure
  54 <a href = "#lu">-A
  55 The counter algorithm
  56 </a>
  57 shows the counter algorithm. Each node contains both a key and a count metadata (shown in bold).
  58 When an element is accessed (<i>e.g.</i> 6)
  59 its count is incremented, as shown in
  60 Figure
  61 <a href = "#lu">
  62 The counter algorithm
  63 </a>-B.
  64 If the count reaches some predetermined value, say 10, as shown in
  65 Figure
  66 <a href = "#lu">
  67 The counter algorithm
  68 </a>-C,
  69 the count is set to 0
  70 and the node is moved to the front of the list,  as in
  71 Figure
  72 <a href = "#lu">
  73 The counter algorithm
  74 </a>-D.
  75
  76
  77 </p>
  78
  79 <h6 align = "center">
  80 <a name = "lu">
  81 <img src = "lu_ops.jpg" width = "65%">
  82 </a>
  83 </h6>
  84 <h6 align = "center">
  85 The counter algorithm.
  86 </h6>
  87
  88
  89
  90 <h2><a name = "imp_pb_assoc">Implementation in <tt>pb_assoc</tt></a></h2>
  91
  92 <p>
  93     The <tt>pb_assoc</tt> library allows instantiating lists with policies
  94 implementing any algorithm moving nodes to the front of the list (policies implementing
  95 algorithms interchanging nodes are currently unsupported).
  96 </p>
  97
  98 <p>
  99     Associative containers based on lists are parameterized by a <tt>Update_Policy</tt> parameter.
 100 This parameter defines the type of metadata each node contains, how to create the metadata, and how to
 101 decide, using this metadata, whether to move a node to the front of the list.
 102     A list-based associative container object derives (publicly) from its update policy.
 103 </p>
 104
 105 <p>
 106     An instantiation of <tt>Update_Policy</tt> must define internally <tt>update_metadata</tt> as the metadata
 107 it requires. Internally, each node of the list contains, besides the usual key and data, an instance
 108 of <tt><b>typename</b> Update_Policy::update_metadata</tt>.
 109 </p>
 110
 111 <p>
 112     An instantiation of <tt>Update_Policy</tt> must define internally two operators:
 113 </p>
 114 <pre>
 115 update_metadata
 116   <b>operator</b>()
 117   ();
 118
 119 <b>bool</b>
 120   <b>operator</b>()
 121   (update_metadata &);
 122 </pre>
 123
 124 <p>
 125     The first is called by the container object, when creating a new node, to create the node's metadata. The
 126 second is called by the container object, when a node is accessed (<i>e.g.</i>, when a find operation's key
 127 is equivalent to the key of the node), to determine whether to move the node to the front of the list.
 128 </p>
 129
 130 <p>
 131     Additionally, the library contains implementations of the move-to-front and counter policies. These
 132 are described in
 133 <a href="interface.html#policy_classes">Policy Classes</a>.
 134 </p>
 135
 136 </body>
 137
 138 </html>