| [/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 Bimap and Boost] |
| |
| [section Bimap and MultiIndex] |
| |
| ['MISC] - [*M]ulti-[*I]ndex [*S]pecialized [*C]ontainers |
| |
| [:[' |
| Let's be generic, construct frameworks, describe the world in an |
| unified way... |
| ]] |
| [:[' |
| No!, it is better to be specialized, design easy-to-use components, |
| offer plug-and-play objects... |
| ]] |
| [:[* |
| Why not take advantage of the best of both worlds? |
| ]] |
| |
| __MI_FRAMEWORK__ |
| |
| With Boost.Bimap, you can build associative containers in which both |
| types can be used as key. There is a library in Boost that already |
| allows the creation of this kind of container: Boost.MultiIndex. It |
| offers great flexibility and lets you construct almost any container |
| that you could dream of. The framework is very clean. You migh want to |
| read this library's tutorial to learn about the power that has been |
| achieved. |
| |
| |
| But generality comes at a price: the interface that results might not be |
| the best for every specialization. People may end up wrapping a B.MI |
| container in its own class every time they want to use it as a |
| bidirectional map. Boost.Bimap takes advantage of the narrower scope to |
| produce a better interface for bidirectional maps |
| [footnote In the same fashion, Boost.MRU will allow the creation of ['most |
| recent updated] aware containers, hiding the complexity of Boost.MultiIndex.]. |
| There is no learning curve if you know how to use standard containers. |
| Great effort was put into mapping the naming scheme of the STL to Boost.Bimap. |
| The library is designed to match the common STL containers. |
| |
| Boost.MultiIndex is, in fact, the core of the bimap container. |
| |
| However, Boost.Bimap do not aim to tackle every problem with two indexed |
| types. There exist some problems that are better modelled with Boost.MultiIndex. |
| |
| |
| [blurb |
| |
| [*Problem I - An employee register] |
| |
| ['Store an ID and a name for an employee, with fast search on each member.] |
| |
| This type of problem is better modelled as a database table, and |
| [*Boost.MultiIndex] is the preferred choice. It is possible that other data |
| will need to be indexed later. |
| |
| ] |
| |
| [blurb |
| |
| [*Problem II - A partners container] |
| |
| ['Store the names of couples and be able to get the name of a person's |
| partner.] |
| |
| This problem is better modelled as a collection of relations, and [*Boost.Bimap] |
| fits nicely here. |
| |
| ] |
| |
| You can also read |
| [link boost_bimap.the_tutorial.additional_information Additional Information] for more |
| information about the relation of this two libraries. |
| |
| [endsect] |
| |
| [section Boost Libraries that work well with Boost.Bimap] |
| |
| [section Introduction] |
| |
| [table |
| [[Name][Description][author][Purpose]] |
| |
| [[ __BOOST_SERIALIZATION__ ][ |
| Serialization for persistence and marshalling] |
| [Robert Ramey] |
| [Serialization support for bimap containers and iterators]] |
| |
| [[ __BOOST_ASSIGN__ ][ |
| Filling containers with constant or generated data has never been easier] |
| [Thorsten Ottosen] |
| [Help to fill a bimap or views of it]] |
| |
| [[ __BOOST_HASH__ ][ |
| A TR1 hash function object that can be extended to hash user defined types] |
| [Daniel James] |
| [Default hashing function]] |
| |
| [[ __BOOST_LAMBDA__ ][ |
| Define small unnamed function objects at the actual call site, and more] |
| [from Jaakko Järvi, Gary Powell] |
| [Functors for modify, range, lower_bound and upper_bound]] |
| |
| [[ __BOOST_RANGE__ ][ |
| A new infrastructure for generic algorithms that builds on top of the new |
| iterator concepts] |
| [Thorsten Ottosen] |
| [Range based algorithms]] |
| |
| [[ __BOOST_FOREACH__ ][ |
| BOOST_FOREACH macro for easily iterating over the elements of a sequence] |
| [Eric Niebler] |
| [Iteration]] |
| |
| [[ __BOOST_TYPEOF__ ][ |
| Typeof operator emulation] |
| [Arkadiy Vertleyb, Peder Holt] |
| [Using BOOST_AUTO while we wait for C++0x]] |
| |
| [[ __BOOST_XPRESSIVE__ ][ |
| Regular expressions that can be written as strings or as expression templates] |
| [Eric Niebler] |
| [Help to fill a bimap from a string]] |
| |
| [[ __BOOST_PROPERTY_MAP__ ][ |
| Concepts defining interfaces which map key objects to value objects] |
| [Jeremy Siek] |
| [Integration with BGL]] |
| ] |
| |
| [endsect] |
| |
| [section Boost.Serialization] |
| |
| A bimap can be archived and retrieved by means of the Boost.Serialization Library. |
| Both regular and XML archives are supported. The usage is straightforward and does |
| not differ from that of any other serializable type. For instance: |
| |
| [import ../example/bimap_and_boost/serialization.cpp] |
| |
| [@../../example/bimap_and_boost/serialization.cpp Go to source code] |
| |
| [code_bimap_and_boost_serialization] |
| |
| Serialization capabilities are automatically provided by just linking with the |
| appropriate Boost.Serialization library module: it is not necessary to explicitly |
| include any header from Boost.Serialization, apart from those declaring the type |
| of archive used in the process. If not used, however, serialization support can |
| be disabled by globally defining the macro BOOST_BIMAP_DISABLE_SERIALIZATION. |
| Disabling serialization for Boost.MultiIndex can yield a small improvement in |
| build times, and may be necessary in those defective compilers that fail to |
| correctly process Boost.Serialization headers. |
| |
| [warning Boost.Bimap and Boost.MultiIndex share a lot of serialization code. |
| The macro `BOOST_BIMAP_DISABLE_SERIALIZATION` disables serialization in *both* |
| libraries. The same happens when `BOOST_MULTI_INDEX_DISABLE_SERIALIZATION` is |
| defined. |
| ] |
| |
| Retrieving an archived bimap restores not only the elements, but also the order |
| they were arranged in the views of the container. There is an exception to this rule, |
| though: for unordered sets, no guarantee is made about the order in which elements |
| will be iterated in the restored container; in general, it is unwise to rely on |
| the ordering of elements of a hashed view, since it can change in arbitrary ways |
| during insertion or rehashing --this is precisely the reason why hashed indices |
| and TR1 unordered associative containers do not define an equality operator. |
| |
| Iterators of a bimap can also be serialized. Serialization of an |
| iterator must be done only after serializing its corresponding container. |
| |
| [endsect] |
| |
| [section Boost.Assign] |
| |
| The purpose of this library is to make it easy to fill containers with data by |
| overloading operator,() and operator()(). These two operators make it possible |
| to construct lists of values that are then copied into a container. |
| |
| These lists are particularly useful in learning, testing, and prototyping |
| situations, but can also be handy otherwise. The library comes with predefined |
| operators for the containers of the standard library, but most functionality will |
| work with any standard compliant container. The library also makes it possible |
| to extend user defined types so for example a member function can be called for |
| a list of values instead of its normal arguments. |
| |
| Boost.Assign can be used with bimap containers. |
| The views of a bimap are signature-compatible with their standard |
| counterparts, so we can use other Boost.Assign utilities with them. |
| |
| [import ../example/bimap_and_boost/assign.cpp] |
| |
| [@../../example/bimap_and_boost/assign.cpp Go to source code] |
| |
| [code_bimap_and_boost_assign] |
| |
| [endsect] |
| |
| [section Boost.Hash] |
| |
| The hash function is the very core of the fast lookup capabilities of the |
| unordered sets: a hasher is just a Unary Function returning an std::size_t value |
| for any given key. In general, it is impossible that every key map to a |
| different hash value, for the space of keys can be greater than the number of permissible hash codes: what makes for a good hasher is that the probability of a collision (two different keys with the same hash value) is as close to zero as possible. |
| |
| This is a statistical property depending on the typical distribution of keys in a given application, so it is not feasible to have a general-purpose hash function with excellent results in every possible scenario; the default value for this parameter uses Boost.Hash, which often provides good enough results. |
| |
| Boost.Hash can be |
| [@http://www.boost.org/doc/html/hash/custom.html |
| extended for custom data types], |
| enabling to use the default parameter of the unordered set types with any user types. |
| |
| [endsect] |
| |
| [section Boost.Lambda] |
| |
| The Boost Lambda Library (BLL in the sequel) is a C++ template library, which implements |
| form of lambda abstractions for C++. The term originates from functional programming and |
| lambda calculus, where a lambda abstraction defines an unnamed function. |
| Lambda expressions are very useful to construct the function objects required by some of |
| the functions in a bimap view. |
| |
| Boost.Bimap defines new placeholders in `<boost/bimap/support/lambda.hpp>` |
| to allow a sounder solution. The placeholders are named _key and _data and both |
| are equivalent to boost::lambda::_1. There are two reasons to include this placeholders: |
| the code looks better with them and they avoid the clash problem between lambda::_1 and |
| boost::_1 from Boost.Bind. |
| |
| [import ../example/bimap_and_boost/lambda.cpp] |
| |
| [@../../example/bimap_and_boost/lambda.cpp Go to source code] |
| |
| [code_bimap_and_boost_lambda] |
| |
| [endsect] |
| |
| [section Boost.Range] |
| |
| Boost.Range is a collection of concepts and utilities that are particularly useful |
| for specifying and implementing generic algorithms. |
| Generic algorithms have so far been specified in terms of two or more iterators. |
| Two iterators would together form a range of values that the algorithm could |
| work on. This leads to a very general interface, but also to a somewhat clumsy |
| use of the algorithms with redundant specification of container names. Therefore |
| we would like to raise the abstraction level for algorithms so they specify their |
| interface in terms of Ranges as much as possible. |
| |
| As Boost.Bimap views are signature-compatible with their standard |
| container counterparts, they are compatible with the concept of a range. |
| As an additional feature, ordered bimap views offer a function named |
| `range` that allows a range of values to be obtained. |
| |
| [import ../example/bimap_and_boost/range.cpp] |
| |
| If we have some generic functions that accepts ranges: |
| |
| [code_bimap_and_boost_range_functions] |
| |
| We can use them with Boost.Bimap with the help of the `range` function. |
| |
| [code_bimap_and_boost_range] |
| |
| [@../../example/bimap_and_boost/range.cpp Go to source code] |
| |
| [endsect] |
| |
| [section Boost.Foreach] |
| |
| In C++, writing a loop that iterates over a sequence is tedious. |
| We can either use iterators, which requires a considerable amount of |
| boiler-plate, or we can use the std::for_each() algorithm and move our |
| loop body into a predicate, which requires no less boiler-plate and forces |
| us to move our logic far from where it will be used. In contrast, some other |
| languages, like Perl, provide a dedicated "foreach" construct that automates |
| this process. BOOST_FOREACH is just such a construct for C++. It iterates |
| over sequences for us, freeing us from having to deal directly with iterators |
| or write predicates. |
| |
| You can use BOOST_FOREACH macro with Boost.Bimap views. The generated code will |
| be as efficient as a std::for_each iteration. |
| Here are some examples: |
| |
| [import ../example/bimap_and_boost/foreach.cpp] |
| |
| [code_bimap_and_boost_foreach] |
| |
| You can use it directly with ranges too: |
| |
| [code_bimap_and_boost_foreach_using_range] |
| |
| [@../../example/bimap_and_boost/foreach.cpp Go to source code] |
| |
| [endsect] |
| |
| [section Boost.Typeof] |
| |
| [import ../example/bimap_and_boost/typeof.cpp] |
| |
| Once C++0x is out we are going to be able to write code like: |
| |
| auto iter = bm.by<name>().find("john"); |
| |
| instead of the more verbose |
| |
| bm_type::map_by<name>::iterator iter = bm.by<name>().find("john"); |
| |
| Boost.Typeof defines a macro BOOST_AUTO that can be used as a library |
| solution to the auto keyword while we wait for the next standard. |
| |
| If we have |
| |
| [code_bimap_and_boost_typeof_first] |
| |
| The following code snippet |
| |
| [code_bimap_and_boost_typeof_not_using_auto] |
| |
| can be rewrited as |
| |
| [code_bimap_and_boost_typeof_using_auto] |
| |
| [@../../example/bimap_and_boost/typeof.cpp Go to source code] |
| |
| [endsect] |
| |
| [section Boost.Xpressive] |
| |
| [import ../example/bimap_and_boost/xpressive.cpp] |
| |
| Using Boost.Xpressive we can parse a file and insert the relations in a bimap |
| in the same step. It is just amazing the power of four lines of code. |
| Here is an example (it is just beatifull) |
| |
| [code_bimap_and_boost_xpressive] |
| |
| [@../../example/bimap_and_boost/xpressive.cpp Go to source code] |
| |
| [endsect] |
| |
| [section Boost.Property_map] |
| |
| The Boost Property Map Library consists mainly of interface specifications in the form of |
| concepts (similar to the iterator concepts in the STL). These interface specifications |
| are intended for use by implementers of generic libraries in communicating requirements on |
| template parameters to their users. In particular, the Boost Property Map concepts define a |
| general purpose interface for mapping key objects to corresponding value objects, thereby |
| hiding the details of how the mapping is implemented from algorithms. |
| |
| The need for the property map interface came from the Boost Graph Library (BGL), which |
| contains many examples of algorithms that use the property map concepts to specify their |
| interface. For an example, note the ColorMap template parameter of the breadth_first_search. |
| In addition, the BGL contains many examples of concrete types that implement the property map |
| interface. The adjacency_list class implements property maps for accessing objects |
| (properties) that are attached to vertices and edges of the graph. |
| |
| The counterparts of two of the views of Boost.Bimap map, the `set` and |
| `unordered_set`, are read-write property maps. In order to use these, you |
| need to include one of the following headers: |
| |
| #include <boost/bimap/property_map/set_support.hpp> |
| #include <boost/bimap/property_map/unordered_set_support.hpp> |
| |
| The following is adapted from the example in the Boost.PropertyMap |
| documentation. |
| |
| [import ../example/bimap_and_boost/property_map.cpp] |
| |
| [@../../example/bimap_and_boost/property_map.cpp Go to source code] |
| |
| [code_bimap_and_boost_property_map] |
| |
| [endsect] |
| |
| [endsect] |
| |
| [section Dependencies] |
| |
| Boost.Bimap is built on top of several Boost libraries. The rationale |
| behind this decision is keeping the Boost code base small by reusing |
| existent code. The libraries used are well-established and have been |
| tested extensively, making this library easy to port since all the hard |
| work has already been done. The glue that holds everything together is |
| Boost.MPL. Clearly Boost.MultiIndex is the heart of this library. |
| |
| [table Boost Libraries needed by Boost.Bimap |
| [[Name][Description][author]] |
| |
| [[ __BOOST_MULTI_INDEX__ ][ |
| Containers with multiple STL-compatible access interfaces] |
| [Joaquín M López Muñoz]] |
| |
| [[ __BOOST_MPL__ ][ |
| Template metaprogramming framework of compile-time algorithms, sequences and metafunction classes] |
| [Aleksey Gurtovoy]] |
| |
| [[ __BOOST_TYPE_TRAITS__ ][ |
| Templates for fundamental properties of types.] |
| [John Maddock, Steve Cleary]] |
| |
| [[ __BOOST_ENABLE_IF__ ][ |
| Selective inclusion of function template overloads] |
| [Jaakko Järvi, Jeremiah Willcock, Andrew Lumsdaine]] |
| |
| [[ __BOOST_ITERATORS__ ][ |
| Iterator construction framework, adaptors, concepts, and more.] |
| [Dave Abrahams, Jeremy Siek, Thomas Witt]] |
| |
| [[ __BOOST_CALL_TRAITS__ ][ |
| Defines types for passing parameters.] |
| [John Maddock, Howard Hinnant]] |
| |
| [[ __BOOST_STATIC_ASSERT__ ][ |
| Static assertions (compile time assertions).] |
| [John Maddock]] |
| |
| ] |
| |
| [table Optional Boost Libraries |
| [[Name][Description][author][Purpose]] |
| |
| [[ __BOOST_SERIALIZATION__ ][ |
| Serialization for persistence and marshalling] |
| [Robert Ramey] |
| [Serialization support for bimap containers and iterators]] |
| |
| [[ __BOOST_ASSIGN__ ][ |
| Filling containers with constant or generated data has never been easier] |
| [Thorsten Ottosen] |
| [Help to fill a bimap or views of it]] |
| |
| [[ __BOOST_HASH__ ][ |
| A TR1 hash function object that can be extended to hash user defined types] |
| [Daniel James] |
| [Default hashing function]] |
| |
| [[ __BOOST_LAMBDA__ ][ |
| Define small unnamed function objects at the actual call site, and more] |
| [from Jaakko Järvi, Gary Powell] |
| [Functors for modify, range, lower_bound and upper_bound]] |
| |
| [[ __BOOST_RANGE__ ][ |
| A new infrastructure for generic algorithms that builds on top of the new |
| iterator concepts] |
| [Thorsten Ottosen] |
| [Range based algorithms]] |
| |
| [[ __BOOST_PROPERTY_MAP__ ][ |
| Concepts defining interfaces which map key objects to value objects] |
| [Jeremy Siek] |
| [Integration with BGL]] |
| ] |
| |
| [table Additional Boost Libraries needed to run the test-suite |
| [[Name][Description][author]] |
| |
| [[ __BOOST_TEST__ ][ |
| Support for simple program testing, full unit testing, and for program execution monitoring.] |
| [Gennadiy Rozental] |
| ] |
| ] |
| |
| [endsect] |
| |
| [endsect] |