]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | [/license |
2 | ||
3 | Boost.Bimap | |
4 | ||
5 | Copyright (c) 2006-2007 Matias Capeletto | |
6 | ||
7 | Distributed under the Boost Software License, Version 1.0. | |
8 | (See accompanying file LICENSE_1_0.txt or copy at | |
9 | http://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 | ||
19 | A Bimap is a data structure that represents bidirectional relations between | |
20 | 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]). | |
21 | ||
22 | The following code creates an empty bimap container: | |
23 | ||
24 | typedef bimap<X,Y> bm_type; | |
25 | bm_type bm; | |
26 | ||
27 | Given 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 | |
29 | signature for functions and metadata. Preconditions, postconditions and the order | |
30 | of 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 | ||
39 | You can see how a bimap container offers three views over the same collection of bidirectional relations. | |
40 | ||
41 | If 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 | ||
53 | We 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 | ||
60 | And 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 | ||
73 | The `relation` class represents two related elements. The two values are | |
74 | named left and right to express the symmetry of this type. | |
75 | The 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 | ||
83 | A convenience header is available in the boost directory: | |
84 | ||
85 | #include <boost/bimap.hpp> | |
86 | ||
87 | Lets define a bidirectional map between integers and strings: | |
88 | ||
89 | [code_step_by_step_definition] | |
90 | ||
91 | [heading The collection of relations view] | |
92 | ||
93 | Remember that `bm` alone can be used as a set of relations. | |
94 | We 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 | |
101 | in 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 | |
108 | important to note that the key is the first type and the data | |
109 | is 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 | ||
115 | The main difference between bimap views and their standard containers counterparts | |
116 | is that, because of the bidirectional nature of a bimap, the values stored in | |
117 | it can not be modified directly using iterators. | |
118 | For 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;`. | |
121 | However 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 | ||
126 | 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 | |
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 | ||
139 | Look how you can reuse code that is intend to be used with std::maps, like the | |
140 | print_map function in this example. | |
141 | ||
142 | [@../../example/simple_bimap.cpp Go to source code] | |
143 | ||
144 | [code_simple_bimap] | |
145 | ||
146 | The 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 | ||
168 | For information on function signatures, see any standard library | |
169 | documentation or read the [link boost_bimap.reference reference] section of | |
170 | this documentation. | |
171 | ||
172 | [caution | |
173 | Be aware that a bidirectional map is only signature-compatible with standard | |
174 | containers. Some functions may give different results, such as in the case of | |
175 | inserting a pair into the left map where the second value conflicts with a | |
176 | stored relation in the container. The functions may be slower in a bimap | |
177 | because of the duplicated constraints. It is strongly recommended that | |
178 | you read [link boost_bimap.the_tutorial The full tutorial] if you intend to | |
179 | use a bimap in a serious project. | |
180 | ] | |
181 | ||
182 | [endsect] |