[thirdparty/gcc.git] / libstdc++-v3 / docs / html / ext / pb_assoc / list_updates.html

<!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 policies for list updates. It is organized as follows:
</p>

<ol>
    <li> The <a href = "#general">General Terms</a> Subsection describes general
        terms.
    </li>
    <li> The <a href = "#imp_pb_assoc">Implementation in <tt>pb_assoc</tt></a>
        Subsection describes the implementation of these concepts in <tt>pb_assoc</tt>.
    </li>
</ol>


<h2><a name = "general">General Terms</a></h2>

<p>
    Associative containers 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 the (rare) case where keys can only be checked for equivalence, these
types of containers cannot be used. In such a case, storing the entries in a list is a reasonable solution.
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>]. Some of these algorithms require storing
metadata with each key, while others do not. Some of these algorithms require only the ability to
move an element to the front of the list, while others require the ability to interchange an element and
its predecessor.
</p>

<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>


<h2><a name = "imp_pb_assoc">Implementation in <tt>pb_assoc</tt></a></h2>

<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>
Commit	Line	Data
fd1e1726 BK	1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
	2	<html>
	3	<head>
	4	<title>List Updates</title>
	5	<meta name="GENERATOR" content="Microsoft Visual Studio .NET 7.1">
	6	<meta name="vs_targetSchema" content="http://schemas.microsoft.com/intellisense/ie5">
	7	</head>
	8
	9	<body bgcolor = "white">
	10
	11	<h1>List-Update Containers</h1>
	12
	13	<p>
	14	This section describes policies for list updates. It is organized as follows:
	15	</p>
	16
	17	<ol>
	18	<li> The <a href = "#general">General Terms</a> Subsection describes general
	19	terms.
	20	</li>
	21	<li> The <a href = "#imp_pb_assoc">Implementation in <tt>pb_assoc</tt></a>
	22	Subsection describes the implementation of these concepts in <tt>pb_assoc</tt>.
	23	</li>
	24	</ol>
	25
	26
	27	<h2><a name = "general">General Terms</a></h2>
	28
	29	<p>
	30	Associative containers use some attributes of the keys of which they store: tree-based
	31	containers use the ability to compare keys; hash-based containers use the ability to map
	32	keys into numbers.
	33	</p>
	34
	35	<p>
	36	In the (rare) case where keys can only be checked for equivalence, these
	37	types of containers cannot be used. In such a case, storing the entries in a list is a reasonable solution.
	38	Clearly, the order of the elements within the list affects performance; ideally, frequently accessed elements
	39	should be at the front of the list.
	40	</p>
	41
	42	<p>
	43	Many remarkable (online competitive
	44	[<a href = "references.html#motwani95random">motwani95random</a>])
	45	algorithms exist for reordering lists to reflect access prediction
	46	[<a href = "references.html#andrew04mtf">andrew04mtf</a>]. Some of these algorithms require storing
	47	metadata with each key, while others do not. Some of these algorithms require only the ability to
	48	move an element to the front of the list, while others require the ability to interchange an element and
	49	its predecessor.
	50	</p>
	51
	52	<p>
	53	For example, Figure
	54	<a href = "#lu">-A
	55	The counter algorithm
	56	</a>
	57	shows the counter algorithm. Each node contains both a key and a count metadata (shown in bold).
	58	When an element is accessed (<i>e.g.</i> 6)
	59	its count is incremented, as shown in
	60	Figure
	61	<a href = "#lu">
	62	The counter algorithm
	63	</a>-B.
	64	If the count reaches some predetermined value, say 10, as shown in
65	Figure
66	<a href = "#lu">
67	The counter algorithm
68	</a>-C,
69	the count is set to 0
70	and the node is moved to the front of the list, as in
71	Figure
72	<a href = "#lu">
73	The counter algorithm
74	</a>-D.
75
76
77	</p>
78
79	<h6 align = "center">
80	<a name = "lu">
55e35fb7	81	<img src = "lu_ops.jpg" width = "65%">
fd1e1726 BK	82	</a>
	83	</h6>
	84	<h6 align = "center">
	85	The counter algorithm.
	86	</h6>
	87
	88
	89
	90	<h2><a name = "imp_pb_assoc">Implementation in <tt>pb_assoc</tt></a></h2>
	91
	92	<p>
	93	The <tt>pb_assoc</tt> library allows instantiating lists with policies
	94	implementing any algorithm moving nodes to the front of the list (policies implementing
	95	algorithms interchanging nodes are currently unsupported).
	96	</p>
	97
	98	<p>
	99	Associative containers based on lists are parameterized by a <tt>Update_Policy</tt> parameter.
	100	This parameter defines the type of metadata each node contains, how to create the metadata, and how to
	101	decide, using this metadata, whether to move a node to the front of the list.
	102	A list-based associative container object derives (publicly) from its update policy.
	103	</p>
	104
	105	<p>
	106	An instantiation of <tt>Update_Policy</tt> must define internally <tt>update_metadata</tt> as the metadata
	107	it requires. Internally, each node of the list contains, besides the usual key and data, an instance
	108	of <tt><b>typename</b> Update_Policy::update_metadata</tt>.
	109	</p>
	110
	111	<p>
	112	An instantiation of <tt>Update_Policy</tt> must define internally two operators:
	113	</p>
	114	<pre>
	115	update_metadata
	116	<b>operator</b>()
	117	();
	118
	119	<b>bool</b>
	120	<b>operator</b>()
	121	(update_metadata &);
	122	</pre>
	123
	124	<p>
	125	The first is called by the container object, when creating a new node, to create the node's metadata. The
	126	second is called by the container object, when a node is accessed (<i>e.g.</i>, when a find operation's key
	127	is equivalent to the key of the node), to determine whether to move the node to the front of the list.
	128	</p>
	129
	130	<p>
	131	Additionally, the library contains implementations of the move-to-front and counter policies. These
	132	are described in
	133	<a href="interface.html#policy_classes">Policy Classes</a>.
	134	</p>
	135
	136	</body>
	137
	138	</html>