]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | [/license |
2 | ||
3 | Boost.Bimap | |
4 | ||
5 | Copyright (c) 2006-2007 Matias Capeletto | |
6 | ||
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) | |
10 | ||
11 | ] | |
12 | ||
13 | [/ QuickBook Document version 1.4 ] | |
14 | ||
15 | [section Bimap and Boost] | |
16 | ||
17 | [section Bimap and MultiIndex] | |
18 | ||
19 | ['MISC] - [*M]ulti-[*I]ndex [*S]pecialized [*C]ontainers | |
20 | ||
21 | [:[' | |
22 | Let's be generic, construct frameworks, describe the world in an | |
23 | unified way... | |
24 | ]] | |
25 | [:[' | |
26 | No!, it is better to be specialized, design easy-to-use components, | |
27 | offer plug-and-play objects... | |
28 | ]] | |
29 | [:[* | |
30 | Why not take advantage of the best of both worlds? | |
31 | ]] | |
32 | ||
33 | __MI_FRAMEWORK__ | |
34 | ||
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 | |
41 | achieved. | |
42 | ||
43 | ||
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. | |
54 | ||
55 | Boost.MultiIndex is, in fact, the core of the bimap container. | |
56 | ||
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. | |
59 | ||
60 | ||
61 | [blurb | |
62 | ||
63 | [*Problem I - An employee register] | |
64 | ||
65 | ['Store an ID and a name for an employee, with fast search on each member.] | |
66 | ||
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. | |
70 | ||
71 | ] | |
72 | ||
73 | [blurb | |
74 | ||
75 | [*Problem II - A partners container] | |
76 | ||
77 | ['Store the names of couples and be able to get the name of a person's | |
78 | partner.] | |
79 | ||
80 | This problem is better modelled as a collection of relations, and [*Boost.Bimap] | |
81 | fits nicely here. | |
82 | ||
83 | ] | |
84 | ||
85 | You can also read | |
86 | [link boost_bimap.the_tutorial.additional_information Additional Information] for more | |
87 | information about the relation of this two libraries. | |
88 | ||
89 | [endsect] | |
90 | ||
91 | [section Boost Libraries that work well with Boost.Bimap] | |
92 | ||
93 | [section Introduction] | |
94 | ||
95 | [table | |
96 | [[Name][Description][author][Purpose]] | |
97 | ||
98 | [[ __BOOST_SERIALIZATION__ ][ | |
99 | Serialization for persistence and marshalling] | |
100 | [Robert Ramey] | |
101 | [Serialization support for bimap containers and iterators]] | |
102 | ||
103 | [[ __BOOST_ASSIGN__ ][ | |
104 | Filling containers with constant or generated data has never been easier] | |
105 | [Thorsten Ottosen] | |
106 | [Help to fill a bimap or views of it]] | |
107 | ||
108 | [[ __BOOST_HASH__ ][ | |
109 | A TR1 hash function object that can be extended to hash user defined types] | |
110 | [Daniel James] | |
111 | [Default hashing function]] | |
112 | ||
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]] | |
117 | ||
118 | [[ __BOOST_RANGE__ ][ | |
119 | A new infrastructure for generic algorithms that builds on top of the new | |
120 | iterator concepts] | |
121 | [Thorsten Ottosen] | |
122 | [Range based algorithms]] | |
123 | ||
124 | [[ __BOOST_FOREACH__ ][ | |
125 | BOOST_FOREACH macro for easily iterating over the elements of a sequence] | |
126 | [Eric Niebler] | |
127 | [Iteration]] | |
128 | ||
129 | [[ __BOOST_TYPEOF__ ][ | |
130 | Typeof operator emulation] | |
131 | [Arkadiy Vertleyb, Peder Holt] | |
132 | [Using BOOST_AUTO while we wait for C++0x]] | |
133 | ||
134 | [[ __BOOST_XPRESSIVE__ ][ | |
135 | Regular expressions that can be written as strings or as expression templates] | |
136 | [Eric Niebler] | |
137 | [Help to fill a bimap from a string]] | |
138 | ||
139 | [[ __BOOST_PROPERTY_MAP__ ][ | |
140 | Concepts defining interfaces which map key objects to value objects] | |
141 | [Jeremy Siek] | |
142 | [Integration with BGL]] | |
143 | ] | |
144 | ||
145 | [endsect] | |
146 | ||
147 | [section Boost.Serialization] | |
148 | ||
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: | |
152 | ||
153 | [import ../example/bimap_and_boost/serialization.cpp] | |
154 | ||
155 | [@../../example/bimap_and_boost/serialization.cpp Go to source code] | |
156 | ||
157 | [code_bimap_and_boost_serialization] | |
158 | ||
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. | |
167 | ||
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 | |
171 | defined. | |
172 | ] | |
173 | ||
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. | |
181 | ||
182 | Iterators of a bimap can also be serialized. Serialization of an | |
183 | iterator must be done only after serializing its corresponding container. | |
184 | ||
185 | [endsect] | |
186 | ||
187 | [section Boost.Assign] | |
188 | ||
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. | |
192 | ||
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. | |
199 | ||
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. | |
203 | ||
204 | [import ../example/bimap_and_boost/assign.cpp] | |
205 | ||
206 | [@../../example/bimap_and_boost/assign.cpp Go to source code] | |
207 | ||
208 | [code_bimap_and_boost_assign] | |
209 | ||
210 | [endsect] | |
211 | ||
212 | [section Boost.Hash] | |
213 | ||
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. | |
218 | ||
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. | |
220 | ||
221 | Boost.Hash can be | |
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. | |
225 | ||
226 | [endsect] | |
227 | ||
228 | [section Boost.Lambda] | |
229 | ||
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. | |
235 | ||
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. | |
241 | ||
242 | [import ../example/bimap_and_boost/lambda.cpp] | |
243 | ||
244 | [@../../example/bimap_and_boost/lambda.cpp Go to source code] | |
245 | ||
246 | [code_bimap_and_boost_lambda] | |
247 | ||
248 | [endsect] | |
249 | ||
250 | [section Boost.Range] | |
251 | ||
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. | |
260 | ||
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. | |
265 | ||
266 | [import ../example/bimap_and_boost/range.cpp] | |
267 | ||
268 | If we have some generic functions that accepts ranges: | |
269 | ||
270 | [code_bimap_and_boost_range_functions] | |
271 | ||
272 | We can use them with Boost.Bimap with the help of the `range` function. | |
273 | ||
274 | [code_bimap_and_boost_range] | |
275 | ||
276 | [@../../example/bimap_and_boost/range.cpp Go to source code] | |
277 | ||
278 | [endsect] | |
279 | ||
280 | [section Boost.Foreach] | |
281 | ||
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 | |
290 | or write predicates. | |
291 | ||
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: | |
295 | ||
296 | [import ../example/bimap_and_boost/foreach.cpp] | |
297 | ||
298 | [code_bimap_and_boost_foreach] | |
299 | ||
300 | You can use it directly with ranges too: | |
301 | ||
302 | [code_bimap_and_boost_foreach_using_range] | |
303 | ||
304 | [@../../example/bimap_and_boost/foreach.cpp Go to source code] | |
305 | ||
306 | [endsect] | |
307 | ||
308 | [section Boost.Typeof] | |
309 | ||
310 | [import ../example/bimap_and_boost/typeof.cpp] | |
311 | ||
312 | Once C++0x is out we are going to be able to write code like: | |
313 | ||
314 | auto iter = bm.by<name>().find("john"); | |
315 | ||
316 | instead of the more verbose | |
317 | ||
318 | bm_type::map_by<name>::iterator iter = bm.by<name>().find("john"); | |
319 | ||
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. | |
322 | ||
323 | If we have | |
324 | ||
325 | [code_bimap_and_boost_typeof_first] | |
326 | ||
327 | The following code snippet | |
328 | ||
329 | [code_bimap_and_boost_typeof_not_using_auto] | |
330 | ||
331 | can be rewrited as | |
332 | ||
333 | [code_bimap_and_boost_typeof_using_auto] | |
334 | ||
335 | [@../../example/bimap_and_boost/typeof.cpp Go to source code] | |
336 | ||
337 | [endsect] | |
338 | ||
339 | [section Boost.Xpressive] | |
340 | ||
341 | [import ../example/bimap_and_boost/xpressive.cpp] | |
342 | ||
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) | |
346 | ||
347 | [code_bimap_and_boost_xpressive] | |
348 | ||
349 | [@../../example/bimap_and_boost/xpressive.cpp Go to source code] | |
350 | ||
351 | [endsect] | |
352 | ||
353 | [section Boost.Property_map] | |
354 | ||
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. | |
361 | ||
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. | |
368 | ||
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: | |
372 | ||
373 | #include <boost/bimap/property_map/set_support.hpp> | |
374 | #include <boost/bimap/property_map/unordered_set_support.hpp> | |
375 | ||
376 | The following is adapted from the example in the Boost.PropertyMap | |
377 | documentation. | |
378 | ||
379 | [import ../example/bimap_and_boost/property_map.cpp] | |
380 | ||
381 | [@../../example/bimap_and_boost/property_map.cpp Go to source code] | |
382 | ||
383 | [code_bimap_and_boost_property_map] | |
384 | ||
385 | [endsect] | |
386 | ||
387 | [endsect] | |
388 | ||
389 | [section Dependencies] | |
390 | ||
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. | |
397 | ||
398 | [table Boost Libraries needed by Boost.Bimap | |
399 | [[Name][Description][author]] | |
400 | ||
401 | [[ __BOOST_MULTI_INDEX__ ][ | |
402 | Containers with multiple STL-compatible access interfaces] | |
403 | [Joaquín M López Muñoz]] | |
404 | ||
405 | [[ __BOOST_MPL__ ][ | |
406 | Template metaprogramming framework of compile-time algorithms, sequences and metafunction classes] | |
407 | [Aleksey Gurtovoy]] | |
408 | ||
409 | [[ __BOOST_TYPE_TRAITS__ ][ | |
410 | Templates for fundamental properties of types.] | |
411 | [John Maddock, Steve Cleary]] | |
412 | ||
413 | [[ __BOOST_ENABLE_IF__ ][ | |
414 | Selective inclusion of function template overloads] | |
415 | [Jaakko Järvi, Jeremiah Willcock, Andrew Lumsdaine]] | |
416 | ||
417 | [[ __BOOST_ITERATORS__ ][ | |
418 | Iterator construction framework, adaptors, concepts, and more.] | |
419 | [Dave Abrahams, Jeremy Siek, Thomas Witt]] | |
420 | ||
421 | [[ __BOOST_CALL_TRAITS__ ][ | |
422 | Defines types for passing parameters.] | |
423 | [John Maddock, Howard Hinnant]] | |
424 | ||
425 | [[ __BOOST_STATIC_ASSERT__ ][ | |
426 | Static assertions (compile time assertions).] | |
427 | [John Maddock]] | |
428 | ||
429 | ] | |
430 | ||
431 | [table Optional Boost Libraries | |
432 | [[Name][Description][author][Purpose]] | |
433 | ||
434 | [[ __BOOST_SERIALIZATION__ ][ | |
435 | Serialization for persistence and marshalling] | |
436 | [Robert Ramey] | |
437 | [Serialization support for bimap containers and iterators]] | |
438 | ||
439 | [[ __BOOST_ASSIGN__ ][ | |
440 | Filling containers with constant or generated data has never been easier] | |
441 | [Thorsten Ottosen] | |
442 | [Help to fill a bimap or views of it]] | |
443 | ||
444 | [[ __BOOST_HASH__ ][ | |
445 | A TR1 hash function object that can be extended to hash user defined types] | |
446 | [Daniel James] | |
447 | [Default hashing function]] | |
448 | ||
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]] | |
453 | ||
454 | [[ __BOOST_RANGE__ ][ | |
455 | A new infrastructure for generic algorithms that builds on top of the new | |
456 | iterator concepts] | |
457 | [Thorsten Ottosen] | |
458 | [Range based algorithms]] | |
459 | ||
460 | [[ __BOOST_PROPERTY_MAP__ ][ | |
461 | Concepts defining interfaces which map key objects to value objects] | |
462 | [Jeremy Siek] | |
463 | [Integration with BGL]] | |
464 | ] | |
465 | ||
466 | [table Additional Boost Libraries needed to run the test-suite | |
467 | [[Name][Description][author]] | |
468 | ||
469 | [[ __BOOST_TEST__ ][ | |
470 | Support for simple program testing, full unit testing, and for program execution monitoring.] | |
471 | [Gennadiy Rozental] | |
472 | ] | |
473 | ] | |
474 | ||
475 | [endsect] | |
476 | ||
477 | [endsect] |