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