tutorial.qbk

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

which is set to the bimap relation and the allocator type. To help users
in the creation of each functor, the collection type of relation templates
takes an mpl lambda expression where the relation type will be evaluated
later. A placeholder named `_relation` is available to bimap users.

The following table lists the meaning of the parameters for each collection type of
relations.

[table
[[name                     ][Additional Parameters]]

[[`left_based`                        ][Not a template.]]
[[`right_based`                       ][Not a template.]]
[[`set_of_relation<KeyComp>`

  `multiset_of_relation<KeyComp>` ]
[[*KeyComp ] is a Functor that compares two types using less than. By
default, the less-than operator is `std::less<_relation>`. ]]

[[`unordered_set_of_relation<HashFunctor,EqualKey>`

  `unordered_multiset_of_relation<HashFunctor,EqualKey>`]
[[*HashFunctor ] converts the `relation` into an `std::size_t` value. By default it is `boost::hash<_relation>`.

 [*EqualKey ] is a Functor that tests two relations for equality. By default,
the equality operator is `std::equal_to<_relation>`. ]]
[[`list_of_relation`                  ][Not a template.]]
[[`vector_of_relation`                ][Not a template.]]
[[`unconstrained_set_of_relation`     ][Not a template.]]
]

[endsect]

[section Examples]

Consider this example:

    template< class Rel >
    struct RelOrder
    {
        bool operator()(Rel ra, Rel rb) const
        {
            return (ra.left+ra.right) < (rb.left+rb.right);
        }
    };

    typedef bimap
    <
            multiset_of< int >,
            multiset_of< int >,
            set_of_relation< RelOrder<_relation> >

    > bimap_type;

Here the bimap relation view is ordered using the information of
both sides. This container will only allow unique relations because
`set_of_relation` has been used but the elements in each side of the
bimap can be repeated.

    struct name         {};
    struct phone_number {};

    typedef bimap
    <
        tagged< unordered_multiset_of< string >, name         >,
        tagged< unordered_set_of     < int    >, phone_number >,
        set_of_relation<>

    > bimap_type;

In this other case the bimap will relate names to phone numbers.
Names can be repeated and phone numbers are unique. You can perform
quick searches by name or phone number and the container can be viewed
ordered using the relation view.

[endsect]

[endsect]

[section Differences with standard maps]

[section Insertion]

Remember that a map can be interpreted as a relation between two collections.
In bimaps we have the freedom to change both collection types, imposing
constrains in each of them. Some insertions that we give for granted to
success in standard maps fails with bimaps.
For example:

    bimap<int,std::string> bm;

    bm.left.insert(1,"orange");
    bm.left.insert(2,"orange"); // No effect! returns make_pair(iter,false)

The insertion will only succeed if it is allowed by all views of the `bimap`.
In the next snippet we define the right collection as a multiset, when we
try to insert the same two elements the second insertion is allowed by the
left map view because both values are different and it is allowed by the
right map view because it is a non-unique collection type.

    bimap<int, multiset_of<std::string> > bm;

    bm.left.insert(1,"orange");
    bm.left.insert(2,"orange"); // Insertion succeed!

If we use a custom collection of relation type, the insertion has to be
allowed by it too.

[endsect]

[section iterator::value_type]

