bimap.qbk

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

[/license

Boost.Bimap

Copyright (c) 2006-2007 Matias Capeletto

Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at
http://www.boost.org/LICENSE_1_0.txt)

]

[/ QuickBook Document version 1.4 ]

[section Bimap Reference]

[section View concepts]

`bimap` instantiations comprise two side views and an view of the relation
specified at compile time. Each view allows read-write access to the elements contained
in a definite manner, mathing an STL container signature.

Views are not isolated objects and so cannot be constructed on their
own; rather they are an integral part of a `bimap`. The name of the view
class implementation proper is never directly exposed to the user, who
has access only to the associated view type specifier.

Insertion and deletion of elements are always performed through the
appropriate interface of any of the three views of the `bimap`; these
operations do, however, have an impact on all other views as well: for
instance, insertion through a given view may fail because there exists
another view that forbids the operation in order to preserve its
invariant (such as uniqueness of elements). The global operations
performed jointly in the any view can be reduced to six primitives:

* copying
* insertion of an element
* hinted insertion, where a pre-existing element is suggested in order to improve
the efficiency of the operation
* deletion of an element
* replacement of the value of an element, which may trigger the
rearrangement of this element in one or more views, or may forbid the
replacement
* modification of an element, and its subsequent
rearrangement/banning by the various views

The last two primitives deserve some further explanation: in order to
guarantee the invariants associated to each view (e.g. some definite
ordering) elements of a `bimap` are not mutable. To overcome this
restriction, the views expose member functions for updating and
modifying, which allows for the mutation of elements in a controlled
fashion.

[endsect]

