ceph/src/boost/libs/multi_index/doc/reference/indices.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 - Index reference</title>
   7 <link rel="stylesheet" href="../style.css" type="text/css">
   8 <link rel="start" href="../index.html">
   9 <link rel="prev" href="multi_index_container.html">
  10 <link rel="up" href="index.html">
  11 <link rel="next" href="ord_indices.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 Index reference</h1>
  17
  18 <div class="prev_link"><a href="multi_index_container.html"><img src="../prev.gif" alt="multi_index_container reference" border="0"><br>
  19 <code>multi_index_container</code> reference
  20 </a></div>
  21 <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex reference" border="0"><br>
  22 Boost.MultiIndex reference
  23 </a></div>
  24 <div class="next_link"><a href="ord_indices.html"><img src="../next.gif" alt="ordered indices" border="0"><br>
  25 Ordered indices
  26 </a></div><br clear="all" style="clear: all;">
  27
  28 <hr>
  29
  30 <h2>Contents</h2>
  31
  32 <ul>
  33   <li><a href="#index_concepts">Index concepts</a></li>
  34   <li><a href="#complexity_signature">Complexity signature</a></li>
  35   <li><a href="#index_specification">Index specification</a></li>
  36   <li><a href="#indexed_by_synopsis">Header
  37     <code>"boost/multi_index/indexed_by.hpp"</code> synopsis</a>
  38     <ul>
  39       <li><a href="#indexed_by">Class template <code>indexed_by</code></a></li>
  40     </ul>
  41   </li>
  42   <li><a href="#tags">Tags</a></li>
  43   <li><a href="#tag_synopsis">Header
  44     <code>"boost/multi_index/tag.hpp"</code> synopsis</a>
  45     <ul>
  46       <li><a href="#tag">Class template <code>tag</code></a></li>
  47     </ul>
  48   </li>
  49   <li><a href="#index_catalog">Indices provided by Boost.MultiIndex</a>
  50     <ul>
  51       <li><a href="#key_based_indices">Key-based indices</a></li>
  52       <li><a href="#other_indices">Other types</a></li>
  53     </ul>
  54   </li>
  55   <li><a href="#views">Index views</a></li>
  56 </ul>
  57
  58 <h2><a name="index_concepts">Index concepts</a></h2>
  59
  60 <p>
  61 <code>multi_index_container</code> instantiations comprise one or more indices
  62 specified at compile time. Each index allows read/write access to the elements
  63 contained in a definite manner. For instance,
  64 <a href="ord_indices.html">ordered indices</a>
  65 provide a set-like interface to the elements, whereas
  66 <a href="seq_indices.html">sequenced indices</a> mimic the functionality
  67 of <code>std::list</code>.
  68 </p>
  69
  70 <p>
  71 Indices are not isolated objects, and so cannot be constructed on their
  72 own. Rather they are embedded into a <code>multi_index_container</code> as specified by
  73 means of an <a href="#index_specification">index specifier</a>. The name of
  74 the index class implementation proper is never directly exposed to the user, who
  75 has only access to the associated index specifier.
  76 </p>
  77
  78 <p>
  79 Insertion and erasing of elements are always performed through the
  80 appropriate interface of some index of the <code>multi_index_container</code>;
  81 these operations, however, do have an impact on all other indices as
  82 well: for instance, insertion through a given index may fail because
  83 there exists another index which bans the operation in order to preserve
  84 its invariant (like uniqueness of elements.) This circumstance, rather
  85 than being an obstacle, yields much of the power of Boost.MultiIndex:
  86 equivalent constructions based on manual composition of standard
  87 containers would have to add a fair amount of code in order to
  88 globally preserve the invariants of each container while guaranteeing
  89 that all of them are synchronized. The global operations performed
  90 in a joint manner among the various indices can be reduced to
  91 six primitives:
  92 <ul>
  93   <li>Copying,</li>
  94   <li>insertion of an element,</li>
  95   <li>hinted insertion, where a preexisting element is suggested in
  96     order to improve the efficiency of the operation,</li>
  97   <li>deletion of an element,</li>
  98   <li>replacement of the value of an element,
  99     which may trigger the rearrangement of this element in one or
 100     more indices, or the banning of the replacement,</li>
 101   <li>modification of an element, and its subsequent
 102     rearrangement/banning by the various indices.
 103 </ul>
 104 The last two primitives deserve some further explanation: in order to
 105 guarantee the invariants associated to each index (e.g. some definite
 106 ordering,) elements of a <code>multi_index_container</code> are not mutable.
 107 To overcome this restriction, indices expose member functions
 108 for replacement and modification which allow for the mutation of elements
 109 in a controlled fashion. Immutability of elements does not significantly
 110 impact the interfaces of ordered and hashed indices, as they are based upon
 111 those of associative and unordered associative containers, respectively,
 112 and these containers
 113 also have non-mutable elements; but it may come as a surprise when dealing
 114 with sequenced and random access indices, which are designed upon the functionality provided
 115 by <code>std::list</code>.
 116 </p>
 117
 118 <p>
 119 These global operations are not directly exposed to the user, but rather
 120 they are wrapped as appropriate by each index (for instance, ordered indices
 121 provide a set-like suite of insertion member functions, whereas sequenced
 122 and random access indices have <code>push_back</code> and <code>push_front</code>
 123 operations.) Boost.MultiIndex poses no particular conditions on
 124 the interface of indices, although each index provided satisfy the C++ requirements for
 125 standard containers to the maximum extent possible within the conceptual framework
 126 of the library.
 127 </p>
 128
 129 <h2><a name="complexity_signature">Complexity signature</a></h2>
 130
 131 <p>
 132 Some member functions of an index interface are implemented by
 133 global primitives from the list above. Complexity of these operations
 134 thus depends on all indices of a given <code>multi_index_container</code>, not just
 135 the currently used index.
 136 </p>
 137
 138 <p>
 139 In order to establish complexity estimates, an index is characterized
 140 by its <i>complexity signature</i>, consisting of the following
 141 associated functions on the number of elements:
 142 <ul>
 143   <li><code>c(n)</code>: copying,
 144   <li><code>i(n)</code>: insertion,
 145   <li><code>h(n)</code>: hinted insertion,
 146   <li><code>d(n)</code>: deletion,
 147   <li><code>r(n)</code>: replacement,
 148   <li><code>m(n)</code>: modifying.
 149 </ul>
 150
 151 </p>
 152 Each function yields the complexity estimate of the contribution of the index
 153 to the corresponding global primitive. Let us consider
 154 an instantiation of <code>multi_index_container</code>
 155 with <code>N</code> indices labelled <code>0</code>,...,<code>N-1</code>
 156 whose complexity signatures are
 157 (<code>c<sub>i</sub></code>,<code>i<sub>i</sub></code>,<code>h<sub>i</sub></code>,<code>d<sub>i</sub></code>,<code>r<sub>i</sub></code>,<code>m<sub>i</sub></code>);
 158 the insertion of an element in such a container is then of complexity
 159 <code>O(i<sub>0</sub>(n)+···+i<sub>N-1</sub>(n))</code> where <code>n</code>
 160 is the number of elements. To abbreviate notation, we adopt the
 161 following definitions:
 162 <ul>
 163   <li><code>C(n)=c<sub>0</sub>(n)+···+c<sub>N-1</sub>(n)</code>,</li>
 164   <li><code>I(n)=i<sub>0</sub>(n)+···+i<sub>N-1</sub>(n)</code>,</li>
 165   <li><code>H(n)=h<sub>0</sub>(n)+···+h<sub>N-1</sub>(n)</code>,</li>
 166   <li><code>D(n)=d<sub>0</sub>(n)+···+d<sub>N-1</sub>(n)</code>,</li>
 167   <li><code>R(n)=r<sub>0</sub>(n)+···+r<sub>N-1</sub>(n)</code>,</li>
 168   <li><code>M(n)=m<sub>0</sub>(n)+···+m<sub>N-1</sub>(n)</code>.</li>
 169 </ul>
 170 For instance, consider a <code>multi_index_container</code> with two ordered indices,
 171 for which <code>i(n)=log(n)</code>, and a sequenced index with <code>i(n)=1</code>
 172 (constant time insertion). Insertion of an element into this <code>multi_index_container</code>
 173 is then of complexity
 174 <blockquote>
 175 <code>O(I(n))=O(2*log(n)+1)=O(log(n))</code>.
 176 </blockquote>
 177 </p>
 178
 179 <h2><a name="index_specification">Index specification</a></h2>
 180
 181 <p>
 182 Index specifiers are passed as instantiation arguments to
 183 <code>multi_index_container</code> and provide the information needed to incorporate
 184 the corresponding indices. Future releases of Boost.MultiIndex may allow for
 185 specification of user-defined indices. Meanwhile, the requirements for an index
 186 specifier remain implementation defined. Currently, Boost.MultiIndex provides the
 187 index specifiers
 188 <ul>
 189   <li><a href="ord_indices.html#unique_non_unique"><code>ordered_unique</code> and
 190     <code>ordered_non_unique</code></a> for
 191     <a href="ord_indices.html">ordered indices</a>,</li>
 192   <li><a href="rnk_indices.html#unique_non_unique"><code>ranked_unique</code> and
 193     <code>ranked_non_unique</code></a> for
 194     <a href="rnk_indices.html">ranked indices</a>,</li>
 195   <li><a href="hash_indices.html#unique_non_unique"><code>hashed_unique</code> and
 196     <code>hashed_non_unique</code></a> for
 197     <a href="hash_indices.html">hashed indices</a>,</li>
 198   <li><a href="seq_indices.html#sequenced"><code>sequenced</code></a> for
 199     <a href="seq_indices.html">sequenced indices</a>,</li>
 200   <li>and <a href="rnd_indices.html#random_access"><code>random_access</code></a> for
 201     <a href="rnd_indices.html">random access indices</a>.</li>
 202 </ul>
 203 </p>
 204
 205 <h2>
 206 <a name="indexed_by_synopsis">Header
 207 <a href="../../../../boost/multi_index/indexed_by.hpp">
 208 <code>"boost/multi_index/indexed_by.hpp"</code></a> synopsis</a></h2>
 209
 210 <blockquote><pre>
 211 <span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
 212
 213 <span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
 214
 215 <span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>T0</span><span class=special>,...,</span><span class=keyword>typename</span> <span class=identifier>Tn</span><span class=special>&gt;</span>
 216 <span class=keyword>struct</span> <span class=identifier>indexed_by</span><span class=special>;</span>
 217
 218 <span class=special>}</span> <span class=comment>// namespace boost::multi_index</span>
 219
 220 <span class=special>}</span> <span class=comment>// namespace boost</span>
 221 </pre></blockquote>
 222
 223 <h3><a name="indexed_by">Class template <code>indexed_by</code></a></h3>
 224
 225 <p>
 226 <code>indexed_by</code> is a model of
 227 <a href="../../../../libs/mpl/doc/refmanual/random-access-sequence.html">
 228 <code>MPL Random Access Sequence</code></a> and
 229 <a href="../../../../libs/mpl/doc/refmanual/extensible-sequence.html">
 230 <code>MPL Extensible Sequence</code></a> meant to be used to specify a
 231 compile-time list of indices as the <code>IndexSpecifierList</code> of
 232 <code>multi_index_container</code>.
 233 </p>
 234
 235 <blockquote><pre>
 236 <span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>T0</span><span class=special>,...,</span><span class=keyword>typename</span> <span class=identifier>Tn</span><span class=special>&gt;</span>
 237 <span class=keyword>struct</span> <span class=identifier>indexed_by</span><span class=special>;</span>
 238 </pre></blockquote>
 239
 240 <p>
 241 Each user-provided element of <code>indexed_list</code> must be an index
 242 specifier. At least an element must be provided. The maximum number of elements
 243 of an <code>indexed_by</code> sequence is implementation defined.
 244 </p>
 245
 246 <h2><a name="tags">Tags</a></h2>
 247
 248 <p>
 249 Tags are just conventional types used as mnemonics for indices of an
 250 <code>multi_index_container</code>, as for instance in member function <code>get</code>.
 251 Each index can have none, one or more tags associated. The way tags are assigned
 252 to a given index is dependent on the particular index specifier. However,
 253 for convenience all indices of Boost.MultiIndex support tagging through the
 254 class template <a href="#tag"><code>tag</code></a>.
 255 </p>
 256
 257 <h2>
 258 <a name="tag_synopsis">Header
 259 <a href="../../../../boost/multi_index/tag.hpp">
 260 <code>"boost/multi_index/tag.hpp"</code></a> synopsis</a></h2>
 261
 262 <blockquote><pre>
 263 <span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
 264
 265 <span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
 266
 267 <span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>T0</span><span class=special>,...,</span><span class=keyword>typename</span> <span class=identifier>Tn</span><span class=special>&gt;</span>
 268 <span class=keyword>struct</span> <span class=identifier>tag</span><span class=special>;</span>
 269
 270 <span class=special>}</span> <span class=comment>// namespace boost::multi_index</span>
 271
 272 <span class=special>}</span> <span class=comment>// namespace boost</span>
 273 </pre></blockquote>
 274
 275 <h3><a name="tag">Class template <code>tag</code></a></h3>
 276
 277 <p>
 278 <code>tag</code> is a typelist construct used to specify a compile-time
 279 sequence of tags to be assigned to an index in instantiation time.
 280 </p>
 281
 282 <blockquote><pre>
 283 <span class=keyword>template</span><span class=special>&lt;</span><span class=keyword>typename</span> <span class=identifier>T0</span><span class=special>,...,</span><span class=keyword>typename</span> <span class=identifier>Tn</span><span class=special>&gt;</span>
 284 <span class=keyword>struct</span> <span class=identifier>tag</span>
 285 <span class=special>{</span>
 286   <span class=keyword>typedef</span> <b>implementation defined</b> <span class=identifier>type</span><span class=special>;</span>
 287 <span class=special>};</span>
 288 </pre></blockquote>
 289
 290 <p>
 291 Elements of <code>tag</code> can be any type, though the user is expected
 292 to provide classes with mnemonic names. Duplicate elements are not allowed.
 293 The maximum number of elements of a <code>tag</code> instantiation is
 294 implementation defined.
 295 The nested
 296 <code>type</code> is a model of
 297 <a href="../../../../libs/mpl/doc/refmanual/random-access-sequence.html">
 298 <code>MPL Random Access Sequence</code></a> and
 299 <a href="../../../../libs/mpl/doc/refmanual/extensible-sequence.html">
 300 <code>MPL Extensible Sequence</code></a> containing the types <code>T0</code>, ... ,
 301 <code>Tn</code> in the same order as specified.
 302 </p>
 303
 304 <h2><a name="index_catalog">Indices provided by Boost.MultiIndex</a></h2>
 305
 306
 307 <h3><a name="key_based_indices">Key-based indices</a></h3>
 308
 309 <p>
 310 Indices of this type are organized around <i>keys</i> obtained from the
 311 elements, as described in the <a href="key_extraction.html">key extraction
 312 reference</a>.
 313 <ul>
 314   <li><a href="ord_indices.html">Ordered indices</a> sort the elements
 315     on the key and provide fast lookup capabilites.</li>
 316   <li><a href="rnk_indices.html">Ranked indices</a> are a variation of
 317     ordered indices providing extra operations based on
 318     <i>rank</i>, the numerical position of an element
 319     in the sequence.</li>
 320   <li><a href="hash_indices.html">Hashed indices</a> offer high
 321     efficiency access through hashing techniques.</li>
 322 </ul>
 323 </p>
 324
 325 <h3><a name="other_indices">Other types</a></h3>
 326
 327 <p>
 328 <ul>
 329   <li><a href="seq_indices.html">Sequenced indices</a> allow to arrange
 330     elements as in a bidirectional list.</li>
 331   <li><a href="rnd_indices.html">Random access indices</a> provide
 332     constant time positional access and free ordering of elements.</li>
 333 </ul>
 334 </p>
 335
 336 <h2><a name="views">Index views</a></h2>
 337
 338 <p>
 339 The following concept is used by the rearrange facilities of non key-based
 340 indices. Given an index <code>i</code> of type <code>Index</code>, a <i>view
 341 of <code>i</code></i> is any range [<code>first</code>,<code>last</code>)
 342 where <code>first</code> and <code>last</code> are input iterators such that
 343 <ol>
 344   <li>the associated value type of <code>Iterator</code> is convertible
 345     to <code>const Index::value_type&amp;</code>
 346   </li>
 347   <li>and each of the elements of <code>i</code> appears exactly once in
 348     [<code>first</code>,<code>last</code>).
 349   </li>
 350 </ol>
 351 Note that the view refers to the actual elements of <code>i</code>, not to
 352 copies of them. Additionally, a view is said to be <i>free</i> if its traversal
 353 order is not affected by changes in the traversal order of <code>i</code>.
 354 Examples of free views are:
 355 <ul>
 356   <li>[<code>c.begin()</code>,<code>c.end()</code>), where <code>c</code> is
 357     any container of reference wrappers (from
 358     <a href="../../../../doc/html/ref.html">Boost.Ref</a>) to the elements
 359     of <code>i</code> containing exactly one reference to every element.
 360   </li>
 361   <li>[<code>i'.begin()</code>,<code>i'.end()</code>), where <code>i'</code> is
 362     any index belonging to the same <code>multi_index_container</code>
 363     as <code>i</code>, except <code>i</code> itself.
 364   </li>
 365   <li>
 366     Any range which is a permutation of the ones described above, as for
 367     instance [<code>c.rbegin()</code>,<code>c.rend()</code>), or
 368     ranges obtained from the former with the aid of
 369     <a href="../../../../libs/iterator/doc/permutation_iterator.html">
 370     <code>permutation_iterator</code></a> from Boost.Iterator.
 371   </li>
 372 </ul>
 373 </p>
 374
 375 <hr>
 376
 377 <div class="prev_link"><a href="multi_index_container.html"><img src="../prev.gif" alt="multi_index_container reference" border="0"><br>
 378 <code>multi_index_container</code> reference
 379 </a></div>
 380 <div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex reference" border="0"><br>
 381 Boost.MultiIndex reference
 382 </a></div>
 383 <div class="next_link"><a href="ord_indices.html"><img src="../next.gif" alt="ordered indices" border="0"><br>
 384 Ordered indices
 385 </a></div><br clear="all" style="clear: all;">
 386
 387 <br>
 388
 389 <p>Revised April 19th 2015</p>
 390
 391 <p>&copy; Copyright 2003-2015 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;oz.
 392 Distributed under the Boost Software
 393 License, Version 1.0. (See accompanying file <a href="../../../../LICENSE_1_0.txt">
 394 LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
 395 http://www.boost.org/LICENSE_1_0.txt</a>)
 396 </p>
 397
 398 </body>
 399 </html>