The relations stored in the Bimap will not be in most cases modifiable
directly by iterators because both sides are used as keys of
['key-based] sets. When a `bimap<A,B>` left view iterator is dereferenced
the return type is ['signature-compatible] with a
`std::pair< const A, const B >`.
However there are some collection types that are not ['key_based], for example
list_of. If a Bimap uses one of these collection types there is no problem with
modifying the data of that side. The following code is valid:

    typedef bimap< int, list_of< std::string > > bm_type;
    bm_type bm;
    bm.insert( bm_type::relation( 1, "one" ) );
    ...
    bm.left.find(1)->second = "1"; // Valid

In this case, when the iterator is dereferenced the return type is
['signature-compatible] with a `std::pair<const int, std::string>`.

The following table shows the constness of the dereferenced data of each
collection type of:

[table
[[Side collection type   ][Dereferenced data]]
[[`set_of`               ][['constant]]]
[[`multiset_of`          ][['constant]]]
[[`unordered_set_of`     ][['constant]]]
[[`unordered_multiset_of`][['constant]]]
[[`list_of`              ][['mutable] ]]
[[`vector_of`            ][['mutable] ]]
[[`unconstrained_set_of` ][['mutable] ]]
]

Here are some examples. When dereferenced the iterators returns a type that
is ['signature-compatible] with these types.

[table
[[Bimap type   ][Signature-compatible types]]
[[`bimap<A,B>`][
    `iterator      ` *->* `relation<const A,const B>`

    `left_iterator ` *->* `pair<const A,const B>`

    `right_iterator` *->* `pair<const B,const A>`
]]
[[`bimap<multiset_of<A>,unordered_set_of<B> >`][
    `iterator      ` *->* `relation<const A,const B>`

    `left_iterator ` *->* `pair<const A,const B>`

    `right_iterator` *->* `pair<const B,const A>`
]]
[[`bimap<set_of<A>,list_of<B> >`][
    `iterator      ` *->* `relation<const A,B>`

    `left_iterator ` *->* `pair<const A,B>`

    `right_iterator` *->* `pair<B,const A>`
]]
[[`bimap<vector_of<A>,set_of<B> >`][
    `iterator      ` *->* `relation<A,const B>`

    `left_iterator ` *->* `pair<A,const B>`

    `right_iterator` *->* `pair<const B,A>`
]]
[[`bimap<list_of<A>,unconstrained_set_of<B> >`][
    `iterator      ` *->* `relation<A,B>`

    `left_iterator ` *->* `pair<A,B>`

    `right_iterator` *->* `pair<B,A>`
]]
]

[endsect]

[section operator\[\] and at()]

`set_of` and `unordered_set_of` map views overload `operator[]` to retrieve the
associated data of a given key only when the other collection type is a 
mutable one. In these cases it works in the same way as the standard.

    bimap< unorderd_set_of< std::string>, list_of<int> > bm;

    bm.left["one"] = 1; // Ok

The standard defines an access function for `map` and `unordered_map`:

    const data_type & at(const key_type & k) const;
          data_type & at(const key_type & k);

These functions look for a key and returns the associated data value, but
throws a `std::out_of_range` exception if the key is not found.

In bimaps the constant version of these functions is given for `set_of` and
`unorderd_set_of` map views independently of the other collection type.
The mutable version is only provided when the other collection type is
mutable.

The following examples shows the behaviour of `at(key)`

[@../../example/at_function_examples.cpp Go to source code]

[import ../example/at_function_examples.cpp]

[code_at_function_first]

[code_at_function_second]

[/
`set_of` and `unordered_set_of` views overload `operator[]` to retrieve the
associated data of a given key.
The symmetry of bimap imposes some constraints on `operator[]` that are
not found in `std::map` or `std::unordered_map`. If other views are unique,
`bimap::duplicate_value` is thrown whenever an assignment is attempted to
a value that is already a key in these views. As for
`bimap::value_not_found`, this exception is thrown while trying to access
a non-existent key: this behaviour differs from the standard containers,
which automatically assigns a default value to non-existent keys referred to
by `operator[]`.


    const data_type & operator[](const typename key_type & k) const;

[:  Returns the `data_type` reference that is associated with `k`, or
    throws `bimap::value_not_found` if such an element does not exist.
]

    ``['-unspecified data_type proxy-]`` operator[](const typename key_type & k);

[:  Returns a proxy to a `data_type` associated with `k` and the
    bimap. The proxy behaves as a reference to the `data_type` object. If this
    proxy is read and `k` was not in the bimap, the bimap::value_not_found is
    thrown. If it is written then `bimap::duplicate_value` is thrown if the
    assignment is not allowed by one of the other views of the `bimap`.
]


The following example shows the behaviour of `operator[]`

    bimap<int,std::string> bm;

    bm.left[1] = "one"; // Ok

    bm.right["two"] = 2; // Ok

    if( bm.left[3] == "three" ) // throws bimap::value_not_found
    {
        ...
    }

    bm.left[3] = "one"; // throws bimap::duplicate_value
]

[endsect]

[section Complexity of operations]

The complexity of some operations is different in bimaps. Read 
[link complexity_signature_explanation the reference] to find the
complexity of each function.

[endsect]

[endsect]

[section Useful functions]

[section Projection of iterators]

Iterators can be projected to any of the three views of the bimap.
A bimap provides three member functions to cope with projection: `project_left`,
`project_right` and `project_up`, with projects iterators to the ['left map view],
the ['right map view] and the ['collection of relations view]. These functions 
take any iterator from the bimap and retrieve an iterator over the projected view 
pointing to the same element.

[import ../example/projection.cpp]

Here is an example that uses projection:

[@../../example/projection.cpp Go to source code]

[code_projection_years]

[endsect]

[section replace and modify]

[import ../example/tutorial_modify_and_replace.cpp]

These functions are members of the views of a bimap that are not founded in 
their standard counterparts.

The `replace` family member functions performs in-place replacement of a given 
element as the following example shows:

[@../../example/tutorial_modify_and_replace.cpp Go to source code]

[code_tutorial_replace]

`replace` functions performs this substitution in such a manner that:

* The complexity is constant time if the changed element retains its original order
with respect to all views; it is logarithmic otherwise.
* Iterator and reference validity are preserved.
* The operation is strongly exception-safe, i.e. the `bimap` remains unchanged if 
some exception (originated by the system or the user's data types) is thrown.

`replace` functions are powerful operations not provided by standard STL containers, 
and one that is specially handy when strong exception-safety is required.

The observant reader might have noticed that the convenience of replace comes at a
cost: namely the whole element has to be copied ['twice] to do the updating (when
retrieving it and inside `replace`). If elements are expensive to copy, this may
be quite a computational cost for the modification of just a tiny part of the
object. To cope with this situation, Boost.Bimap provides an alternative
updating mechanism: `modify` functions.

`modify` functions accepts a functor (or pointer to function) taking a reference 
to the data to be changed, thus eliminating the need for spurious copies. Like
`replace` functions, `modify` functions does preserve the internal orderings of
all the indices of the `bimap`. However, the semantics of modify functions are not
entirely equivalent to replace functions. Consider what happens if a collision occurs
as a result of modifying the element, i.e. the modified element clashes with another
with respect to some unique view. In the case of `replace` functions, the original
value is kept and the method returns without altering the container, but `modify`
functions cannot afford such an approach, since the modifying functor leaves no
trace of the previous value of the element. Integrity constraints thus lead to the
following policy: when a collision happens in the process of calling a modify functions,
the element is erased and the method returns false. This difference in behavior
between `replace` and `modify` functions has to be considered by the programmer on
a case-by-case basis.

Boost.Bimap defines new placeholders named `_key` and `_data` to allow a sounder solution.
You have to include `<boost/bimap/support/lambda.hpp>` to use them.

[/
Boost.Bimap defines new placeholders to allow a sounder solution. For
pairs, two new placeholders are instantiated: `_first` and `_second`, and
for a relation, two more complete the set: `_left` and `_right`.