[/license Boost.Bimap Copyright (c) 2006-2007 Matias Capeletto Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) ] [/ QuickBook Document version 1.4 ] [section The tutorial] [section Roadmap] # Boost.Bimap is intuitive because it is based on the standard template library. New concepts are however presented to extend the standard maps to bidirectional maps. The first step is to gain a firm grasp of the bimap framework. The first section ([link boost_bimap.the_tutorial.discovering_the_bimap_framework Discovering the bimap framework]) aims to explain this. # Boost.Bimap offers much more than just a one-to-one ordered unique bidirectional map. It is possible to control the collection type of each side of the relationship that the bimap represents, giving one-to-many containers, hashed bidirectional containers and others that may be more suitable to the the task at hand. The second section ([link boost_bimap.the_tutorial.controlling_collection_types Controlling collection types]) explains how to instantiate a bimap with different collection constraints. # The section ([link boost_bimap.the_tutorial.the_collection_of_relations_type The "collection of relations" type]) explains how to create new types of bidirectional maps using custom collection types. # 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. # The section [link boost_bimap.the_tutorial.useful_functions Useful functions] provides information about functions of a bimap that are not found in the STL. # The types of a bimap can be tagged so that each side is accessible by something closer to the problem than left and right. This leads to more readable, self-documenting code. The fourth section ([link boost_bimap.the_tutorial.bimaps_with_user_defined_names Bimaps with user defined names]) shows how to use this feature. # The bimap mapping framework allows to disable a view of a bimap, including the standard mapping containers as a particular case. The section [link boost_bimap.the_tutorial.unconstrained_sets Unconstrained Sets] explains how they work. # The section [link boost_bimap.the_tutorial.additional_information Additional information] explains how to attach information to each relation of a bimap. # The final section ([link boost_bimap.the_tutorial.complete_instantiation_scheme Complete Instantiation Scheme]) summarizes bimap instantiation and explains how change the allocator type to be used. [endsect] [section Discovering the bimap framework] [section Interpreting bidirectional maps] One way to interpret bidirectional maps is as a function between two collections of data, lets call them the left and the right collection. An element in this bimap is a relation between an element from the left collection and an element from the right collection. The types of both collections defines the bimap behaviour. We can view the stored data from the left side, as a mapping between keys from the left collection and data from the right one, or from the right side, as a mapping between keys from the right collection and data from the left collection. [endsect] [section Standard mapping framework] Relationships between data in the STL are represented by maps. A standard map is a directed relation of keys from a left collection and data from a right unconstrained collection. The following diagram shows the relationship represented and the user's viewpoint. __STANDARD_MAPPING_FRAMEWORK__ 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`. The following table shows the equivalent types for the std associative containers. [table std associative containers [[container ][left collection type ][right collection type]] [[`map` ][`set_of` ][no constraints ]] [[`multimap` ][`multiset_of` ][no constraints ]] [[`unordered_map` ][`unordered_set_of` ][no constraints ]] [[`unordered_multimap`][`unordered_multiset_of` ][no constraints ]] ] [endsect] [section Bimap mapping framework] Boost.Bimap design is based on the STL, and extends the framework in a natural way. The following diagram represents the new situation. __EXTENDED_MAPPING_FRAMEWORK__ Notice that now the `std::maps` are a particular case of a Boost.Bimap container, where you can view only one side of the relationship and can control the constraints of only one of the collections. Boost.Bimap allows the user to view the relationship from three viewpoints. You can view it from one side, obtaining a `std::map` compatible container, or you can work directly with the whole relation. The next diagram shows the layout of the relation and pairs of a bimap. It is the one from the ['one minute tutorial] __RELATION_AND_PAIR__ Bimap pairs are signature-compatible with standard pairs but are different from them. As you will see in other sections they can be tagged with user defined names and additional information can be attached to them. You can convert from `std::pairs` to bimap pairs directly but the reverse conversion is not provided. This mean that you can insert elements in a bimap using algorithms like `std::copy` from containers `like std::map`, or use `std::make_pair` 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 copy constructor of each type. The following code snippet shows the relation between a bimap and standard maps. [note You have to used references to views, and not directly views object. Views cannot be constructed as separate objects from the container they belong to, so the following: `` // Wrong: we forgot the & after bm_type::left_type bm_type::left_map lm = bm.left; `` does not compile, since it is trying to construct the view object `lm`. This is a common source of errors in user code. ] [@../../example/standard_map_comparison.cpp Go to source code] [import ../example/standard_map_comparison.cpp] [code_standard_map_comparison] [endsect] [endsect] [section Controlling collection types] [section Freedom of choice] As has already been said, in STL maps, you can only control the constraints from one of the collections, namely the one that you are viewing. In Boost.Bimap, you can control both and it is as easy as using the STL. __EXTENDED_MAPPING_FRAMEWORK__ The idea is to use the same constraint names that are used in the standard. If you don't specify the collection type, Boost.Bimap assumes that the collection is a set. The instantiation of a bimap with custom collection types looks like this: typedef bimap< ``*CollectionType*``_of, ``*CollectionType*``_of > bm_type; The following is the list of all supported collection types. [table Collection of Key Types [[name ][Features ][map view type ]] [[`set_of` ][['ordered, unique]][`map` ]] [[`multiset_of` ][['ordered ]][`multimap` ]] [[`unordered_set_of` ][['hashed, unique ]][`unordered_map` ]] [[`unordered_multiset_of`][['hashed ]][`unordered_multimap` ]] [[`list_of` ][['sequenced ]][`list_map` ]] [[`vector_of` ][['random access ]][`vector_map` ]] [[`unconstrained_set_of` ][['unconstrained ]][['can not be viewed] ]] ] `list_of` and `vector_of` map views are not associated with any existing STL associative containers. They are two examples of unsorted associative containers. `unconstrained_set_of` allow the user to ignore a view. This will be explained later. __BIMAP_STRUCTURES__ The selection of the collection type affects the possible operations that you can perform with each side of the bimap and the time it takes to do each. If we have: typedef bimap< ``*CollectionType*``_of, ``*CollectionType*``_of > bm_type; bm_type bm; The following now describes the resulting map views of the bidirectional map. * `bm.left` is signature-compatible with *LeftMapType*`` * `bm.right` is signature-compatible with *RightMapType*`` [endsect] [section Configuration parameters] Each collection type template has different parameters to control its behaviour. For example, in `set_of` specification, you can pass a Functor type that compares two types. All of these parameters are exactly the same as those of the standard library container, except for the allocator type. You will learn later how to change the allocator for a bimap. The following table lists the meanings of each collection type's parameters. [table [[name ][Additional Parameters]] [[`set_of` `multiset_of` ] [[*KeyComp ] is a Functor that compares two types using a less-than operator. By default, this is `std::less`. ]] [[`unordered_set_of` `unordered_multiset_of`] [[*HashFunctor ] converts a `T` object into an `std::size_t` value. By default it is `boost::hash`. [*EqualKey ] is a Functor that tests two types for equality. By default, the equality operator is `std::equal_to`. ]] [[`list_of` ][No additional parameters.]] [[`vector_of` ][No additional parameters.]] [[`unconstrained_set_of` ][No additional parameters.]] ] [endsect] [section Examples] [heading Countries Populations] We want to store countries populations. The requirements are: # Get a list of countries in decreasing order of their populations. # Given a country, get their population. Lets create the appropriate bimap. typedef bimap< unordered_set_of< std::string >, multiset_of< long, std::greater > > populations_bimap; First of all countries names are unique identifiers, while two countries may have the same population. This is why we choose *multi*`set_of` for populations. Using a `multiset_of` for population allow us to iterate over the data. Since listing countries ordered by their names is not a requisite, we can use an `unordered_set_of` that allows constant order look up. And now lets use it in a complete example [@../../example/population_bimap.cpp Go to source code] [import ../example/population_bimap.cpp] [code_population_bimap] [heading Repetitions counter] We want to count the repetitions for each word in a text and print them in order of appearance. [@../../example/repetitions_counter.cpp Go to source code] [import ../example/repetitions_counter.cpp] [code_repetitions_counter] [endsect] [endsect] [section The collection of relations type] [section A new point of view] Being able to change the collection type of the bimap relation view is another very important feature. Remember that this view allows the user to see the container as a group of the stored relations. This view has set semantics instead of map semantics. __COLLECTION_TYPE_OF_RELATION__ By default, Boost.Bimap will base the collection type of the relation on the type of the left collection. If the left collection type is a set, then the collection type of the relation will be a set with the same order as the left view. In general, Boost.Bimap users will base the collection type of a relation on the type of the collection on one of the two sides. However there are times where it is useful to give this collection other constraints or simply to order it differently. The user is allowed to choose between: * left_based * right_based * set_of_relation<> * multiset_of_relation<> * unordered_set_of_relation<> * unordered_multiset_of_relation<> * list_of_relation * vector_of_relation * unconstrained_set_of_relation [tip The first two options and the last produce faster bimaps, so prefer these where possible. ] __MORE_BIMAP_STRUCTURES__ The collection type of relation can be used to create powerful containers. For example, if you need to maximize search speed, then the best bidirectional map possible is one that relates elements from an `unordered_set` to another `unordered_set`. The problem is that this container cannot be iterated. If you need to know the list of relations inside the container, you need another collection type of relation. In this case, a `list_of_relation` is a good choice. The resulting container trades insertion and deletion time against fast search capabilities and the possibility of bidirectional iteration. [@../../example/mighty_bimap.cpp Go to source code] [code_mighty_bimap] [endsect] [section Configuration parameters] Each collection type of relation has different parameters to control its behaviour. For example, in the `set_of_relation` specification, you can pass a Functor type that compares two types. All of the parameters are exactly as in the standard library containers, except for the type, which is set to the bimap relation and the allocator type. To help users in the creation of each functor, the collection type of relation templates takes an mpl lambda expression where the relation type will be evaluated later. A placeholder named `_relation` is available to bimap users. The following table lists the meaning of the parameters for each collection type of relations. [table [[name ][Additional Parameters]] [[`left_based` ][Not a template.]] [[`right_based` ][Not a template.]] [[`set_of_relation` `multiset_of_relation` ] [[*KeyComp ] is a Functor that compares two types using less than. By default, the less-than operator is `std::less<_relation>`. ]] [[`unordered_set_of_relation` `unordered_multiset_of_relation`] [[*HashFunctor ] converts the `relation` into an `std::size_t` value. By default it is `boost::hash<_relation>`. [*EqualKey ] is a Functor that tests two relations for equality. By default, the equality operator is `std::equal_to<_relation>`. ]] [[`list_of_relation` ][Not a template.]] [[`vector_of_relation` ][Not a template.]] [[`unconstrained_set_of_relation` ][Not a template.]] ] [endsect] [section Examples] Consider this example: template< class Rel > struct RelOrder { bool operator()(Rel ra, Rel rb) const { return (ra.left+ra.right) < (rb.left+rb.right); } }; typedef bimap < multiset_of< int >, multiset_of< int >, set_of_relation< RelOrder<_relation> > > bimap_type; Here the bimap relation view is ordered using the information of both sides. This container will only allow unique relations because `set_of_relation` has been used but the elements in each side of the bimap can be repeated. struct name {}; struct phone_number {}; typedef bimap < tagged< unordered_multiset_of< string >, name >, tagged< unordered_set_of < int >, phone_number >, set_of_relation<> > bimap_type; In this other case the bimap will relate names to phone numbers. Names can be repeated and phone numbers are unique. You can perform quick searches by name or phone number and the container can be viewed ordered using the relation view. [endsect] [endsect] [section Differences with standard maps] [section Insertion] Remember that a map can be interpreted as a relation between two collections. In bimaps we have the freedom to change both collection types, imposing constrains in each of them. Some insertions that we give for granted to success in standard maps fails with bimaps. For example: bimap bm; bm.left.insert(1,"orange"); bm.left.insert(2,"orange"); // No effect! returns make_pair(iter,false) The insertion will only succeed if it is allowed by all views of the `bimap`. In the next snippet we define the right collection as a multiset, when we try to insert the same two elements the second insertion is allowed by the left map view because both values are different and it is allowed by the right map view because it is a non-unique collection type. bimap > bm; bm.left.insert(1,"orange"); bm.left.insert(2,"orange"); // Insertion succeed! If we use a custom collection of relation type, the insertion has to be allowed by it too. [endsect] [section iterator::value_type] The relations stored in the Bimap will not be in most cases modifiable directly by iterators because both sides are used as keys of ['key-based] sets. When a `bimap` left view iterator is dereferenced the return type is ['signature-compatible] with a `std::pair< const A, const B >`. However there are some collection types that are not ['key_based], for example list_of. If a Bimap uses one of these collection types there is no problem with modifying the data of that side. The following code is valid: typedef bimap< int, list_of< std::string > > bm_type; bm_type bm; bm.insert( bm_type::relation( 1, "one" ) ); ... bm.left.find(1)->second = "1"; // Valid In this case, when the iterator is dereferenced the return type is ['signature-compatible] with a `std::pair`. The following table shows the constness of the dereferenced data of each collection type of: [table [[Side collection type ][Dereferenced data]] [[`set_of` ][['constant]]] [[`multiset_of` ][['constant]]] [[`unordered_set_of` ][['constant]]] [[`unordered_multiset_of`][['constant]]] [[`list_of` ][['mutable] ]] [[`vector_of` ][['mutable] ]] [[`unconstrained_set_of` ][['mutable] ]] ] Here are some examples. When dereferenced the iterators returns a type that is ['signature-compatible] with these types. [table [[Bimap type ][Signature-compatible types]] [[`bimap`][ `iterator ` *->* `relation` `left_iterator ` *->* `pair` `right_iterator` *->* `pair` ]] [[`bimap,unordered_set_of >`][ `iterator ` *->* `relation` `left_iterator ` *->* `pair` `right_iterator` *->* `pair` ]] [[`bimap,list_of >`][ `iterator ` *->* `relation` `left_iterator ` *->* `pair` `right_iterator` *->* `pair` ]] [[`bimap,set_of >`][ `iterator ` *->* `relation` `left_iterator ` *->* `pair` `right_iterator` *->* `pair` ]] [[`bimap,unconstrained_set_of >`][ `iterator ` *->* `relation` `left_iterator ` *->* `pair` `right_iterator` *->* `pair` ]] ] [endsect] [section operator\[\] and at()] `set_of` and `unordered_set_of` map views overload `operator[]` to retrieve the associated data of a given key only when the other collection type is a mutable one. In these cases it works in the same way as the standard. bimap< unorderd_set_of< std::string>, list_of > bm; bm.left["one"] = 1; // Ok The standard defines an access function for `map` and `unordered_map`: const data_type & at(const key_type & k) const; data_type & at(const key_type & k); These functions look for a key and returns the associated data value, but throws a `std::out_of_range` exception if the key is not found. In bimaps the constant version of these functions is given for `set_of` and `unorderd_set_of` map views independently of the other collection type. The mutable version is only provided when the other collection type is mutable. The following examples shows the behaviour of `at(key)` [@../../example/at_function_examples.cpp Go to source code] [import ../example/at_function_examples.cpp] [code_at_function_first] [code_at_function_second] [/ `set_of` and `unordered_set_of` views overload `operator[]` to retrieve the associated data of a given key. The symmetry of bimap imposes some constraints on `operator[]` that are not found in `std::map` or `std::unordered_map`. If other views are unique, `bimap::duplicate_value` is thrown whenever an assignment is attempted to a value that is already a key in these views. As for `bimap::value_not_found`, this exception is thrown while trying to access a non-existent key: this behaviour differs from the standard containers, which automatically assigns a default value to non-existent keys referred to by `operator[]`. const data_type & operator[](const typename key_type & k) const; [: Returns the `data_type` reference that is associated with `k`, or throws `bimap::value_not_found` if such an element does not exist. ] ``['-unspecified data_type proxy-]`` operator[](const typename key_type & k); [: Returns a proxy to a `data_type` associated with `k` and the bimap. The proxy behaves as a reference to the `data_type` object. If this proxy is read and `k` was not in the bimap, the bimap::value_not_found is thrown. If it is written then `bimap::duplicate_value` is thrown if the assignment is not allowed by one of the other views of the `bimap`. ] The following example shows the behaviour of `operator[]` bimap bm; bm.left[1] = "one"; // Ok bm.right["two"] = 2; // Ok if( bm.left[3] == "three" ) // throws bimap::value_not_found { ... } bm.left[3] = "one"; // throws bimap::duplicate_value ] [endsect] [section Complexity of operations] The complexity of some operations is different in bimaps. Read [link complexity_signature_explanation the reference] to find the complexity of each function. [endsect] [endsect] [section Useful functions] [section Projection of iterators] Iterators can be projected to any of the three views of the bimap. A bimap provides three member functions to cope with projection: `project_left`, `project_right` and `project_up`, with projects iterators to the ['left map view], the ['right map view] and the ['collection of relations view]. These functions take any iterator from the bimap and retrieve an iterator over the projected view pointing to the same element. [import ../example/projection.cpp] Here is an example that uses projection: [@../../example/projection.cpp Go to source code] [code_projection_years] [endsect] [section replace and modify] [import ../example/tutorial_modify_and_replace.cpp] These functions are members of the views of a bimap that are not founded in their standard counterparts. The `replace` family member functions performs in-place replacement of a given element as the following example shows: [@../../example/tutorial_modify_and_replace.cpp Go to source code] [code_tutorial_replace] `replace` functions performs this substitution in such a manner that: * The complexity is constant time if the changed element retains its original order with respect to all views; it is logarithmic otherwise. * Iterator and reference validity are preserved. * The operation is strongly exception-safe, i.e. the `bimap` remains unchanged if some exception (originated by the system or the user's data types) is thrown. `replace` functions are powerful operations not provided by standard STL containers, and one that is specially handy when strong exception-safety is required. The observant reader might have noticed that the convenience of replace comes at a cost: namely the whole element has to be copied ['twice] to do the updating (when retrieving it and inside `replace`). If elements are expensive to copy, this may be quite a computational cost for the modification of just a tiny part of the object. To cope with this situation, Boost.Bimap provides an alternative updating mechanism: `modify` functions. `modify` functions accepts a functor (or pointer to function) taking a reference to the data to be changed, thus eliminating the need for spurious copies. Like `replace` functions, `modify` functions does preserve the internal orderings of all the indices of the `bimap`. However, the semantics of modify functions are not entirely equivalent to replace functions. Consider what happens if a collision occurs as a result of modifying the element, i.e. the modified element clashes with another with respect to some unique view. In the case of `replace` functions, the original value is kept and the method returns without altering the container, but `modify` functions cannot afford such an approach, since the modifying functor leaves no trace of the previous value of the element. Integrity constraints thus lead to the following policy: when a collision happens in the process of calling a modify functions, the element is erased and the method returns false. This difference in behavior between `replace` and `modify` functions has to be considered by the programmer on a case-by-case basis. Boost.Bimap defines new placeholders named `_key` and `_data` to allow a sounder solution. You have to include `` to use them. [/ Boost.Bimap defines new placeholders to allow a sounder solution. For pairs, two new placeholders are instantiated: `_first` and `_second`, and for a relation, two more complete the set: `_left` and `_right`. ] [@../../example/tutorial_modify_and_replace.cpp Go to source code] [code_tutorial_modify] [endsect] [section Retrieval of ranges] [import ../example/tutorial_range.cpp] Standard `lower_bound` and `upper_bound` functions can be used to lookup for all the elements in a given range. Suppose we want to retrieve the elements from a `bimap` where the left value is in the range `[20,50]` [code_tutorial_range_standard_way] Subtle changes to the code are required when strict inequalities are considered. To retrieve the elements greater than 20 and less than 50, the code has to be rewritten as [code_tutorial_range_standard_way_subtle_changes] To add to this complexity, the careful programmer has to take into account that the lower and upper bounds of the interval searched be compatible: for instance, if the lower bound is 50 and the upper bound is 20, the iterators `iter_first` and `iter_second` produced by the code above will be in reverse order, with possibly catastrophic results if a traversal from `iter_first` to `iter_second` is tried. All these details make range searching a tedious and error prone task. The range member function, often in combination with lambda expressions, can greatly help alleviate this situation: [code_tutorial_range] `range` simply accepts predicates specifying the lower and upper bounds of the interval searched. Please consult the reference for a detailed explanation of the permissible predicates passed to range. One or both bounds can be omitted with the special unbounded marker: [code_tutorial_range_unbounded] [@../../example/tutorial_range.cpp Go to source code] [endsect] [endsect] [section Bimaps with user defined names] [import ../example/user_defined_names.cpp] In the following example, the library user inserted comments to guide future programmers: [@../../example/user_defined_names.cpp Go to source code] [code_user_defined_names_untagged_version] In Boost.Bimap there is a better way to document the code and in the meantime helping you to write more maintainable and readable code. You can tag the two collections of the bimap so they can be accessed by more descriptive names. __TAGGED__ A tagged type is a type that has been labelled using a tag. A tag is any valid C++ type. In a bimap, the types are always tagged. If you do not specify your own tag, the container uses `member_at::left` and `member_at::right` to tag the left and right sides respectively. In order to specify a custom tag, the type of each side has to be tagged. Tagging a type is very simple: typedef tagged< int, a_tag > tagged_int; Now we can rewrite the example: [@../../example/user_defined_names.cpp Go to source code] [code_user_defined_names_tagged_version] Here is a list of common structures in both tagged and untagged versions. Remember that when the bimap has user defined tags you can still use the untagged version structures. struct Left {}; struct Right {}; typedef bimap< multiset_of< tagged< int, Left > >, unordered_set_of< tagged< int, Right > > > bm_type; bm_type bm; //... bm_type::iterator iter = bm.begin(); bm_type::left_iterator left_iter = bm.left.begin(); bm_type::right_iterator right_iter = bm.right.begin(); [table Equivalence of expresions using user defined names [[Untagged version] [Tagged version] ] [[`bm.left`] [`bm.by()`] ] [[`bm.right`] [`bm.by()`] ] [[`bm_type::left_map`] [`bm::map_by::type`] ] [[`bm_type::right_value_type`] [`bm::map_by::value_type`] ] [[`bm_type::left_iterator`] [`bm::map_by::iterator`] ] [[`bm_type::right_const_iterator`][`bm::map_by::const_iterator`]] [[`iter->left`] [`iter->get()`] ] [[`iter->right`] [`iter->get()`] ] [[`left_iter->first`] [`left_iter->get()`] ] [[`left_iter->second`] [`left_iter->get()`] ] [[`right_iter->first`] [`right_iter->get()`] ] [[`right_iter->second`] [`right_iter->get()`] ] [[`bm.project_left(iter)`] [`bm.project(iter)`] ] [[`bm.project_right(iter)`] [`bm.project(iter)`] ] ] [endsect] [section Unconstrained Sets] Unconstrained sets allow the user to disable one of the views of a bimap. Doing so makes the bimap operations execute faster and reduces memory consumption. This completes the bidirectional mapping framework by including unidirectional mappings as a particular case. Unconstrained sets are useful for the following reasons: * A bimap type has stronger guarantees than its standard equivalent, and includes some useful functions (replace, modify) that the standard does not have. * You can view the mapping as a collection of relations. * Using this kind of map makes the code very extensible. If, at any moment of the development, the need to perform searches from the right side of the mapping arises, the only necessary change is to the `typedef`. [import ../example/unconstrained_collection.cpp] Given this bimap instance, [code_unconstrained_collection_bimap] or this standard map one [code_unconstrained_collection_map] The following code snippet is valid [code_unconstrained_collection_common] But using a bimap has some benefits [code_unconstrained_collection_only_for_bimap] [@../../example/unconstrained_collection.cpp Go to source code] [endsect] [section Additional information] [import ../example/tutorial_info_hook.cpp] Bidirectional maps may have associated information about each relation. Suppose we want to represent a books and author bidirectional map. [code_tutorial_info_hook_nothing] Suppose now that we want to store abstract of each book. We have two options: # Books name are unique identifiers, so we can create a separate `std::map< string, string >` that relates books names with abstracts. # We can use __BOOST_MULTI_INDEX__ for the new beast. Option 1 is the wrong approach, if we go this path we lost what bimap has won us. We now have to maintain the logic of two interdependent containers, there is an extra string stored for each book name, and the performance will be worse. This is far away from being a good solution. Option 2 is correct. We start thinking books as entries in a table. So it makes sense to start using Boost.MultiIndex. We can then add the year of publication, the price, etc... and we can index this new items too. So Boost.MultiIndex is a sound solution for our problem. The thing is that there are cases where we want to maintain bimap semantics (use `at()` to find an author given a book name and the other way around) and add information about the relations that we are sure we will not want to index later (like the abstracts). Option 1 is not possible, option 2 neither. Boost.Bimap provides support for this kind of situations by means of an embedded information member. You can pass an extra parameter to a bimap: `with_info< InfoType >` and an `info` member of type `InfoType` will appear in the relation and bimap pairs. __RELATION_AND_PAIR_WITH_INFO__ Relations and bimap pairs constructors will take an extra argument. If only two arguments are used, the information will be initialized with their default constructor. [code_tutorial_info_hook_first] Contrary to the two key types, the information will be mutable using iterators. [code_tutorial_info_hook_mutable] A new function is included in ['unique] map views: `info_at(key)`, that mimics the standard `at(key)` function but returned the associated information instead of the data. [code_tutorial_info_hook_info_at] The info member can be tagged just as the left or the right member. The following is a rewrite of the above example using user defined names: [code_tutorial_info_hook_tagged_info] [@../../example/tutorial_info_hook.cpp Go to source code] [endsect] [section Complete instantiation scheme] To summarize, this is the complete instantiation scheme. typedef bimap < LeftCollectionType, RightCollectionType [ , SetTypeOfRelation ] // Default to left_based [ , with_info< Info > ] // Default to no info [ , Allocator ] // Default to std::allocator<> > bm; `{Side}CollectionType` can directly be a type. This defaults to `set_of`, or can be a `{CollectionType}_of` specification. Additionally, the type of this two parameters can be tagged to specify user defined names instead of the usual `member_at::-Side-` tags. The possible way to use the first parameter are: bimap< Type, R > * Left type: `Type` * Left collection type: `set_of< Type >` * Left tag: `member_at::left` bimap< {CollectionType}_of< Type >, R > * Left type: `Type` * Left collection type: `{CollectionType}_of< LeftType >` * Left tag: `member_at::left` bimap< tagged< Type, Tag >, R > * Left type: `Type` * Left collection type: `set_of< LeftType >` * Left tag: `Tag` bimap< {CollectionType}_of< tagged< Type, Tag > >, R > * Left type: `Type` * Left collection type: `{CollectionType}_of< LeftType >` * Left tag: `Tag` The same options are available for the second parameter. The last three parameters are used to specify the collection type of the relation, the information member and the allocator type. If you want to specify a custom allocator type while relying on the default value of CollectionTypeOfRelation, you can do so by simply writing `bimap`. Boost.Bimap's internal machinery detects that the third parameter in this case does not refer to the relation type but rather to an allocator. The following are the possible ways of instantiating the last three parameters of a bimap. You can ignore some of the parameter but the order must be respected. bimap< L, R > * set_of_relation_type: based on the left key type * info: no info * allocator: std::allocator bimap< L, R ,SetOfRelationType> * set_of_relation_type: SetOfRelationType * info: no info * allocator: std::allocator bimap< L, R , SetOfRelationType, with_info > * set_of_relation_type: SetOfRelationType * info: Info * allocator: std::allocator bimap< L, R , SetOfRelationType, with_info, Allocator> * set_of_relation_type: SetOfRelationType * info: Info * allocator: Allocator bimap< L, R , SetOfRelationType, Allocator> * set_of_relation_type: SetOfRelationType * info: no info * allocator: Allocator bimap< L, R , with_info > * set_of_relation_type: based on the left key type * info: Info * allocator: std::allocator bimap< L, R , with_info, Allocator> * set_of_relation_type: based on the left key type * allocator: Allocator bimap< L, R , Allocator> * set_of_relation_type: based on the left key type * info: no info * allocator: Allocator [endsect] [endsect]