| Brian Silverman | 3cbbaca | 2018-08-04 23:38:07 -0700 | [diff] [blame^] | 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 - Tutorial</title> |
| 7 | <link rel="stylesheet" href="../style.css" type="text/css"> |
| 8 | <link rel="start" href="../index.html"> |
| 9 | <link rel="prev" href="../index.html"> |
| 10 | <link rel="up" href="../index.html"> |
| 11 | <link rel="next" href="basics.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 Tutorial</h1> |
| 17 | |
| 18 | <div class="prev_link"><a href="../index.html"><img src="../prev.gif" alt="index" border="0"><br> |
| 19 | Index |
| 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="basics.html"><img src="../next.gif" alt="basics" border="0"><br> |
| 25 | Basics |
| 26 | </a></div><br clear="all" style="clear: all;"> |
| 27 | |
| 28 | <hr> |
| 29 | |
| 30 | <h2>Contents</h2> |
| 31 | |
| 32 | <ul> |
| 33 | <li><a href="#rationale">Rationale</a></li> |
| 34 | <li><a href="#namespace">Namespace</a></li> |
| 35 | <li><a href="basics.html">Basics</a></li> |
| 36 | <li><a href="indices.html">Index types</a></li> |
| 37 | <li><a href="key_extraction.html">Key extraction</a></li> |
| 38 | <li><a href="creation.html">Container creation</a></li> |
| 39 | <li><a href="debug.html">Debugging support</a></li> |
| 40 | <li><a href="techniques.html">Techniques</a></li> |
| 41 | </ul> |
| 42 | |
| 43 | <h2><a name="rationale">Rationale</a></h2> |
| 44 | |
| 45 | <p> |
| 46 | STL containers are designed around the concept that each container controls its |
| 47 | own collection of elements, giving access to them in a manner specified by the |
| 48 | container's type: so, an <code>std::set</code> maintains the elements ordered |
| 49 | by a specified sorting criterion, <code>std::list</code> allows for free |
| 50 | positioning of elements along a linear sequence, and so on. |
| 51 | </p> |
| 52 | |
| 53 | <p> |
| 54 | Sometimes, the necessity arises of having different access interfaces |
| 55 | to the same underlying collection: for instance, some data might need to be |
| 56 | sorted according to more than one comparison predicate, or a bidirectional list |
| 57 | might benefit from a supplemental logarithmic lookup interface. In these |
| 58 | situations, programmers typically resort to manual compositions of different |
| 59 | containers, a solution that generally involves a fair amount of code |
| 60 | devoted to preserve the synchronization of the different parts of |
| 61 | the composition. Boost.MultiIndex allows for the specification of |
| 62 | <code>multi_index_container</code>s comprised of one or more <i>indices</i> with |
| 63 | different interfaces to the same collection of elements. The resulting constructs |
| 64 | are conceptually cleaner than manual compositions, and often perform much better. |
| 65 | An important design decision has been taken that the indices of a given |
| 66 | <code>multi_index_container</code> instantiation be specified at compile time: this |
| 67 | gives ample room for static type checking and code optimization. |
| 68 | </p> |
| 69 | |
| 70 | <p> |
| 71 | Boost.MultiIndex takes inspiration from basic concepts of indexing arising in the |
| 72 | theory of relational databases, though it is not intended to provide a full-fledged |
| 73 | relational database framework. <code>multi_index_container</code> integrates seamlessly |
| 74 | into the STL container/algorithm design, and features some extra capabilities regarding |
| 75 | lookup operations and element updating which are useful extensions even for |
| 76 | single-indexed containers. |
| 77 | </p> |
| 78 | |
| 79 | <p align="center"> |
| 80 | <img src="multi_index_cont_example.png" |
| 81 | alt="diagram of a multi_index_container with three indices" |
| 82 | width="600" height="304"><br> |
| 83 | <b>Fig. 1: Diagram of a <code>multi_index_container</code> with three indices.</b> |
| 84 | </p> |
| 85 | |
| 86 | <p> |
| 87 | The figure above depicts a <code>multi_index_container</code> composed of three indices: |
| 88 | the first two present a set-like interface to the elements sorted by |
| 89 | shape and id, respectively, while the latter index provides the functionality |
| 90 | of a bidirectional list in the spirit of <code>std::list</code>. These |
| 91 | indices act as "views" to the internal collection of elements, but they do not only |
| 92 | provide read access to the set: insertion/deletion methods are also implemented much |
| 93 | as those of <code>std::set</code>s or <code>std::list</code>s. Insertion of an |
| 94 | element through one given index will only succeed if the uniqueness constraints of all |
| 95 | indices are met. |
| 96 | </p> |
| 97 | |
| 98 | <h2> |
| 99 | <a name="namespace">Namespace</a> |
| 100 | </h2> |
| 101 | |
| 102 | <p> |
| 103 | All the public types of Boost.MultiIndex reside in namespace <code>::boost::multi_index</code>. |
| 104 | Additionaly, the main class template <code>multi_index_container</code> and global functions |
| 105 | <code>get</code> and <code>project</code> are lifted to namespace <code>::boost</code> |
| 106 | by means of <code>using</code> declarations. For brevity of exposition, the fragments |
| 107 | of code in the documentation are written as if the following declarations were in effect: |
| 108 | </p> |
| 109 | |
| 110 | <blockquote><pre> |
| 111 | <span class=keyword>using</span> <span class=keyword>namespace</span> <span class=special>::</span><span class=identifier>boost</span><span class=special>;</span> |
| 112 | <span class=keyword>using</span> <span class=keyword>namespace</span> <span class=special>::</span><span class=identifier>boost</span><span class=special>::</span><span class=identifier>multi_index</span><span class=special>;</span> |
| 113 | </pre></blockquote> |
| 114 | |
| 115 | <hr> |
| 116 | |
| 117 | <div class="prev_link"><a href="../index.html"><img src="../prev.gif" alt="index" border="0"><br> |
| 118 | Index |
| 119 | </a></div> |
| 120 | <div class="up_link"><a href="../index.html"><img src="../up.gif" alt="index" border="0"><br> |
| 121 | Index |
| 122 | </a></div> |
| 123 | <div class="next_link"><a href="basics.html"><img src="../next.gif" alt="basics" border="0"><br> |
| 124 | Basics |
| 125 | </a></div><br clear="all" style="clear: all;"> |
| 126 | |
| 127 | <br> |
| 128 | |
| 129 | <p>Revised February 21st 2006</p> |
| 130 | |
| 131 | <p>© Copyright 2003-2006 Joaquín M López Muñoz. |
| 132 | Distributed under the Boost Software |
| 133 | License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt"> |
| 134 | LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt"> |
| 135 | http://www.boost.org/LICENSE_1_0.txt</a>) |
| 136 | </p> |
| 137 | |
| 138 | </body> |
| 139 | </html> |