<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta name="generator" content=
"HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" />
<title>List-Based Containers</title>
<meta http-equiv="Content-Type" content=
"text/html; charset=us-ascii" />
</head>
<body>
<div id="page">
<h1>List-Update Design</h1>
<h2><a name="overview" id="overview">Overview</a></h2>
<p>The list-based container has the following declaration:</p>
<pre>
<b>template</b><
<b>typename</b> Key,
<b>typename</b> Mapped,
<b>typename</b> Eq_Fn = std::equal_to<Key>,
<b>typename</b> Update_Policy = <a href=
"move_to_front_lu_policy.html">move_to_front_lu_policy<></a>,
<b>typename</b> Allocator = std::allocator<<b>char</b>> >
<b>class</b> <a href="list_update.html">list_update</a>;
</pre>
<p>The parameters have the following meaning:</p>
<ol>
<li><tt>Key</tt> is the key type.</li>
<li><tt>Mapped</tt> is the mapped-policy, and is explained in
<a href="tutorial.html#assoc_ms">Tutorial::Associative
Containers::Associative Containers Others than Maps</a>.</li>
<li><tt>Eq_Fn</tt> is a key equivalence functor.</li>
<li><tt>Update_Policy</tt> is a policy updating positions in
the list based on access patterns. It is described in the
following subsection.</li>
<li><tt>Allocator</tt> is an allocator
type.</li>
</ol>
<p>A list-based associative container is a container that
stores elements in a linked-list. It does not order the
elements by any particular order related to the keys.
List-based containers are primarily useful for creating
"multimaps" (see <a href=
"motivation.html#assoc_mapping_semantics">Motivation::Associative
Containers::Avoiding Multiple Keys</a> and <a href=
"tutorial.html#assoc_ms">Tutorial::Associative
Containers::Associative Containers Others than Maps</a>). In
fact, list-based containers are designed in <tt>pb_ds</tt>
expressly for this purpose. This is explained further in
<a href="#mmaps">Use for "Multimaps"</a>.</p>
<p>List-based containers might also be useful for some rare
cases, where a key is encapsulated to the extent that only
key-equivalence can be tested. Hash-based containers need to
know how to transform a key into a size type, and tree-based
containers need to know if some key is larger than another.
List-based associative containers, conversely, only need to
know if two keys are equivalent.</p>
<p>Since a list-based associative container does not order
elements by keys, is it possible to order the list in some
useful manner? Remarkably, many on-line competitive [<a href=
"references.html#motwani95random">motwani95random</a>]
algorithms exist for reordering lists to reflect access
prediction [<a href=
"references.html#andrew04mtf">andrew04mtf</a>].</p>
<h2><a name="list_updates" id="list_updates">List
Updates</a></h2>
<h3><a name="general" id="general">General Terms</a></h3>
<p>Figure <a href="#simple_list">A simple list</a> shows a
simple list of integer keys. If we search for the integer 6, we
are paying an overhead: the link with key 6 is only the fifth
link; if it were the first link, it could be accessed
faster.</p>
<h6 class="c1"><a name="simple_list" id="simple_list"><img src=
"simple_list.png" alt="no image" /></a></h6>
<h6 class="c1">A simple list.</h6>
<p>List-update algorithms reorder lists as elements are
accessed. They try to determine, by the access history, which
keys to move to the front of the list. Some of these algorithms
require adding some metadata alongside each entry.</p>
<p>For example, Figure <a href="#lu">The counter algorithm</a>
-A shows the counter algorithm. Each node contains both a key
and a count metadata (shown in bold). When an element is
accessed (<i>e.g.</i> 6) its count is incremented, as shown in
Figure <a href="#lu">The counter algorithm</a> -B. If the count
reaches some predetermined value, say 10, as shown in Figure
<a href="#lu">The counter algorithm</a> -C, the count is set to
0 and the node is moved to the front of the list, as in Figure
<a href="#lu">The counter algorithm</a> -D.</p>
<h6 class="c1"><a name="lu" id="lu"><img src="lu.png" alt=
"no image" /></a></h6>
<h6 class="c1">The counter algorithm.</h6>
<h3><a name="imp_pb_ds" id="imp_pb_ds">Implementation</a></h3>
<p><tt>pb_ds</tt> allows instantiating lists with policies
implementing any algorithm moving nodes to the front of the
list (policies implementing algorithms interchanging nodes are
unsupported).</p>
<p>Associative containers based on lists are parametrized by a
<tt>Update_Policy</tt> parameter. This parameter defines the
type of metadata each node contains, how to create the
metadata, and how to decide, using this metadata, whether to
move a node to the front of the list. A list-based associative
container object derives (publicly) from its update policy.
Figure <a href="#update_policy_cd">A list and its update
policy</a> shows the scheme, as well as some predefined
policies (which are explained below).</p>
<h6 class="c1"><a name="update_policy_cd" id=
"update_policy_cd"><img src="update_policy_cd.png" alt=
"no image" /></a></h6>
<h6 class="c1">A list and its update policy.</h6>
<p>An instantiation of <tt>Update_Policy</tt> must define
internally <tt>update_metadata</tt> as the metadata it
requires. Internally, each node of the list contains, besides
the usual key and data, an instance of <tt><b>typename</b>
Update_Policy::update_metadata</tt>.</p>
<p>An instantiation of <tt>Update_Policy</tt> must define
internally two operators:</p>
<pre>
update_metadata
<b>operator</b>()();
<b>bool</b>
<b>operator</b>()(update_metadata &);
</pre>
<p>The first is called by the container object, when creating a
new node, to create the node's metadata. The second is called
by the container object, when a node is accessed (<i>e.g.</i>,
when a find operation's key is equivalent to the key of the
node), to determine whether to move the node to the front of
the list.</p>
<p>The library contains two predefined implementations of
list-update policies [<a href=
"references.html#andrew04mtf">andrew04mtf</a>]. The first is
<a href=
"counter_lu_policy.html"><tt>counter_lu_policy</tt></a>, which
implements the counter algorithm described above. The second is
<a href=
"move_to_front_lu_policy.html"><tt>move_to_front_lu_policy</tt></a>,
which unconditionally move an accessed element to the front of
the list. The latter type is very useful in <tt>pb_ds</tt>,
since there is no need to associate metadata with each element
(this is explained further in <a href="#mmaps">Use for
"Multimaps"</a>).</p>
<h2><a name="mmaps" id="mmaps">Use for "Multimaps"</a></h2>
<p>In <tt>pb_ds</tt>, there are no equivalents for the STL's
multimaps and multisets; instead one uses an associative
container mapping primary keys to secondary keys (see <a href=
"motivation.html#assoc_mapping_semantics">Motivation::Associative
Containers::Alternative to Multiple Equivalent Keys</a> and
<a href="tutorial.html#assoc_ms">Tutorial::Associative
Containers::Associative Containers Others than Maps</a>).</p>
<p>List-based containers are especially useful as associative
containers for secondary keys. In fact, they are implemented
here expressly for this purpose.</p>
<p>To begin with, these containers use very little per-entry
structure memory overhead, since they can be implemented as
singly-linked lists. (Arrays use even lower per-entry memory
overhead, but they are less flexible in moving around entries,
and have weaker invalidation guarantees).</p>
<p>More importantly, though, list-based containers use very
little per-container memory overhead. The memory overhead of an
empty list-based container is practically that of a pointer.
This is important for when they are used as secondary
associative-containers in situations where the average ratio of
secondary keys to primary keys is low (or even 1).</p>
<p>In order to reduce the per-container memory overhead as much
as possible, they are implemented as closely as possible to
singly-linked lists.</p>
<ol>
<li>List-based containers do not store internally the number
of values that they hold. This means that their <tt>size</tt>
method has linear complexity (just like <tt>std::list</tt>).
Note that finding the number of equivalent-key values in an
STL multimap also has linear complexity (because it must be
done, <i>e.g.</i>, via <tt>std::distance</tt> of the
multimap's <tt>equal_range</tt> method), but usually with
higher constants.</li>
<li>Most associative-container objects each hold a policy
object (<i>e.g.</i>, a hash-based container object holds a
hash functor). List-based containers, conversely, only have
class-wide policy objects.</li>
</ol>
<p>See also <a href=
"assoc_performance_tests.html#msc">Associative-Container
Performance Tests::Observations::Mapping-Semantics
Considerations</a>.</p>
</div>
</body>
</html>
