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
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
|
<!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">
<link rel="start" href="index.html">
<link rel="prev" href="performance.html">
<link rel="up" href="index.html">
<link rel="next" href="tests.html">
</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 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>
<li><a href="#example10">Example 10: random access indices</a></li>
<li><a href="#example11">Example 11: index rearrangement</a></li>
<li><a href="#example12">Example 12: using Boost.Interprocess allocators</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 functions as keys</a></h2>
<p>
See <a href="../example/fun_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 or a global 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>
and <code>global_fun</code> key extractors to deal with this situation.
</p>
<p>
Keys based on 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="tutorial/creation.html#ctor_args_list">tutorial</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>
<p>
This bidirectional map can be considered as a primitive precursor
to the full-fledged container provided by
<a href="../../bimap/index.html">Boost.Bimap</a>.
</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="tutorial/key_extraction.html#advanced_key_extractors">advanced features
of Boost.MultiIndex key extractors</a> in the tutorial), 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="tutorial/key_extraction.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="tutorial/creation.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>
<h2><a name="example10">Example 10: random access indices</a></h2>
<p>
See <a href="../example/random_access.cpp">source code</a>.
</p>
<p>
The example resumes the text container introduced in
<a href="#example5">example 5</a> and shows how substituting a random
access index for a sequenced index allows for extra capabilities like
efficient access by position and calculation of the offset of a given
element into the container.
</p>
<h2><a name="example11">Example 11: index rearrangement</a></h2>
<p>
See <a href="../example/rearrange.cpp">source code</a>.
</p>
<p>
There is a relatively common piece of urban lore claiming that
a deck of cards must be shuffled seven times in a row to be perfectly
mixed. The statement derives from the works of mathematician Persi
Diaconis on <i>riffle shuffling</i>: this shuffling
technique involves splitting the deck in two packets roughly the same
size and then dropping the cards from both packets so that they become
interleaved. It has been shown that when repeating this procedure
seven times the statistical distribution of cards is reasonably
close to that associated with a truly random permutation. A measure
of "randomness" can be estimated by counting <i>rising sequences</i>:
consider a permutation of the sequence 1,2, ... , <i>n</i>, a rising sequence
is a maximal chain of consecutive elements <i>m</i>, <i>m+1</i>, ... , <i>m+r</i>
such that they are arranged in ascending order. For instance, the permutation
125364789 is composed of the two rising sequences 1234 and 56789,
as becomes obvious by displaying the sequence like this,
<span style="vertical-align:sub">1</span><span style="vertical-align:sub">2</span><span style="vertical-align:super">5</span><span style="vertical-align:sub">3</span><span style="vertical-align:super">6</span><span style="vertical-align:sub">4</span><span style="vertical-align:super">7</span><span style="vertical-align:super">8</span><span style="vertical-align:super">9</span>.
The average number of rising sequences in a random permutation of
<i>n</i> elements is (<i>n</i>+1)/2: by contrast, after a single riffle
shuffle of an initially sorted deck of cards, there cannot be more than
two rising sequences. The average number of rising sequences approximates
to (<i>n</i>+1)/2 as the number of consecutive riffle shuffles increases,
with seven shuffles yielding a close result for a 52-card poker deck.
Brad Mann's paper
<a href="http://www.dartmouth.edu/~chance/teaching_aids/books_articles/Mann.pdf">"How
many times should you shuffle a deck of cards?"</a> provides a
rigorous yet very accessible treatment of this subject.
</p>
<p>
The example program estimates the average number of rising sequences
in a 52-card deck after repeated riffle shuffling as well as applying
a completely random permutation. The deck is modeled by the following
container:
<blockquote><pre>
<span class=identifier>multi_index_container</span><span class=special><</span>
<span class=keyword>int</span><span class=special>,</span>
<span class=identifier>indexed_by</span><span class=special><</span>
<span class=identifier>random_access</span><span class=special><>,</span>
<span class=identifier>random_access</span><span class=special><></span>
<span class=special>></span>
<span class=special>></span>
</pre></blockquote>
where the first index stores the current arrangement of the deck, while
the second index is used to remember the start position. This representation
allows for an efficient implementation of a rising sequences counting
algorithm in linear time.
<a href="reference/rnd_indices.html#rearrange"><code>rearrange</code></a>
is used to apply to the deck a shuffle performed externally on an
auxiliary data structure.
</p>
<h2><a name="example12">Example 12: using Boost.Interprocess allocators</a></h2>
<p>
See <a href="../example/ip_allocator.cpp">source code</a>.
</p>
<p>
Boost.MultiIndex supports special allocators such as those provided by
<a href="../../interprocess/index.html">Boost.Interprocess</a>,
which allows for <code>multi_index_container</code>s to be placed in shared
memory. The example features a front-end to a small book database
implemented by means of a <code>multi_index_container</code> stored
in a Boost.Interprocess memory mapped file. The reader can verify that several
instances of the program correctly work simultaneously and immediately see
the changes to the database performed by any other instance.
</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 July 16th 2007</p>
<p>© Copyright 2003-2007 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>
|
