tutorial.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 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 requeriments are:

# Get a list of countries in decresing order of their populations.
# Given a countrie, get their population.

Lets create the appropiate 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,