5 Copyright (c) 2006-2007 Matias Capeletto
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)
13 [/ QuickBook Document version 1.4 ]
15 [section Bimap Reference]
17 [section View concepts]
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.
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.
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:
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
44 * modification of an element, and its subsequent
45 rearrangement/banning by the various views
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
56 [#complexity_signature_explanation]
58 [section Complexity signature]
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.
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:
70 * `h(n)`: hinted insertion
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:
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) ]`
94 [section Set type specification]
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.
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` ]]
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
128 [section Header "boost/bimap/bimap.hpp" synopsis]
133 template< class Type, typename Tag >
136 // bimap template class
140 class LeftCollectionType, class RightCollectionType,
142 class AdditionalParameter_1 = detail::not_specified,
143 class AdditionalParameter_2 = detail::not_specified
145 class bimap ``['- implementation defined { : public SetView } -]``
151 typedef ``['-unspecified-]`` left_tag;
152 typedef ``['-unspecified-]`` left_map;
154 typedef ``['-unspecified-]`` right_tag;
155 typedef ``['-unspecified-]`` right_map;
158 // typedef -side-_map::-type- -side-_-type-;
160 typedef ``['-unspecified-]`` info_type;
171 template< class InputIterator >
172 bimap(InputIterator first,InputIterator last);
174 bimap(const bimap &);
176 bimap& operator=(const bimap& b);
178 // Projection of iterators
180 template< class IteratorType >
181 left_iterator project_left(IteratorType iter);
183 template< class IteratorType >
184 left_const_iterator project_left(IteratorType iter) const;
186 template< class IteratorType >
187 right_iterator project_right(IteratorType iter);
189 template< class IteratorType >
190 right_const_iterator project_right(IteratorType iter) const;
192 template< class IteratorType >
193 iterator project_up(IteratorType iter);
195 template< class IteratorType >
196 const_iterator project_up(IteratorType iter) const;
200 template< class Tag >
203 template< class Tag >
204 map_by<Tag>::type by();
206 template< class Tag >
207 const map_by<Tag>::type & by() const;
209 template< class Tag, class IteratorType >
210 map_by<Tag>::iterator project(IteratorType iter);
212 template< class Tag, class IteratorType >
213 map_by<Tag>::const_iterator project(IteratorType iter) const
223 // Metafunctions for a bimap
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;
235 // Functions for a bimap
237 template<class Tag, class Relation>
238 result_of::map_by< Tag, Bimap>::type map_by(Bimap &);
240 // Metafunctions for a relation
242 template< class Tag, class Relation > struct value_type_of;
243 template< class Tag, class Relation > struct pair_type_by;
245 // Functions for a relation
247 template<class Tag, class Relation>
248 result_of::get< Tag, Relation>::type get(Relation &r);
250 template<class Tag, class Relation>
251 result_of::pair_by< Tag, Relation>::type pair_by(Relation &);
257 [section Class template bimap]
259 This is the main component of Boost.Bimap.
263 In the descriptions of the operations of `bimap`, we adopt the scheme
264 outlined in the complexity signature section.
268 [section Instantiation types]
270 `bimap` is instantiated with the following types:
272 # LeftCollectionType and RightCollectionType are collection type specifications
273 optionally tagged, or any type optionally tagged, in which case that
275 # AdditionalParameter_{1/2} can be any ordered subset of:
276 * CollectionTypeOfRelation specification
281 [section Nested types]
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`.
289 left_key_type, right_key_type
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`.
296 left_data_type, right_data_type
298 [: Data type of each side. In a bimap<A,B> left_key_type is B and
300 If there are tags, it is better to use: `Bimap::map_by<Tag>::data_type`.
303 left_value_type, right_value_type
305 [: Value type used for the views.
306 If there are tags, it is better to use: `Bimap::map_by<Tag>::value_type`.
310 left_iterator, right_iterator
311 left_const_iterator, right_const_iterator
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`
322 [: Map view type of each side.
323 If there are tags, it is better to use:
324 `Bimap::map_by<Tag>::type`.
329 [section Constructors, copy and assignment]
333 * [*Effects:] Constructs an empty `bimap`.
334 * [*Complexity:] Constant.
336 template<typename InputIterator>
337 bimap(InputIterator first,InputIterator last);
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)`.
348 bimap(const bimap & x);
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()))
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).
364 bimap& operator=(const bimap& x);
366 * [*Effects:] Replaces the elements and internal objects of the `bimap`
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.
376 allocator_type get_allocator() const;
378 * [*Effects:] Returns a copy of the `allocator_type` object used to construct
380 * [*Complexity:] Constant.
385 [#reference_projection_operations]
387 [section Projection operations]
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:
392 * `it1 == i1.end()` AND `it2 == i2.end()`,
393 * OR `it1` and `it2` point to the same element.
396 template< class IteratorType >
397 left_iterator project_left(IteratorType iter);
399 template< class IteratorType >
400 left_const_iterator project_left(IteratorType iter) const;
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
405 * [*Effects:] Returns a left map view iterator equivalent to `it`.
406 * [*Complexity:] Constant.
407 * [*Exception safety:] nothrow.
410 template< class IteratorType >
411 right_iterator project_right(IteratorType iter);
413 template< class IteratorType >
414 right_const_iterator project_right(IteratorType iter) const;
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
419 * [*Effects:] Returns a right map view iterator equivalent to `it`.
420 * [*Complexity:] Constant.
421 * [*Exception safety:] nothrow.
424 template< class IteratorType >
425 iterator project_up(IteratorType iter);
427 template< class IteratorType >
428 const_iterator project_up(IteratorType iter) const;
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
433 * [*Effects:] Returns a collection of relations view iterator equivalent to `it`.
434 * [*Complexity:] Constant.
435 * [*Exception safety:] nothrow.
439 [#reference_support_for_used_defined_names]
441 [section Support for user defined names]
443 template< class Tag >
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.
451 template< class Tag >
452 map_by<Tag>::type by();
454 template< class Tag >
455 const map_by<Tag>::type & by() const;
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
461 * [*Complexity:] Constant.
462 * [*Exception safety:] nothrow.
465 template< class Tag, class IteratorType >
466 map_by<Tag>::iterator project(IteratorType iter);
468 template< class Tag, class IteratorType >
469 map_by<Tag>::const_iterator project(IteratorType iter) const
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
476 * [*Complexity:] Constant.
477 * [*Exception safety:] nothrow.
482 [section Serialization]
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
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
499 * `p(x,y) == q(x`'`,y`'`)`
501 for every `x` and `y` of type `T` and `x`' and `y`' being restored copies of `x`
502 and `y`, respectively.
504 [blurb [*Operation:] saving of a `bimap b` to an output archive
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.
512 [blurb [*Operation:] loading of a `bimap` m' from an input archive
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