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:

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.

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:

If the set 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 set type of relation is not side-based, then there is an additional term to add that is contributed by the set 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:

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 set type specifiers. The side set type specifiers define the constraints of the two map views of the bimap. The set type of relation specifier defines the main set view constraints. If left_based (the default parameter) or right_based is used, then the set type of relation will be based on the left or right set type correspondingly.

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.

namespace boost {
namespace bimap {

template< class Type, typename Tag >
struct tagged;

// Metafunctions for a bimap

template< class Tag, class Bimap > struct value_type_by;
template< class Tag, class Bimap > struct key_type_of;
template< class Tag, class Bimap > struct data_type_of;
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 &);

// exceptions

class duplicate_value;
class value_not_found;

// bimap template class

template
<
    class LeftSetType, class RightSetType,

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

    public:

    typedef -unspecified- left_tag;
    typedef -unspecified- left_data_type;
    typedef -unspecified- left_value_type;
    typedef -unspecified- left_key_type;
    typedef -unspecified- left_iterator;
    typedef -unspecified- left_const_iterator;
    typedef -unspecified- left_reverse_iterator;
    typedef -unspecified- left_const_reverse_iterator;
    typedef -unspecified- left_set_type;
    typedef -unspecified- left_map_type;

    typedef -unspecified- right_tag;
    typedef -unspecified- right_data_type;
    typedef -unspecified- right_value_type;
    typedef -unspecified- right_key_type;
    typedef -unspecified- right_iterator;
    typedef -unspecified- right_const_iterator;
    typedef -unspecified- right_reverse_iterator;
    typedef -unspecified- right_const_reverse_iterator;
    typedef -unspecified- right_set_type;
    typedef -unspecified- right_map_type;

    typedef -unspecified- relation_set_type_of;
    typedef -unspecified- relation_set;

     left_map_type  left;
    right_map_type right;

    bimap();

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

};


} // namespace bimap
} // namespace boost

This is the main component of Boost.Bimap.

left_tag, right_tag

left_key_type, right_key_type

left_data_type, right_data_type

left_value_type, right_value_type

left_iterator, right_iterator
left_const_iterator, right_const_iterator

left_set_type, right_set_type

left_map_type, right_map_type

relation_set_type_of

relation_set

bimap();

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

bimap(const bimap & x);

~bimap()

bimap& operator=(const bimap& x);

allocator_type get_allocator() const;