1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<title>Boost.MultiIndex Documentation - Examples</title>
<link rel="stylesheet" href="style.css" type="text/css">
</head>
<body>
<h1><img src="../../../boost.png" alt="boost.png (6897 bytes)" align=
"middle" width="277" height="86">Boost.MultiIndex Examples</h1>
<div class="prev_link"><a href="performance.html"><img src="prev.gif" alt="performance" border="0"><br>
Performance
</a></div>
<div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br>
Index
</a></div>
<div class="next_link"><a href="tests.html"><img src="next.gif" alt="tests" border="0"><br>
Tests
</a></div><br clear="all" style="clear: all;">
<hr>
<h2>Contents</h2>
<ul>
<li><a href="#example1">Example 1: basic usage</a></li>
<li><a href="#example2">Example 2: using member functions as keys</a></li>
<li><a href="#example3">Example 3: constructing <code>multi_index_container</code>s
with <code>ctor_args_list</code></a></li>
<li><a href="#example4">Example 4: bidirectional map</a></li>
<li><a href="#example5">Example 5: sequenced indices</a></li>
<li><a href="#example6">Example 6: complex searches and foreign keys</a></li>
<li><a href="#example7">Example 7: composite keys</a></li>
<li><a href="#example8">Example 8: hashed indices</a></li>
<li><a href="#example9">Example 9: serialization and MRU lists</a></li>
</ul>
<h2><a name="example1">Example 1: basic usage</a></h2>
<p>
See <a href="../example/basic.cpp">source code</a>.
</p>
<p>
Basic program showing the multi-indexing capabilities of Boost.MultiIndex
with an admittedly boring set of <code>employee</code> records.
</p>
<h2><a name="example2">Example 2: using member functions as keys</a></h2>
<p>
See <a href="../example/memfun_key.cpp">source code</a>.
</p>
<p>
Usually keys assigned to an index are based on a member variable of the
element, but key extractors can be defined which take their value from
a member function. This has some similarity with the concept of
<i>calculated keys</i> supported by some relational database engines.
The example shows how to use the predefined <code>const_mem_fun</code>
key extractor to deal with this situation.
</p>
<p>
Keys based on member functions usually will not be actual references,
but rather the temporary values resulting from the invocation of the
member function used. This implies that <code>modify_key</code> cannot be
applied to this type of extractors, which is a perfectly logical
constraint anyway.
</p>
<h2><a name="example3">Example 3: constructing <code>multi_index_container</code>s
with <code>ctor_args_list</code></a></h2>
<p>
See <a href="../example/non_default_ctor.cpp">source code</a>.
</p>
<p>
We show a practical example of usage of <code>multi_index_container::ctor_arg_list</code>,
whose definition and purpose are explained in the
<a href="advanced_topics.html#ctor_args_list">Advanced topics section</a>. The
program groups a sorted collection of numbers based on identification through
modulo arithmetics, by which <code>x</code> and <code>y</code> are equivalent
if <code>(x%n)==(y%n)</code>, for some fixed <code>n</code>.
</p>
<h2><a name="example4">Example 4: bidirectional map</a></h2>
<p>
See <a href="../example/bimap.cpp">source code</a>.
</p>
<p>
This example shows how to construct a bidirectional map with
<code>multi_index_container</code>. By a <i>bidirectional map</i> we mean
a container of elements of <code>std::pair<const FromType,const ToType></code>
such that no two elements exists with the same <code>first</code>
<i>or</i> <code>second</code> value (<code>std::map</code> only
guarantees uniqueness of the first member). Fast lookup is provided
for both keys. The program features a tiny Spanish-English
dictionary with online query of words in both languages.
</p>
<h2><a name="example5">Example 5: sequenced indices</a></h2>
<p>
See <a href="../example/sequenced.cpp">source code</a>.
</p>
<p>
The combination of a sequenced index with an index of type <code>ordered_non_unique</code>
yields a <code>list</code>-like structure with fast lookup capabilities. The
example performs some operations on a given text, like word counting and
selective deletion of some words.
</p>
<h2><a name="example6">Example 6: complex searches and foreign keys</a></h2>
<p>
See <a href="../example/complex_structs.cpp">source code</a>.
</p>
<p>
This program illustrates some advanced techniques that can be applied
for complex data structures using <code>multi_index_container</code>.
Consider a <code>car_model</code> class for storing information
about automobiles. On a first approach, <code>car_model</code> can
be defined as:
</p>
<blockquote><pre>
<span class=keyword>struct</span> <span class=identifier>car_model</span>
<span class=special>{</span>
<span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>model</span><span class=special>;</span>
<span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>manufacturer</span><span class=special>;</span>
<span class=keyword>int</span> <span class=identifier>price</span><span class=special>;</span>
<span class=special>};</span>
</pre></blockquote>
<p>
This definition has a design flaw that any reader acquainted with
relational databases can easily spot: The <code>manufacturer</code>
member is duplicated among all cars having the same manufacturer.
This is a waste of space and poses difficulties when, for instance,
the name of a manufacturer has to be changed. Following the usual
principles in relational database design, the appropriate design
involves having the manufactures stored in a separate
<code>multi_index_container</code> and store pointers to these in
<code>car_model</code>:
</p>
<blockquote><pre>
<span class=keyword>struct</span> <span class=identifier>car_manufacturer</span>
<span class=special>{</span>
<span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>name</span><span class=special>;</span>
<span class=special>};</span>
<span class=keyword>struct</span> <span class=identifier>car_model</span>
<span class=special>{</span>
<span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>model</span><span class=special>;</span>
<span class=identifier>car_manufacturer</span><span class=special>*</span> <span class=identifier>manufacturer</span><span class=special>;</span>
<span class=keyword>int</span> <span class=identifier>price</span><span class=special>;</span>
<span class=special>};</span>
</pre></blockquote>
<p>
Although predefined Boost.MultiIndex key extractors can handle many
situations involving pointers (see
<a href="advanced_topics.html#advanced_key_extractors">advanced features
of Boost.MultiIndex key extractors</a> in the Advanced topics section), this case
is complex enough that a suitable key extractor has to be defined. The following
utility cascades two key extractors:
</p>
<blockquote><pre>
<span class=keyword>template</span><span class=special><</span><span class=keyword>class</span> <span class=identifier>KeyExtractor1</span><span class=special>,</span><span class=keyword>class</span> <span class=identifier>KeyExtractor2</span><span class=special>></span>
<span class=keyword>struct</span> <span class=identifier>key_from_key</span>
<span class=special>{</span>
<span class=keyword>public</span><span class=special>:</span>
<span class=keyword>typedef</span> <span class=keyword>typename</span> <span class=identifier>KeyExtractor1</span><span class=special>::</span><span class=identifier>result_type</span> <span class=identifier>result_type</span><span class=special>;</span>
<span class=identifier>key_from_key</span><span class=special>(</span>
<span class=keyword>const</span> <span class=identifier>KeyExtractor1</span><span class=special>&</span> <span class=identifier>key1_</span><span class=special>=</span><span class=identifier>KeyExtractor1</span><span class=special>(),</span>
<span class=keyword>const</span> <span class=identifier>KeyExtractor2</span><span class=special>&</span> <span class=identifier>key2_</span><span class=special>=</span><span class=identifier>KeyExtractor2</span><span class=special>()):</span>
<span class=identifier>key1</span><span class=special>(</span><span class=identifier>key1_</span><span class=special>),</span><span class=identifier>key2</span><span class=special>(</span><span class=identifier>key2_</span><span class=special>)</span>
<span class=special>{}</span>
<span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>Arg</span><span class=special>></span>
<span class=identifier>result_type</span> <span class=keyword>operator</span><span class=special>()(</span><span class=identifier>Arg</span><span class=special>&</span> <span class=identifier>arg</span><span class=special>)</span><span class=keyword>const</span>
<span class=special>{</span>
<span class=keyword>return</span> <span class=identifier>key1</span><span class=special>(</span><span class=identifier>key2</span><span class=special>(</span><span class=identifier>arg</span><span class=special>));</span>
<span class=special>}</span>
<span class=keyword>private</span><span class=special>:</span>
<span class=identifier>KeyExtractor1</span> <span class=identifier>key1</span><span class=special>;</span>
<span class=identifier>KeyExtractor2</span> <span class=identifier>key2</span><span class=special>;</span>
<span class=special>};</span>
</pre></blockquote>
<p>
so that access from a <code>car_model</code> to the <code>name</code> field
of its associated <code>car_manufacturer</code> can be accomplished with
</p>
<blockquote><pre>
<span class=identifier>key_from_key</span><span class=special><</span>
<span class=identifier>member</span><span class=special><</span><span class=identifier>car_manufacturer</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span><span class=special>,&</span><span class=identifier>car_manufacturer</span><span class=special>::</span><span class=identifier>name</span><span class=special>>,</span>
<span class=identifier>member</span><span class=special><</span><span class=identifier>car_model</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>car_manufacturer</span> <span class=special>*,</span><span class=identifier>car_model</span><span class=special>::</span><span class=identifier>manufacturer</span><span class=special>></span>
<span class=special>></span>
</pre></blockquote>
<p>
The program asks the user for a car manufacturer and a range of prices
and returns the car models satisfying these requirements. This is a complex
search that cannot be performed on a single operation. Broadly sketched,
one procedure for executing the selection is:
<ol>
<li>Select the elements with the given manufacturer by means
of <code>equal_range</code>,
<li>feed these elements into a <code>multi_index_container</code> sorted
by price,
<li>select by price using <code>lower_bound</code> and
<code>upper_bound</code>;
</ol>
or alternatively:
<ol>
<li>Select the elements within the price range with
<code>lower_bound</code> and <code>upper_bound</code>,
<li>feed these elements into a <code>multi_index_container</code> sorted
by manufacturer,
<li>locate the elements with given manufacturer using
<code>equal_range</code>.
</ol>
An interesting technique developed in the example lies in
the construction of the intermediate <code>multi_index_container</code>.
In order to avoid object copying, appropriate <i>view</i> types
are defined with <code>multi_index_container</code>s having as elements
pointers to <code>car_model</code>s instead of actual objects.
These views have to be supplemented with appropriate
dereferencing key extractors.
</p>
<h2><a name="example7">Example 7: composite keys</a></h2>
<p>
See <a href="../example/composite_keys.cpp">source code</a>.
</p>
<p>
Boost.MultiIndex <a href="advanced_topics.html#composite_keys">
<code>composite_key</code></a> construct provides a flexible tool for
creating indices with non-trivial sorting criteria.
The program features a rudimentary simulation of a file system
along with an interactive Unix-like shell. A file entry is represented by
the following structure:
</p>
<blockquote><pre>
<span class=keyword>struct</span> <span class=identifier>file_entry</span>
<span class=special>{</span>
<span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>name</span><span class=special>;</span>
<span class=keyword>unsigned</span> <span class=identifier>size</span><span class=special>;</span>
<span class=keyword>bool</span> <span class=identifier>is_dir</span><span class=special>;</span> <span class=comment>// true if the entry is a directory</span>
<span class=keyword>const</span> <span class=identifier>file_entry</span><span class=special>*</span> <span class=identifier>dir</span><span class=special>;</span> <span class=comment>// directory this entry belongs in</span>
<span class=special>};</span>
</pre></blockquote>
<p>
Entries are kept in a <code>multi_index_container</code> maintaining two indices
with composite keys:
<ul>
<li>A primary index ordered by directory and name,</li>
<li>a secondary index ordered by directory and size.</li>
</ul>
The reason that the order is made firstly by the directory in which
the files are located obeys to the local nature of the shell commands,
like for instance <code>ls</code>. The shell simulation only has three
commands:
<ul>
<li><code>cd [.|..|<i><directory></i>]</code></li>
<li><code>ls [-s]</code> (<code>-s</code> orders the output by size)</li>
<li><code>mkdir <i><directory></i></code></li>
</ul>
The program exits when the user presses the Enter key at the command prompt.
</p>
<p>
The reader is challenged to add more functionality to the program; for
instance:
<ul>
<li>Implement additional commands, like <code>cp</code>.</li>
<li>Add handling of absolute paths.</li>
<li>Use <a href="advanced_topics.html#serialization">serialization</a>
to store and retrieve the filesystem state between program runs.</li>
</ul>
</p>
<h2><a name="example8">Example 8: hashed indices</a></h2>
<p>
See <a href="../example/hashed.cpp">source code</a>.
</p>
<p>
Hashed indices can be used as an alternative to ordered indices when
fast lookup is needed and sorting information is of no interest. The
example features a word counter where duplicate entries are checked
by means of a hashed index. Confront the word counting algorithm with
that of <a href="#example5">example 5</a>.
</p>
<h2><a name="example9">Example 9: serialization and MRU lists</a></h2>
<p>
See <a href="../example/serialization.cpp">source code</a>.
</p>
<p>
A typical application of serialization capabilities allows a program to
restore the user context between executions. The example program asks
the user for words and keeps a record of the ten most recently entered
ones, in the current or in previous sessions. The serialized data structure,
sometimes called an <i>MRU (most recently used) list</i>, has some interest
on its own: an MRU list behaves as a regular FIFO queue, with the exception
that, when inserting a preexistent entry, this does not appear twice, but
instead the entry is moved to the front of the list. You can observe this
behavior in many programs featuring a "Recent files" menu command. This
data structure is implemented with <code>multi_index_container</code> by
combining a sequenced index and an index of type <code>hashed_unique</code>.
</p>
<hr>
<div class="prev_link"><a href="performance.html"><img src="prev.gif" alt="performance" border="0"><br>
Performance
</a></div>
<div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br>
Index
</a></div>
<div class="next_link"><a href="tests.html"><img src="next.gif" alt="tests" border="0"><br>
Tests
</a></div><br clear="all" style="clear: all;">
<br>
<p>Revised August 22nd 2005</p>
<p>© Copyright 2003-2005 Joaquín M López Muñoz.
Distributed under the Boost Software
License, Version 1.0. (See accompanying file <a href="../../../LICENSE_1_0.txt">
LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
http://www.boost.org/LICENSE_1_0.txt</a>)
</p>
</body>
</html>
|
