123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477 |
- [/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 might 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]
|