add subtree-ish sources for 12.0.3

[ceph.git] / ceph / src / boost / libs / bimap / doc / tutorial.qbk

[/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 The tutorial]

[section Roadmap]

# Boost.Bimap is intuitive because it is based on the standard
template library. New concepts are however presented to extend the
standard maps to bidirectional maps. The first step is to gain a
firm grasp of the bimap framework. The first section
([link boost_bimap.the_tutorial.discovering_the_bimap_framework Discovering the bimap framework])
aims to explain this.

# Boost.Bimap offers much more than just a one-to-one ordered unique
bidirectional map. It is possible to control the collection type of each side
of the relationship that the bimap represents, giving one-to-many
containers, hashed bidirectional containers and others that may be more
suitable to the the task at hand. The second section
([link boost_bimap.the_tutorial.controlling_collection_types Controlling collection types])
explains how to instantiate a bimap with different collection constraints.

# The section
([link boost_bimap.the_tutorial.the_collection_of_relations_type The "collection of relations" type])
explains how to create new types of bidirectional maps using custom collection types.

# In the section [link boost_bimap.the_tutorial.differences_with_standard_maps Differences with standard maps] we will learn about the subtle differences between a bimap map view and a standard map.

# The section [link boost_bimap.the_tutorial.useful_functions Useful functions] provides information
about functions of a bimap that are not found in the STL.

# The types of a bimap can be tagged so that each side is accessible
by something closer to the problem than left and right. This leads to
more readable, self-documenting code. The fourth section
([link boost_bimap.the_tutorial.bimaps_with_user_defined_names Bimaps with user defined names]) shows
how to use this feature.

# The bimap mapping framework allows to disable a view of a bimap, including the standard
mapping containers as a particular case. The section
[link boost_bimap.the_tutorial.unconstrained_sets Unconstrained Sets] explains how they work.

# The section [link boost_bimap.the_tutorial.additional_information Additional information]
explains how to attach information to each relation of a bimap.

# The final section
([link boost_bimap.the_tutorial.complete_instantiation_scheme Complete Instantiation Scheme])
summarizes bimap instantiation and explains how change the allocator type to be used.

[endsect]

[section Discovering the bimap framework]

[section Interpreting bidirectional maps]

One way to interpret bidirectional maps is as a function between two
collections of data, lets call them the left and the right collection. 
An element in this bimap is a relation between an element from the left 
collection and an element from the right collection.
The types of both collections defines the bimap behaviour. We can view
the stored data from the left side, as a mapping between keys from the
left collection and data from the right one, or from the right side, as
a mapping between keys from the right collection and data from the
left collection.

[endsect]

[section Standard mapping framework]

Relationships between data in the STL are represented by maps. A
standard map is a directed relation of keys from a left collection and 
data from a right unconstrained collection.
The following diagram shows the relationship represented and the 
user's viewpoint.

__STANDARD_MAPPING_FRAMEWORK__

The left collection type depends on the selected map type. For example if the the map type is `std::multimap` the collection type of X is a `multiset_of`.
The following table shows the equivalent types for the std associative containers.

[table std associative containers
[[container           ][left collection type      ][right collection type]]
[[`map`               ][`set_of`                  ][no constraints       ]]
[[`multimap`          ][`multiset_of`             ][no constraints       ]]
[[`unordered_map`     ][`unordered_set_of`        ][no constraints       ]]
[[`unordered_multimap`][`unordered_multiset_of`   ][no constraints       ]]
]

[endsect]

[section Bimap mapping framework]

Boost.Bimap design is based on the STL, and extends the framework in a natural way.
The following diagram represents the new situation.

__EXTENDED_MAPPING_FRAMEWORK__

Notice that now the `std::maps` are a particular case of a Boost.Bimap
container, where you can view only one side of the relationship and can
control the constraints of only one of the collections. Boost.Bimap
allows the user to view the relationship from three viewpoints.
You can view it from one side, obtaining a `std::map` compatible
container, or you can work directly with the whole relation.

