5 Copyright (c) 2006-2007 Matias Capeletto
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)
13 [/ QuickBook Document version 1.4 ]
15 [section The tutorial]
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])
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.
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.
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.
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.
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.
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.
53 # The section [link boost_bimap.the_tutorial.additional_information Additional information]
54 explains how to attach information to each relation of a bimap.
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.
62 [section Discovering the bimap framework]
64 [section Interpreting bidirectional maps]
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
78 [section Standard mapping framework]
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
86 __STANDARD_MAPPING_FRAMEWORK__
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.
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 ]]
101 [section Bimap mapping framework]
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.
106 __EXTENDED_MAPPING_FRAMEWORK__
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.
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]
118 __RELATION_AND_PAIR__
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.
129 The following code snippet shows the relation between a bimap and standard
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:
137 // Wrong: we forgot the & after bm_type::left_type
138 bm_type::left_map lm = bm.left;
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.
144 [@../../example/standard_map_comparison.cpp Go to source code]
146 [import ../example/standard_map_comparison.cpp]
148 [code_standard_map_comparison]
154 [section Controlling collection types]
156 [section Freedom of choice]
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.
162 __EXTENDED_MAPPING_FRAMEWORK__
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:
169 typedef bimap< ``*CollectionType*``_of<A>, ``*CollectionType*``_of<B> > bm_type;
171 The following is the list of all supported collection types.
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] ]]
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.
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
197 typedef bimap< ``*CollectionType*``_of<A>, ``*CollectionType*``_of<B> > bm_type;
200 The following now describes the resulting map views of the bidirectional
203 * `bm.left` is signature-compatible with *LeftMapType*`<A,B>`
204 * `bm.right` is signature-compatible with *RightMapType*`<B,A>`
208 [section Configuration parameters]
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
217 The following table lists the meanings of each collection type's parameters.
220 [[name ][Additional Parameters]]
222 [[`set_of<T,KeyComp>`
224 `multiset_of<T,KeyComp>` ]
226 [[*KeyComp ] is a Functor that compares two types using a less-than operator.
227 By default, this is `std::less<T>`. ]]
229 [[`unordered_set_of<T,HashFunctor,EqualKey>`
231 `unordered_multiset_of<T,HashFunctor,EqualKey>`]
233 [[*HashFunctor ] converts a `T` object into an `std::size_t` value. By default it is `boost::hash<T>`.
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.]]
246 [heading Countries Populations]
248 We want to store countries populations.
249 The requirements are:
251 # Get a list of countries in decreasing order of their populations.
252 # Given a country, get their population.
254 Lets create the appropriate bimap.
258 unordered_set_of< std::string >,
259 multiset_of< long, std::greater<long> >
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
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.
271 And now lets use it in a complete example
273 [@../../example/population_bimap.cpp Go to source code]
275 [import ../example/population_bimap.cpp]
277 [code_population_bimap]
280 [heading Repetitions counter]
282 We want to count the repetitions for each word in a text and print them
283 in order of appearance.
285 [@../../example/repetitions_counter.cpp Go to source code]
287 [import ../example/repetitions_counter.cpp]
289 [code_repetitions_counter]
295 [section The collection of relations type]
297 [section A new point of view]
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.
304 __COLLECTION_TYPE_OF_RELATION__
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.
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:
318 * multiset_of_relation<>
319 * unordered_set_of_relation<>
320 * unordered_multiset_of_relation<>
323 * unconstrained_set_of_relation
326 The first two options and the last produce faster bimaps, so prefer
327 these where possible.
330 __MORE_BIMAP_STRUCTURES__
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.
342 [@../../example/mighty_bimap.cpp Go to source code]
348 [section Configuration parameters]
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.
359 The following table lists the meaning of the parameters for each collection type of
363 [[name ][Additional Parameters]]
365 [[`left_based` ][Not a template.]]
366 [[`right_based` ][Not a template.]]
367 [[`set_of_relation<KeyComp>`
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>`. ]]
373 [[`unordered_set_of_relation<HashFunctor,EqualKey>`
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>`.
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.]]
389 Consider this example:
391 template< class Rel >
394 bool operator()(Rel ra, Rel rb) const
396 return (ra.left+ra.right) < (rb.left+rb.right);
404 set_of_relation< RelOrder<_relation> >
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.
414 struct phone_number {};
418 tagged< unordered_multiset_of< string >, name >,
419 tagged< unordered_set_of < int >, phone_number >,
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.
433 [section Differences with standard maps]
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.
443 bimap<int,std::string> bm;
445 bm.left.insert(1,"orange");
446 bm.left.insert(2,"orange"); // No effect! returns make_pair(iter,false)
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.
454 bimap<int, multiset_of<std::string> > bm;
456 bm.left.insert(1,"orange");
457 bm.left.insert(2,"orange"); // Insertion succeed!
459 If we use a custom collection of relation type, the insertion has to be
464 [section iterator::value_type]
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:
475 typedef bimap< int, list_of< std::string > > bm_type;
477 bm.insert( bm_type::relation( 1, "one" ) );
479 bm.left.find(1)->second = "1"; // Valid
481 In this case, when the iterator is dereferenced the return type is
482 ['signature-compatible] with a `std::pair<const int, std::string>`.
484 The following table shows the constness of the dereferenced data of each
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] ]]
498 Here are some examples. When dereferenced the iterators returns a type that
499 is ['signature-compatible] with these types.
502 [[Bimap type ][Signature-compatible types]]
504 `iterator ` *->* `relation<const A,const B>`
506 `left_iterator ` *->* `pair<const A,const B>`
508 `right_iterator` *->* `pair<const B,const A>`
510 [[`bimap<multiset_of<A>,unordered_set_of<B> >`][
511 `iterator ` *->* `relation<const A,const B>`
513 `left_iterator ` *->* `pair<const A,const B>`
515 `right_iterator` *->* `pair<const B,const A>`
517 [[`bimap<set_of<A>,list_of<B> >`][
518 `iterator ` *->* `relation<const A,B>`
520 `left_iterator ` *->* `pair<const A,B>`
522 `right_iterator` *->* `pair<B,const A>`
524 [[`bimap<vector_of<A>,set_of<B> >`][
525 `iterator ` *->* `relation<A,const B>`
527 `left_iterator ` *->* `pair<A,const B>`
529 `right_iterator` *->* `pair<const B,A>`
531 [[`bimap<list_of<A>,unconstrained_set_of<B> >`][
532 `iterator ` *->* `relation<A,B>`
534 `left_iterator ` *->* `pair<A,B>`
536 `right_iterator` *->* `pair<B,A>`
542 [section operator\[\] and at()]
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.
548 bimap< unorderd_set_of< std::string>, list_of<int> > bm;
550 bm.left["one"] = 1; // Ok
552 The standard defines an access function for `map` and `unordered_map`:
554 const data_type & at(const key_type & k) const;
555 data_type & at(const key_type & k);
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.
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
565 The following examples shows the behaviour of `at(key)`
567 [@../../example/at_function_examples.cpp Go to source code]
569 [import ../example/at_function_examples.cpp]
571 [code_at_function_first]
573 [code_at_function_second]
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
588 const data_type & operator[](const typename key_type & k) const;
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.
594 ``['-unspecified data_type proxy-]`` operator[](const typename key_type & k);
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`.
604 The following example shows the behaviour of `operator[]`
606 bimap<int,std::string> bm;
608 bm.left[1] = "one"; // Ok
610 bm.right["two"] = 2; // Ok
612 if( bm.left[3] == "three" ) // throws bimap::value_not_found
617 bm.left[3] = "one"; // throws bimap::duplicate_value
622 [section Complexity of operations]
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.
632 [section Useful functions]
634 [section Projection of iterators]
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.
643 [import ../example/projection.cpp]
645 Here is an example that uses projection:
647 [@../../example/projection.cpp Go to source code]
649 [code_projection_years]
653 [section replace and modify]
655 [import ../example/tutorial_modify_and_replace.cpp]
657 These functions are members of the views of a bimap that are not founded in
658 their standard counterparts.
660 The `replace` family member functions performs in-place replacement of a given
661 element as the following example shows:
663 [@../../example/tutorial_modify_and_replace.cpp Go to source code]
665 [code_tutorial_replace]
667 `replace` functions performs this substitution in such a manner that:
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.
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.
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.
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.
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.
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`.
709 [@../../example/tutorial_modify_and_replace.cpp Go to source code]
711 [code_tutorial_modify]
715 [section Retrieval of ranges]
717 [import ../example/tutorial_range.cpp]
719 Standard `lower_bound` and `upper_bound` functions can be used to lookup for
720 all the elements in a given range.
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]`
725 [code_tutorial_range_standard_way]
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
731 [code_tutorial_range_standard_way_subtle_changes]
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.
740 The range member function, often in combination with lambda expressions,
741 can greatly help alleviate this situation:
743 [code_tutorial_range]
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.
749 One or both bounds can be omitted with the special unbounded marker:
751 [code_tutorial_range_unbounded]
753 [@../../example/tutorial_range.cpp Go to source code]
759 [section Bimaps with user defined names]
761 [import ../example/user_defined_names.cpp]
763 In the following example, the library user inserted comments to guide
766 [@../../example/user_defined_names.cpp Go to source code]
768 [code_user_defined_names_untagged_version]
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.
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:
784 typedef tagged< int, a_tag > tagged_int;
786 Now we can rewrite the example:
788 [@../../example/user_defined_names.cpp Go to source code]
790 [code_user_defined_names_tagged_version]
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.
800 multiset_of< tagged< int, Left > >,
801 unordered_set_of< tagged< int, Right > >
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();
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)`] ]
834 [section Unconstrained Sets]
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.
841 Unconstrained sets are useful for the following reasons:
843 * A bimap type has stronger guarantees than its standard equivalent,
844 and includes some useful functions (replace, modify) that the standard
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`.
851 [import ../example/unconstrained_collection.cpp]
853 Given this bimap instance,
855 [code_unconstrained_collection_bimap]
857 or this standard map one
859 [code_unconstrained_collection_map]
861 The following code snippet is valid
863 [code_unconstrained_collection_common]
865 But using a bimap has some benefits
867 [code_unconstrained_collection_only_for_bimap]
869 [@../../example/unconstrained_collection.cpp Go to source code]
873 [section Additional information]
875 [import ../example/tutorial_info_hook.cpp]
877 Bidirectional maps may have associated information about each relation.
878 Suppose we want to represent a books and author bidirectional map.
880 [code_tutorial_info_hook_nothing]
882 Suppose now that we want to store abstract of each book.
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.
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.
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.
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
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
911 __RELATION_AND_PAIR_WITH_INFO__
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.
917 [code_tutorial_info_hook_first]
919 Contrary to the two key types, the information will be mutable using iterators.
921 [code_tutorial_info_hook_mutable]
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
927 [code_tutorial_info_hook_info_at]
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:
932 [code_tutorial_info_hook_tagged_info]
934 [@../../example/tutorial_info_hook.cpp Go to source code]
938 [section Complete instantiation scheme]
940 To summarize, this is the complete instantiation scheme.
944 LeftCollectionType, RightCollectionType
946 [ , SetTypeOfRelation ] // Default to left_based
947 [ , with_info< Info > ] // Default to no info
948 [ , Allocator ] // Default to std::allocator<>
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.
957 The possible way to use the first parameter are:
962 * Left collection type: `set_of< Type >`
963 * Left tag: `member_at::left`
965 bimap< {CollectionType}_of< Type >, R >
968 * Left collection type: `{CollectionType}_of< LeftType >`
969 * Left tag: `member_at::left`
971 bimap< tagged< Type, Tag >, R >
974 * Left collection type: `set_of< LeftType >`
977 bimap< {CollectionType}_of< tagged< Type, Tag > >, R >
980 * Left collection type: `{CollectionType}_of< LeftType >`
983 The same options are available for the second parameter.
985 The last three parameters are used to specify the collection type of the relation,
986 the information member and the allocator type.
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.
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.
1000 * set_of_relation_type: based on the left key type
1002 * allocator: std::allocator
1005 bimap< L, R ,SetOfRelationType>
1007 * set_of_relation_type: SetOfRelationType
1009 * allocator: std::allocator
1012 bimap< L, R , SetOfRelationType, with_info<Info> >
1014 * set_of_relation_type: SetOfRelationType
1016 * allocator: std::allocator
1019 bimap< L, R , SetOfRelationType, with_info<Info>, Allocator>
1021 * set_of_relation_type: SetOfRelationType
1023 * allocator: Allocator
1026 bimap< L, R , SetOfRelationType, Allocator>
1028 * set_of_relation_type: SetOfRelationType
1030 * allocator: Allocator
1033 bimap< L, R , with_info<Info> >
1035 * set_of_relation_type: based on the left key type
1037 * allocator: std::allocator
1040 bimap< L, R , with_info<Info>, Allocator>
1042 * set_of_relation_type: based on the left key type
1043 * allocator: Allocator
1046 bimap< L, R , Allocator>
1048 * set_of_relation_type: based on the left key type
1050 * allocator: Allocator