OSDN Git Service

2006-02-22 Paolo Carlini <pcarlini@suse.de>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / docs / html / ext / pb_assoc / lu_based_containers.html
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
14 <p>
15         This section describes list-based containers. It is organized as follows.
16 </p>
17
18 <ol>
19         <li> <a href = "#overview">Overview</a> is an overview.</li>
20         <li> <a href = "#list_updates">List Updates</a> describes updating lists
21 as elements are accessed.</li>
22 </ol>
23
24
25 <h2><a name = "overview">Overview</a></h2>
26
27 <p>
28     Associative containers typically use some attributes of the keys of which they store: tree-based
29 containers use the ability to compare keys; hash-based containers use the ability to map
30 keys into numbers.
31 </p>
32
33 <p>
34         In some cases it is better to avoid this:
35 </p>
36
37 <ol>
38         <li>
39                 Hash-based and tree-based containers typically require additional memory
40         for time efficiency.
41         </li>
42         <li>
43                 Hash-based and tree-based containers require extra information
44                 about keys: hash-based containers need hash functors, tree-based containers need
45                 comparison functors. In some (rare) cases, a key might be encapsulated to the extent that it is not possible to supply these functors.
46         </li>
47 </ol>
48
49 <p>
50         In such cases, storing the entries in a unique-key list is a reasonable solution.
51 This uses the minimal amount of memory, and requires only an equivalence functor.
52 Clearly, the order of the elements within the list affects performance; ideally, frequently accessed elements
53 should be at the front of the list.
54 </p>
55
56 <p>
57     Many remarkable (online competitive
58 [<a href = "references.html#motwani95random">motwani95random</a>])
59 algorithms exist for reordering lists to reflect access prediction
60 [<a href = "references.html#andrew04mtf">andrew04mtf</a>].
61 </p>
62
63 <p>
64         Figure
65 <a href = "#lu_cd">List-update containers</a>
66         shows the container-hierarchy; the list-based container is circled.
67 </p>
68
69 <h6 align = "center">
70 <a name = "lu_cd">
71 <img src = "lu_cd.jpg" width = "70%" alt = "no image">
72 </h6>
73 <h6 align = "center">
74 </a>
75 List-update containers.
76 </h6>
77
78
79 <p>
80         The list-based container has the following declaration:
81 </p>
82
83 <pre>
84 <b>template</b>&lt;
85         <b>typename</b> Key,
86         <b>typename</b> Data,
87         <b>class</b> Eq_Fn = std::equal_to&lt;Key&gt;,
88         <b>class</b> Update_Policy =
89                 <a href = "move_to_front_lu_policy.html">move_to_front_lu_policy&lt;&gt;</a>,
90         <b>class</b> Allocator =
91                 std::allocator&lt;<b>char</b>&gt; &gt;
92 <b>class</b> <a href = "lu_assoc_cntnr.html">lu_assoc_cntnr</a>;
93 </pre>
94
95
96 <p>
97         The parameters have the following meaning:
98 </p>
99 <ol>
100         <li> <tt>Key</tt> is the key type.
101         </li>
102         <li> <tt>Data</tt> is the data-policy, and is explained in
103 <a href = "ms_gen.html#ds_policy">Mapping-Semantics Genericity::Data Types as a Policy</a>.
104         </li>
105         <li> <tt>Eq_Fn</tt> is a key equivalence functor.</li>
106         <li> <tt>Update_Policy</tt> is a policy updating
107         positions in the list based on access patterns. It is described in
108         the following subsection.
109         </li>
110         <li> <tt>Allocator</tt> is (surprisingly) an allocator type.
111         </li>
112 </ol>
113
114
115
116
117
118 <h2><a name = "list_updates">List Updates</a></h2>
119
120 <p>
121     This subsection describes list-update policies. It is organized as follows.
122 </p>
123
124 <ol>
125     <li> <a href = "#general">General Terms</a> describes general
126         terms.
127     </li>
128     <li> <a href = "#imp_pb_assoc">Implementation in <tt>pb_assoc</tt></a>
129          describes the implementation of these concepts in <tt>pb_assoc</tt>.
130     </li>
131 </ol>
132
133
134
135
136 <h3><a name = "general">General Terms</a></h3>
137
138
139 <p>
140     For example, Figure
141 <a href = "#lu">-A
142 The counter algorithm
143 </a>
144 shows the counter algorithm. Each node contains both a key and a count metadata (shown in bold).
145 When an element is accessed (<i>e.g.</i> 6)
146 its count is incremented, as shown in
147 Figure
148 <a href = "#lu">
149 The counter algorithm
150 </a>-B.
151 If the count reaches some predetermined value, say 10, as shown in
152 Figure
153 <a href = "#lu">
154 The counter algorithm
155 </a>-C,
156 the count is set to 0
157 and the node is moved to the front of the list,  as in
158 Figure
159 <a href = "#lu">
160 The counter algorithm
161 </a>-D.
162
163
164 </p>
165
166 <h6 align = "center">
167 <a name = "lu">
168 <img src = "lu_ops.jpg" width = "65%">
169 </a>
170 </h6>
171 <h6 align = "center">
172 The counter algorithm.
173 </h6>
174
175
176
177 <h3><a name = "imp_pb_assoc">Implementation in <tt>pb_assoc</tt></a></h3>
178
179 <p>
180     The <tt>pb_assoc</tt> library allows instantiating lists with policies
181 implementing any algorithm moving nodes to the front of the list (policies implementing
182 algorithms interchanging nodes are currently unsupported).
183 </p>
184
185 <p>
186     Associative containers based on lists are parameterized by a <tt>Update_Policy</tt> parameter.
187 This parameter defines the type of metadata each node contains, how to create the metadata, and how to
188 decide, using this metadata, whether to move a node to the front of the list.
189     A list-based associative container object derives (publicly) from its update policy.
190 </p>
191
192 <p>
193     An instantiation of <tt>Update_Policy</tt> must define internally <tt>update_metadata</tt> as the metadata
194 it requires. Internally, each node of the list contains, besides the usual key and data, an instance
195 of <tt><b>typename</b> Update_Policy::update_metadata</tt>.
196 </p>
197
198 <p>
199     An instantiation of <tt>Update_Policy</tt> must define internally two operators:
200 </p>
201 <pre>
202 update_metadata
203   <b>operator</b>()
204   ();
205
206 <b>bool</b>
207   <b>operator</b>()
208   (update_metadata &);
209 </pre>
210
211 <p>
212     The first is called by the container object, when creating a new node, to create the node's metadata. The
213 second is called by the container object, when a node is accessed (<i>e.g.</i>, when a find operation's key
214 is equivalent to the key of the node), to determine whether to move the node to the front of the list.
215 </p>
216
217 <p>
218     Additionally, the library contains implementations of the move-to-front and counter policies. These
219 are described in
220 <a href="interface.html#policy_classes">Policy Classes</a>.
221 </p>
222
223 </body>
224
225 </html>