[#complexity_signature_explanation]

[section Complexity signature]

Some member functions of a view interface are implemented by global
primitives from the above list. The complexity of these operations thus
depends on all views of a given `bimap`, not just the currently used view.

In order to establish complexity estimates, a view is characterised by
its complexity signature, consisting of the following associated
functions on the number of elements:

* `c(n)`: copying
* `i(n)`: insertion
* `h(n)`: hinted insertion
* `d(n)`: deletion
* `r(n)`: replacement
* `m(n)`: modifying

If the collection type of the relation is `left_based` or `right_based`, and we use
an `l` subscript to denote the left view and an `r` for the right view, then
the insertion of an element in such a container is of complexity
`O(i_l(n)+i_r(n))`, where n is the number of elements. If the collection type of
relation is not side-based, then there is an additional term to add that
is contributed by the collection type of relation view. Using `a` to denote the
above view, the complexity of insertion will now be
`O(i_l(n)+i_r(n)+i_a(n))`. To abbreviate the notation, we adopt the
following definitions:

* `C(n) = c_l(n) + c_r(n) [ + c_a(n) ]`
* `I(n) = i_l(n) + i_r(n) [ + i_a(n) ]`
* `H(n) = h_l(n) + h_r(n) [ + h_a(n) ]`
* `D(n) = d_l(n) + d_r(n) [ + d_a(n) ]`
* `R(n) = r_l(n) + r_r(n) [ + r_a(n) ]`
* `M(n) = m_l(n) + m_r(n) [ + m_a(n) ]`

[endsect]

[section Set type specification]

Set type specifiers are passed as instantiation arguments to `bimap` and
provide the information needed to incorporate the corresponding views.
Currently, Boost.Bimap provides the collection type specifiers. The ['side collection type]
specifiers define the constraints of the two map views of the
bimap. The ['collection type of relation] specifier defines the main set view
constraints. If `left_based` (the default parameter) or `right_based` is
used, then the collection type of relation will be based on the left or right
collection type correspondingly.

[table
[[Side collection type      ][Collection type of relation       ][Include                                 ]]
[[`set_of`                  ][`set_of_relation`               ][`boost/bimap/set_of.hpp`                ]]
[[`multiset_of`             ][`multiset_of_relation`          ][`boost/bimap/multiset_of.hpp`           ]]
[[`unordered_set_of`        ][`unordered_set_of_relation`     ][`boost/bimap/unordered_set_of.hpp`      ]]
[[`unordered_multiset_of`   ][`unordered_multiset_of_relation`][`boost/bimap/unordered_multiset_of.hpp` ]]
[[`list_of`                 ][`list_of_relation`              ][`boost/bimap/list_of.hpp`               ]]
[[`vector_of`               ][`vector_of_relation`            ][`boost/bimap/vector_of.hpp`             ]]
[[`unconstrained_set_of`    ][`unconstrained_set_of_relation` ][`boost/bimap/unconstrained_set_of.hpp`  ]]
[[                          ][`left_based`                    ][`boost/bimap/bimap.hpp`                 ]]
[[                          ][`right_based`                   ][`boost/bimap/bimap.hpp`                 ]]
]

[endsect]

[section Tags]

Tags are just conventional types used as mnemonics for the types stored
in a `bimap`. Boost.Bimap uses the tagged idiom to let the user specify
this tags.

[endsect]

[section Header "boost/bimap/bimap.hpp" synopsis]

    namespace boost {
    namespace bimaps {

    template< class Type, typename Tag >
    struct tagged;

    // bimap template class

    template
    <
        class LeftCollectionType, class RightCollectionType,

        class AdditionalParameter_1 = detail::not_specified,
        class AdditionalParameter_2 = detail::not_specified
    >
    class bimap ``['- implementation defined { : public SetView } -]``
    {
        public:

        // Metadata

        typedef ``['-unspecified-]`` left_tag;
        typedef ``['-unspecified-]`` left_map;

        typedef ``['-unspecified-]`` right_tag;
        typedef ``['-unspecified-]`` right_map;

        // Shortcuts
        // typedef -side-_map::-type- -side-_-type-;

        typedef ``['-unspecified-]`` info_type;

        // Map views

         left_map  left;
        right_map right;

        // Constructors

        bimap();

        template< class InputIterator >
        bimap(InputIterator first,InputIterator last);

        bimap(const bimap &);

        bimap& operator=(const bimap& b);

        // Projection of iterators

        template< class IteratorType >
        left_iterator project_left(IteratorType iter);

        template< class IteratorType >
        left_const_iterator project_left(IteratorType iter) const;

        template< class IteratorType >
        right_iterator project_right(IteratorType iter);

        template< class IteratorType >
        right_const_iterator project_right(IteratorType iter) const;

        template< class IteratorType >
        iterator project_up(IteratorType iter);

        template< class IteratorType >
        const_iterator project_up(IteratorType iter) const;

        // Support for tags

        template< class Tag >
        struct map_by;

        template< class Tag >
        map_by<Tag>::type by();

        template< class Tag >
        const map_by<Tag>::type & by() const;

        template< class Tag, class IteratorType >
        map_by<Tag>::iterator project(IteratorType iter);

        template< class Tag, class IteratorType >
        map_by<Tag>::const_iterator project(IteratorType iter) const

    };


    } // namespace bimap
    } // namespace boost


[/
    // Metafunctions for a bimap

    template< class Tag, class Bimap > struct value_type_by;
    template< class Tag, class Bimap > struct key_type_by;
    template< class Tag, class Bimap > struct data_type_by;
    template< class Tag, class Bimap > struct iterator_type_by;
    template< class Tag, class Bimap > struct const_iterator_type_by;
    template< class Tag, class Bimap > struct reverse_iterator_type_by;
    template< class Tag, class Bimap > struct const_reverse_iterator_type_by;
    template< class Tag, class Bimap > struct local_iterator_type_by;
    template< class Tag, class Bimap > struct const_local_iterator_type_by;

    // Functions for a bimap

    template<class Tag, class Relation>
    result_of::map_by< Tag, Bimap>::type map_by(Bimap &);

    // Metafunctions for a relation

    template< class Tag, class Relation > struct value_type_of;
    template< class Tag, class Relation > struct pair_type_by;

    // Functions for a relation

    template<class Tag, class Relation>
    result_of::get< Tag, Relation>::type get(Relation &r);

    template<class Tag, class Relation>
    result_of::pair_by< Tag, Relation>::type pair_by(Relation &);

]

[endsect]

[section Class template bimap]

This is the main component of Boost.Bimap.

[section Complexity]