5 Copyright (c) 2006-2007 Matias Capeletto
7 Distributed under the Boost Software License, Version 1.0.
8 (See accompanying file LICENSE_1_0.txt or copy at
9 http://www.boost.org/LICENSE_1_0.txt)
13 [/ QuickBook Document version 1.4 ]
15 [section Bimap and Boost]
17 [section Bimap and MultiIndex]
19 ['MISC] - [*M]ulti-[*I]ndex [*S]pecialized [*C]ontainers
22 Let's be generic, construct frameworks, describe the world in an
26 No!, it is better to be specialized, design easy-to-use components,
27 offer plug-and-play objects...
30 Why not take advantage of the best of both worlds?
35 With Boost.Bimap, you can build associative containers in which both
36 types can be used as key. There is a library in Boost that already
37 allows the creation of this kind of container: Boost.MultiIndex. It
38 offers great flexibility and lets you construct almost any container
39 that you could dream of. The framework is very clean. You might want to
40 read this library's tutorial to learn about the power that has been
44 But generality comes at a price: the interface that results might not be
45 the best for every specialization. People may end up wrapping a B.MI
46 container in its own class every time they want to use it as a
47 bidirectional map. Boost.Bimap takes advantage of the narrower scope to
48 produce a better interface for bidirectional maps
49 [footnote In the same fashion, Boost.MRU will allow the creation of ['most
50 recent updated] aware containers, hiding the complexity of Boost.MultiIndex.].
51 There is no learning curve if you know how to use standard containers.
52 Great effort was put into mapping the naming scheme of the STL to Boost.Bimap.
53 The library is designed to match the common STL containers.
55 Boost.MultiIndex is, in fact, the core of the bimap container.
57 However, Boost.Bimap do not aim to tackle every problem with two indexed
58 types. There exist some problems that are better modelled with Boost.MultiIndex.
63 [*Problem I - An employee register]
65 ['Store an ID and a name for an employee, with fast search on each member.]
67 This type of problem is better modelled as a database table, and
68 [*Boost.MultiIndex] is the preferred choice. It is possible that other data
69 will need to be indexed later.
75 [*Problem II - A partners container]
77 ['Store the names of couples and be able to get the name of a person's
80 This problem is better modelled as a collection of relations, and [*Boost.Bimap]
86 [link boost_bimap.the_tutorial.additional_information Additional Information] for more
87 information about the relation of this two libraries.
91 [section Boost Libraries that work well with Boost.Bimap]
93 [section Introduction]
96 [[Name][Description][author][Purpose]]
98 [[ __BOOST_SERIALIZATION__ ][
99 Serialization for persistence and marshalling]
101 [Serialization support for bimap containers and iterators]]
103 [[ __BOOST_ASSIGN__ ][
104 Filling containers with constant or generated data has never been easier]
106 [Help to fill a bimap or views of it]]
109 A TR1 hash function object that can be extended to hash user defined types]
111 [Default hashing function]]
113 [[ __BOOST_LAMBDA__ ][
114 Define small unnamed function objects at the actual call site, and more]
115 [from Jaakko Järvi, Gary Powell]
116 [Functors for modify, range, lower_bound and upper_bound]]
118 [[ __BOOST_RANGE__ ][
119 A new infrastructure for generic algorithms that builds on top of the new
122 [Range based algorithms]]
124 [[ __BOOST_FOREACH__ ][
125 BOOST_FOREACH macro for easily iterating over the elements of a sequence]
129 [[ __BOOST_TYPEOF__ ][
130 Typeof operator emulation]
131 [Arkadiy Vertleyb, Peder Holt]
132 [Using BOOST_AUTO while we wait for C++0x]]
134 [[ __BOOST_XPRESSIVE__ ][
135 Regular expressions that can be written as strings or as expression templates]
137 [Help to fill a bimap from a string]]
139 [[ __BOOST_PROPERTY_MAP__ ][
140 Concepts defining interfaces which map key objects to value objects]
142 [Integration with BGL]]
147 [section Boost.Serialization]
149 A bimap can be archived and retrieved by means of the Boost.Serialization Library.
150 Both regular and XML archives are supported. The usage is straightforward and does
151 not differ from that of any other serializable type. For instance:
153 [import ../example/bimap_and_boost/serialization.cpp]
155 [@../../example/bimap_and_boost/serialization.cpp Go to source code]
157 [code_bimap_and_boost_serialization]
159 Serialization capabilities are automatically provided by just linking with the
160 appropriate Boost.Serialization library module: it is not necessary to explicitly
161 include any header from Boost.Serialization, apart from those declaring the type
162 of archive used in the process. If not used, however, serialization support can
163 be disabled by globally defining the macro BOOST_BIMAP_DISABLE_SERIALIZATION.
164 Disabling serialization for Boost.MultiIndex can yield a small improvement in
165 build times, and may be necessary in those defective compilers that fail to
166 correctly process Boost.Serialization headers.
168 [warning Boost.Bimap and Boost.MultiIndex share a lot of serialization code.
169 The macro `BOOST_BIMAP_DISABLE_SERIALIZATION` disables serialization in *both*
170 libraries. The same happens when `BOOST_MULTI_INDEX_DISABLE_SERIALIZATION` is
174 Retrieving an archived bimap restores not only the elements, but also the order
175 they were arranged in the views of the container. There is an exception to this rule,
176 though: for unordered sets, no guarantee is made about the order in which elements
177 will be iterated in the restored container; in general, it is unwise to rely on
178 the ordering of elements of a hashed view, since it can change in arbitrary ways
179 during insertion or rehashing --this is precisely the reason why hashed indices
180 and TR1 unordered associative containers do not define an equality operator.
182 Iterators of a bimap can also be serialized. Serialization of an
183 iterator must be done only after serializing its corresponding container.
187 [section Boost.Assign]
189 The purpose of this library is to make it easy to fill containers with data by
190 overloading operator,() and operator()(). These two operators make it possible
191 to construct lists of values that are then copied into a container.
193 These lists are particularly useful in learning, testing, and prototyping
194 situations, but can also be handy otherwise. The library comes with predefined
195 operators for the containers of the standard library, but most functionality will
196 work with any standard compliant container. The library also makes it possible
197 to extend user defined types so for example a member function can be called for
198 a list of values instead of its normal arguments.
200 Boost.Assign can be used with bimap containers.
201 The views of a bimap are signature-compatible with their standard
202 counterparts, so we can use other Boost.Assign utilities with them.
204 [import ../example/bimap_and_boost/assign.cpp]
206 [@../../example/bimap_and_boost/assign.cpp Go to source code]
208 [code_bimap_and_boost_assign]
214 The hash function is the very core of the fast lookup capabilities of the
215 unordered sets: a hasher is just a Unary Function returning an std::size_t value
216 for any given key. In general, it is impossible that every key map to a
217 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.
219 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.
222 [@http://www.boost.org/doc/html/hash/custom.html
223 extended for custom data types],
224 enabling to use the default parameter of the unordered set types with any user types.
228 [section Boost.Lambda]
230 The Boost Lambda Library (BLL in the sequel) is a C++ template library, which implements
231 form of lambda abstractions for C++. The term originates from functional programming and
232 lambda calculus, where a lambda abstraction defines an unnamed function.
233 Lambda expressions are very useful to construct the function objects required by some of
234 the functions in a bimap view.
236 Boost.Bimap defines new placeholders in `<boost/bimap/support/lambda.hpp>`
237 to allow a sounder solution. The placeholders are named _key and _data and both
238 are equivalent to boost::lambda::_1. There are two reasons to include this placeholders:
239 the code looks better with them and they avoid the clash problem between lambda::_1 and
240 boost::_1 from Boost.Bind.
242 [import ../example/bimap_and_boost/lambda.cpp]
244 [@../../example/bimap_and_boost/lambda.cpp Go to source code]
246 [code_bimap_and_boost_lambda]
250 [section Boost.Range]
252 Boost.Range is a collection of concepts and utilities that are particularly useful
253 for specifying and implementing generic algorithms.
254 Generic algorithms have so far been specified in terms of two or more iterators.
255 Two iterators would together form a range of values that the algorithm could
256 work on. This leads to a very general interface, but also to a somewhat clumsy
257 use of the algorithms with redundant specification of container names. Therefore
258 we would like to raise the abstraction level for algorithms so they specify their
259 interface in terms of Ranges as much as possible.
261 As Boost.Bimap views are signature-compatible with their standard
262 container counterparts, they are compatible with the concept of a range.
263 As an additional feature, ordered bimap views offer a function named
264 `range` that allows a range of values to be obtained.
266 [import ../example/bimap_and_boost/range.cpp]
268 If we have some generic functions that accepts ranges:
270 [code_bimap_and_boost_range_functions]
272 We can use them with Boost.Bimap with the help of the `range` function.
274 [code_bimap_and_boost_range]
276 [@../../example/bimap_and_boost/range.cpp Go to source code]
280 [section Boost.Foreach]
282 In C++, writing a loop that iterates over a sequence is tedious.
283 We can either use iterators, which requires a considerable amount of
284 boiler-plate, or we can use the std::for_each() algorithm and move our
285 loop body into a predicate, which requires no less boiler-plate and forces
286 us to move our logic far from where it will be used. In contrast, some other
287 languages, like Perl, provide a dedicated "foreach" construct that automates
288 this process. BOOST_FOREACH is just such a construct for C++. It iterates
289 over sequences for us, freeing us from having to deal directly with iterators
292 You can use BOOST_FOREACH macro with Boost.Bimap views. The generated code will
293 be as efficient as a std::for_each iteration.
294 Here are some examples:
296 [import ../example/bimap_and_boost/foreach.cpp]
298 [code_bimap_and_boost_foreach]
300 You can use it directly with ranges too:
302 [code_bimap_and_boost_foreach_using_range]
304 [@../../example/bimap_and_boost/foreach.cpp Go to source code]
308 [section Boost.Typeof]
310 [import ../example/bimap_and_boost/typeof.cpp]
312 Once C++0x is out we are going to be able to write code like:
314 auto iter = bm.by<name>().find("john");
316 instead of the more verbose
318 bm_type::map_by<name>::iterator iter = bm.by<name>().find("john");
320 Boost.Typeof defines a macro BOOST_AUTO that can be used as a library
321 solution to the auto keyword while we wait for the next standard.
325 [code_bimap_and_boost_typeof_first]
327 The following code snippet
329 [code_bimap_and_boost_typeof_not_using_auto]
333 [code_bimap_and_boost_typeof_using_auto]
335 [@../../example/bimap_and_boost/typeof.cpp Go to source code]
339 [section Boost.Xpressive]
341 [import ../example/bimap_and_boost/xpressive.cpp]
343 Using Boost.Xpressive we can parse a file and insert the relations in a bimap
344 in the same step. It is just amazing the power of four lines of code.
345 Here is an example (it is just beatifull)
347 [code_bimap_and_boost_xpressive]
349 [@../../example/bimap_and_boost/xpressive.cpp Go to source code]
353 [section Boost.Property_map]
355 The Boost Property Map Library consists mainly of interface specifications in the form of
356 concepts (similar to the iterator concepts in the STL). These interface specifications
357 are intended for use by implementers of generic libraries in communicating requirements on
358 template parameters to their users. In particular, the Boost Property Map concepts define a
359 general purpose interface for mapping key objects to corresponding value objects, thereby
360 hiding the details of how the mapping is implemented from algorithms.
362 The need for the property map interface came from the Boost Graph Library (BGL), which
363 contains many examples of algorithms that use the property map concepts to specify their
364 interface. For an example, note the ColorMap template parameter of the breadth_first_search.
365 In addition, the BGL contains many examples of concrete types that implement the property map
366 interface. The adjacency_list class implements property maps for accessing objects
367 (properties) that are attached to vertices and edges of the graph.
369 The counterparts of two of the views of Boost.Bimap map, the `set` and
370 `unordered_set`, are read-write property maps. In order to use these, you
371 need to include one of the following headers:
373 #include <boost/bimap/property_map/set_support.hpp>
374 #include <boost/bimap/property_map/unordered_set_support.hpp>
376 The following is adapted from the example in the Boost.PropertyMap
379 [import ../example/bimap_and_boost/property_map.cpp]
381 [@../../example/bimap_and_boost/property_map.cpp Go to source code]
383 [code_bimap_and_boost_property_map]
389 [section Dependencies]
391 Boost.Bimap is built on top of several Boost libraries. The rationale
392 behind this decision is keeping the Boost code base small by reusing
393 existent code. The libraries used are well-established and have been
394 tested extensively, making this library easy to port since all the hard
395 work has already been done. The glue that holds everything together is
396 Boost.MPL. Clearly Boost.MultiIndex is the heart of this library.
398 [table Boost Libraries needed by Boost.Bimap
399 [[Name][Description][author]]
401 [[ __BOOST_MULTI_INDEX__ ][
402 Containers with multiple STL-compatible access interfaces]
403 [Joaquín M López Muñoz]]
406 Template metaprogramming framework of compile-time algorithms, sequences and metafunction classes]
409 [[ __BOOST_TYPE_TRAITS__ ][
410 Templates for fundamental properties of types.]
411 [John Maddock, Steve Cleary]]
413 [[ __BOOST_ENABLE_IF__ ][
414 Selective inclusion of function template overloads]
415 [Jaakko Järvi, Jeremiah Willcock, Andrew Lumsdaine]]
417 [[ __BOOST_ITERATORS__ ][
418 Iterator construction framework, adaptors, concepts, and more.]
419 [Dave Abrahams, Jeremy Siek, Thomas Witt]]
421 [[ __BOOST_CALL_TRAITS__ ][
422 Defines types for passing parameters.]
423 [John Maddock, Howard Hinnant]]
425 [[ __BOOST_STATIC_ASSERT__ ][
426 Static assertions (compile time assertions).]
431 [table Optional Boost Libraries
432 [[Name][Description][author][Purpose]]
434 [[ __BOOST_SERIALIZATION__ ][
435 Serialization for persistence and marshalling]
437 [Serialization support for bimap containers and iterators]]
439 [[ __BOOST_ASSIGN__ ][
440 Filling containers with constant or generated data has never been easier]
442 [Help to fill a bimap or views of it]]
445 A TR1 hash function object that can be extended to hash user defined types]
447 [Default hashing function]]
449 [[ __BOOST_LAMBDA__ ][
450 Define small unnamed function objects at the actual call site, and more]
451 [from Jaakko Järvi, Gary Powell]
452 [Functors for modify, range, lower_bound and upper_bound]]
454 [[ __BOOST_RANGE__ ][
455 A new infrastructure for generic algorithms that builds on top of the new
458 [Range based algorithms]]
460 [[ __BOOST_PROPERTY_MAP__ ][
461 Concepts defining interfaces which map key objects to value objects]
463 [Integration with BGL]]
466 [table Additional Boost Libraries needed to run the test-suite
467 [[Name][Description][author]]
470 Support for simple program testing, full unit testing, and for program execution monitoring.]