The next diagram shows the layout of the relation and pairs of a bimap. It is
the one from the ['one minute tutorial]

__RELATION_AND_PAIR__

Bimap pairs are signature-compatible with standard pairs but are different
from them. As you will see in other sections they can be tagged with user
defined names and additional information can be attached to them. You can
convert from `std::pairs` to bimap pairs directly but the reverse conversion
is not provided. This mean that you can insert elements in a bimap using
algorithms like `std::copy` from containers `like std::map`, or use `std::make_pair`
to add new elements. However it is best to use `bm.left.insert( bm_type::left_value_type(f,s) )` instead of `bm.insert( std::make_pair(f,s) )` to avoid an extra call to the
copy constructor of each type.

The following code snippet shows the relation between a bimap and standard
maps.

[note
You have to used references to views, and not directly views object. 
Views cannot be constructed as separate objects from the container they 
belong to, so the following:
``
// Wrong: we forgot the & after bm_type::left_type
bm_type::left_map lm = bm.left;
``
does not compile, since it is trying to construct the view object `lm`. 
This is a common source of errors in user code.
]

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

[import ../example/standard_map_comparison.cpp]

[code_standard_map_comparison]

[endsect]

[endsect]

[section Controlling collection types]

[section Freedom of choice]

As has already been said, in STL maps, you can only control the
constraints from one of the collections, namely the one that you are
viewing. In Boost.Bimap, you can control both and it is as easy as using the STL.

__EXTENDED_MAPPING_FRAMEWORK__

The idea is to use the same constraint names that are used in the
standard. If you don't specify the collection type, Boost.Bimap assumes
that the collection is a set. The instantiation of a bimap with custom
collection types looks like this:

    typedef bimap< ``*CollectionType*``_of<A>, ``*CollectionType*``_of<B> > bm_type;

The following is the list of all supported collection types.


[table Collection of Key Types
[[name                   ][Features          ][map view type            ]]
[[`set_of`               ][['ordered, unique]][`map`                    ]]
[[`multiset_of`          ][['ordered        ]][`multimap`               ]]
[[`unordered_set_of`     ][['hashed, unique ]][`unordered_map`          ]]
[[`unordered_multiset_of`][['hashed         ]][`unordered_multimap`     ]]
[[`list_of`              ][['sequenced      ]][`list_map`               ]]
[[`vector_of`            ][['random access  ]][`vector_map`             ]]
[[`unconstrained_set_of` ][['unconstrained  ]][['can not be viewed]     ]]
]


`list_of` and `vector_of` map views are not associated with any existing STL
associative containers. They are two examples of unsorted associative
containers. `unconstrained_set_of` allow the user to ignore a view. This
will be explained later.

__BIMAP_STRUCTURES__

The selection of the collection type affects the possible operations that you
can perform with each side of the bimap and the time it takes to do
each. If we have:

    typedef bimap< ``*CollectionType*``_of<A>, ``*CollectionType*``_of<B> > bm_type;
    bm_type bm;

The following now describes the resulting map views of the bidirectional
map.

* `bm.left` is signature-compatible with *LeftMapType*`<A,B>`
* `bm.right` is signature-compatible with *RightMapType*`<B,A>`

[endsect]

[section Configuration parameters]

Each collection type template has different parameters to control its
behaviour. For example, in `set_of` specification, you can pass a Functor
type that compares two types. All of these parameters are exactly the
same as those of the standard library container, except for the
allocator type. You will learn later how to change the allocator for a
bimap.

The following table lists the meanings of each collection type's parameters.

[table
[[name                     ][Additional Parameters]]

[[`set_of<T,KeyComp>`

  `multiset_of<T,KeyComp>` ]

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

[[`unordered_set_of<T,HashFunctor,EqualKey>`

  `unordered_multiset_of<T,HashFunctor,EqualKey>`]

[[*HashFunctor ] converts a `T` object into an `std::size_t` value. By default it is `boost::hash<T>`.

 [*EqualKey ] is a Functor that tests two types for equality. By default, the
equality operator is `std::equal_to<T>`. ]]
[[`list_of<T>`              ][No additional parameters.]]
[[`vector_of<T>`            ][No additional parameters.]]
[[`unconstrained_set_of<T>` ][No additional parameters.]]
]

[endsect]

[section Examples]

[heading Countries Populations]

We want to store countries populations.
The requirements are:

# Get a list of countries in decreasing order of their populations.
# Given a country, get their population.

Lets create the appropriate bimap.

    typedef bimap<

        unordered_set_of< std::string >,
        multiset_of< long, std::greater<long> >

    > populations_bimap;

First of all countries names are unique identifiers, while two countries 
may have the same population. This is why we choose *multi*`set_of` for
populations.

Using a `multiset_of` for population allow us to iterate over the data.
Since listing countries ordered by their names is not a requisite, we can
use an `unordered_set_of` that allows constant order look up.

And now lets use it in a complete example

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

[import ../example/population_bimap.cpp]

[code_population_bimap]


[heading Repetitions counter]

We want to count the repetitions for each word in a text and print them
in order of appearance.

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

[import ../example/repetitions_counter.cpp]

[code_repetitions_counter]

[endsect]

[endsect]

[section The collection of relations type]

[section A new point of view]

Being able to change the collection type of the bimap relation view is another
very important feature. Remember that this view allows the user to see
the container as a group of the stored relations. This view has set
semantics instead of map semantics.

__COLLECTION_TYPE_OF_RELATION__

By default, Boost.Bimap will base the collection type of the relation on the
type of the left collection. If the left collection type is a set, then the collection
type of the relation will be a set with the same order as the left view.

In general, Boost.Bimap users will base the collection type of a relation on
the type of the collection on one of the two sides. However there are times
where it is useful to give this collection other constraints or simply to order
it differently. The user is allowed to choose between:

* left_based
* right_based
* set_of_relation<>
* multiset_of_relation<>
* unordered_set_of_relation<>
* unordered_multiset_of_relation<>
* list_of_relation
* vector_of_relation
* unconstrained_set_of_relation

[tip
The first two options and the last produce faster bimaps, so prefer
these where possible.
]

__MORE_BIMAP_STRUCTURES__

The collection type of relation can be used to create powerful containers. For
example, if you need to maximize search speed, then the best
bidirectional map possible is one that relates elements from an
`unordered_set` to another `unordered_set`. The problem is that this
container cannot be iterated. If you need to know the list of relations
inside the container, you need another collection type of relation. In this
case, a `list_of_relation` is a good choice. The resulting container
trades insertion and deletion time against fast search capabilities and
the possibility of bidirectional iteration.

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

[code_mighty_bimap]

[endsect]

[section Configuration parameters]

Each collection type of relation has different parameters to control its
behaviour. For example, in the `set_of_relation` specification, you can
pass a Functor type that compares two types. All of the parameters are
exactly as in the standard library containers, except for the type,
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`.
]

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

[code_tutorial_modify]

[endsect]

[section Retrieval of ranges]

[import ../example/tutorial_range.cpp]

Standard `lower_bound` and `upper_bound` functions can be used to lookup for
all the elements in a given range.

Suppose we want to retrieve the elements from a `bimap<int,std::string>`
where the left value is in the range `[20,50]`

[code_tutorial_range_standard_way]

Subtle changes to the code are required when strict inequalities are considered.
To retrieve the elements greater than 20 and less than 50, the code has to be 
rewritten as

[code_tutorial_range_standard_way_subtle_changes]

To add to this complexity, the careful programmer has to take into account that
the lower and upper bounds of the interval searched be compatible: for instance,
if the lower bound is 50 and the upper bound is 20, the iterators `iter_first` and
`iter_second` produced by the code above will be in reverse order, with possibly
catastrophic results if a traversal from `iter_first` to `iter_second` is tried.
All these details make range searching a tedious and error prone task.

The range member function, often in combination with lambda expressions,
can greatly help alleviate this situation:

[code_tutorial_range]

`range` simply accepts predicates specifying the lower and upper bounds of 
the interval searched. Please consult the reference for a detailed explanation 
of the permissible predicates passed to range.

One or both bounds can be omitted with the special unbounded marker:

[code_tutorial_range_unbounded]

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

[endsect]

[endsect]

[section Bimaps with user defined names]

[import ../example/user_defined_names.cpp]

In the following example, the library user inserted comments to guide
future programmers:

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

[code_user_defined_names_untagged_version]

In Boost.Bimap there is a better way to document the code and
in the meantime helping you to write more maintainable and readable code.
You can tag the two collections of the bimap so they can be 
accessed by more descriptive names.

__TAGGED__

A tagged type is a type that has been labelled using a tag. A tag is any
valid C++ type. In a bimap, the types are always tagged. If you do not
specify your own tag, the container uses `member_at::left` and
`member_at::right` to tag the left and right sides respectively. In order
to specify a custom tag, the type of each side has to be tagged. 
Tagging a type is very simple:

    typedef tagged< int, a_tag > tagged_int;

Now we can rewrite the example:

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

[code_user_defined_names_tagged_version]

Here is a list of common structures in both tagged and untagged versions.
Remember that when the bimap has user defined tags you can still use 
the untagged version structures.


    struct Left  {};
    struct Right {};
    typedef bimap< 
             multiset_of< tagged< int, Left  > >,
        unordered_set_of< tagged< int, Right > >
    > bm_type;

    bm_type bm;

    //...

    bm_type::iterator       iter       = bm.begin();
    bm_type::left_iterator  left_iter  = bm.left.begin();
    bm_type::right_iterator right_iter = bm.right.begin();



[table Equivalence of expresions using user defined names
[[Untagged version]               [Tagged version]                     ]
[[`bm.left`]                      [`bm.by<Left>()`]                    ]
[[`bm.right`]                     [`bm.by<Right>()`]                   ]
[[`bm_type::left_map`]            [`bm::map_by<Left>::type`]           ]
[[`bm_type::right_value_type`]    [`bm::map_by<Right>::value_type`]    ]
[[`bm_type::left_iterator`]       [`bm::map_by<Left>::iterator`]       ]
[[`bm_type::right_const_iterator`][`bm::map_by<Right>::const_iterator`]]
[[`iter->left`]                   [`iter->get<Left>()`]                ]
[[`iter->right`]                  [`iter->get<Right>()`]               ]
[[`left_iter->first`]             [`left_iter->get<Left>()`]           ]
[[`left_iter->second`]            [`left_iter->get<Right>()`]          ]
[[`right_iter->first`]            [`right_iter->get<Right>()`]         ]
[[`right_iter->second`]           [`right_iter->get<Left>()`]          ]
[[`bm.project_left(iter)`]        [`bm.project<Left>(iter)`]           ]
[[`bm.project_right(iter)`]       [`bm.project<Right>(iter)`]          ]
]

[endsect]

[section Unconstrained Sets]

Unconstrained sets allow the user to disable one of the views of a
bimap. Doing so makes the bimap operations execute faster and reduces
memory consumption. This completes the bidirectional mapping framework
by including unidirectional mappings as a particular case.

Unconstrained sets are useful for the following reasons:

* A bimap type has stronger guarantees than its standard equivalent,
and includes some useful functions (replace, modify) that the standard
does not have.
* You can view the mapping as a collection of relations.
* Using this kind of map makes the code very extensible. If, at any
moment of the development, the need to perform searches from the right
side of the mapping arises, the only necessary change is to the `typedef`.

[import ../example/unconstrained_collection.cpp]

Given this bimap instance,

[code_unconstrained_collection_bimap]

or this standard map one

[code_unconstrained_collection_map]

The following code snippet is valid

[code_unconstrained_collection_common]

But using a bimap has some benefits

[code_unconstrained_collection_only_for_bimap]

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

[endsect]

[section Additional information]

[import ../example/tutorial_info_hook.cpp]

Bidirectional maps may have associated information about each relation.
Suppose we want to represent a books and author bidirectional map.

[code_tutorial_info_hook_nothing]

Suppose now that we want to store abstract of each book.
We have two options:

# Books name are unique identifiers, so we can create a separate
`std::map< string, string >` that relates books names with abstracts.
# We can use __BOOST_MULTI_INDEX__ for the new beast.

Option 1 is the wrong approach, if we go this path we lost what bimap has 
won us. We now have to maintain the logic of two interdependent containers,
there is an extra string stored for each book name, and the performance will
be worse. This is far away from being a good solution.

Option 2 is correct. We start thinking books as entries in a table. So it
makes sense to start using Boost.MultiIndex. We can then add the year
of publication, the price, etc... and we can index this new items too. So
Boost.MultiIndex is a sound solution for our problem.

The thing is that there are cases where we want to maintain bimap
semantics (use `at()` to find an author given a book name and the other way
around) and add information about the relations that we are sure we will not
want to index later (like the abstracts). Option 1 is not possible, option 2
neither.

Boost.Bimap provides support for this kind of situations by means of
an embedded information member.
You can pass an extra parameter to a bimap: `with_info< InfoType >`
and an `info` member of type `InfoType` will appear in the relation and bimap
pairs.

__RELATION_AND_PAIR_WITH_INFO__

Relations and bimap pairs constructors will take an extra argument.
If only two arguments are used, the information will be initialized with
their default constructor.

[code_tutorial_info_hook_first]

Contrary to the two key types, the information will be mutable using iterators.

[code_tutorial_info_hook_mutable]

A new function is included in ['unique] map views: `info_at(key)`, that mimics the
standard `at(key)` function but returned the associated information instead of
the data.

[code_tutorial_info_hook_info_at]

The info member can be tagged just as the left or the right member. The following
is a rewrite of the above example using user defined names:

[code_tutorial_info_hook_tagged_info]

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

[endsect]

[section Complete instantiation scheme]

To summarize, this is the complete instantiation scheme.

    typedef bimap
    <
        LeftCollectionType, RightCollectionType

        [ , SetTypeOfRelation  ]  // Default to left_based
        [ , with_info< Info >  ]  // Default to no info
        [ , Allocator          ]  // Default to std::allocator<>

    > bm;

`{Side}CollectionType` can directly be a type. This defaults to
`set_of<Type>`, or can be a `{CollectionType}_of<Type>` specification.
Additionally, the type of this two parameters can be tagged to specify 
user defined names instead of the usual `member_at::-Side-` tags. 

The possible way to use the first parameter are:

    bimap< Type, R >

* Left type:                `Type`
* Left collection type:     `set_of< Type >`
* Left tag:                 `member_at::left`

    bimap< {CollectionType}_of< Type >, R >

* Left type:                `Type`
* Left collection type:     `{CollectionType}_of< LeftType >`
* Left tag:                 `member_at::left`

    bimap< tagged< Type, Tag >, R >

* Left type:                `Type`
* Left collection type:     `set_of< LeftType >`
* Left tag:                 `Tag`

    bimap< {CollectionType}_of< tagged< Type, Tag > >, R >

* Left type:                `Type`
* Left collection type:     `{CollectionType}_of< LeftType >`
* Left tag:                 `Tag`

The same options are available for the second parameter.

The last three parameters are used to specify the collection type of the relation,
the information member and the allocator type.

If you want to specify a custom allocator type while relying on the default
value of CollectionTypeOfRelation, you can do so by simply writing
`bimap<LeftKeyType, RightKeyType, Allocator>`. Boost.Bimap's internal
machinery detects that the third parameter in this case does not refer
to the relation type but rather to an allocator.

The following are the possible ways of instantiating the last three parameters
of a bimap. You can ignore some of the parameter but the order must be respected.


    bimap< L, R >

* set_of_relation_type: based on the left key type
* info:                 no info
* allocator:            std::allocator


    bimap< L, R ,SetOfRelationType>

* set_of_relation_type: SetOfRelationType
* info:                 no info
* allocator:            std::allocator


    bimap< L, R , SetOfRelationType, with_info<Info> >

* set_of_relation_type: SetOfRelationType
* info:                 Info
* allocator:            std::allocator


    bimap< L, R , SetOfRelationType, with_info<Info>, Allocator>

* set_of_relation_type: SetOfRelationType
* info:                 Info
* allocator:            Allocator


    bimap< L, R , SetOfRelationType, Allocator>

* set_of_relation_type: SetOfRelationType
* info:                 no info
* allocator:            Allocator


    bimap< L, R , with_info<Info> >

* set_of_relation_type: based on the left key type
* info:                 Info
* allocator:            std::allocator


    bimap< L, R , with_info<Info>, Allocator>

* set_of_relation_type: based on the left key type
* allocator:            Allocator


    bimap< L, R , Allocator>

* set_of_relation_type: based on the left key type
* info:                 no info
* allocator:            Allocator




[endsect]

[endsect]