]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | [/license |
2 | ||
3 | Boost.Bimap | |
4 | ||
5 | Copyright (c) 2006-2007 Matias Capeletto | |
6 | ||
7 | Distributed under the Boost Software License, Version 1.0. | |
8 | (See accompanying file LICENSE_1_0.txt or copy at | |
9 | http://www.boost.org/LICENSE_1_0.txt) | |
10 | ||
11 | ] | |
12 | ||
13 | [/ QuickBook Document version 1.4 ] | |
14 | ||
15 | [section Bimap Reference] | |
16 | ||
17 | [section View concepts] | |
18 | ||
19 | `bimap` instantiations comprise two side views and an view of the relation | |
20 | specified at compile time. Each view allows read-write access to the elements contained | |
21 | in a definite manner, mathing an STL container signature. | |
22 | ||
23 | Views are not isolated objects and so cannot be constructed on their | |
24 | own; rather they are an integral part of a `bimap`. The name of the view | |
25 | class implementation proper is never directly exposed to the user, who | |
26 | has access only to the associated view type specifier. | |
27 | ||
28 | Insertion and deletion of elements are always performed through the | |
29 | appropriate interface of any of the three views of the `bimap`; these | |
30 | operations do, however, have an impact on all other views as well: for | |
31 | instance, insertion through a given view may fail because there exists | |
32 | another view that forbids the operation in order to preserve its | |
33 | invariant (such as uniqueness of elements). The global operations | |
34 | performed jointly in the any view can be reduced to six primitives: | |
35 | ||
36 | * copying | |
37 | * insertion of an element | |
38 | * hinted insertion, where a pre-existing element is suggested in order to improve | |
39 | the efficiency of the operation | |
40 | * deletion of an element | |
41 | * replacement of the value of an element, which may trigger the | |
42 | rearrangement of this element in one or more views, or may forbid the | |
43 | replacement | |
44 | * modification of an element, and its subsequent | |
45 | rearrangement/banning by the various views | |
46 | ||
47 | The last two primitives deserve some further explanation: in order to | |
48 | guarantee the invariants associated to each view (e.g. some definite | |
49 | ordering) elements of a `bimap` are not mutable. To overcome this | |
50 | restriction, the views expose member functions for updating and | |
51 | modifying, which allows for the mutation of elements in a controlled | |
52 | fashion. | |
53 | ||
54 | [endsect] | |
55 | ||
56 | [#complexity_signature_explanation] | |
57 | ||
58 | [section Complexity signature] | |
59 | ||
60 | Some member functions of a view interface are implemented by global | |
61 | primitives from the above list. The complexity of these operations thus | |
62 | depends on all views of a given `bimap`, not just the currently used view. | |
63 | ||
64 | In order to establish complexity estimates, a view is characterised by | |
65 | its complexity signature, consisting of the following associated | |
66 | functions on the number of elements: | |
67 | ||
68 | * `c(n)`: copying | |
69 | * `i(n)`: insertion | |
70 | * `h(n)`: hinted insertion | |
71 | * `d(n)`: deletion | |
72 | * `r(n)`: replacement | |
73 | * `m(n)`: modifying | |
74 | ||
75 | If the collection type of the relation is `left_based` or `right_based`, and we use | |
76 | an `l` subscript to denote the left view and an `r` for the right view, then | |
77 | the insertion of an element in such a container is of complexity | |
78 | `O(i_l(n)+i_r(n))`, where n is the number of elements. If the collection type of | |
79 | relation is not side-based, then there is an additional term to add that | |
80 | is contributed by the collection type of relation view. Using `a` to denote the | |
81 | above view, the complexity of insertion will now be | |
82 | `O(i_l(n)+i_r(n)+i_a(n))`. To abbreviate the notation, we adopt the | |
83 | following definitions: | |
84 | ||
85 | * `C(n) = c_l(n) + c_r(n) [ + c_a(n) ]` | |
86 | * `I(n) = i_l(n) + i_r(n) [ + i_a(n) ]` | |
87 | * `H(n) = h_l(n) + h_r(n) [ + h_a(n) ]` | |
88 | * `D(n) = d_l(n) + d_r(n) [ + d_a(n) ]` | |
89 | * `R(n) = r_l(n) + r_r(n) [ + r_a(n) ]` | |
90 | * `M(n) = m_l(n) + m_r(n) [ + m_a(n) ]` | |
91 | ||
92 | [endsect] | |
93 | ||
94 | [section Set type specification] | |
95 | ||
96 | Set type specifiers are passed as instantiation arguments to `bimap` and | |
97 | provide the information needed to incorporate the corresponding views. | |
98 | Currently, Boost.Bimap provides the collection type specifiers. The ['side collection type] | |
99 | specifiers define the constraints of the two map views of the | |
100 | bimap. The ['collection type of relation] specifier defines the main set view | |
101 | constraints. If `left_based` (the default parameter) or `right_based` is | |
102 | used, then the collection type of relation will be based on the left or right | |
103 | collection type correspondingly. | |
104 | ||
105 | [table | |
106 | [[Side collection type ][Collection type of relation ][Include ]] | |
107 | [[`set_of` ][`set_of_relation` ][`boost/bimap/set_of.hpp` ]] | |
108 | [[`multiset_of` ][`multiset_of_relation` ][`boost/bimap/multiset_of.hpp` ]] | |
109 | [[`unordered_set_of` ][`unordered_set_of_relation` ][`boost/bimap/unordered_set_of.hpp` ]] | |
110 | [[`unordered_multiset_of` ][`unordered_multiset_of_relation`][`boost/bimap/unordered_multiset_of.hpp` ]] | |
111 | [[`list_of` ][`list_of_relation` ][`boost/bimap/list_of.hpp` ]] | |
112 | [[`vector_of` ][`vector_of_relation` ][`boost/bimap/vector_of.hpp` ]] | |
113 | [[`unconstrained_set_of` ][`unconstrained_set_of_relation` ][`boost/bimap/unconstrained_set_of.hpp` ]] | |
114 | [[ ][`left_based` ][`boost/bimap/bimap.hpp` ]] | |
115 | [[ ][`right_based` ][`boost/bimap/bimap.hpp` ]] | |
116 | ] | |
117 | ||
118 | [endsect] | |
119 | ||
120 | [section Tags] | |
121 | ||
122 | Tags are just conventional types used as mnemonics for the types stored | |
123 | in a `bimap`. Boost.Bimap uses the tagged idiom to let the user specify | |
124 | this tags. | |
125 | ||
126 | [endsect] | |
127 | ||
128 | [section Header "boost/bimap/bimap.hpp" synopsis] | |
129 | ||
130 | namespace boost { | |
131 | namespace bimaps { | |
132 | ||
133 | template< class Type, typename Tag > | |
134 | struct tagged; | |
135 | ||
136 | // bimap template class | |
137 | ||
138 | template | |
139 | < | |
140 | class LeftCollectionType, class RightCollectionType, | |
141 | ||
142 | class AdditionalParameter_1 = detail::not_specified, | |
143 | class AdditionalParameter_2 = detail::not_specified | |
144 | > | |
145 | class bimap ``['- implementation defined { : public SetView } -]`` | |
146 | { | |
147 | public: | |
148 | ||
149 | // Metadata | |
150 | ||
151 | typedef ``['-unspecified-]`` left_tag; | |
152 | typedef ``['-unspecified-]`` left_map; | |
153 | ||
154 | typedef ``['-unspecified-]`` right_tag; | |
155 | typedef ``['-unspecified-]`` right_map; | |
156 | ||
157 | // Shortcuts | |
158 | // typedef -side-_map::-type- -side-_-type-; | |
159 | ||
160 | typedef ``['-unspecified-]`` info_type; | |
161 | ||
162 | // Map views | |
163 | ||
164 | left_map left; | |
165 | right_map right; | |
166 | ||
167 | // Constructors | |
168 | ||
169 | bimap(); | |
170 | ||
171 | template< class InputIterator > | |
172 | bimap(InputIterator first,InputIterator last); | |
173 | ||
174 | bimap(const bimap &); | |
175 | ||
176 | bimap& operator=(const bimap& b); | |
177 | ||
178 | // Projection of iterators | |
179 | ||
180 | template< class IteratorType > | |
181 | left_iterator project_left(IteratorType iter); | |
182 | ||
183 | template< class IteratorType > | |
184 | left_const_iterator project_left(IteratorType iter) const; | |
185 | ||
186 | template< class IteratorType > | |
187 | right_iterator project_right(IteratorType iter); | |
188 | ||
189 | template< class IteratorType > | |
190 | right_const_iterator project_right(IteratorType iter) const; | |
191 | ||
192 | template< class IteratorType > | |
193 | iterator project_up(IteratorType iter); | |
194 | ||
195 | template< class IteratorType > | |
196 | const_iterator project_up(IteratorType iter) const; | |
197 | ||
198 | // Support for tags | |
199 | ||
200 | template< class Tag > | |
201 | struct map_by; | |
202 | ||
203 | template< class Tag > | |
204 | map_by<Tag>::type by(); | |
205 | ||
206 | template< class Tag > | |
207 | const map_by<Tag>::type & by() const; | |
208 | ||
209 | template< class Tag, class IteratorType > | |
210 | map_by<Tag>::iterator project(IteratorType iter); | |
211 | ||
212 | template< class Tag, class IteratorType > | |
213 | map_by<Tag>::const_iterator project(IteratorType iter) const | |
214 | ||
215 | }; | |
216 | ||
217 | ||
218 | } // namespace bimap | |
219 | } // namespace boost | |
220 | ||
221 | ||
222 | [/ | |
223 | // Metafunctions for a bimap | |
224 | ||
225 | template< class Tag, class Bimap > struct value_type_by; | |
226 | template< class Tag, class Bimap > struct key_type_by; | |
227 | template< class Tag, class Bimap > struct data_type_by; | |
228 | template< class Tag, class Bimap > struct iterator_type_by; | |
229 | template< class Tag, class Bimap > struct const_iterator_type_by; | |
230 | template< class Tag, class Bimap > struct reverse_iterator_type_by; | |
231 | template< class Tag, class Bimap > struct const_reverse_iterator_type_by; | |
232 | template< class Tag, class Bimap > struct local_iterator_type_by; | |
233 | template< class Tag, class Bimap > struct const_local_iterator_type_by; | |
234 | ||
235 | // Functions for a bimap | |
236 | ||
237 | template<class Tag, class Relation> | |
238 | result_of::map_by< Tag, Bimap>::type map_by(Bimap &); | |
239 | ||
240 | // Metafunctions for a relation | |
241 | ||
242 | template< class Tag, class Relation > struct value_type_of; | |
243 | template< class Tag, class Relation > struct pair_type_by; | |
244 | ||
245 | // Functions for a relation | |
246 | ||
247 | template<class Tag, class Relation> | |
248 | result_of::get< Tag, Relation>::type get(Relation &r); | |
249 | ||
250 | template<class Tag, class Relation> | |
251 | result_of::pair_by< Tag, Relation>::type pair_by(Relation &); | |
252 | ||
253 | ] | |
254 | ||
255 | [endsect] | |
256 | ||
257 | [section Class template bimap] | |
258 | ||
259 | This is the main component of Boost.Bimap. | |
260 | ||
261 | [section Complexity] | |
262 | ||
263 | In the descriptions of the operations of `bimap`, we adopt the scheme | |
264 | outlined in the complexity signature section. | |
265 | ||
266 | [endsect] | |
267 | ||
268 | [section Instantiation types] | |
269 | ||
270 | `bimap` is instantiated with the following types: | |
271 | ||
272 | # LeftCollectionType and RightCollectionType are collection type specifications | |
273 | optionally tagged, or any type optionally tagged, in which case that | |
274 | side acts as a set. | |
275 | # AdditionalParameter_{1/2} can be any ordered subset of: | |
276 | * CollectionTypeOfRelation specification | |
277 | * Allocator | |
278 | ||
279 | [endsect] | |
280 | ||
281 | [section Nested types] | |
282 | ||
283 | left_tag, right_tag | |
284 | ||
285 | [: Tags for each side of the bimap. If the user has not specified any tag the | |
286 | tags default to `member_at::left` and `member_at::right`. | |
287 | ] | |
288 | ||
289 | left_key_type, right_key_type | |
290 | ||
291 | [: Key type of each side. In a `bimap<A,B> ` `left_key_type` is `A` and | |
292 | `right_key_type` is `B`. | |
293 | If there are tags, it is better to use: `Bimap::map_by<Tag>::key_type`. | |
294 | ] | |
295 | ||
296 | left_data_type, right_data_type | |
297 | ||
298 | [: Data type of each side. In a bimap<A,B> left_key_type is B and | |
299 | right_key_type is A. | |
300 | If there are tags, it is better to use: `Bimap::map_by<Tag>::data_type`. | |
301 | ] | |
302 | ||
303 | left_value_type, right_value_type | |
304 | ||
305 | [: Value type used for the views. | |
306 | If there are tags, it is better to use: `Bimap::map_by<Tag>::value_type`. | |
307 | ] | |
308 | ||
309 | ||
310 | left_iterator, right_iterator | |
311 | left_const_iterator, right_const_iterator | |
312 | ||
313 | [: Iterators of the views. | |
314 | If there are tags, it is better to use: | |
315 | `Bimap::map_by<Tag>::iterator` and | |
316 | `Bimap::map_by<Tag>::const_iterator` | |
317 | ] | |
318 | ||
319 | ||
320 | left_map, right_map | |
321 | ||
322 | [: Map view type of each side. | |
323 | If there are tags, it is better to use: | |
324 | `Bimap::map_by<Tag>::type`. | |
325 | ] | |
326 | ||
327 | [endsect] | |
328 | ||
329 | [section Constructors, copy and assignment] | |
330 | ||
331 | bimap(); | |
332 | ||
333 | * [*Effects:] Constructs an empty `bimap`. | |
334 | * [*Complexity:] Constant. | |
335 | ||
336 | template<typename InputIterator> | |
337 | bimap(InputIterator first,InputIterator last); | |
338 | ||
339 | * [*Requires: ] `InputIterator` is a model of Input Iterator over elements of | |
340 | type `relation` or a type convertible to `relation`. last is reachable from `first`. | |
341 | * [*Effects:] Constructs an empty `bimap` and fills it with the elements in the range | |
342 | `[first,last)`. Insertion of each element may or may not succeed depending on | |
343 | acceptance by the collection types of the `bimap`. | |
344 | * [link complexity_signature_explanation | |
345 | [*Complexity:]] O(m*H(m)), where m is the number of elements in `[first,last)`. | |
346 | ||
347 | ||
348 | bimap(const bimap & x); | |
349 | ||
350 | * [*Effects:] Constructs a copy of x, copying its elements as well as its | |
351 | internal objects (key extractors, comparison objects, allocator.) | |
352 | * [*Postconditions:] `*this == x`. The order of the views of the `bimap` | |
353 | is preserved as well. | |
354 | * [*Complexity:] O(x.size()*log(x.size()) + C(x.size())) | |
355 | ||
356 | ||
357 | ~bimap() | |
358 | ||
359 | * [*Effects:] Destroys the `bimap` and all the elements contained. | |
360 | The order in which the elements are destroyed is not specified. | |
361 | * [*Complexity:] O(n). | |
362 | ||
363 | ||
364 | bimap& operator=(const bimap& x); | |
365 | ||
366 | * [*Effects:] Replaces the elements and internal objects of the `bimap` | |
367 | with copies from x. | |
368 | * [*Postconditions:] `*this==x`. The order on the views of the `bimap` | |
369 | is preserved as well. | |
370 | * [*Returns: ] `*this`. | |
371 | * [*Complexity:] O(n + x.size()*log(x.size()) + C(x.size())). | |
372 | * [*Exception safety:] Strong, provided the copy and assignment operations | |
373 | of the types of `ctor_args_list` do not throw. | |
374 | ||
375 | [/ | |
376 | allocator_type get_allocator() const; | |
377 | ||
378 | * [*Effects:] Returns a copy of the `allocator_type` object used to construct | |
379 | the `bimap`. | |
380 | * [*Complexity:] Constant. | |
381 | ] | |
382 | ||
383 | [endsect] | |
384 | ||
385 | [#reference_projection_operations] | |
386 | ||
387 | [section Projection operations] | |
388 | ||
389 | Given a `bimap` with views v1 and v2, we say than an v1-iterator | |
390 | it1 and an v2-iterator it2 are equivalent if: | |
391 | ||
392 | * `it1 == i1.end()` AND `it2 == i2.end()`, | |
393 | * OR `it1` and `it2` point to the same element. | |
394 | ||
395 | ||
396 | template< class IteratorType > | |
397 | left_iterator project_left(IteratorType iter); | |
398 | ||
399 | template< class IteratorType > | |
400 | left_const_iterator project_left(IteratorType iter) const; | |
401 | ||
402 | * [*Requires:] `IteratorType` is a bimap view iterator. it is a | |
403 | valid iterator of some view of `*this` (i.e. does not refer to some other | |
404 | `bimap`.) | |
405 | * [*Effects:] Returns a left map view iterator equivalent to `it`. | |
406 | * [*Complexity:] Constant. | |
407 | * [*Exception safety:] nothrow. | |
408 | ||
409 | ||
410 | template< class IteratorType > | |
411 | right_iterator project_right(IteratorType iter); | |
412 | ||
413 | template< class IteratorType > | |
414 | right_const_iterator project_right(IteratorType iter) const; | |
415 | ||
416 | * [*Requires:] `IteratorType` is a bimap view iterator. it is a | |
417 | valid iterator of some view of `*this` (i.e. does not refer to some other | |
418 | `bimap`.) | |
419 | * [*Effects:] Returns a right map view iterator equivalent to `it`. | |
420 | * [*Complexity:] Constant. | |
421 | * [*Exception safety:] nothrow. | |
422 | ||
423 | ||
424 | template< class IteratorType > | |
425 | iterator project_up(IteratorType iter); | |
426 | ||
427 | template< class IteratorType > | |
428 | const_iterator project_up(IteratorType iter) const; | |
429 | ||
430 | * [*Requires:] `IteratorType` is a bimap view iterator. it is a | |
431 | valid iterator of some view of `*this` (i.e. does not refer to some other | |
432 | `bimap`.) | |
433 | * [*Effects:] Returns a collection of relations view iterator equivalent to `it`. | |
434 | * [*Complexity:] Constant. | |
435 | * [*Exception safety:] nothrow. | |
436 | ||
437 | [endsect] | |
438 | ||
439 | [#reference_support_for_used_defined_names] | |
440 | ||
441 | [section Support for user defined names] | |
442 | ||
443 | template< class Tag > | |
444 | struct map_by; | |
445 | ||
446 | * `map_by<Tag>::type` yields the type of the map view tagged with `Tag`. | |
447 | `map_by<Tag>::`['-type name-] is the same as `map_by<Tag>::type::`['-type name-]. | |
448 | * [*Requires: ] `Tag` is a valid user defined name of the bimap. | |
449 | ||
450 | ||
451 | template< class Tag > | |
452 | map_by<Tag>::type by(); | |
453 | ||
454 | template< class Tag > | |
455 | const map_by<Tag>::type & by() const; | |
456 | ||
457 | ||
458 | * [*Requires: ] `Tag` is a valid user defined name of the bimap. | |
459 | * [*Effects:] Returns a reference to the map view tagged with `Tag` held by | |
460 | `*this`. | |
461 | * [*Complexity:] Constant. | |
462 | * [*Exception safety:] nothrow. | |
463 | ||
464 | ||
465 | template< class Tag, class IteratorType > | |
466 | map_by<Tag>::iterator project(IteratorType iter); | |
467 | ||
468 | template< class Tag, class IteratorType > | |
469 | map_by<Tag>::const_iterator project(IteratorType iter) const | |
470 | ||
471 | * [*Requires: ] `Tag` is a valid user defined name of the bimap. `IteratorType` | |
472 | is a bimap view iterator. it is a valid iterator of some view of `*this` | |
473 | (i.e. does not refer to some other `bimap`.) | |
474 | * [*Effects:] Returns a reference to the map view tagged with `Tag` held by | |
475 | `*this`. | |
476 | * [*Complexity:] Constant. | |
477 | * [*Exception safety:] nothrow. | |
478 | ||
479 | ||
480 | [endsect] | |
481 | ||
482 | [section Serialization] | |
483 | ||
484 | A `bimap` can be archived and retrieved by means of __BOOST_SERIALIZATION__. | |
485 | Boost.Bimap does not expose a public serialisation interface, as this is | |
486 | provided by Boost.Serialization itself. Both regular and XML archives | |
487 | are supported. | |
488 | ||
489 | Each of the set specifications comprising a given `bimap` contributes its | |
490 | own preconditions as well as guarantees on the retrieved containers. In describing | |
491 | these, the following concepts are used. A type `T` is ['serializable] | |
492 | (resp. XML-serializable) if any object of type `T` can be saved to an output | |
493 | archive (XML archive) and later retrieved from an input archive (XML archive) | |
494 | associated to the same storage. If `x`' of type `T` is loaded from the serialization | |
495 | information saved from another object x, we say that x' is a ['restored copy] of x. | |
496 | Given a __SGI_BINARY_PREDICATE__ `Pred` over `(T, T)`, and objects `p` and `q` of | |
497 | type `Pred`, we say that `q` is ['serialization-compatible] with `p` if | |
498 | ||
499 | * `p(x,y) == q(x`'`,y`'`)` | |
500 | ||
501 | for every `x` and `y` of type `T` and `x`' and `y`' being restored copies of `x` | |
502 | and `y`, respectively. | |
503 | ||
504 | [blurb [*Operation:] saving of a `bimap b` to an output archive | |
505 | (XML archive) ar.] | |
506 | ||
507 | * [*Requires:] Value is serializable (XML-serializable). Additionally, each | |
508 | of the views of b can impose other requirements. | |
509 | * [*Exception safety:] Strong with respect to `b`. If an exception is thrown, ar | |
510 | may be left in an inconsistent state. | |
511 | ||
512 | [blurb [*Operation:] loading of a `bimap` m' from an input archive | |
513 | (XML archive) ar.] | |
514 | ||
515 | * [*Requires:] Value is serializable (XML-serializable). Additionally, each of | |
516 | the views of `b`' can impose other requirements. | |
517 | * [*Exception safety:] Basic. If an exception is thrown, ar may be left in an | |
518 | inconsistent state. | |
519 | ||
520 | [endsect] | |
521 | [endsect] | |
522 | ||
523 | [endsect] |