ceph/src/boost/libs/multi_index/doc/examples.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN">
   2
   3 <html>
   4 <head>
   5 <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
   6 <title>Boost.MultiIndex Documentation - Examples</title>
   7 <link rel="stylesheet" href="style.css" type="text/css">
   8 <link rel="start" href="index.html">
   9 <link rel="prev" href="performance.html">
  10 <link rel="up" href="index.html">
  11 <link rel="next" href="tests.html">
  12 </head>
  13
  14 <body>
  15 <h1><img src="../../../boost.png" alt="boost.png (6897 bytes)" align=
  16 "middle" width="277" height="86">Boost.MultiIndex Examples</h1>
  17
  18 <div class="prev_link"><a href="performance.html"><img src="prev.gif" alt="performance" border="0"><br>
  19 Performance
  20 </a></div>
  21 <div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br>
  22 Index
  23 </a></div>
  24 <div class="next_link"><a href="tests.html"><img src="next.gif" alt="tests" border="0"><br>
  25 Tests
  26 </a></div><br clear="all" style="clear: all;">
  27
  28 <hr>
  29
  30 <h2>Contents</h2>
  31
  32 <ul>
  33   <li><a href="#example1">Example 1: basic usage</a></li>
  34   <li><a href="#example2">Example 2: using functions as keys</a></li>
  35   <li><a href="#example3">Example 3: constructing <code>multi_index_container</code>s
  36     with <code>ctor_args_list</code></a></li>
  37   <li><a href="#example4">Example 4: bidirectional map</a></li>
  38   <li><a href="#example5">Example 5: sequenced indices</a></li>
  39   <li><a href="#example6">Example 6: complex searches and foreign keys</a></li>
  40   <li><a href="#example7">Example 7: composite keys</a></li>
  41   <li><a href="#example8">Example 8: hashed indices</a></li>
  42   <li><a href="#example9">Example 9: serialization and MRU lists</a></li>
  43   <li><a href="#example10">Example 10: random access indices</a></li>
  44   <li><a href="#example11">Example 11: index rearrangement</a></li>
  45   <li><a href="#example12">Example 12: using Boost.Interprocess allocators</a></li>
  46 </ul>
  47
  48 <h2><a name="example1">Example 1: basic usage</a></h2>
  49
  50 <p>
  51 See <a href="../example/basic.cpp">source code</a>.
  52 </p>
  53
  54 <p>
  55 Basic program showing the multi-indexing capabilities of Boost.MultiIndex
  56 with an admittedly boring set of <code>employee</code> records.
  57 </p>
  58
  59 <h2><a name="example2">Example 2: using functions as keys</a></h2>
  60
  61 <p>
  62 See <a href="../example/fun_key.cpp">source code</a>.
  63 </p>
  64
  65 <p>
  66 Usually keys assigned to an index are based on a member variable of the
  67 element, but key extractors can be defined which take their value from
  68 a member function or a global function. This has some similarity with the concept of
  69 <i>calculated keys</i> supported by some relational database engines.
  70 The example shows how to use the predefined <code>const_mem_fun</code>
  71 and <code>global_fun</code> key extractors to deal with this situation.
  72 </p>
  73
  74 <p>
  75 Keys based on functions usually will not be actual references,
  76 but rather the temporary values resulting from the invocation of the
  77 member function used. This implies that <code>modify_key</code> cannot be
  78 applied to this type of extractors, which is a perfectly logical
  79 constraint anyway.
  80 </p>
  81
  82 <h2><a name="example3">Example 3: constructing <code>multi_index_container</code>s
  83 with <code>ctor_args_list</code></a></h2>
  84
  85 <p>
  86 See <a href="../example/non_default_ctor.cpp">source code</a>.
  87 </p>
  88
  89 <p>
  90 We show a practical example of usage of <code>multi_index_container::ctor_arg_list</code>,
  91 whose definition and purpose are explained in the
  92 <a href="tutorial/creation.html#ctor_args_list">tutorial</a>. The
  93 program groups a sorted collection of numbers based on identification through
  94 modulo arithmetics, by which <code>x</code> and <code>y</code> are equivalent
  95 if <code>(x%n)==(y%n)</code>, for some fixed <code>n</code>.
  96 </p>
  97
  98 <h2><a name="example4">Example 4: bidirectional map</a></h2>
  99
 100 <p>
 101 See <a href="../example/bimap.cpp">source code</a>.
 102 </p>
 103
 104 <p>
 105 This example shows how to construct a bidirectional map with
 106 <code>multi_index_container</code>. By a <i>bidirectional map</i> we mean
 107 a container of <code>(const FromType,const ToType)</code> pairs
 108 such that no two elements exists with the same first
 109 <i>or</i> second component (<code>std::map</code> only
 110 guarantees uniqueness of the first component). Fast lookup is provided
 111 for both keys. The program features a tiny Spanish-English
 112 dictionary with online query of words in both languages.
 113 </p>
 114
 115 <p>
 116 This bidirectional map can be considered as a primitive precursor
 117 to the full-fledged container provided by
 118 <a href="../../bimap/index.html">Boost.Bimap</a>.
 119 </p>
 120
 121 <h2><a name="example5">Example 5: sequenced indices</a></h2>
 122
 123 <p>
 124 See <a href="../example/sequenced.cpp">source code</a>.
 125 </p>
 126
 127 <p>
 128 The combination of a sequenced index with an index of type <code>ordered_non_unique</code>
 129 yields a <code>list</code>-like structure with fast lookup capabilities. The
 130 example performs some operations on a given text, like word counting and
 131 selective deletion of some words.
 132 </p>
 133
 134 <h2><a name="example6">Example 6: complex searches and foreign keys</a></h2>
 135
 136 <p>
 137 See <a href="../example/complex_structs.cpp">source code</a>.
 138 </p>
 139
 140 <p>
 141 This program illustrates some advanced techniques that can be applied
 142 for complex data structures using <code>multi_index_container</code>.
 143 Consider a <code>car_model</code> class for storing information
 144 about automobiles. On a first approach, <code>car_model</code> can
 145 be defined as:
 146 </p>
 147
 148 <blockquote><pre>
 149 <span class=keyword>struct</span> <span class=identifier>car_model</span>
 150 <span class=special>{</span>
 151   <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>model</span><span class=special>;</span>
 152   <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>manufacturer</span><span class=special>;</span>
 153   <span class=keyword>int</span>         <span class=identifier>price</span><span class=special>;</span>
 154 <span class=special>};</span>
 155 </pre></blockquote>
 156
 157 <p>
 158 This definition has a design flaw that any reader acquainted with
 159 relational databases can easily spot: The <code>manufacturer</code>
 160 member is duplicated among all cars having the same manufacturer.
 161 This is a waste of space and poses difficulties when, for instance,
 162 the name of a manufacturer has to be changed. Following the usual
 163 principles in relational database design, the appropriate design
 164 involves having the manufactures stored in a separate
 165 <code>multi_index_container</code> and store pointers to these in
 166 <code>car_model</code>:
 167 </p>
 168
 169 <blockquote><pre>
 170 <span class=keyword>struct</span> <span class=identifier>car_manufacturer</span>
 171 <span class=special>{</span>
 172   <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span> <span class=identifier>name</span><span class=special>;</span>
 173 <span class=special>};</span>
 174
 175 <span class=keyword>struct</span> <span class=identifier>car_model</span>
 176 <span class=special>{</span>
 177   <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span>       <span class=identifier>model</span><span class=special>;</span>
 178   <span class=identifier>car_manufacturer</span><span class=special>*</span> <span class=identifier>manufacturer</span><span class=special>;</span>
 179   <span class=keyword>int</span>               <span class=identifier>price</span><span class=special>;</span>
 180 <span class=special>};</span>
 181 </pre></blockquote>
 182
 183 <p>
 184 Although predefined Boost.MultiIndex key extractors can handle many
 185 situations involving pointers (see
 186 <a href="tutorial/key_extraction.html#advanced_key_extractors">advanced features
 187 of Boost.MultiIndex key extractors</a> in the tutorial), this case
 188 is complex enough that a suitable key extractor has to be defined. The following
 189 utility cascades two key extractors:
 190 </p>
 191
 192 <blockquote><pre>
 193 <span class=keyword>template</span><span class=special>&lt;</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>&gt;</span>
 194 <span class=keyword>struct</span> <span class=identifier>key_from_key</span>
 195 <span class=special>{</span>
 196 <span class=keyword>public</span><span class=special>:</span>
 197   <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>
 198
 199   <span class=identifier>key_from_key</span><span class=special>(</span>
 200     <span class=keyword>const</span> <span class=identifier>KeyExtractor1</span><span class=special>&amp;</span> <span class=identifier>key1_</span><span class=special>=</span><span class=identifier>KeyExtractor1</span><span class=special>(),</span>
 201     <span class=keyword>const</span> <span class=identifier>KeyExtractor2</span><span class=special>&amp;</span> <span class=identifier>key2_</span><span class=special>=</span><span class=identifier>KeyExtractor2</span><span class=special>()):</span>
 202     <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>
 203   <span class=special>{}</span>
 204
 205   <span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>Arg</span><span class=special>&gt;</span>
 206   <span class=identifier>result_type</span> <span class=keyword>operator</span><span class=special>()(</span><span class=identifier>Arg</span><span class=special>&amp;</span> <span class=identifier>arg</span><span class=special>)</span><span class=keyword>const</span>
 207   <span class=special>{</span>
 208     <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>
 209   <span class=special>}</span>
 210
 211 <span class=keyword>private</span><span class=special>:</span>
 212   <span class=identifier>KeyExtractor1</span> <span class=identifier>key1</span><span class=special>;</span>
 213   <span class=identifier>KeyExtractor2</span> <span class=identifier>key2</span><span class=special>;</span>
 214 <span class=special>};</span>
 215 </pre></blockquote>
 216
 217 <p>
 218 so that access from a <code>car_model</code> to the <code>name</code> field
 219 of its associated <code>car_manufacturer</code> can be accomplished with
 220 </p>
 221
 222 <blockquote><pre>
 223 <span class=identifier>key_from_key</span><span class=special>&lt;</span>
 224   <span class=identifier>member</span><span class=special>&lt;</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>,&amp;</span><span class=identifier>car_manufacturer</span><span class=special>::</span><span class=identifier>name</span><span class=special>&gt;,</span>
 225   <span class=identifier>member</span><span class=special>&lt;</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>&gt;</span>
 226 <span class=special>&gt;</span>
 227 </pre></blockquote>
 228
 229 <p>
 230 The program asks the user for a car manufacturer and a range of prices
 231 and returns the car models satisfying these requirements. This is a complex
 232 search that cannot be performed on a single operation. Broadly sketched,
 233 one procedure for executing the selection is:
 234 <ol>
 235   <li>Select the elements with the given manufacturer by means
 236     of <code>equal_range</code>,
 237   <li>feed these elements into a <code>multi_index_container</code> sorted
 238     by price,
 239   <li>select by price using <code>lower_bound</code> and
 240     <code>upper_bound</code>;
 241 </ol>
 242 or alternatively:
 243 <ol>
 244   <li>Select the elements within the price range with
 245   <code>lower_bound</code> and <code>upper_bound</code>,
 246   <li>feed these elements into a <code>multi_index_container</code> sorted
 247     by manufacturer,
 248   <li>locate the elements with given manufacturer using
 249     <code>equal_range</code>.
 250 </ol>
 251 An interesting technique developed in the example lies in
 252 the construction of the intermediate <code>multi_index_container</code>.
 253 In order to avoid object copying, appropriate <i>view</i> types
 254 are defined with <code>multi_index_container</code>s having as elements
 255 pointers to <code>car_model</code>s instead of actual objects.
 256 These views have to be supplemented with appropriate
 257 dereferencing key extractors.
 258 </p>
 259
 260 <h2><a name="example7">Example 7: composite keys</a></h2>
 261
 262 <p>
 263 See <a href="../example/composite_keys.cpp">source code</a>.
 264 </p>
 265
 266 <p>
 267 Boost.MultiIndex <a href="tutorial/key_extraction.html#composite_keys">
 268 <code>composite_key</code></a> construct provides a flexible tool for
 269 creating indices with non-trivial sorting criteria.
 270 The program features a rudimentary simulation of a file system
 271 along with an interactive Unix-like shell. A file entry is represented by
 272 the following structure:
 273 </p>
 274
 275 <blockquote><pre>
 276 <span class=keyword>struct</span> <span class=identifier>file_entry</span>
 277 <span class=special>{</span>
 278   <span class=identifier>std</span><span class=special>::</span><span class=identifier>string</span>       <span class=identifier>name</span><span class=special>;</span>
 279   <span class=keyword>unsigned</span>          <span class=identifier>size</span><span class=special>;</span>
 280   <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>
 281   <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>
 282 <span class=special>};</span>
 283 </pre></blockquote>
 284
 285 <p>
 286 Entries are kept in a <code>multi_index_container</code> maintaining two indices
 287 with composite keys:
 288 <ul>
 289   <li>A primary index ordered by directory and name,</li>
 290   <li>a secondary index ordered by directory and size.</li>
 291 </ul>
 292 The reason that the order is made firstly by the directory in which
 293 the files are located obeys to the local nature of the shell commands,
 294 like for instance <code>ls</code>. The shell simulation only has three
 295 commands:
 296 <ul>
 297   <li><code>cd [.|..|<i>&lt;directory&gt;</i>]</code></li>
 298   <li><code>ls [-s]</code> (<code>-s</code> orders the output by size)</li>
 299   <li><code>mkdir <i>&lt;directory&gt;</i></code></li>
 300 </ul>
 301 The program exits when the user presses the Enter key at the command prompt.
 302 </p>
 303
 304 <p>
 305 The reader is challenged to add more functionality to the program; for
 306 instance:
 307 <ul>
 308   <li>Implement additional commands, like <code>cp</code>.</li>
 309   <li>Add handling of absolute paths.</li>
 310   <li>Use <a href="tutorial/creation.html#serialization">serialization</a>
 311     to store and retrieve the filesystem state between program runs.</li>
 312 </ul>
 313 </p>
 314
 315 <h2><a name="example8">Example 8: hashed indices</a></h2>
 316
 317 <p>
 318 See <a href="../example/hashed.cpp">source code</a>.
 319 </p>
 320
 321 <p>
 322 Hashed indices can be used as an alternative to ordered indices when
 323 fast lookup is needed and sorting information is of no interest. The
 324 example features a word counter where duplicate entries are checked
 325 by means of a hashed index. Confront the word counting algorithm with
 326 that of <a href="#example5">example 5</a>.
 327 </p>
 328
 329 <h2><a name="example9">Example 9: serialization and MRU lists</a></h2>
 330
 331 <p>
 332 See <a href="../example/serialization.cpp">source code</a>.
 333 </p>
 334
 335 <p>
 336 A typical application of serialization capabilities allows a program to
 337 restore the user context between executions. The example program asks
 338 the user for words and keeps a record of the ten most recently entered
 339 ones, in the current or in previous sessions. The serialized data structure,
 340 sometimes called an <i>MRU (most recently used) list</i>, has some interest
 341 on its own: an MRU list behaves as a regular FIFO queue, with the exception
 342 that, when inserting a preexistent entry, this does not appear twice, but
 343 instead the entry is moved to the front of the list. You can observe this
 344 behavior in many programs featuring a "Recent files" menu command. This
 345 data structure is implemented with <code>multi_index_container</code> by
 346 combining a sequenced index and an index of type <code>hashed_unique</code>.
 347 </p>
 348
 349 <h2><a name="example10">Example 10: random access indices</a></h2>
 350
 351 <p>
 352 See <a href="../example/random_access.cpp">source code</a>.
 353 </p>
 354
 355 <p>
 356 The example resumes the text container introduced in
 357 <a href="#example5">example 5</a> and shows how substituting a random
 358 access index for a sequenced index allows for extra capabilities like
 359 efficient access by position and calculation of the offset of a given
 360 element into the container.
 361 </p>
 362
 363 <h2><a name="example11">Example 11: index rearrangement</a></h2>
 364
 365 <p>
 366 See <a href="../example/rearrange.cpp">source code</a>.
 367 </p>
 368
 369 <p>
 370 There is a relatively common piece of urban lore claiming that
 371 a deck of cards must be shuffled seven times in a row to be perfectly
 372 mixed. The statement derives from the works of mathematician Persi
 373 Diaconis on <i>riffle shuffling</i>: this shuffling
 374 technique involves splitting the deck in two packets roughly the same
 375 size and then dropping the cards from both packets so that they become
 376 interleaved. It has been shown that when repeating this procedure
 377 seven times the statistical distribution of cards is reasonably
 378 close to that associated with a truly random permutation. A measure
 379 of "randomness" can be estimated by counting <i>rising sequences</i>:
 380 consider a permutation of the sequence 1,2, ... , <i>n</i>, a rising sequence
 381 is a maximal chain of consecutive elements <i>m</i>, <i>m+1</i>, ... , <i>m+r</i>
 382 such that they are arranged in ascending order. For instance, the permutation
 383 125364789 is composed of the two rising sequences 1234 and 56789,
 384 as becomes obvious by displaying the sequence like this,
 385 <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>.
 386 The average number of rising sequences in a random permutation of
 387 <i>n</i> elements is (<i>n</i>+1)/2: by contrast, after a single riffle
 388 shuffle of an initially sorted deck of cards, there cannot be more than
 389 two rising sequences. The average number of rising sequences approximates
 390 to (<i>n</i>+1)/2 as the number of consecutive riffle shuffles increases,
 391 with seven shuffles yielding a close result for a 52-card poker deck.
 392 Brad Mann's paper
 393 <a href="http://www.dartmouth.edu/~chance/teaching_aids/books_articles/Mann.pdf">"How
 394 many times should you shuffle a deck of cards?"</a> provides a
 395 rigorous yet very accessible treatment of this subject.
 396
 397 </p>
 398
 399 <p>
 400 The example program estimates the average number of rising sequences
 401 in a 52-card deck after repeated riffle shuffling as well as applying
 402 a completely random permutation. The deck is modeled by the following
 403 container:
 404 <blockquote><pre>
 405 <span class=identifier>multi_index_container</span><span class=special>&lt;</span>
 406   <span class=keyword>int</span><span class=special>,</span>
 407   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 408     <span class=identifier>random_access</span><span class=special>&lt;&gt;,</span>
 409     <span class=identifier>random_access</span><span class=special>&lt;&gt;</span>
 410   <span class=special>&gt;</span>
 411 <span class=special>&gt;</span>
 412 </pre></blockquote>
 413 where the first index stores the current arrangement of the deck, while
 414 the second index is used to remember the start position. This representation
 415 allows for an efficient implementation of a rising sequences counting
 416 algorithm in linear time.
 417 <a href="reference/rnd_indices.html#rearrange"><code>rearrange</code></a>
 418 is used to apply to the deck a shuffle performed externally on an
 419 auxiliary data structure.
 420 </p>
 421
 422 <h2><a name="example12">Example 12: using Boost.Interprocess allocators</a></h2>
 423
 424 <p>
 425 See <a href="../example/ip_allocator.cpp">source code</a>.
 426 </p>
 427
 428 <p>
 429 Boost.MultiIndex supports special allocators such as those provided by
 430 <a href="../../interprocess/index.html">Boost.Interprocess</a>,
 431 which allows for <code>multi_index_container</code>s to be placed in shared
 432 memory. The example features a front-end to a small book database
 433 implemented by means of a <code>multi_index_container</code> stored
 434 in a Boost.Interprocess memory mapped file. The reader can verify that several
 435 instances of the program correctly work simultaneously and immediately see
 436 the changes to the database performed by any other instance.
 437 </p>
 438
 439 <hr>
 440
 441 <div class="prev_link"><a href="performance.html"><img src="prev.gif" alt="performance" border="0"><br>
 442 Performance
 443 </a></div>
 444 <div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br>
 445 Index
 446 </a></div>
 447 <div class="next_link"><a href="tests.html"><img src="next.gif" alt="tests" border="0"><br>
 448 Tests
 449 </a></div><br clear="all" style="clear: all;">
 450
 451 <br>
 452
 453 <p>Revised May 26th 2009</p>
 454
 455 <p>&copy; Copyright 2003-2009 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;oz.
 456 Distributed under the Boost Software
 457 License, Version 1.0. (See accompanying file <a href="../../../LICENSE_1_0.txt">
 458 LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
 459 http://www.boost.org/LICENSE_1_0.txt</a>)
 460 </p>
 461
 462 </body>
 463 </html>