230 lines
9.5 KiB
HTML
230 lines
9.5 KiB
HTML
<!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>
|