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>< 23 <b>typename</b> Key, 24 <b>typename</b> Mapped, 25 <b>typename</b> Eq_Fn = std::equal_to<Key>, 26 <b>typename</b> Update_Policy = <a href= 27"move_to_front_lu_policy.html">move_to_front_lu_policy<></a>, 28 <b>typename</b> Allocator = std::allocator<<b>char</b>> > 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> 148update_metadata 149<b>operator</b>()(); 150 151<b>bool</b> 152<b>operator</b>()(update_metadata &); 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> 230
