URL
https://opencores.org/ocsvn/scarts/scarts/trunk
Subversion Repositories scarts
[/] [scarts/] [trunk/] [toolchain/] [scarts-gcc/] [gcc-4.1.1/] [libstdc++-v3/] [docs/] [html/] [ext/] [pb_assoc/] [lu_based_containers.html] - Rev 20
Compare with Previous | Blame | View Log
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<title>List Updates</title>
<meta name="GENERATOR" content="Microsoft Visual Studio .NET 7.1">
<meta name="vs_targetSchema" content="http://schemas.microsoft.com/intellisense/ie5">
</head>
<body bgcolor = "white">
<h1>List-Update Containers</h1>
<p>
This section describes list-based containers. It is organized as follows.
</p>
<ol>
<li> <a href = "#overview">Overview</a> is an overview.</li>
<li> <a href = "#list_updates">List Updates</a> describes updating lists
as elements are accessed.</li>
</ol>
<h2><a name = "overview">Overview</a></h2>
<p>
Associative containers typically use some attributes of the keys of which they store: tree-based
containers use the ability to compare keys; hash-based containers use the ability to map
keys into numbers.
</p>
<p>
In some cases it is better to avoid this:
</p>
<ol>
<li>
Hash-based and tree-based containers typically require additional memory
for time efficiency.
</li>
<li>
Hash-based and tree-based containers require extra information
about keys: hash-based containers need hash functors, tree-based containers need
comparison functors. In some (rare) cases, a key might be encapsulated to the extent that it is not possible to supply these functors.
</li>
</ol>
<p>
In such cases, storing the entries in a unique-key list is a reasonable solution.
This uses the minimal amount of memory, and requires only an equivalence functor.
Clearly, the order of the elements within the list affects performance; ideally, frequently accessed elements
should be at the front of the list.
</p>
<p>
Many remarkable (online 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>
<p>
Figure
<a href = "#lu_cd">List-update containers</a>
shows the container-hierarchy; the list-based container is circled.
</p>
<h6 align = "center">
<a name = "lu_cd">
<img src = "lu_cd.jpg" width = "70%" alt = "no image">
</h6>
<h6 align = "center">
</a>
List-update containers.
</h6>
<p>
The list-based container has the following declaration:
</p>
<pre>
<b>template</b><
<b>typename</b> Key,
<b>typename</b> Data,
<b>class</b> Eq_Fn = std::equal_to<Key>,
<b>class</b> Update_Policy =
<a href = "move_to_front_lu_policy.html">move_to_front_lu_policy<></a>,
<b>class</b> Allocator =
std::allocator<<b>char</b>> >
<b>class</b> <a href = "lu_assoc_cntnr.html">lu_assoc_cntnr</a>;
</pre>
<p>
The parameters have the following meaning:
</p>
<ol>
<li> <tt>Key</tt> is the key type.
</li>
<li> <tt>Data</tt> is the data-policy, and is explained in
<a href = "ms_gen.html#ds_policy">Mapping-Semantics Genericity::Data Types as a Policy</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 (surprisingly) an allocator type.
</li>
</ol>
<h2><a name = "list_updates">List Updates</a></h2>
<p>
This subsection describes list-update policies. It is organized as follows.
</p>
<ol>
<li> <a href = "#general">General Terms</a> describes general
terms.
</li>
<li> <a href = "#imp_pb_assoc">Implementation in <tt>pb_assoc</tt></a>
describes the implementation of these concepts in <tt>pb_assoc</tt>.
</li>
</ol>
<h3><a name = "general">General Terms</a></h3>
<p>
For example, Figure
<a href = "#lu">-A
The counter algorithm
</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 align = "center">
<a name = "lu">
<img src = "lu_ops.jpg" width = "65%">
</a>
</h6>
<h6 align = "center">
The counter algorithm.
</h6>
<h3><a name = "imp_pb_assoc">Implementation in <tt>pb_assoc</tt></a></h3>
<p>
The <tt>pb_assoc</tt> library allows instantiating lists with policies
implementing any algorithm moving nodes to the front of the list (policies implementing
algorithms interchanging nodes are currently unsupported).
</p>
<p>
Associative containers based on lists are parameterized 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.
</p>
<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>
Additionally, the library contains implementations of the move-to-front and counter policies. These
are described in
<a href="interface.html#policy_classes">Policy Classes</a>.
</p>
</body>
</html>