libs/bimap/doc/reference/bimap.qbk

   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]