123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182 |
- [/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 One minute tutorial]
- [heading What is a bimap?]
- A Bimap is a data structure that represents bidirectional relations between
- elements of two collections. The container is designed to work as two opposed STL maps. A bimap between a collection `X` and a collection `Y` can be viewed as a map from `X` to `Y` (this view will be called the ['left map view]) or as a map from `Y` to `X` (known as the ['right map view]). Additionally, the bimap can also be viewed as a set of relations between `X` and `Y` (named the ['collection of relations view]).
- The following code creates an empty bimap container:
- typedef bimap<X,Y> bm_type;
- bm_type bm;
- Given this code, the following is the complete description of the resulting bimap.
- [footnote A type is ['signature-compatible] with other type if it has the same
- signature for functions and metadata. Preconditions, postconditions and the order
- of operations need not be the same.
- ]
- * `bm.left` is signature-compatible with `std::map<X,Y>`
- * `bm.right` is signature-compatible with `std::map<Y,X>`
- * `bm` is signature-compatible with `std::set< relation<X,Y> >`
- __SIMPLE_BIMAP__
- You can see how a bimap container offers three views over the same collection of bidirectional relations.
- If we have any generic function that work with maps
- template< class MapType >
- void print_map(const MapType & m)
- {
- typedef typename MapType::const_iterator const_iterator;
- for( const_iterator iter = m.begin(), iend = m.end(); iter != iend; ++iter )
- {
- std::cout << iter->first << "-->" << iter->second << std::endl;
- }
- }
- We can use the ['left map view] and the ['right map view] with it
- bimap< int, std::string > bm;
- ...
- print_map( bm.left );
- print_map( bm.right );
- And the output will be
- [pre
- [^1 --> one]
- [^2 --> two]
- ...
- [^one --> 1]
- [^two --> 2]
- ...
- ]
- [heading Layout of the relation and the pairs of a bimap]
- The `relation` class represents two related elements. The two values are
- named left and right to express the symmetry of this type.
- The bimap pair classes are signature-compatible with `std::pairs`.
- __RELATION_AND_PAIR__
- [heading Step by step]
- [import ../example/step_by_step.cpp]
- A convenience header is available in the boost directory:
- #include <boost/bimap.hpp>
- Lets define a bidirectional map between integers and strings:
- [code_step_by_step_definition]
- [heading The collection of relations view]
- Remember that `bm` alone can be used as a set of relations.
- We can insert elements or iterate over them using this view.
- [code_step_by_step_set_of_relations_view]
- [heading The left map view]
- `bm.left` works like a `std::map< int, std::string >`. We use it
- in the same way we will use a standard map.
- [code_step_by_step_left_map_view]
- [heading The right map view]
- `bm.right` works like a `std::map< std::string, int >`. It is
- important to note that the key is the first type and the data
- is the second one, exactly as with standard maps.
- [code_step_by_step_right_map_view]
- [heading Differences with std::map]
- The main difference between bimap views and their standard containers counterparts
- is that, because of the bidirectional nature of a bimap, the values stored in
- it can not be modified directly using iterators.
- For example, when a `std::map<X,Y>` iterator is dereferenced the return type is
- `std::pair<const X, Y>`, so the following code is valid:
- `m.begin()->second = new_value;`.
- However dereferencing a `bimap<X,Y>::left_iterator` returns a type that is
- ['signature-compatible] with a `std::pair<const X, const Y>`
- bm.left.find(1)->second = "1"; // Compilation error
- If you insert `(1,"one")` and `(1,"1")` in a `std::map<int,std::string>` the second insertion will have no effect. In a `bimap<X,Y>` both keys have to remain unique. The insertion may fail in other situations too. Lets see an example
- bm.clear();
- bm.insert( bm_type::value_type( 1, "one" ) );
- bm.insert( bm_type::value_type( 1, "1" ) ); // No effect!
- bm.insert( bm_type::value_type( 2, "one" ) ); // No effect!
- assert( bm.size() == 1 );
- [heading A simple example]
- Look how you can reuse code that is intend to be used with std::maps, like the
- print_map function in this example.
- [@../../example/simple_bimap.cpp Go to source code]
- [code_simple_bimap]
- The output of this program will be the following:
- [pre
- [^The number of countries is 4]
- [^The winner is Argentina]
- [^Countries names ordered by their final position:]
- [^1) Argentina]
- [^2) Spain]
- [^3) Germany]
- [^4) France]
- [^Countries names ordered alphabetically along with their final position:]
- [^Argentina ends in position 1]
- [^France ends in position 4]
- [^Germany ends in position 3]
- [^Spain ends in position 2]
- ]
- [heading Continuing the journey]
- For information on function signatures, see any standard library
- documentation or read the [link boost_bimap.reference reference] section of
- this documentation.
- [caution
- Be aware that a bidirectional map is only signature-compatible with standard
- containers. Some functions may give different results, such as in the case of
- inserting a pair into the left map where the second value conflicts with a
- stored relation in the container. The functions may be slower in a bimap
- because of the duplicated constraints. It is strongly recommended that
- you read [link boost_bimap.the_tutorial The full tutorial] if you intend to
- use a bimap in a serious project.
- ]
- [endsect]
|