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
|
<!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 - Index reference</title>
<link rel="stylesheet" href="../style.css" type="text/css">
</head>
<body>
<h1><img src="../../../../boost.png" alt="boost.png (6897 bytes)" align=
"middle" width="277" height="86">Boost.MultiIndex Index reference</h1>
<div class="prev_link"><a href="multi_index_container.html"><img src="../prev.gif" alt="multi_index_container reference" border="0"><br>
<code>multi_index_container</code> reference
</a></div>
<div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex reference" border="0"><br>
Boost.MultiIndex reference
</a></div>
<div class="next_link"><a href="ord_indices.html"><img src="../next.gif" alt="ordered indices" border="0"><br>
Ordered indices
</a></div><br clear="all" style="clear: all;">
<hr>
<h2>Contents</h2>
<ul>
<li><a href="#index_concepts">Index concepts</a></li>
<li><a href="#complexity_signature">Complexity signature</a></li>
<li><a href="#index_specification">Index specification</a></li>
<li><a href="#indexed_by_synopsis">Header
<code>"boost/multi_index/indexed_by.hpp"</code> synopsis</a>
<ul>
<li><a href="#indexed_by">Class template <code>indexed_by</code></a></li>
</ul>
</li>
<li><a href="#tags">Tags</a></li>
<li><a href="#tag_synopsis">Header
<code>"boost/multi_index/tag.hpp"</code> synopsis</a>
<ul>
<li><a href="#tag">Class template <code>tag</code></a></li>
</ul>
</li>
<li><a href="#index_catalog">Indices provided by Boost.MultiIndex</a>
<ul>
<li><a href="#key_based_indices">Key-based indices</a></li>
<li><a href="#other_indices">Other types</a></li>
</ul>
</li>
</ul>
<h2><a name="index_concepts">Index concepts</a></h2>
<p>
<code>multi_index_container</code> instantiations comprise one or more indices
specified at compile time. Each index allows read/write access to the elements
contained in a definite manner. For instance,
<a href="ord_indices.html">ordered indices</a>
provide a set-like interface to the elements, whereas
<a href="seq_indices.html">sequenced indices</a> mimic the functionality
of <code>std::list</code>.
</p>
<p>
Indices are not isolated objects, and so cannot be constructed on their
own. Rather they are embedded into a <code>multi_index_container</code> as specified by
means of an <a href="#index_specification">index specifier</a>. The name of
the index class implementation proper is never directly exposed to the user, who
has only access to the associated index specifier.
</p>
<p>
Insertion and erasing of elements are always performed through the
appropriate interface of some index of the <code>multi_index_container</code>;
these operations, however, do have an impact on all other indices as
well: for instance, insertion through a given index may fail because
there exists another index which bans the operation in order to preserve
its invariant (like uniqueness of elements.) This circumstance, rather
than an obstacle, yields much of the power of Boost.MultiIndex:
equivalent constructions based on manual composition of standard
containers would have to add a fair amount of code in order to
globally preserve the invariants of each container while guaranteeing
that all of them are synchronized. The global operations performed
in a joint manner among the various indices can be reduced to
six primitives:
<ul>
<li>Copying,</li>
<li>insertion of an element,</li>
<li>hinted insertion, where a preexisting element is suggested in
order to improve the efficiency of the operation,</li>
<li>deletion of an element,</li>
<li>replacement of the value of an element,
which may trigger the rearrangement of this element in one or
more indices, or the banning of the replacement,</li>
<li>modification of an element, and its subsequent
rearrangement/banning by the various indices.
</ul>
The last two primitives deserve some further explanation: in order to
guarantee the invariants associated to each index (e.g. some definite
ordering,) elements of a <code>multi_index_container</code> are not mutable.
To overcome this restriction, indices expose member functions
for updating and modifying, which allow for the mutation of elements
in a controlled fashion. Immutability of elements does not significantly
impact the interface of ordered indices, as it is based upon that of
<code>std::set</code> and <code>std:multiset</code>, and these containers
also have non-mutable elements; but it may come as a surprise when dealing
with sequenced indices, which are designed upon the functionality provided
by <code>std::list</code>.
</p>
<p>
These global operations are not directly exposed to the user, but rather
they are wrapped as appropriate by each index (for instance, ordered indices
provide a set-like suite of insertion member functions, whereas sequenced
indices do have <code>push_back</code> and <code>push_front</code>
operations.) Boost.MultiIndex poses no particular conditions on
the interface of indices, save that they must model
<a href="http://www.sgi.com/tech/stl/Container.html">
<code>Container</code></a> (without the requirement of being
<a href="http://www.sgi.com/tech/stl/Assignable.html">
<code>Assignable</code></a>.)
</p>
<h2><a name="complexity_signature">Complexity signature</a></h2>
<p>
Some member functions of an index interface are implemented by
global primitives from the list above. Complexity of these operations
thus depends on all indices of a given <code>multi_index_container</code>, not just
the currently used index.
</p>
<p>
In order to establish complexity estimates, an index is characterized
by its <i>complexity signature</i>, consisting of the following
associated functions on the number of elements:
<ul>
<li><code>c(n)</code>: copying,
<li><code>i(n)</code>: insertion,
<li><code>h(n)</code>: hinted insertion,
<li><code>d(n)</code>: deletion,
<li><code>r(n)</code>: replacement,
<li><code>m(n)</code>: modifying.
</ul>
</p>
Each function yields the complexity estimate of the contribution of the index
to the corresponding global primitive. Let us consider
an instantiation of <code>multi_index_container</code>
with <code>N</code> indices labelled <code>0</code>,...,<code>N-1</code>
whose complexity signatures are
(<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>);
the insertion of an element in such a container is then of complexity
<code>O(i<sub>0</sub>(n)++i<sub>N-1</sub>(n))</code> where <code>n</code>
is the number of elements. To abbreviate notation, we adopt the
following definitions:
<ul>
<li><code>C(n)=c<sub>0</sub>(n)++c<sub>N-1</sub>(n)</code>,</li>
<li><code>I(n)=i<sub>0</sub>(n)++i<sub>N-1</sub>(n)</code>,</li>
<li><code>H(n)=h<sub>0</sub>(n)++h<sub>N-1</sub>(n)</code>,</li>
<li><code>D(n)=d<sub>0</sub>(n)++d<sub>N-1</sub>(n)</code>,</li>
<li><code>R(n)=r<sub>0</sub>(n)++r<sub>N-1</sub>(n)</code>,</li>
<li><code>M(n)=m<sub>0</sub>(n)++m<sub>N-1</sub>(n)</code>.</li>
</ul>
For instance, consider a <code>multi_index_container</code> with two ordered indices,
for which <code>i(n)=log(n)</code>, and a sequenced index with <code>i(n)=1</code>
(constant time insertion). Insertion of an element into this <code>multi_index_container</code>
is then of complexity
<blockquote>
<code>O(I(n))=O(2*log(n)+1)=O(log(n))</code>.
</blockquote>
</p>
<h2><a name="index_specification">Index specification</a></h2>
<p>
Index specifiers are passed as instantiation arguments to
<code>multi_index_container</code> and provide the information needed to incorporate
the corresponding indices. Future releases of Boost.MultiIndex may allow for
specification of user-defined indices. Meanwhile, the requirements for an index
specifier remain implementation defined. Currently, Boost.MultiIndex provides the
index specifiers
<ul>
<li><a href="ord_indices.html#unique_non_unique"><code>ordered_unique</code> and
<code>ordered_non_unique</code></a> for
<a href="ord_indices.html">ordered indices</a>,</li>
<li><a href="hash_indices.html#unique_non_unique"><code>hashed_unique</code> and
<code>hashed_non_unique</code></a> for
<a href="hash_indices.html">hashed indices</a>,</li>
<li>and <a href="seq_indices.html#sequenced"><code>sequenced</code></a> for
<a href="seq_indices.html">sequenced indices</a>.</li>
</ul>
</p>
<h2>
<a name="indexed_by_synopsis">Header
<a href="../../../../boost/multi_index/indexed_by.hpp">
<code>"boost/multi_index/indexed_by.hpp"</code></a> synopsis</a></h2>
<blockquote><pre>
<span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
<span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
<span class=keyword>template</span><span class=special><</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>></span>
<span class=keyword>struct</span> <span class=identifier>indexed_by</span><span class=special>;</span>
<span class=special>}</span> <span class=comment>// namespace boost::multi_index</span>
<span class=special>}</span> <span class=comment>// namespace boost</span>
</pre></blockquote>
<h3><a name="indexed_by">Class template <code>indexed_by</code></a></h3>
<p>
<code>indexed_by</code> is a model of
<a href="../../../../libs/mpl/doc/refmanual/random-access-sequence.html">
<code>MPL Random Access Sequence</code></a> and
<a href="../../../../libs/mpl/doc/refmanual/extensible-sequence.html">
<code>MPL Extensible Sequence</code></a> meant to be used to specify a
compile-time list of indices as the <code>IndexSpecifierList</code> of
<code>multi_index_container</code>.
</p>
<blockquote><pre>
<span class=keyword>template</span><span class=special><</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>></span>
<span class=keyword>struct</span> <span class=identifier>indexed_by</span><span class=special>;</span>
</pre></blockquote>
<p>
Each user-provided element of <code>indexed_list</code> must be an index
specifier. At least an element must be provided. The maximum number of elements
of an <code>indexed_by</code> sequence is implementation defined.
</p>
<h2><a name="tags">Tags</a></h2>
<p>
Tags are just conventional types used as mnemonics for indices of an
<code>multi_index_container</code>, as for instance in member function <code>get</code>.
Each index can have none, one or more tags associated. The way tags are assigned
to a given index is dependent on the particular index specifier. However,
for convenience all indices of Boost.MultiIndex support tagging through the
class template <a href="#tag"><code>tag</code></a>.
</p>
<h2>
<a name="tag_synopsis">Header
<a href="../../../../boost/multi_index/tag.hpp">
<code>"boost/multi_index/tag.hpp"</code></a> synopsis</a></h2>
<blockquote><pre>
<span class=keyword>namespace</span> <span class=identifier>boost</span><span class=special>{</span>
<span class=keyword>namespace</span> <span class=identifier>multi_index</span><span class=special>{</span>
<span class=keyword>template</span><span class=special><</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>></span>
<span class=keyword>struct</span> <span class=identifier>tag</span><span class=special>;</span>
<span class=special>}</span> <span class=comment>// namespace boost::multi_index</span>
<span class=special>}</span> <span class=comment>// namespace boost</span>
</pre></blockquote>
<h3><a name="tag">Class template <code>tag</code></a></h3>
<p>
<code>tag</code> is a typelist construct used to specify a compile-time
sequence of tags to be assigned to an index in instantiation time.
</p>
<blockquote><pre>
<span class=keyword>template</span><span class=special><</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>></span>
<span class=keyword>struct</span> <span class=identifier>tag</span><span class=special>;</span>
</pre></blockquote>
<p>
Elements of <code>tag</code> can be any type, though the user is expected
to provide classes with mnemonic names. Duplicate elements are not allowed.
The maximum number of elements of a <code>tag</code> instantiation is
implementation defined.
</p>
<h2><a name="index_catalog">Indices provided by Boost.MultiIndex</a></h2>
<h3><a name="key_based_indices">Key-based indices</a></h3>
<p>
Indices of this type are organized around <i>keys</i> obtained from the
elements, as described in the <a href="key_extraction.html">key extraction
reference</a>.
<ul>
<li><a href="ord_indices.html">Ordered indices</a> sort the elements
on the key and provide fast lookup capabilites.</li>
<li><a href="hash_indices.html">Hashed indices</a> offer high
efficiency access through hashing techniques.</li>
</ul>
</p>
<h3><a name="other_indices">Other types</a></h3>
<p>
<ul>
<li><a href="seq_indices.html">Sequenced indices</a> allow to arrange
elements as in a bidirectional list. </li>
</ul>
</p>
<hr>
<div class="prev_link"><a href="multi_index_container.html"><img src="../prev.gif" alt="multi_index_container reference" border="0"><br>
<code>multi_index_container</code> reference
</a></div>
<div class="up_link"><a href="index.html"><img src="../up.gif" alt="Boost.MultiIndex reference" border="0"><br>
Boost.MultiIndex reference
</a></div>
<div class="next_link"><a href="ord_indices.html"><img src="../next.gif" alt="ordered indices" border="0"><br>
Ordered indices
</a></div><br clear="all" style="clear: all;">
<br>
<p>Revised May 30th 2005</p>
<p>© Copyright 2003-2005 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>
|
