]>
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 The tutorial] | |
16 | ||
17 | [section Roadmap] | |
18 | ||
19 | # Boost.Bimap is intuitive because it is based on the standard | |
20 | template library. New concepts are however presented to extend the | |
21 | standard maps to bidirectional maps. The first step is to gain a | |
22 | firm grasp of the bimap framework. The first section | |
23 | ([link boost_bimap.the_tutorial.discovering_the_bimap_framework Discovering the bimap framework]) | |
24 | aims to explain this. | |
25 | ||
26 | # Boost.Bimap offers much more than just a one-to-one ordered unique | |
27 | bidirectional map. It is possible to control the collection type of each side | |
28 | of the relationship that the bimap represents, giving one-to-many | |
29 | containers, hashed bidirectional containers and others that may be more | |
30 | suitable to the the task at hand. The second section | |
31 | ([link boost_bimap.the_tutorial.controlling_collection_types Controlling collection types]) | |
32 | explains how to instantiate a bimap with different collection constraints. | |
33 | ||
34 | # The section | |
35 | ([link boost_bimap.the_tutorial.the_collection_of_relations_type The "collection of relations" type]) | |
36 | explains how to create new types of bidirectional maps using custom collection types. | |
37 | ||
38 | # 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. | |
39 | ||
40 | # The section [link boost_bimap.the_tutorial.useful_functions Useful functions] provides information | |
41 | about functions of a bimap that are not found in the STL. | |
42 | ||
43 | # The types of a bimap can be tagged so that each side is accessible | |
44 | by something closer to the problem than left and right. This leads to | |
45 | more readable, self-documenting code. The fourth section | |
46 | ([link boost_bimap.the_tutorial.bimaps_with_user_defined_names Bimaps with user defined names]) shows | |
47 | how to use this feature. | |
48 | ||
49 | # The bimap mapping framework allows to disable a view of a bimap, including the standard | |
50 | mapping containers as a particular case. The section | |
51 | [link boost_bimap.the_tutorial.unconstrained_sets Unconstrained Sets] explains how they work. | |
52 | ||
53 | # The section [link boost_bimap.the_tutorial.additional_information Additional information] | |
54 | explains how to attach information to each relation of a bimap. | |
55 | ||
56 | # The final section | |
57 | ([link boost_bimap.the_tutorial.complete_instantiation_scheme Complete Instantiation Scheme]) | |
58 | summarizes bimap instantiation and explains how change the allocator type to be used. | |
59 | ||
60 | [endsect] | |
61 | ||
62 | [section Discovering the bimap framework] | |
63 | ||
64 | [section Interpreting bidirectional maps] | |
65 | ||
66 | One way to interpret bidirectional maps is as a function between two | |
67 | collections of data, lets call them the left and the right collection. | |
68 | An element in this bimap is a relation between an element from the left | |
69 | collection and an element from the right collection. | |
70 | The types of both collections defines the bimap behaviour. We can view | |
71 | the stored data from the left side, as a mapping between keys from the | |
72 | left collection and data from the right one, or from the right side, as | |
73 | a mapping between keys from the right collection and data from the | |
74 | left collection. | |
75 | ||
76 | [endsect] | |
77 | ||
78 | [section Standard mapping framework] | |
79 | ||
80 | Relationships between data in the STL are represented by maps. A | |
81 | standard map is a directed relation of keys from a left collection and | |
82 | data from a right unconstrained collection. | |
83 | The following diagram shows the relationship represented and the | |
84 | user's viewpoint. | |
85 | ||
86 | __STANDARD_MAPPING_FRAMEWORK__ | |
87 | ||
88 | 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`. | |
89 | The following table shows the equivalent types for the std associative containers. | |
90 | ||
91 | [table std associative containers | |
92 | [[container ][left collection type ][right collection type]] | |
93 | [[`map` ][`set_of` ][no constraints ]] | |
94 | [[`multimap` ][`multiset_of` ][no constraints ]] | |
95 | [[`unordered_map` ][`unordered_set_of` ][no constraints ]] | |
96 | [[`unordered_multimap`][`unordered_multiset_of` ][no constraints ]] | |
97 | ] | |
98 | ||
99 | [endsect] | |
100 | ||
101 | [section Bimap mapping framework] | |
102 | ||
103 | Boost.Bimap design is based on the STL, and extends the framework in a natural way. | |
104 | The following diagram represents the new situation. | |
105 | ||
106 | __EXTENDED_MAPPING_FRAMEWORK__ | |
107 | ||
108 | Notice that now the `std::maps` are a particular case of a Boost.Bimap | |
109 | container, where you can view only one side of the relationship and can | |
110 | control the constraints of only one of the collections. Boost.Bimap | |
111 | allows the user to view the relationship from three viewpoints. | |
112 | You can view it from one side, obtaining a `std::map` compatible | |
113 | container, or you can work directly with the whole relation. | |
114 | ||
115 | The next diagram shows the layout of the relation and pairs of a bimap. It is | |
116 | the one from the ['one minute tutorial] | |
117 | ||
118 | __RELATION_AND_PAIR__ | |
119 | ||
120 | Bimap pairs are signature-compatible with standard pairs but are different | |
121 | from them. As you will see in other sections they can be tagged with user | |
122 | defined names and additional information can be attached to them. You can | |
123 | convert from `std::pairs` to bimap pairs directly but the reverse conversion | |
124 | is not provided. This mean that you can insert elements in a bimap using | |
125 | algorithms like `std::copy` from containers `like std::map`, or use `std::make_pair` | |
126 | 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 | |
127 | copy constructor of each type. | |
128 | ||
129 | The following code snippet shows the relation between a bimap and standard | |
130 | maps. | |
131 | ||
132 | [note | |
133 | You have to used references to views, and not directly views object. | |
134 | Views cannot be constructed as separate objects from the container they | |
135 | belong to, so the following: | |
136 | `` | |
137 | // Wrong: we forgot the & after bm_type::left_type | |
138 | bm_type::left_map lm = bm.left; | |
139 | `` | |
140 | does not compile, since it is trying to construct the view object `lm`. | |
141 | This is a common source of errors in user code. | |
142 | ] | |
143 | ||
144 | [@../../example/standard_map_comparison.cpp Go to source code] | |
145 | ||
146 | [import ../example/standard_map_comparison.cpp] | |
147 | ||
148 | [code_standard_map_comparison] | |
149 | ||
150 | [endsect] | |
151 | ||
152 | [endsect] | |
153 | ||
154 | [section Controlling collection types] | |
155 | ||
156 | [section Freedom of choice] | |
157 | ||
158 | As has already been said, in STL maps, you can only control the | |
159 | constraints from one of the collections, namely the one that you are | |
160 | viewing. In Boost.Bimap, you can control both and it is as easy as using the STL. | |
161 | ||
162 | __EXTENDED_MAPPING_FRAMEWORK__ | |
163 | ||
164 | The idea is to use the same constraint names that are used in the | |
165 | standard. If you don't specify the collection type, Boost.Bimap assumes | |
166 | that the collection is a set. The instantiation of a bimap with custom | |
167 | collection types looks like this: | |
168 | ||
169 | typedef bimap< ``*CollectionType*``_of<A>, ``*CollectionType*``_of<B> > bm_type; | |
170 | ||
171 | The following is the list of all supported collection types. | |
172 | ||
173 | ||
174 | [table Collection of Key Types | |
175 | [[name ][Features ][map view type ]] | |
176 | [[`set_of` ][['ordered, unique]][`map` ]] | |
177 | [[`multiset_of` ][['ordered ]][`multimap` ]] | |
178 | [[`unordered_set_of` ][['hashed, unique ]][`unordered_map` ]] | |
179 | [[`unordered_multiset_of`][['hashed ]][`unordered_multimap` ]] | |
180 | [[`list_of` ][['sequenced ]][`list_map` ]] | |
181 | [[`vector_of` ][['random access ]][`vector_map` ]] | |
182 | [[`unconstrained_set_of` ][['unconstrained ]][['can not be viewed] ]] | |
183 | ] | |
184 | ||
185 | ||
186 | `list_of` and `vector_of` map views are not associated with any existing STL | |
187 | associative containers. They are two examples of unsorted associative | |
188 | containers. `unconstrained_set_of` allow the user to ignore a view. This | |
189 | will be explained later. | |
190 | ||
191 | __BIMAP_STRUCTURES__ | |
192 | ||
193 | The selection of the collection type affects the possible operations that you | |
194 | can perform with each side of the bimap and the time it takes to do | |
195 | each. If we have: | |
196 | ||
197 | typedef bimap< ``*CollectionType*``_of<A>, ``*CollectionType*``_of<B> > bm_type; | |
198 | bm_type bm; | |
199 | ||
200 | The following now describes the resulting map views of the bidirectional | |
201 | map. | |
202 | ||
203 | * `bm.left` is signature-compatible with *LeftMapType*`<A,B>` | |
204 | * `bm.right` is signature-compatible with *RightMapType*`<B,A>` | |
205 | ||
206 | [endsect] | |
207 | ||
208 | [section Configuration parameters] | |
209 | ||
210 | Each collection type template has different parameters to control its | |
211 | behaviour. For example, in `set_of` specification, you can pass a Functor | |
212 | type that compares two types. All of these parameters are exactly the | |
213 | same as those of the standard library container, except for the | |
214 | allocator type. You will learn later how to change the allocator for a | |
215 | bimap. | |
216 | ||
217 | The following table lists the meanings of each collection type's parameters. | |
218 | ||
219 | [table | |
220 | [[name ][Additional Parameters]] | |
221 | ||
222 | [[`set_of<T,KeyComp>` | |
223 | ||
224 | `multiset_of<T,KeyComp>` ] | |
225 | ||
226 | [[*KeyComp ] is a Functor that compares two types using a less-than operator. | |
227 | By default, this is `std::less<T>`. ]] | |
228 | ||
229 | [[`unordered_set_of<T,HashFunctor,EqualKey>` | |
230 | ||
231 | `unordered_multiset_of<T,HashFunctor,EqualKey>`] | |
232 | ||
233 | [[*HashFunctor ] converts a `T` object into an `std::size_t` value. By default it is `boost::hash<T>`. | |
234 | ||
235 | [*EqualKey ] is a Functor that tests two types for equality. By default, the | |
236 | equality operator is `std::equal_to<T>`. ]] | |
237 | [[`list_of<T>` ][No additional parameters.]] | |
238 | [[`vector_of<T>` ][No additional parameters.]] | |
239 | [[`unconstrained_set_of<T>` ][No additional parameters.]] | |
240 | ] | |
241 | ||
242 | [endsect] | |
243 | ||
244 | [section Examples] | |
245 | ||
246 | [heading Countries Populations] | |
247 | ||
248 | We want to store countries populations. | |
249 | The requirements are: | |
250 | ||
251 | # Get a list of countries in decreasing order of their populations. | |
252 | # Given a country, get their population. | |
253 | ||
254 | Lets create the appropriate bimap. | |
255 | ||
256 | typedef bimap< | |
257 | ||
258 | unordered_set_of< std::string >, | |
259 | multiset_of< long, std::greater<long> > | |
260 | ||
261 | > populations_bimap; | |
262 | ||
263 | First of all countries names are unique identifiers, while two countries | |
264 | may have the same population. This is why we choose *multi*`set_of` for | |
265 | populations. | |
266 | ||
267 | Using a `multiset_of` for population allow us to iterate over the data. | |
268 | Since listing countries ordered by their names is not a requisite, we can | |
269 | use an `unordered_set_of` that allows constant order look up. | |
270 | ||
271 | And now lets use it in a complete example | |
272 | ||
273 | [@../../example/population_bimap.cpp Go to source code] | |
274 | ||
275 | [import ../example/population_bimap.cpp] | |
276 | ||
277 | [code_population_bimap] | |
278 | ||
279 | ||
280 | [heading Repetitions counter] | |
281 | ||
282 | We want to count the repetitions for each word in a text and print them | |
283 | in order of appearance. | |
284 | ||
285 | [@../../example/repetitions_counter.cpp Go to source code] | |
286 | ||
287 | [import ../example/repetitions_counter.cpp] | |
288 | ||
289 | [code_repetitions_counter] | |
290 | ||
291 | [endsect] | |
292 | ||
293 | [endsect] | |
294 | ||
295 | [section The collection of relations type] | |
296 | ||
297 | [section A new point of view] | |
298 | ||
299 | Being able to change the collection type of the bimap relation view is another | |
300 | very important feature. Remember that this view allows the user to see | |
301 | the container as a group of the stored relations. This view has set | |
302 | semantics instead of map semantics. | |
303 | ||
304 | __COLLECTION_TYPE_OF_RELATION__ | |
305 | ||
306 | By default, Boost.Bimap will base the collection type of the relation on the | |
307 | type of the left collection. If the left collection type is a set, then the collection | |
308 | type of the relation will be a set with the same order as the left view. | |
309 | ||
310 | In general, Boost.Bimap users will base the collection type of a relation on | |
311 | the type of the collection on one of the two sides. However there are times | |
312 | where it is useful to give this collection other constraints or simply to order | |
313 | it differently. The user is allowed to choose between: | |
314 | ||
315 | * left_based | |
316 | * right_based | |
317 | * set_of_relation<> | |
318 | * multiset_of_relation<> | |
319 | * unordered_set_of_relation<> | |
320 | * unordered_multiset_of_relation<> | |
321 | * list_of_relation | |
322 | * vector_of_relation | |
323 | * unconstrained_set_of_relation | |
324 | ||
325 | [tip | |
326 | The first two options and the last produce faster bimaps, so prefer | |
327 | these where possible. | |
328 | ] | |
329 | ||
330 | __MORE_BIMAP_STRUCTURES__ | |
331 | ||
332 | The collection type of relation can be used to create powerful containers. For | |
333 | example, if you need to maximize search speed, then the best | |
334 | bidirectional map possible is one that relates elements from an | |
335 | `unordered_set` to another `unordered_set`. The problem is that this | |
336 | container cannot be iterated. If you need to know the list of relations | |
337 | inside the container, you need another collection type of relation. In this | |
338 | case, a `list_of_relation` is a good choice. The resulting container | |
339 | trades insertion and deletion time against fast search capabilities and | |
340 | the possibility of bidirectional iteration. | |
341 | ||
342 | [@../../example/mighty_bimap.cpp Go to source code] | |
343 | ||
344 | [code_mighty_bimap] | |
345 | ||
346 | [endsect] | |
347 | ||
348 | [section Configuration parameters] | |
349 | ||
350 | Each collection type of relation has different parameters to control its | |
351 | behaviour. For example, in the `set_of_relation` specification, you can | |
352 | pass a Functor type that compares two types. All of the parameters are | |
353 | exactly as in the standard library containers, except for the type, | |
354 | which is set to the bimap relation and the allocator type. To help users | |
355 | in the creation of each functor, the collection type of relation templates | |
356 | takes an mpl lambda expression where the relation type will be evaluated | |
357 | later. A placeholder named `_relation` is available to bimap users. | |
358 | ||
359 | The following table lists the meaning of the parameters for each collection type of | |
360 | relations. | |
361 | ||
362 | [table | |
363 | [[name ][Additional Parameters]] | |
364 | ||
365 | [[`left_based` ][Not a template.]] | |
366 | [[`right_based` ][Not a template.]] | |
367 | [[`set_of_relation<KeyComp>` | |
368 | ||
369 | `multiset_of_relation<KeyComp>` ] | |
370 | [[*KeyComp ] is a Functor that compares two types using less than. By | |
371 | default, the less-than operator is `std::less<_relation>`. ]] | |
372 | ||
373 | [[`unordered_set_of_relation<HashFunctor,EqualKey>` | |
374 | ||
375 | `unordered_multiset_of_relation<HashFunctor,EqualKey>`] | |
376 | [[*HashFunctor ] converts the `relation` into an `std::size_t` value. By default it is `boost::hash<_relation>`. | |
377 | ||
378 | [*EqualKey ] is a Functor that tests two relations for equality. By default, | |
379 | the equality operator is `std::equal_to<_relation>`. ]] | |
380 | [[`list_of_relation` ][Not a template.]] | |
381 | [[`vector_of_relation` ][Not a template.]] | |
382 | [[`unconstrained_set_of_relation` ][Not a template.]] | |
383 | ] | |
384 | ||
385 | [endsect] | |
386 | ||
387 | [section Examples] | |
388 | ||
389 | Consider this example: | |
390 | ||
391 | template< class Rel > | |
392 | struct RelOrder | |
393 | { | |
394 | bool operator()(Rel ra, Rel rb) const | |
395 | { | |
396 | return (ra.left+ra.right) < (rb.left+rb.right); | |
397 | } | |
398 | }; | |
399 | ||
400 | typedef bimap | |
401 | < | |
402 | multiset_of< int >, | |
403 | multiset_of< int >, | |
404 | set_of_relation< RelOrder<_relation> > | |
405 | ||
406 | > bimap_type; | |
407 | ||
408 | Here the bimap relation view is ordered using the information of | |
409 | both sides. This container will only allow unique relations because | |
410 | `set_of_relation` has been used but the elements in each side of the | |
411 | bimap can be repeated. | |
412 | ||
413 | struct name {}; | |
414 | struct phone_number {}; | |
415 | ||
416 | typedef bimap | |
417 | < | |
418 | tagged< unordered_multiset_of< string >, name >, | |
419 | tagged< unordered_set_of < int >, phone_number >, | |
420 | set_of_relation<> | |
421 | ||
422 | > bimap_type; | |
423 | ||
424 | In this other case the bimap will relate names to phone numbers. | |
425 | Names can be repeated and phone numbers are unique. You can perform | |
426 | quick searches by name or phone number and the container can be viewed | |
427 | ordered using the relation view. | |
428 | ||
429 | [endsect] | |
430 | ||
431 | [endsect] | |
432 | ||
433 | [section Differences with standard maps] | |
434 | ||
435 | [section Insertion] | |
436 | ||
437 | Remember that a map can be interpreted as a relation between two collections. | |
438 | In bimaps we have the freedom to change both collection types, imposing | |
439 | constrains in each of them. Some insertions that we give for granted to | |
440 | success in standard maps fails with bimaps. | |
441 | For example: | |
442 | ||
443 | bimap<int,std::string> bm; | |
444 | ||
445 | bm.left.insert(1,"orange"); | |
446 | bm.left.insert(2,"orange"); // No effect! returns make_pair(iter,false) | |
447 | ||
448 | The insertion will only succeed if it is allowed by all views of the `bimap`. | |
449 | In the next snippet we define the right collection as a multiset, when we | |
450 | try to insert the same two elements the second insertion is allowed by the | |
451 | left map view because both values are different and it is allowed by the | |
452 | right map view because it is a non-unique collection type. | |
453 | ||
454 | bimap<int, multiset_of<std::string> > bm; | |
455 | ||
456 | bm.left.insert(1,"orange"); | |
457 | bm.left.insert(2,"orange"); // Insertion succeed! | |
458 | ||
459 | If we use a custom collection of relation type, the insertion has to be | |
460 | allowed by it too. | |
461 | ||
462 | [endsect] | |
463 | ||
464 | [section iterator::value_type] | |
465 | ||
466 | The relations stored in the Bimap will not be in most cases modifiable | |
467 | directly by iterators because both sides are used as keys of | |
468 | ['key-based] sets. When a `bimap<A,B>` left view iterator is dereferenced | |
469 | the return type is ['signature-compatible] with a | |
470 | `std::pair< const A, const B >`. | |
471 | However there are some collection types that are not ['key_based], for example | |
472 | list_of. If a Bimap uses one of these collection types there is no problem with | |
473 | modifying the data of that side. The following code is valid: | |
474 | ||
475 | typedef bimap< int, list_of< std::string > > bm_type; | |
476 | bm_type bm; | |
477 | bm.insert( bm_type::relation( 1, "one" ) ); | |
478 | ... | |
479 | bm.left.find(1)->second = "1"; // Valid | |
480 | ||
481 | In this case, when the iterator is dereferenced the return type is | |
482 | ['signature-compatible] with a `std::pair<const int, std::string>`. | |
483 | ||
484 | The following table shows the constness of the dereferenced data of each | |
485 | collection type of: | |
486 | ||
487 | [table | |
488 | [[Side collection type ][Dereferenced data]] | |
489 | [[`set_of` ][['constant]]] | |
490 | [[`multiset_of` ][['constant]]] | |
491 | [[`unordered_set_of` ][['constant]]] | |
492 | [[`unordered_multiset_of`][['constant]]] | |
493 | [[`list_of` ][['mutable] ]] | |
494 | [[`vector_of` ][['mutable] ]] | |
495 | [[`unconstrained_set_of` ][['mutable] ]] | |
496 | ] | |
497 | ||
498 | Here are some examples. When dereferenced the iterators returns a type that | |
499 | is ['signature-compatible] with these types. | |
500 | ||
501 | [table | |
502 | [[Bimap type ][Signature-compatible types]] | |
503 | [[`bimap<A,B>`][ | |
504 | `iterator ` *->* `relation<const A,const B>` | |
505 | ||
506 | `left_iterator ` *->* `pair<const A,const B>` | |
507 | ||
508 | `right_iterator` *->* `pair<const B,const A>` | |
509 | ]] | |
510 | [[`bimap<multiset_of<A>,unordered_set_of<B> >`][ | |
511 | `iterator ` *->* `relation<const A,const B>` | |
512 | ||
513 | `left_iterator ` *->* `pair<const A,const B>` | |
514 | ||
515 | `right_iterator` *->* `pair<const B,const A>` | |
516 | ]] | |
517 | [[`bimap<set_of<A>,list_of<B> >`][ | |
518 | `iterator ` *->* `relation<const A,B>` | |
519 | ||
520 | `left_iterator ` *->* `pair<const A,B>` | |
521 | ||
522 | `right_iterator` *->* `pair<B,const A>` | |
523 | ]] | |
524 | [[`bimap<vector_of<A>,set_of<B> >`][ | |
525 | `iterator ` *->* `relation<A,const B>` | |
526 | ||
527 | `left_iterator ` *->* `pair<A,const B>` | |
528 | ||
529 | `right_iterator` *->* `pair<const B,A>` | |
530 | ]] | |
531 | [[`bimap<list_of<A>,unconstrained_set_of<B> >`][ | |
532 | `iterator ` *->* `relation<A,B>` | |
533 | ||
534 | `left_iterator ` *->* `pair<A,B>` | |
535 | ||
536 | `right_iterator` *->* `pair<B,A>` | |
537 | ]] | |
538 | ] | |
539 | ||
540 | [endsect] | |
541 | ||
542 | [section operator\[\] and at()] | |
543 | ||
544 | `set_of` and `unordered_set_of` map views overload `operator[]` to retrieve the | |
545 | associated data of a given key only when the other collection type is a | |
546 | mutable one. In these cases it works in the same way as the standard. | |
547 | ||
548 | bimap< unorderd_set_of< std::string>, list_of<int> > bm; | |
549 | ||
550 | bm.left["one"] = 1; // Ok | |
551 | ||
552 | The standard defines an access function for `map` and `unordered_map`: | |
553 | ||
554 | const data_type & at(const key_type & k) const; | |
555 | data_type & at(const key_type & k); | |
556 | ||
557 | These functions look for a key and returns the associated data value, but | |
558 | throws a `std::out_of_range` exception if the key is not found. | |
559 | ||
560 | In bimaps the constant version of these functions is given for `set_of` and | |
561 | `unorderd_set_of` map views independently of the other collection type. | |
562 | The mutable version is only provided when the other collection type is | |
563 | mutable. | |
564 | ||
565 | The following examples shows the behaviour of `at(key)` | |
566 | ||
567 | [@../../example/at_function_examples.cpp Go to source code] | |
568 | ||
569 | [import ../example/at_function_examples.cpp] | |
570 | ||
571 | [code_at_function_first] | |
572 | ||
573 | [code_at_function_second] | |
574 | ||
575 | [/ | |
576 | `set_of` and `unordered_set_of` views overload `operator[]` to retrieve the | |
577 | associated data of a given key. | |
578 | The symmetry of bimap imposes some constraints on `operator[]` that are | |
579 | not found in `std::map` or `std::unordered_map`. If other views are unique, | |
580 | `bimap::duplicate_value` is thrown whenever an assignment is attempted to | |
581 | a value that is already a key in these views. As for | |
582 | `bimap::value_not_found`, this exception is thrown while trying to access | |
583 | a non-existent key: this behaviour differs from the standard containers, | |
584 | which automatically assigns a default value to non-existent keys referred to | |
585 | by `operator[]`. | |
586 | ||
587 | ||
588 | const data_type & operator[](const typename key_type & k) const; | |
589 | ||
590 | [: Returns the `data_type` reference that is associated with `k`, or | |
591 | throws `bimap::value_not_found` if such an element does not exist. | |
592 | ] | |
593 | ||
594 | ``['-unspecified data_type proxy-]`` operator[](const typename key_type & k); | |
595 | ||
596 | [: Returns a proxy to a `data_type` associated with `k` and the | |
597 | bimap. The proxy behaves as a reference to the `data_type` object. If this | |
598 | proxy is read and `k` was not in the bimap, the bimap::value_not_found is | |
599 | thrown. If it is written then `bimap::duplicate_value` is thrown if the | |
600 | assignment is not allowed by one of the other views of the `bimap`. | |
601 | ] | |
602 | ||
603 | ||
604 | The following example shows the behaviour of `operator[]` | |
605 | ||
606 | bimap<int,std::string> bm; | |
607 | ||
608 | bm.left[1] = "one"; // Ok | |
609 | ||
610 | bm.right["two"] = 2; // Ok | |
611 | ||
612 | if( bm.left[3] == "three" ) // throws bimap::value_not_found | |
613 | { | |
614 | ... | |
615 | } | |
616 | ||
617 | bm.left[3] = "one"; // throws bimap::duplicate_value | |
618 | ] | |
619 | ||
620 | [endsect] | |
621 | ||
622 | [section Complexity of operations] | |
623 | ||
624 | The complexity of some operations is different in bimaps. Read | |
625 | [link complexity_signature_explanation the reference] to find the | |
626 | complexity of each function. | |
627 | ||
628 | [endsect] | |
629 | ||
630 | [endsect] | |
631 | ||
632 | [section Useful functions] | |
633 | ||
634 | [section Projection of iterators] | |
635 | ||
636 | Iterators can be projected to any of the three views of the bimap. | |
637 | A bimap provides three member functions to cope with projection: `project_left`, | |
638 | `project_right` and `project_up`, with projects iterators to the ['left map view], | |
639 | the ['right map view] and the ['collection of relations view]. These functions | |
640 | take any iterator from the bimap and retrieve an iterator over the projected view | |
641 | pointing to the same element. | |
642 | ||
643 | [import ../example/projection.cpp] | |
644 | ||
645 | Here is an example that uses projection: | |
646 | ||
647 | [@../../example/projection.cpp Go to source code] | |
648 | ||
649 | [code_projection_years] | |
650 | ||
651 | [endsect] | |
652 | ||
653 | [section replace and modify] | |
654 | ||
655 | [import ../example/tutorial_modify_and_replace.cpp] | |
656 | ||
657 | These functions are members of the views of a bimap that are not founded in | |
658 | their standard counterparts. | |
659 | ||
660 | The `replace` family member functions performs in-place replacement of a given | |
661 | element as the following example shows: | |
662 | ||
663 | [@../../example/tutorial_modify_and_replace.cpp Go to source code] | |
664 | ||
665 | [code_tutorial_replace] | |
666 | ||
667 | `replace` functions performs this substitution in such a manner that: | |
668 | ||
669 | * The complexity is constant time if the changed element retains its original order | |
670 | with respect to all views; it is logarithmic otherwise. | |
671 | * Iterator and reference validity are preserved. | |
672 | * The operation is strongly exception-safe, i.e. the `bimap` remains unchanged if | |
673 | some exception (originated by the system or the user's data types) is thrown. | |
674 | ||
675 | `replace` functions are powerful operations not provided by standard STL containers, | |
676 | and one that is specially handy when strong exception-safety is required. | |
677 | ||
678 | The observant reader might have noticed that the convenience of replace comes at a | |
679 | cost: namely the whole element has to be copied ['twice] to do the updating (when | |
680 | retrieving it and inside `replace`). If elements are expensive to copy, this may | |
681 | be quite a computational cost for the modification of just a tiny part of the | |
682 | object. To cope with this situation, Boost.Bimap provides an alternative | |
683 | updating mechanism: `modify` functions. | |
684 | ||
685 | `modify` functions accepts a functor (or pointer to function) taking a reference | |
686 | to the data to be changed, thus eliminating the need for spurious copies. Like | |
687 | `replace` functions, `modify` functions does preserve the internal orderings of | |
688 | all the indices of the `bimap`. However, the semantics of modify functions are not | |
689 | entirely equivalent to replace functions. Consider what happens if a collision occurs | |
690 | as a result of modifying the element, i.e. the modified element clashes with another | |
691 | with respect to some unique view. In the case of `replace` functions, the original | |
692 | value is kept and the method returns without altering the container, but `modify` | |
693 | functions cannot afford such an approach, since the modifying functor leaves no | |
694 | trace of the previous value of the element. Integrity constraints thus lead to the | |
695 | following policy: when a collision happens in the process of calling a modify functions, | |
696 | the element is erased and the method returns false. This difference in behavior | |
697 | between `replace` and `modify` functions has to be considered by the programmer on | |
698 | a case-by-case basis. | |
699 | ||
700 | Boost.Bimap defines new placeholders named `_key` and `_data` to allow a sounder solution. | |
701 | You have to include `<boost/bimap/support/lambda.hpp>` to use them. | |
702 | ||
703 | [/ | |
704 | Boost.Bimap defines new placeholders to allow a sounder solution. For | |
705 | pairs, two new placeholders are instantiated: `_first` and `_second`, and | |
706 | for a relation, two more complete the set: `_left` and `_right`. | |
707 | ] | |
708 | ||
709 | [@../../example/tutorial_modify_and_replace.cpp Go to source code] | |
710 | ||
711 | [code_tutorial_modify] | |
712 | ||
713 | [endsect] | |
714 | ||
715 | [section Retrieval of ranges] | |
716 | ||
717 | [import ../example/tutorial_range.cpp] | |
718 | ||
719 | Standard `lower_bound` and `upper_bound` functions can be used to lookup for | |
720 | all the elements in a given range. | |
721 | ||
722 | Suppose we want to retrieve the elements from a `bimap<int,std::string>` | |
723 | where the left value is in the range `[20,50]` | |
724 | ||
725 | [code_tutorial_range_standard_way] | |
726 | ||
727 | Subtle changes to the code are required when strict inequalities are considered. | |
728 | To retrieve the elements greater than 20 and less than 50, the code has to be | |
729 | rewritten as | |
730 | ||
731 | [code_tutorial_range_standard_way_subtle_changes] | |
732 | ||
733 | To add to this complexity, the careful programmer has to take into account that | |
734 | the lower and upper bounds of the interval searched be compatible: for instance, | |
735 | if the lower bound is 50 and the upper bound is 20, the iterators `iter_first` and | |
736 | `iter_second` produced by the code above will be in reverse order, with possibly | |
737 | catastrophic results if a traversal from `iter_first` to `iter_second` is tried. | |
738 | All these details make range searching a tedious and error prone task. | |
739 | ||
740 | The range member function, often in combination with lambda expressions, | |
741 | can greatly help alleviate this situation: | |
742 | ||
743 | [code_tutorial_range] | |
744 | ||
745 | `range` simply accepts predicates specifying the lower and upper bounds of | |
746 | the interval searched. Please consult the reference for a detailed explanation | |
747 | of the permissible predicates passed to range. | |
748 | ||
749 | One or both bounds can be omitted with the special unbounded marker: | |
750 | ||
751 | [code_tutorial_range_unbounded] | |
752 | ||
753 | [@../../example/tutorial_range.cpp Go to source code] | |
754 | ||
755 | [endsect] | |
756 | ||
757 | [endsect] | |
758 | ||
759 | [section Bimaps with user defined names] | |
760 | ||
761 | [import ../example/user_defined_names.cpp] | |
762 | ||
763 | In the following example, the library user inserted comments to guide | |
764 | future programmers: | |
765 | ||
766 | [@../../example/user_defined_names.cpp Go to source code] | |
767 | ||
768 | [code_user_defined_names_untagged_version] | |
769 | ||
770 | In Boost.Bimap there is a better way to document the code and | |
771 | in the meantime helping you to write more maintainable and readable code. | |
772 | You can tag the two collections of the bimap so they can be | |
773 | accessed by more descriptive names. | |
774 | ||
775 | __TAGGED__ | |
776 | ||
777 | A tagged type is a type that has been labelled using a tag. A tag is any | |
778 | valid C++ type. In a bimap, the types are always tagged. If you do not | |
779 | specify your own tag, the container uses `member_at::left` and | |
780 | `member_at::right` to tag the left and right sides respectively. In order | |
781 | to specify a custom tag, the type of each side has to be tagged. | |
782 | Tagging a type is very simple: | |
783 | ||
784 | typedef tagged< int, a_tag > tagged_int; | |
785 | ||
786 | Now we can rewrite the example: | |
787 | ||
788 | [@../../example/user_defined_names.cpp Go to source code] | |
789 | ||
790 | [code_user_defined_names_tagged_version] | |
791 | ||
792 | Here is a list of common structures in both tagged and untagged versions. | |
793 | Remember that when the bimap has user defined tags you can still use | |
794 | the untagged version structures. | |
795 | ||
796 | ||
797 | struct Left {}; | |
798 | struct Right {}; | |
799 | typedef bimap< | |
800 | multiset_of< tagged< int, Left > >, | |
801 | unordered_set_of< tagged< int, Right > > | |
802 | > bm_type; | |
803 | ||
804 | bm_type bm; | |
805 | ||
806 | //... | |
807 | ||
808 | bm_type::iterator iter = bm.begin(); | |
809 | bm_type::left_iterator left_iter = bm.left.begin(); | |
810 | bm_type::right_iterator right_iter = bm.right.begin(); | |
811 | ||
812 | ||
813 | ||
814 | [table Equivalence of expresions using user defined names | |
815 | [[Untagged version] [Tagged version] ] | |
816 | [[`bm.left`] [`bm.by<Left>()`] ] | |
817 | [[`bm.right`] [`bm.by<Right>()`] ] | |
818 | [[`bm_type::left_map`] [`bm::map_by<Left>::type`] ] | |
819 | [[`bm_type::right_value_type`] [`bm::map_by<Right>::value_type`] ] | |
820 | [[`bm_type::left_iterator`] [`bm::map_by<Left>::iterator`] ] | |
821 | [[`bm_type::right_const_iterator`][`bm::map_by<Right>::const_iterator`]] | |
822 | [[`iter->left`] [`iter->get<Left>()`] ] | |
823 | [[`iter->right`] [`iter->get<Right>()`] ] | |
824 | [[`left_iter->first`] [`left_iter->get<Left>()`] ] | |
825 | [[`left_iter->second`] [`left_iter->get<Right>()`] ] | |
826 | [[`right_iter->first`] [`right_iter->get<Right>()`] ] | |
827 | [[`right_iter->second`] [`right_iter->get<Left>()`] ] | |
828 | [[`bm.project_left(iter)`] [`bm.project<Left>(iter)`] ] | |
829 | [[`bm.project_right(iter)`] [`bm.project<Right>(iter)`] ] | |
830 | ] | |
831 | ||
832 | [endsect] | |
833 | ||
834 | [section Unconstrained Sets] | |
835 | ||
836 | Unconstrained sets allow the user to disable one of the views of a | |
837 | bimap. Doing so makes the bimap operations execute faster and reduces | |
838 | memory consumption. This completes the bidirectional mapping framework | |
839 | by including unidirectional mappings as a particular case. | |
840 | ||
841 | Unconstrained sets are useful for the following reasons: | |
842 | ||
843 | * A bimap type has stronger guarantees than its standard equivalent, | |
844 | and includes some useful functions (replace, modify) that the standard | |
845 | does not have. | |
846 | * You can view the mapping as a collection of relations. | |
847 | * Using this kind of map makes the code very extensible. If, at any | |
848 | moment of the development, the need to perform searches from the right | |
849 | side of the mapping arises, the only necessary change is to the `typedef`. | |
850 | ||
851 | [import ../example/unconstrained_collection.cpp] | |
852 | ||
853 | Given this bimap instance, | |
854 | ||
855 | [code_unconstrained_collection_bimap] | |
856 | ||
857 | or this standard map one | |
858 | ||
859 | [code_unconstrained_collection_map] | |
860 | ||
861 | The following code snippet is valid | |
862 | ||
863 | [code_unconstrained_collection_common] | |
864 | ||
865 | But using a bimap has some benefits | |
866 | ||
867 | [code_unconstrained_collection_only_for_bimap] | |
868 | ||
869 | [@../../example/unconstrained_collection.cpp Go to source code] | |
870 | ||
871 | [endsect] | |
872 | ||
873 | [section Additional information] | |
874 | ||
875 | [import ../example/tutorial_info_hook.cpp] | |
876 | ||
877 | Bidirectional maps may have associated information about each relation. | |
878 | Suppose we want to represent a books and author bidirectional map. | |
879 | ||
880 | [code_tutorial_info_hook_nothing] | |
881 | ||
882 | Suppose now that we want to store abstract of each book. | |
883 | We have two options: | |
884 | ||
885 | # Books name are unique identifiers, so we can create a separate | |
886 | `std::map< string, string >` that relates books names with abstracts. | |
887 | # We can use __BOOST_MULTI_INDEX__ for the new beast. | |
888 | ||
889 | Option 1 is the wrong approach, if we go this path we lost what bimap has | |
890 | won us. We now have to maintain the logic of two interdependent containers, | |
891 | there is an extra string stored for each book name, and the performance will | |
892 | be worse. This is far away from being a good solution. | |
893 | ||
894 | Option 2 is correct. We start thinking books as entries in a table. So it | |
895 | makes sense to start using Boost.MultiIndex. We can then add the year | |
896 | of publication, the price, etc... and we can index this new items too. So | |
897 | Boost.MultiIndex is a sound solution for our problem. | |
898 | ||
899 | The thing is that there are cases where we want to maintain bimap | |
900 | semantics (use `at()` to find an author given a book name and the other way | |
901 | around) and add information about the relations that we are sure we will not | |
902 | want to index later (like the abstracts). Option 1 is not possible, option 2 | |
903 | neither. | |
904 | ||
905 | Boost.Bimap provides support for this kind of situations by means of | |
906 | an embedded information member. | |
907 | You can pass an extra parameter to a bimap: `with_info< InfoType >` | |
908 | and an `info` member of type `InfoType` will appear in the relation and bimap | |
909 | pairs. | |
910 | ||
911 | __RELATION_AND_PAIR_WITH_INFO__ | |
912 | ||
913 | Relations and bimap pairs constructors will take an extra argument. | |
914 | If only two arguments are used, the information will be initialized with | |
915 | their default constructor. | |
916 | ||
917 | [code_tutorial_info_hook_first] | |
918 | ||
919 | Contrary to the two key types, the information will be mutable using iterators. | |
920 | ||
921 | [code_tutorial_info_hook_mutable] | |
922 | ||
923 | A new function is included in ['unique] map views: `info_at(key)`, that mimics the | |
924 | standard `at(key)` function but returned the associated information instead of | |
925 | the data. | |
926 | ||
927 | [code_tutorial_info_hook_info_at] | |
928 | ||
929 | The info member can be tagged just as the left or the right member. The following | |
930 | is a rewrite of the above example using user defined names: | |
931 | ||
932 | [code_tutorial_info_hook_tagged_info] | |
933 | ||
934 | [@../../example/tutorial_info_hook.cpp Go to source code] | |
935 | ||
936 | [endsect] | |
937 | ||
938 | [section Complete instantiation scheme] | |
939 | ||
940 | To summarize, this is the complete instantiation scheme. | |
941 | ||
942 | typedef bimap | |
943 | < | |
944 | LeftCollectionType, RightCollectionType | |
945 | ||
946 | [ , SetTypeOfRelation ] // Default to left_based | |
947 | [ , with_info< Info > ] // Default to no info | |
948 | [ , Allocator ] // Default to std::allocator<> | |
949 | ||
950 | > bm; | |
951 | ||
952 | `{Side}CollectionType` can directly be a type. This defaults to | |
953 | `set_of<Type>`, or can be a `{CollectionType}_of<Type>` specification. | |
954 | Additionally, the type of this two parameters can be tagged to specify | |
955 | user defined names instead of the usual `member_at::-Side-` tags. | |
956 | ||
957 | The possible way to use the first parameter are: | |
958 | ||
959 | bimap< Type, R > | |
960 | ||
961 | * Left type: `Type` | |
962 | * Left collection type: `set_of< Type >` | |
963 | * Left tag: `member_at::left` | |
964 | ||
965 | bimap< {CollectionType}_of< Type >, R > | |
966 | ||
967 | * Left type: `Type` | |
968 | * Left collection type: `{CollectionType}_of< LeftType >` | |
969 | * Left tag: `member_at::left` | |
970 | ||
971 | bimap< tagged< Type, Tag >, R > | |
972 | ||
973 | * Left type: `Type` | |
974 | * Left collection type: `set_of< LeftType >` | |
975 | * Left tag: `Tag` | |
976 | ||
977 | bimap< {CollectionType}_of< tagged< Type, Tag > >, R > | |
978 | ||
979 | * Left type: `Type` | |
980 | * Left collection type: `{CollectionType}_of< LeftType >` | |
981 | * Left tag: `Tag` | |
982 | ||
983 | The same options are available for the second parameter. | |
984 | ||
985 | The last three parameters are used to specify the collection type of the relation, | |
986 | the information member and the allocator type. | |
987 | ||
988 | If you want to specify a custom allocator type while relying on the default | |
989 | value of CollectionTypeOfRelation, you can do so by simply writing | |
990 | `bimap<LeftKeyType, RightKeyType, Allocator>`. Boost.Bimap's internal | |
991 | machinery detects that the third parameter in this case does not refer | |
992 | to the relation type but rather to an allocator. | |
993 | ||
994 | The following are the possible ways of instantiating the last three parameters | |
995 | of a bimap. You can ignore some of the parameter but the order must be respected. | |
996 | ||
997 | ||
998 | bimap< L, R > | |
999 | ||
1000 | * set_of_relation_type: based on the left key type | |
1001 | * info: no info | |
1002 | * allocator: std::allocator | |
1003 | ||
1004 | ||
1005 | bimap< L, R ,SetOfRelationType> | |
1006 | ||
1007 | * set_of_relation_type: SetOfRelationType | |
1008 | * info: no info | |
1009 | * allocator: std::allocator | |
1010 | ||
1011 | ||
1012 | bimap< L, R , SetOfRelationType, with_info<Info> > | |
1013 | ||
1014 | * set_of_relation_type: SetOfRelationType | |
1015 | * info: Info | |
1016 | * allocator: std::allocator | |
1017 | ||
1018 | ||
1019 | bimap< L, R , SetOfRelationType, with_info<Info>, Allocator> | |
1020 | ||
1021 | * set_of_relation_type: SetOfRelationType | |
1022 | * info: Info | |
1023 | * allocator: Allocator | |
1024 | ||
1025 | ||
1026 | bimap< L, R , SetOfRelationType, Allocator> | |
1027 | ||
1028 | * set_of_relation_type: SetOfRelationType | |
1029 | * info: no info | |
1030 | * allocator: Allocator | |
1031 | ||
1032 | ||
1033 | bimap< L, R , with_info<Info> > | |
1034 | ||
1035 | * set_of_relation_type: based on the left key type | |
1036 | * info: Info | |
1037 | * allocator: std::allocator | |
1038 | ||
1039 | ||
1040 | bimap< L, R , with_info<Info>, Allocator> | |
1041 | ||
1042 | * set_of_relation_type: based on the left key type | |
1043 | * allocator: Allocator | |
1044 | ||
1045 | ||
1046 | bimap< L, R , Allocator> | |
1047 | ||
1048 | * set_of_relation_type: based on the left key type | |
1049 | * info: no info | |
1050 | * allocator: Allocator | |
1051 | ||
1052 | ||
1053 | ||
1054 | ||
1055 | [endsect] | |
1056 | ||
1057 | [endsect] |