1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057 |
- [/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<A>, ``*CollectionType*``_of<B> > 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<A>, ``*CollectionType*``_of<B> > bm_type;
- bm_type bm;
- The following now describes the resulting map views of the bidirectional
- map.
- * `bm.left` is signature-compatible with *LeftMapType*`<A,B>`
- * `bm.right` is signature-compatible with *RightMapType*`<B,A>`
- [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<T,KeyComp>`
- `multiset_of<T,KeyComp>` ]
- [[*KeyComp ] is a Functor that compares two types using a less-than operator.
- By default, this is `std::less<T>`. ]]
- [[`unordered_set_of<T,HashFunctor,EqualKey>`
- `unordered_multiset_of<T,HashFunctor,EqualKey>`]
- [[*HashFunctor ] converts a `T` object into an `std::size_t` value. By default it is `boost::hash<T>`.
- [*EqualKey ] is a Functor that tests two types for equality. By default, the
- equality operator is `std::equal_to<T>`. ]]
- [[`list_of<T>` ][No additional parameters.]]
- [[`vector_of<T>` ][No additional parameters.]]
- [[`unconstrained_set_of<T>` ][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<long> >
- > 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<KeyComp>`
- `multiset_of_relation<KeyComp>` ]
- [[*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<HashFunctor,EqualKey>`
- `unordered_multiset_of_relation<HashFunctor,EqualKey>`]
- [[*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<int,std::string> 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<int, multiset_of<std::string> > 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<A,B>` 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<const int, std::string>`.
- 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<A,B>`][
- `iterator ` *->* `relation<const A,const B>`
- `left_iterator ` *->* `pair<const A,const B>`
- `right_iterator` *->* `pair<const B,const A>`
- ]]
- [[`bimap<multiset_of<A>,unordered_set_of<B> >`][
- `iterator ` *->* `relation<const A,const B>`
- `left_iterator ` *->* `pair<const A,const B>`
- `right_iterator` *->* `pair<const B,const A>`
- ]]
- [[`bimap<set_of<A>,list_of<B> >`][
- `iterator ` *->* `relation<const A,B>`
- `left_iterator ` *->* `pair<const A,B>`
- `right_iterator` *->* `pair<B,const A>`
- ]]
- [[`bimap<vector_of<A>,set_of<B> >`][
- `iterator ` *->* `relation<A,const B>`
- `left_iterator ` *->* `pair<A,const B>`
- `right_iterator` *->* `pair<const B,A>`
- ]]
- [[`bimap<list_of<A>,unconstrained_set_of<B> >`][
- `iterator ` *->* `relation<A,B>`
- `left_iterator ` *->* `pair<A,B>`
- `right_iterator` *->* `pair<B,A>`
- ]]
- ]
- [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<int> > 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<int,std::string> 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 `<boost/bimap/support/lambda.hpp>` 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<int,std::string>`
- 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<Left>()`] ]
- [[`bm.right`] [`bm.by<Right>()`] ]
- [[`bm_type::left_map`] [`bm::map_by<Left>::type`] ]
- [[`bm_type::right_value_type`] [`bm::map_by<Right>::value_type`] ]
- [[`bm_type::left_iterator`] [`bm::map_by<Left>::iterator`] ]
- [[`bm_type::right_const_iterator`][`bm::map_by<Right>::const_iterator`]]
- [[`iter->left`] [`iter->get<Left>()`] ]
- [[`iter->right`] [`iter->get<Right>()`] ]
- [[`left_iter->first`] [`left_iter->get<Left>()`] ]
- [[`left_iter->second`] [`left_iter->get<Right>()`] ]
- [[`right_iter->first`] [`right_iter->get<Right>()`] ]
- [[`right_iter->second`] [`right_iter->get<Left>()`] ]
- [[`bm.project_left(iter)`] [`bm.project<Left>(iter)`] ]
- [[`bm.project_right(iter)`] [`bm.project<Right>(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<Type>`, or can be a `{CollectionType}_of<Type>` 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<LeftKeyType, RightKeyType, Allocator>`. 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<Info> >
- * set_of_relation_type: SetOfRelationType
- * info: Info
- * allocator: std::allocator
- bimap< L, R , SetOfRelationType, with_info<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<Info> >
- * set_of_relation_type: based on the left key type
- * info: Info
- * allocator: std::allocator
- bimap< L, R , with_info<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]
|