libstdc++-v3/docs/html/ext/pb_ds/lu_based_containers.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>List-Based Containers</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>List-Update Design</h1>
  17
  18     <h2><a name="overview" id="overview">Overview</a></h2>
  19
  20     <p>The list-based container has the following declaration:</p>
  21     <pre>
  22 <b>template</b>&lt;
  23     <b>typename</b> Key,
  24     <b>typename</b> Mapped,
  25     <b>typename</b> Eq_Fn = std::equal_to&lt;Key&gt;,
  26     <b>typename</b> Update_Policy = <a href=
  27 "move_to_front_lu_policy.html">move_to_front_lu_policy&lt;&gt;</a>,
  28     <b>typename</b> Allocator = std::allocator&lt;<b>char</b>&gt; &gt;
  29 <b>class</b> <a href="list_update.html">list_update</a>;
  30 </pre>
  31
  32     <p>The parameters have the following meaning:</p>
  33
  34     <ol>
  35       <li><tt>Key</tt> is the key type.</li>
  36
  37       <li><tt>Mapped</tt> is the mapped-policy, and is explained in
  38       <a href="tutorial.html#assoc_ms">Tutorial::Associative
  39       Containers::Associative Containers Others than Maps</a>.</li>
  40
  41       <li><tt>Eq_Fn</tt> is a key equivalence functor.</li>
  42
  43       <li><tt>Update_Policy</tt> is a policy updating positions in
  44       the list based on access patterns. It is described in the
  45       following subsection.</li>
  46
  47       <li><tt>Allocator</tt> is an allocator
  48       type.</li>
  49     </ol>
  50
  51     <p>A list-based associative container is a container that
  52     stores elements in a linked-list. It does not order the
  53     elements by any particular order related to the keys.
  54     List-based containers are primarily useful for creating
  55     "multimaps" (see <a href=
  56     "motivation.html#assoc_mapping_semantics">Motivation::Associative
  57     Containers::Avoiding Multiple Keys</a> and <a href=
  58     "tutorial.html#assoc_ms">Tutorial::Associative
  59     Containers::Associative Containers Others than Maps</a>). In
  60     fact, list-based containers are designed in <tt>pb_ds</tt>
  61     expressly for this purpose. This is explained further in
  62     <a href="#mmaps">Use for "Multimaps"</a>.</p>
  63
  64     <p>List-based containers might also be useful for some rare
  65     cases, where a key is encapsulated to the extent that only
  66     key-equivalence can be tested. Hash-based containers need to
  67     know how to transform a key into a size type, and tree-based
  68     containers need to know if some key is larger than another.
  69     List-based associative containers, conversely, only need to
  70     know if two keys are equivalent.</p>
  71
  72     <p>Since a list-based associative container does not order
  73     elements by keys, is it possible to order the list in some
  74     useful manner? Remarkably, many on-line competitive [<a href=
  75     "references.html#motwani95random">motwani95random</a>]
  76     algorithms exist for reordering lists to reflect access
  77     prediction [<a href=
  78     "references.html#andrew04mtf">andrew04mtf</a>].</p>
  79
  80     <h2><a name="list_updates" id="list_updates">List
  81     Updates</a></h2>
  82
  83     <h3><a name="general" id="general">General Terms</a></h3>
  84
  85     <p>Figure <a href="#simple_list">A simple list</a> shows a
  86     simple list of integer keys. If we search for the integer 6, we
  87     are paying an overhead: the link with key 6 is only the fifth
  88     link; if it were the first link, it could be accessed
  89     faster.</p>
  90
  91     <h6 class="c1"><a name="simple_list" id="simple_list"><img src=
  92     "simple_list.png" alt="no image" /></a></h6>
  93
  94     <h6 class="c1">A simple list.</h6>
  95
  96     <p>List-update algorithms reorder lists as elements are
  97     accessed. They try to determine, by the access history, which
  98     keys to move to the front of the list. Some of these algorithms
  99     require adding some metadata alongside each entry.</p>
 100
 101     <p>For example, Figure <a href="#lu">The counter algorithm</a>
 102     -A shows the counter algorithm. Each node contains both a key
 103     and a count metadata (shown in bold). When an element is
 104     accessed (<i>e.g.</i> 6) its count is incremented, as shown in
 105     Figure <a href="#lu">The counter algorithm</a> -B. If the count
 106     reaches some predetermined value, say 10, as shown in Figure
 107     <a href="#lu">The counter algorithm</a> -C, the count is set to
 108     0 and the node is moved to the front of the list, as in Figure
 109     <a href="#lu">The counter algorithm</a> -D.</p>
 110
 111     <h6 class="c1"><a name="lu" id="lu"><img src="lu.png" alt=
 112     "no image" /></a></h6>
 113
 114     <h6 class="c1">The counter algorithm.</h6>
 115
 116     <h3><a name="imp_pb_ds" id="imp_pb_ds">Implementation</a></h3>
 117
 118     <p><tt>pb_ds</tt> allows instantiating lists with policies
 119     implementing any algorithm moving nodes to the front of the
 120     list (policies implementing algorithms interchanging nodes are
 121     unsupported).</p>
 122
 123     <p>Associative containers based on lists are parametrized by a
 124     <tt>Update_Policy</tt> parameter. This parameter defines the
 125     type of metadata each node contains, how to create the
 126     metadata, and how to decide, using this metadata, whether to
 127     move a node to the front of the list. A list-based associative
 128     container object derives (publicly) from its update policy.
 129     Figure <a href="#update_policy_cd">A list and its update
 130     policy</a> shows the scheme, as well as some predefined
 131     policies (which are explained below).</p>
 132
 133     <h6 class="c1"><a name="update_policy_cd" id=
 134     "update_policy_cd"><img src="update_policy_cd.png" alt=
 135     "no image" /></a></h6>
 136
 137     <h6 class="c1">A list and its update policy.</h6>
 138
 139     <p>An instantiation of <tt>Update_Policy</tt> must define
 140     internally <tt>update_metadata</tt> as the metadata it
 141     requires. Internally, each node of the list contains, besides
 142     the usual key and data, an instance of <tt><b>typename</b>
 143     Update_Policy::update_metadata</tt>.</p>
 144
 145     <p>An instantiation of <tt>Update_Policy</tt> must define
 146     internally two operators:</p>
 147     <pre>
 148 update_metadata
 149 <b>operator</b>()();
 150
 151 <b>bool</b>
 152 <b>operator</b>()(update_metadata &amp;);
 153 </pre>
 154
 155     <p>The first is called by the container object, when creating a
 156     new node, to create the node's metadata. The second is called
 157     by the container object, when a node is accessed (<i>e.g.</i>,
 158     when a find operation's key is equivalent to the key of the
 159     node), to determine whether to move the node to the front of
 160     the list.</p>
 161
 162     <p>The library contains two predefined implementations of
 163     list-update policies [<a href=
 164     "references.html#andrew04mtf">andrew04mtf</a>]. The first is
 165     <a href=
 166     "counter_lu_policy.html"><tt>counter_lu_policy</tt></a>, which
 167     implements the counter algorithm described above. The second is
 168     <a href=
 169     "move_to_front_lu_policy.html"><tt>move_to_front_lu_policy</tt></a>,
 170     which unconditionally move an accessed element to the front of
 171     the list. The latter type is very useful in <tt>pb_ds</tt>,
 172     since there is no need to associate metadata with each element
 173     (this is explained further in <a href="#mmaps">Use for
 174     "Multimaps"</a>).</p>
 175
 176     <h2><a name="mmaps" id="mmaps">Use for "Multimaps"</a></h2>
 177
 178     <p>In <tt>pb_ds</tt>, there are no equivalents for the STL's
 179     multimaps and multisets; instead one uses an associative
 180     container mapping primary keys to secondary keys (see <a href=
 181     "motivation.html#assoc_mapping_semantics">Motivation::Associative
 182     Containers::Alternative to Multiple Equivalent Keys</a> and
 183     <a href="tutorial.html#assoc_ms">Tutorial::Associative
 184     Containers::Associative Containers Others than Maps</a>).</p>
 185
 186     <p>List-based containers are especially useful as associative
 187     containers for secondary keys. In fact, they are implemented
 188     here expressly for this purpose.</p>
 189
 190     <p>To begin with, these containers use very little per-entry
 191     structure memory overhead, since they can be implemented as
 192     singly-linked lists. (Arrays use even lower per-entry memory
 193     overhead, but they are less flexible in moving around entries,
 194     and have weaker invalidation guarantees).</p>
 195
 196     <p>More importantly, though, list-based containers use very
 197     little per-container memory overhead. The memory overhead of an
 198     empty list-based container is practically that of a pointer.
 199     This is important for when they are used as secondary
 200     associative-containers in situations where the average ratio of
 201     secondary keys to primary keys is low (or even 1).</p>
 202
 203     <p>In order to reduce the per-container memory overhead as much
 204     as possible, they are implemented as closely as possible to
 205     singly-linked lists.</p>
 206
 207     <ol>
 208       <li>List-based containers do not store internally the number
 209       of values that they hold. This means that their <tt>size</tt>
 210       method has linear complexity (just like <tt>std::list</tt>).
 211       Note that finding the number of equivalent-key values in an
 212       STL multimap also has linear complexity (because it must be
 213       done, <i>e.g.</i>, via <tt>std::distance</tt> of the
 214       multimap's <tt>equal_range</tt> method), but usually with
 215       higher constants.</li>
 216
 217       <li>Most associative-container objects each hold a policy
 218       object (<i>e.g.</i>, a hash-based container object holds a
 219       hash functor). List-based containers, conversely, only have
 220       class-wide policy objects.</li>
 221     </ol>
 222
 223     <p>See also <a href=
 224     "assoc_performance_tests.html#msc">Associative-Container
 225     Performance Tests::Observations::Mapping-Semantics
 226     Considerations</a>.</p>
 227   </div>
 228 </body>
 229 </html>