1[/license 2 3Boost.Bimap 4 5Copyright (c) 2006-2007 Matias Capeletto 6 7Distributed under the Boost Software License, Version 1.0. 8(See accompanying file LICENSE_1_0.txt or copy at 9http://www.boost.org/LICENSE_1_0.txt) 10 11] 12 13[/ QuickBook Document version 1.4 ] 14 15[section One minute tutorial] 16 17[heading What is a bimap?] 18 19A Bimap is a data structure that represents bidirectional relations between 20elements 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]). 21 22The following code creates an empty bimap container: 23 24 typedef bimap<X,Y> bm_type; 25 bm_type bm; 26 27Given this code, the following is the complete description of the resulting bimap. 28[footnote A type is ['signature-compatible] with other type if it has the same 29signature for functions and metadata. Preconditions, postconditions and the order 30of operations need not be the same. 31] 32 33* `bm.left` is signature-compatible with `std::map<X,Y>` 34* `bm.right` is signature-compatible with `std::map<Y,X>` 35* `bm` is signature-compatible with `std::set< relation<X,Y> >` 36 37__SIMPLE_BIMAP__ 38 39You can see how a bimap container offers three views over the same collection of bidirectional relations. 40 41If we have any generic function that work with maps 42 43 template< class MapType > 44 void print_map(const MapType & m) 45 { 46 typedef typename MapType::const_iterator const_iterator; 47 for( const_iterator iter = m.begin(), iend = m.end(); iter != iend; ++iter ) 48 { 49 std::cout << iter->first << "-->" << iter->second << std::endl; 50 } 51 } 52 53We can use the ['left map view] and the ['right map view] with it 54 55 bimap< int, std::string > bm; 56 ... 57 print_map( bm.left ); 58 print_map( bm.right ); 59 60And the output will be 61 62[pre 63[^1 --> one] 64[^2 --> two] 65... 66[^one --> 1] 67[^two --> 2] 68... 69] 70 71[heading Layout of the relation and the pairs of a bimap] 72 73The `relation` class represents two related elements. The two values are 74named left and right to express the symmetry of this type. 75The bimap pair classes are signature-compatible with `std::pairs`. 76 77__RELATION_AND_PAIR__ 78 79[heading Step by step] 80 81[import ../example/step_by_step.cpp] 82 83A convenience header is available in the boost directory: 84 85 #include <boost/bimap.hpp> 86 87Lets define a bidirectional map between integers and strings: 88 89[code_step_by_step_definition] 90 91[heading The collection of relations view] 92 93Remember that `bm` alone can be used as a set of relations. 94We can insert elements or iterate over them using this view. 95 96[code_step_by_step_set_of_relations_view] 97 98[heading The left map view] 99 100`bm.left` works like a `std::map< int, std::string >`. We use it 101in the same way we will use a standard map. 102 103[code_step_by_step_left_map_view] 104 105[heading The right map view] 106 107`bm.right` works like a `std::map< std::string, int >`. It is 108important to note that the key is the first type and the data 109is the second one, exactly as with standard maps. 110 111[code_step_by_step_right_map_view] 112 113[heading Differences with std::map] 114 115The main difference between bimap views and their standard containers counterparts 116is that, because of the bidirectional nature of a bimap, the values stored in 117it can not be modified directly using iterators. 118For example, when a `std::map<X,Y>` iterator is dereferenced the return type is 119`std::pair<const X, Y>`, so the following code is valid: 120`m.begin()->second = new_value;`. 121However dereferencing a `bimap<X,Y>::left_iterator` returns a type that is 122['signature-compatible] with a `std::pair<const X, const Y>` 123 124 bm.left.find(1)->second = "1"; // Compilation error 125 126If 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 127 128 bm.clear(); 129 130 bm.insert( bm_type::value_type( 1, "one" ) ); 131 132 bm.insert( bm_type::value_type( 1, "1" ) ); // No effect! 133 bm.insert( bm_type::value_type( 2, "one" ) ); // No effect! 134 135 assert( bm.size() == 1 ); 136 137[heading A simple example] 138 139Look how you can reuse code that is intend to be used with std::maps, like the 140print_map function in this example. 141 142[@../../example/simple_bimap.cpp Go to source code] 143 144[code_simple_bimap] 145 146The output of this program will be the following: 147[pre 148[^The number of countries is 4] 149 150[^The winner is Argentina] 151 152[^Countries names ordered by their final position:] 153[^1) Argentina] 154[^2) Spain] 155[^3) Germany] 156[^4) France] 157 158[^Countries names ordered alphabetically along with their final position:] 159[^Argentina ends in position 1] 160[^France ends in position 4] 161[^Germany ends in position 3] 162[^Spain ends in position 2] 163] 164 165 166[heading Continuing the journey] 167 168For information on function signatures, see any standard library 169documentation or read the [link boost_bimap.reference reference] section of 170this documentation. 171 172[caution 173Be aware that a bidirectional map is only signature-compatible with standard 174containers. Some functions may give different results, such as in the case of 175inserting a pair into the left map where the second value conflicts with a 176stored relation in the container. The functions may be slower in a bimap 177because of the duplicated constraints. It is strongly recommended that 178you read [link boost_bimap.the_tutorial The full tutorial] if you intend to 179use a bimap in a serious project. 180] 181 182[endsect] 183