]>
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 Rationale] | |
16 | ||
17 | This section assumes that you have read all other sections, the most of | |
18 | important of which being ['tutorial], ['std::set theory] and the ['reference], | |
19 | and that you have tested the library. A lot of effort was invested in | |
20 | making the interface as intuitive and clean as possible. If you | |
21 | understand, and hopefully like, the interface of this library, it will | |
22 | be a lot easier to read this rationale. The following section is little | |
23 | more than a rationale. This library was coded in the context of the | |
24 | Google SoC 2006 and the student and mentor were in different continents. | |
25 | A great deal of email flowed between Joaquin and Matias. The juiciest | |
26 | parts of the conversations where extracted and rearranged here. | |
27 | ||
28 | [note To browse the code, you can use the [@doxydoc/index.html ['Bimap Complete Reference]], a | |
29 | doxygen-powered document targeted at developers. | |
30 | ] | |
31 | ||
32 | [section General Design] | |
33 | ||
34 | The initial explanation includes few features. This section aims to | |
35 | describe the general design of the library and excludes details of those | |
36 | features that are of lesser importance; these features will be | |
37 | introduced later. | |
38 | ||
39 | The design of the library is divided into two parts. The first is the | |
40 | construction of a [^relation] class. This will be the object stored and | |
41 | managed by the [^multi_index_container] core. The idea is to make this | |
42 | class as easy as possible to use, while making it efficient in terms of | |
43 | memory and access time. This is a cornerstone in the design of | |
44 | [*Boost.Bimap] and, as you will see in this rationale, the rest of the | |
45 | design follows easily. | |
46 | ||
47 | The following interface is necessary for the [^relation] class: | |
48 | ||
49 | typedef -unspecified- TA; typedef -unspecified- TB; | |
50 | ||
51 | TA a, ai; TB b, bi; | |
52 | ||
53 | typedef relation< TA, TB > rel; | |
54 | STATIC_ASSERT( is_same< rel::left_type , TA >::value ); | |
55 | STATIC_ASSERT( is_same< rel::right_type, TB >::value ); | |
56 | ||
57 | rel r(ai,bi); | |
58 | assert( r.left == ai && r.right == bi ); | |
59 | ||
60 | r.left = a; r.right = b; | |
61 | assert( r.left == a && r.right == b ); | |
62 | ||
63 | typedef pair_type_by< member_at::left , rel >::type pba_type; | |
64 | STATIC_ASSERT( is_same< pba_type::first_type , TA >::value ); | |
65 | STATIC_ASSERT( is_same< pba_type::second_type, TB >::value ); | |
66 | ||
67 | typedef pair_type_by< member_at::right, rel >::type pbb_type; | |
68 | STATIC_ASSERT( is_same< pbb_type::first_type , TB >::value ); | |
69 | STATIC_ASSERT( is_same< pbb_type::second_type, TA >::value ); | |
70 | ||
71 | pba_type pba = pair_by< member_at::left >(r); | |
72 | assert( pba.first == r.left && pba.second == r.right ); | |
73 | ||
74 | pbb_type pbb = pair_by< member_at::right >(r); | |
75 | assert( pbb.first == r.right && pbb.second == r.left ); | |
76 | ||
77 | ||
78 | __RELATION__ | |
79 | ||
80 | Although this seems straightforward, as will be seen later, it is the | |
81 | most difficult code hack of the library. It is indeed very easy if we | |
82 | relax some of the efficiency constraints. For example, it is trivial if | |
83 | we allow a relation to have greater size than the the sum of those of | |
84 | its components. It is equally simple if access speed is not important. | |
85 | One of the first decisions made about [*Boost.Bimap] was, however, that, in | |
86 | order to be useful, it had to achieve zero overhead over the wrapped | |
87 | [*Boost.MultiIndex] container. Finally, there is another constraint that | |
88 | can be relaxed: conformance to C++ standards, but this is quite | |
89 | unacceptable. Let us now suppose that we have coded this class, and it | |
90 | conforms to what was required. | |
91 | ||
92 | The second part is based on this [^relation] class. We can now view the | |
93 | data in any of three ways: `pair<A,B>`, `relation<A,B>` and `pair<B,A>`. | |
94 | Suppose that our bimap supports only one-to-one relations. (Other | |
95 | relation types are considered additional features in this design.) | |
96 | The proposed interface is very simple, and it is based heavily on the | |
97 | concepts of the STL. Given a `bimap<A,B> bm`: | |
98 | ||
99 | # `bm.left` is signature-compatible with a `std::map<A,B>` | |
100 | # `bm.right` is signature-compatible with a `std::map<B,A>` | |
101 | # `bm` is signature-compatible with a `std::set<relation<A,B> >` | |
102 | ||
103 | __SIMPLE_BIMAP__ | |
104 | ||
105 | This interface is easily learned by users who have a STL background, as | |
106 | well as being simple and powerful. This is the general design. | |
107 | ||
108 | [heading Relation Implementation] | |
109 | ||
110 | This section explains the details of the actual [^relation] class implementation. | |
111 | ||
112 | The first thing that we can imagine is the use of an [^union]. Regrettably, | |
113 | the current C++ standard only allows unions of POD types. For the views, | |
114 | we can try a wrapper around a `relation<A,B>` that has two references | |
115 | named first and second that bind to `A` and `B`, or to `B` and `A`. | |
116 | ||
117 | relation<TA,TB> r; | |
118 | ||
119 | const_reference_pair<A,B> pba(r); | |
120 | const_reference_pair<B,A> pbb(r); | |
121 | ||
122 | It is not difficult to code the relation class using this, but two | |
123 | references are initialized at every access and using of `pba.first` will | |
124 | be slower in most compilers than using `r.left` directly . There is | |
125 | another hidden drawback of using this scheme: it is not | |
126 | iterator-friendly, since the map views iterators must be degraded to | |
127 | ['Read Write] instead of ['LValue]. This will be explained later. | |
128 | ||
129 | At first, this seems to be the best we can do with the current C++ | |
130 | standard. However there is a solution to this problem that does not | |
131 | conform very well to C++ standards but does achieve zero overhead in | |
132 | terms of access time and memory, and additionally allows the view | |
133 | iterators to be upgraded to ['LValue] again. | |
134 | ||
135 | In order to use this, the compiler must conform to a | |
136 | layout-compatibility clause that is not currently in the standard but is | |
137 | very natural. The additional clause imposes that if we have two classes: | |
138 | ||
139 | struct class_a_b | |
140 | { | |
141 | Type1 name_a; | |
142 | Type2 name_b; | |
143 | }; | |
144 | ||
145 | struct class_b_a | |
146 | { | |
147 | Type1 name_b; | |
148 | Type2 name_a; | |
149 | }; | |
150 | ||
151 | then the storage layout of [^class_a_b] is equal to the storage layout of | |
152 | [^class_b_a]. If you are surprised to learn that this does not hold in a | |
153 | standards-compliant C++ compiler, welcome to the club. It is the natural | |
154 | way to implement it from the point of view of the compiler's vendor and | |
155 | is very useful for the developer. Maybe it will be included in the | |
156 | standard some day. Every current compiler conforms to this. | |
157 | ||
158 | If we are able to count on this, then we can implement an idiom called | |
159 | [^mutant]. The idea is to provide a secure wrapper around [^reinterpret_cast]. | |
160 | A class can declare that it can be viewed using different view classes | |
161 | that are storage-compatible with it. Then we use the free function | |
162 | [^mutate<view>(mutant)] to get the view. The `mutate` function checks at | |
163 | compile time that the requested view is declared in the mutant views list. | |
164 | We implement a class name `structured_pair` that is signature-compatible | |
165 | with a `std::pair`, while the storage layout is configured with a third | |
166 | template parameter. Two instances of this template class will provide | |
167 | the views of the relation. | |
168 | ||
169 | The thing is that if we want to be standards-compliant, we cannot use | |
170 | this approach. It is very annoying not to be able to use something that | |
171 | we know will work with every compiler and that is far better than | |
172 | alternatives. So -- and this is an important decision -- we have to find | |
173 | a way to use it and still make the library standards-compliant. | |
174 | ||
175 | The idea is very simple. We code both approaches: the | |
176 | const_reference_pair-based and the mutant-based, and use the mutant | |
177 | approach if the compiler is compliant with our new layout-compatible | |
178 | clause. If the compiler really messes things up, we degrade the | |
179 | performance of the bimap a little. The only drawback here is that, while | |
180 | the mutant approach allows to make ['LValue] iterators, we have to degrade | |
181 | them to ['Read Write] in both cases, because we require that the same code | |
182 | be compilable by any standards-compliant compiler. | |
183 | ||
184 | [note | |
185 | Testing this approach in all the supported compilers indicated that the | |
186 | mutant idiom was always supported. The strictly compliant version was | |
187 | removed from the code because it was never used. | |
188 | ] | |
189 | ||
190 | ||
191 | [heading Bimap Implementation] | |
192 | ||
193 | The core of bimap will be obviously a `multi_index_container`. The basic | |
194 | idea to tackle the implementation of the bimap class is to use | |
195 | [^iterator_adaptor] to convert the iterators from Boost.MultiIndex to the | |
196 | `std::map` and `std::set` behaviour. The `map_view` and the `set_view` can be | |
197 | implemented directly using this new transformed iterators and a wrapper | |
198 | around each index of the core container. However, there is a hidden | |
199 | idiom here, that, once coded, will be very useful for other parts of | |
200 | this library and for Boost.MRU library. Following the ideas from | |
201 | `iterator_adaptor`, Boost.Bimap views are implemented using a | |
202 | [^container_adaptor]. There are several template classes (for example | |
203 | `map_adaptor` and `set_adaptor`) that take a `std::map` signature-conformant | |
204 | class and new iterators, and adapt the container so it now uses this | |
205 | iterators instead of the originals. For example, if you have a | |
206 | `std::set<int*>`, you can build other container that behaves exactly as a | |
207 | `std::set<int>` using `set_adaptor` and [^iterator_adaptor]. The combined use | |
208 | of this two tools is very powerful. A [^container_adaptor] can take classes | |
209 | that do not fulfil all the requirements of the adapted container. The | |
210 | new container must define these missing functions. | |
211 | ||
212 | [endsect] | |
213 | ||
214 | [section Additional Features] | |
215 | ||
216 | [heading N-1, N-N, hashed maps] | |
217 | ||
218 | This is a very interesting point of the design. The framework introduced | |
219 | in ['std::set theory] permits the management of the different constraints | |
220 | with a very simple and conceptual approach. It is easy both to remember | |
221 | and to learn. The idea here is to allow the user to specify the collection type | |
222 | of each key directly. In order to implement this feature, we have to | |
223 | solve two problems: | |
224 | ||
225 | * The index types of the `multi_index_container` core now depends on | |
226 | the collection type used for each key. | |
227 | * The map views now change their semantics according to the collection type | |
228 | chosen. | |
229 | ||
230 | Boost.Bimap relies heavily on Boost.MPL to implement all of the | |
231 | metaprogramming necessary to make this framework work. By default, if | |
232 | the user does not specify the kind of the set, a `std::set` type is used. | |
233 | ||
234 | __BIMAP_STRUCTURES__ | |
235 | ||
236 | [heading Collection type of relation constraints] | |
237 | ||
238 | The constraints of the bimap set view are another very important | |
239 | feature. In general, Boost.Bimap users will base the set view type on | |
240 | one of the two collection types of their keys. It may be useful however to give | |
241 | this set other constraints or simply to order it differently. By | |
242 | default, Boost.Bimap bases the collection type of relations on the left collection | |
243 | type, but the user may choose between: | |
244 | ||
245 | * left_based | |
246 | * right_based | |
247 | * set_of_relation<> | |
248 | * multiset_of_relation<> | |
249 | * unordered_set_of_relation<> | |
250 | * unordered_multiset_of_relation<> | |
251 | * list_of | |
252 | * vector_of | |
253 | ||
254 | In the first two cases, there are only two indices in the | |
255 | `multi_index_core`, and for this reason, these are the preferred options. | |
256 | The implementation uses further metaprogramming to define a new index if | |
257 | necessary. | |
258 | ||
259 | [/ | |
260 | [heading Hooking Data] | |
261 | ||
262 | This is one of the things that makes Boost.Bimap very appealing in | |
263 | tackling a problem. In general, programmers use maps to access | |
264 | information quickly. Boost.Bimap allows the user to hook data inside the | |
265 | bimap so that it is not necessary to maintain another map. The | |
266 | implementation is based heavily on metaprogramming. | |
267 | ] | |
268 | ||
269 | [heading Tagged] | |
270 | ||
271 | The idea of using tags instead of the [^member_at::side] idiom is very | |
272 | appealing since code that uses it is more readable. The only cost is | |
273 | compile time. ['boost/bimap/tagged] is the implementation of a non-invasive | |
274 | tagged idiom. The [^relation] class is built in such a way that even when | |
275 | the user uses tags, the [^member_at::side] idiom continues to work. This is | |
276 | good since an user can start tagging even before completing the coding | |
277 | of the algorithm, and the untagged code continues to work. The | |
278 | development becomes a little more complicated when user-defined tags are | |
279 | included, but there are many handy metafunctions defined in the [^tagged] | |
280 | idiom that help to keep things simple enough. | |
281 | ||
282 | __TAGGED__ | |
283 | ||
284 | [endsect] | |
285 | ||
286 | [section Code] | |
287 | ||
288 | You can browse the code using the [@doxydoc/index.html [*Boost.Bimap doxygen docs]]. | |
289 | ||
290 | The code follows the [@http://www.boost.org/more/lib_guide.htm Boost Library Requirement and Guidelines] as | |
291 | closely as possible. | |
292 | ||
293 | [table folders in boost/bimap | |
294 | [[name][what is inside?]] | |
295 | [[/ ][user level header files ]] | |
296 | [[tagged/ ][tagged idiom ]] | |
297 | [[relation/ ][the bimap data ]] | |
298 | [[container_adaptor/ ][easy way of adapting containers ]] | |
299 | [[views/ ][bimap views ]] | |
300 | [[property_map/ ][support for property map concept ]] | |
301 | ] | |
302 | ||
303 | [table folders in each folder | |
304 | [[name][what is inside?]] | |
305 | [[ ][class definitions]] | |
306 | [[support/ ][optional metafunctions and free functions]] | |
307 | [[detail/ ][things not intended for the user's eyes]] | |
308 | ] | |
309 | ||
310 | [endsect] | |
311 | ||
312 | [section The student and the mentor] | |
313 | ||
314 | [tip It is a good idea to read the original | |
315 | [@http://h1.ripway.com/mcape/boost/libs/misc/ Boost.Misc SoC proposal] first.] | |
316 | ||
317 | [:[^- The discussion starts with Joaquin trying to strip out the "misc" name out of the library -]] | |
318 | ||
319 | __JOAQUIN_PHOTO__ | |
320 | ||
321 | [*Joaquin] | |
322 | [:[' | |
323 | Thinking about it, the unifying principle of MISC containers is perhaps | |
324 | misleading: certainly all miscs use multi-indexing internally, but this does | |
325 | not reflect much in the external interface (as it should be, OTOH). So, from | |
326 | the user's point of view, miscs are entirely heterogeneous beasts. Moreover, | |
327 | there isn't in your proposal any kind of global facility common to all miscs. | |
328 | What about dropping the misc principle and working on each container as a | |
329 | separate library, then? You'd have boost::bimap, boost::mru, etc, and no common | |
330 | intro to them. This also opens up the possibility to add other containers to | |
331 | the suite which aren't based on B.MI. What's your stance on this? Do you see a | |
332 | value in keeping miscs conceptually together? | |
333 | ]] | |
334 | ||
335 | __MATIAS_PHOTO__ | |
336 | ||
337 | [*Matias] | |
338 | [:[' | |
339 | As the original proposal states only two containers (bimap and mru set) both | |
340 | based in B.MI, it was straight forward to group them together. When I was | |
341 | writing the SoC proposal I experienced a similar feeling when the two families | |
342 | begin to grow. As you say, the only common denominator is their internal | |
343 | implementation. I thought a bit about a more general framework to join this two | |
344 | families (and other internally related ones) and finally came up with an idea: | |
345 | Boost.MultiIndex! So I think that it is not a good idea to try to unify the two | |
346 | families and I voted in favor of get rid of the misc part of boost::misc::bimap | |
347 | and boost::misc::mru. Anyway, for my SoC application it seems OK to put the | |
348 | two families in the same project because although from the outside they are | |
349 | completely unrelated, the work I will have to do in order to build the libraries | |
350 | will be consistent and what I will learn coding the bimap family will be used | |
351 | when I start to code the mru family. When the mru family is in place, I will | |
352 | surely have learnt other things to improve the bimap group. | |
353 | ]] | |
354 | [:[' | |
355 | On the other hand, I think it will be useful for the general user to | |
356 | have at least some document linked in the B.MI documentation that | |
357 | enumerates the most common cases of uses (a bimap and an mru set for | |
358 | example) and points where to find clean implementation for this useful | |
359 | containers. For now, a link to boost::bimap and other one to boost::mru | |
360 | will suffice. If you think about the title of such a document, | |
361 | you will probably come up with something like: Common Multi Index | |
362 | Specialized Containers, and we are back to our misc proposal. | |
363 | So, to order some ideas: | |
364 | ]] | |
365 | [:['- A new family of containers that can be accessed by both key will | |
366 | be created. (boost::bimap)]] | |
367 | [:['- A new family of time aware containers will see the light. | |
368 | (boost::mru)]] | |
369 | [:['- A page can be added to B.MI documentation, titled misc that links | |
370 | this new libraries.]] | |
371 | [:[' | |
372 | This is a clearer framework for the user. They can use a mru container | |
373 | without hearing about Boost.MultiIndex at all. | |
374 | And B.MI users will get some of their common containers already | |
375 | implemented with an STL friendly interface in other libraries. | |
376 | And as you stated this is more extensible because opens the door to use | |
377 | other libraries in bimap and mru families than just Boost.MultiIndex | |
378 | without compromising the more general boost framework. | |
379 | The word "misc" it is going to disappear from the code and | |
380 | the documentation of bimap and mru. From now on the only use for it will be to | |
381 | identify our SoC project. I am thinking in a name for the bimap library. | |
382 | What about Boost.BidirectionalMap? Ideas? | |
383 | ]] | |
384 | ||
385 | [*Joaquin] | |
386 | [:[' | |
387 | Yes, Boost.Bimap. In my opinion, bimap is a well known name | |
388 | in the Boost and even in the C++ community. It sounds and is short. Why not to | |
389 | vindicate yourself as the owner of this name? | |
390 | ]] | |
391 | ||
392 | [^- Then after a week of work -] | |
393 | ||
394 | [*Matias] | |
395 | [:[' | |
396 | Now that Boost.Bimap is getting some shape, I see that as | |
397 | you have told me, we must offer a "one_to_many_map" and a "multi_bimap" | |
398 | as part of the library. The framework I am actually working allowed to | |
399 | construct this kind of bidirectional maps and it is easy to understand from | |
400 | the user side. | |
401 | ]] | |
402 | ||
403 | [*Joaquin] | |
404 | [:[' | |
405 | OK, I am glad we agree on this point. | |
406 | ]] | |
407 | ||
408 | [*Matias] | |
409 | [:[' | |
410 | With respect to the symmetry of the key access names, I have to | |
411 | agree that there is not much a difference between the following ones: | |
412 | ]] | |
413 | [:['- to - from]] | |
414 | [:['- to - b]] | |
415 | [:['- 0 - 1]] | |
416 | [:['- left - right]] | |
417 | [:[' | |
418 | In my opinion it is a matter of taste, but left/right sounds more symmetrical than | |
419 | the others. | |
420 | ]] | |
421 | ||
422 | [*Joaquin] | |
423 | [:[' | |
424 | I like very much the left/right notation, it is very simple to | |
425 | remember and it is a lot more symmetrical than to/from. | |
426 | ]] | |
427 | ||
428 | [*Matias] | |
429 | [:[' | |
430 | At first my idea was to obtain ease of use hiding the B.MI | |
431 | core, making it more STL-intuitive. Nevertheless I have realized | |
432 | that B.MI is a lot more coherent and easy to use that I had imagined. This | |
433 | makes me think again in the problem. In the design that I am coding now, bimap | |
434 | *is-a* multi_index_container specializes with a data type very comfortable | |
435 | called bipair, that can be seen like any of the two maps that integrates it | |
436 | using map views. This scheme has great benefits for users: | |
437 | ]] | |
438 | [:[' | |
439 | - If the user already knows B.MI, he can take advantage of the tools that | |
440 | it provides and that are not present in the STL containers. In addition, in some | |
441 | cases the use to indices to see the data can be very useful. | |
442 | ]] | |
443 | [:[' | |
444 | - If the user does not know anything about B.MI but have an STL framework, | |
445 | the learning curve is reduced to understand the bimap instantiation and how a | |
446 | is obtained the desired map view. | |
447 | ]] | |
448 | [:[' | |
449 | Another very important benefit holds: All the algorithms done for | |
450 | B.MI continues to work with Boost.Bimap and if B.MI continues growing, bimap | |
451 | grow automatically. | |
452 | ]] | |
453 | ||
454 | [*Joaquin] | |
455 | [:[' | |
456 | Umm... This is an interesting design decision, but | |
457 | controversial in my opinion. Basically you decide to expose the | |
458 | implementation of bimap; that has advantages, as you stated, but also | |
459 | a nonsmall disadvantage: once *you have documented* the implementation, | |
460 | it is not possible to change it anymore. It is a marriage with B.MI without | |
461 | the chance of divorce. The other possibility, to hide the implementation and | |
462 | to duplicate and document the provided functionality, explicitly or | |
463 | implicitly due to the same characteristics of the implementation, is | |
464 | of course heavier to maintain, but it gives a degree of freedom to change | |
465 | the guts of your software if you need to. Do not take this like a frontal | |
466 | objection, but I think that it is quite important design decision, not only | |
467 | in the context of bimap but in general. | |
468 | ]] | |
469 | ||
470 | [*Matias] | |
471 | [:[' | |
472 | You are quite right here. I think we have to choose the hardest | |
473 | path and hide the B.MI core from the user. I am sending you the first draft of | |
474 | bimap along with some documentation. | |
475 | ]] | |
476 | ||
477 | [^- This completes the second week, the documentation was basically the first | |
478 | section of this rationale -] | |
479 | ||
480 | [*Joaquin] | |
481 | [:[' | |
482 | I must confess that I am beginning to like what I see. | |
483 | I am mathematical by vocation, and when I see symmetry in a formulation | |
484 | I believe that it is in the right track. | |
485 | ]] | |
486 | ||
487 | [*Matias] | |
488 | [:[' | |
489 | We are two mathematicians by vocation then. | |
490 | ]] | |
491 | ||
492 | [*Joaquin] | |
493 | [:[' | |
494 | I think that the part of std::set theory is very clear. | |
495 | To me, it turns out to me somewhat strange to consider the rank of a map | |
496 | (values X) like a std::set, but of course the formulation is consistent. | |
497 | ]] | |
498 | ||
499 | [*Matias] | |
500 | [:[' | |
501 | I like it very much, it can be a little odd at first, but | |
502 | now that I have get used to it, it is very easy to express in the code my | |
503 | contrains on the data, and I believe that if somebody reads the code and | |
504 | sees the bimap instantiation he is not going to have problems understanding | |
505 | it. Perhaps it is easier to understand it if we use your notation: | |
506 | ordered_nonunique, unordered_unique, but this goes against our STL facade. | |
507 | In my opinion the user that comes from STL must have to learn as less as possible. | |
508 | ]] | |
509 | ||
510 | [*Joaquin] | |
511 | [:[' | |
512 | Considering a relation like a `struct {left, right}` | |
513 | is clean and clear. If I understand it well, one relation has views of type | |
514 | `pair{first, second}`, is this correct? | |
515 | ]] | |
516 | ||
517 | [*Matias] | |
518 | [:[' | |
519 | Yes, I believe that the left/right notation to express symmetry | |
520 | is great. I believe that to people is going to love it. | |
521 | ]] | |
522 | ||
523 | [*Joaquin] | |
524 | [:[' | |
525 | OK, perfect. I likes this very much: | |
526 | ]] | |
527 | [:['- bm.left is compatible with std::map<A,B>]] | |
528 | [:['- bm.right is compatible with std::map<B,A>]] | |
529 | [:['- bm is compatible with std::set<relation<A,B>>]] | |
530 | [:[' | |
531 | It is elegant and symmetric. I feel good vibrations here. | |
532 | ]] | |
533 | ||
534 | [*Matias] | |
535 | [:[' | |
536 | Great! | |
537 | ]] | |
538 | ||
539 | [*Joaquin] | |
540 | [:[' | |
541 | Moving on, the support for N-1, N-N, and hashed index is very easy | |
542 | to grasp, and it fits well in framework. | |
543 | However I do not finish to understand very well the "set<relation> constraints" section. | |
544 | Will you came up with some examples of which is the meaning of the different | |
545 | cases that you enumerate? | |
546 | ]] | |
547 | ||
548 | [*Matias - ] | |
549 | [:[' | |
550 | Yes, I mean: | |
551 | ]] | |
552 | [:['- based on the left]] | |
553 | [:['- based on the right]] | |
554 | [:[' | |
555 | The bimap core must be based on some index of multi index. If the index | |
556 | of the left is of the type hash, then in fact the main view is going | |
557 | to be an unordered_set< relation<A,B> >. Perhaps this is not what the user | |
558 | prefers and he wants to base its main view on the right index. | |
559 | ]] | |
560 | [:['- set_of_relation ]] | |
561 | [:['- multiset_of_relation ]] | |
562 | [:['- unordered_set_of_relation ]] | |
563 | [:['- unordered_multiset_of_relation ]] | |
564 | [:[' | |
565 | However, if both of them are hash indexes, the user may want the main view | |
566 | to be ordered. As we have a B.MI core this is very easy to support, we just have | |
567 | to add another index to it. | |
568 | ]] | |
569 | ||
570 | [*Joaquin] | |
571 | [:[' | |
572 | I understand it now. OK, I do not know if we have to include this | |
573 | in the first version, is going to be a functionality avalanche! | |
574 | ]] | |
575 | ||
576 | [*Matias] | |
577 | [:[' | |
578 | The user is not affected by the addition of this functionality, | |
579 | because by default it will be based on the left index that is a very natural | |
580 | behaviour. I do not think that this is functionality bloat, but I agree with | |
581 | you that it is a functionality avalanche. | |
582 | ]] | |
583 | ||
584 | [*Joaquin] | |
585 | [:[' | |
586 | There are restrictions between the left and right set types | |
587 | and the possible main view set types. For example if some of the index is | |
588 | of unique type, then the main view cannot be of type multiset_of_relation. | |
589 | To the inverse one, if the main view is of type set_of_relation the left and | |
590 | the right index cannot be of type multi_set. All this subject of the unicity | |
591 | constrictions and the resulting interactions between indexes is one of the subtle | |
592 | subjects of B.MI. | |
593 | ]] | |
594 | ||
595 | [*Matias] | |
596 | [:[' | |
597 | This can be checked at compile time and informed as an error | |
598 | in compile time. | |
599 | ]] | |
600 | ||
601 | [*Joaquin] | |
602 | [:[' | |
603 | It can be interesting. | |
604 | ]] | |
605 | ||
606 | [^- And right when everything seems to be perfect... - ] | |
607 | ||
608 | [*Joaquin] | |
609 | [:[' | |
610 | I have some worse news with respect to mutant, it is very a | |
611 | well designed and manageable class, unfortunately, C++ does not guarantee | |
612 | layout-compatibility almost in any case. For example, the C++ standard does | |
613 | not guarantee that the classes `struct{T1 a; T2 b;}` and `struct{T1 b; T2 a;}` | |
614 | are layout-compatible, and therefore the trick of reinterpret_cast is an | |
615 | undefined behavior. I am with you in which that in the 100% of the cases | |
616 | this scheme will really work, but the standard is the standard. If you can | |
617 | look the layout-compatibility subject in it (http://www.kuzbass.ru/docs/isocpp/). | |
618 | As you see, sometimes the standard is cruel. Although mutant seems a lost case, | |
619 | please do not hurry to eliminate it. We will see what can be done for it. | |
620 | ]] | |
621 | ||
622 | [*Matias] | |
623 | [:[' | |
624 | I read the standard, and you were right about it. Mutant was an implementation | |
625 | detail. It is a pity because I am sure that it will work perfect in any compiler. | |
626 | Perhaps the standard becomes more strict some day and mutant returns to life... | |
627 | We can then try a wrapper around a relation<A,B> that have two references named | |
628 | first and second that bind to A and B, or B and A. | |
629 | ]] | |
630 | `` | |
631 | relation<TA,TB> r; | |
632 | const_reference_pair<A,B> pba(r); | |
633 | const_reference_pair<B,A> pbb(r); | |
634 | `` | |
635 | [:[' | |
636 | It is not difficult to code the relation class in this way but two references | |
637 | are initialized with every access and the use of `pba.first` will be slower | |
638 | than `r.left` in most compilers. It is very difficult to optimize this kind of | |
639 | references. | |
640 | ]] | |
641 | ||
642 | [*Joaquin] | |
643 | [:[' | |
644 | This workaround is not possible, due to technical problems with | |
645 | the expected behavior of the iterators. If the iterators of bm.left are of | |
646 | bidirectional type, then standard stated that it have to return an object of type | |
647 | const value_type& when dereferenced. You will have to return a const_reference_pair | |
648 | created in the flight, making it impossible to return a reference. | |
649 | ]] | |
650 | ||
651 | [*Matias] | |
652 | [:[' | |
653 | I understand... I have workaround for that also but surely | |
654 | the standard will attack me again! We must manage to create the class relation | |
655 | that responds as we want, the rest of the code will flow from this point. | |
656 | This clear separation between the relation class and the rest of the library, | |
657 | is going to help to us to separate the problems and to attack them better. | |
658 | ]] | |
659 | ||
660 | [*Joaquin] | |
661 | [:[' | |
662 | What workaround? It already pricks my curiosity,I have dedicated | |
663 | a long time to the subject and I do not find any solution except that we | |
664 | allow the relation class to occupy more memory. | |
665 | ]] | |
666 | ||
667 | [*Matias] | |
668 | [:[' | |
669 | We must achieve that the relation<A,B> size equals the pair<A,B> size | |
670 | if we want this library to be really useful. I was going to write my workaround and | |
671 | I realized that It does not work. Look at this: | |
672 | http://www.boost.org/libs/iterator/doc/new-iter-concepts.html | |
673 | Basically the problem that we are dealing is solved if we based our iterators on | |
674 | this proposal. The present standard forces that the bidirectional iterators also | |
675 | are of the type input and output. Using the new concepts there is no inconvenient | |
676 | in making our iterators "Readable Writable Swappable Bidirectional Traversal". | |
677 | Therefore the const_reference_pair returns to be valid. | |
678 | ]] | |
679 | ||
680 | [*Joaquin] | |
681 | [:[' | |
682 | It is correct in the sense that you simply say that | |
683 | your iterators are less powerful than those of the std::map. It is | |
684 | not that it is wrong, simply that instead of fixing the problem, you | |
685 | confess it. | |
686 | ]] | |
687 | ||
688 | [*Matias] | |
689 | [:[' | |
690 | OK, but in our particular case; What are the benefits | |
691 | of offering a LValue iterator against a Read Write iterator? | |
692 | It does not seem to me that it is less powerful in this case. | |
693 | ]] | |
694 | ||
695 | [*Joaquin] | |
696 | [:[' | |
697 | The main problem with a ReadWrite is that the following thing: | |
698 | `value_type * p=&(*it);` | |
699 | fails or stores a transitory direction in p. Is this important in the real life? | |
700 | I do not know. How frequently you store the direction of the elements of a map? | |
701 | Perhaps it is not very frequent, since the logical thing is to store the | |
702 | iterators instead of the directions of the elements. | |
703 | Let us review our options: | |
704 | ]] | |
705 | [:[' | |
706 | 1. We used mutant knowing that is not standard, but of course it is | |
707 | supported in the 100% of the cases. | |
708 | ]] | |
709 | [:[' | |
710 | 2. We used const_reference_pair and we declared the iterators not LValue. | |
711 | ]] | |
712 | [:[' | |
713 | 3. We found some trick that still we do not know. I have thus been playing | |
714 | with unions and things, without much luck. | |
715 | ]] | |
716 | [:[' | |
717 | 4. We leverage the restriction that views have to support the first, second | |
718 | notation. If we made this decision, there are several possibilities: | |
719 | ]] | |
720 | [:[' | |
721 | ''' '''a. The left map has standard semantics first/second while the right map | |
722 | has the inverse semantics. | |
723 | ]] | |
724 | [:[' | |
725 | ''' '''b. Instead of first and second we provide first() and second(), with | |
726 | which the problem is trivial. | |
727 | ]] | |
728 | [:[' | |
729 | ''' '''c. The map view do not support first/second but left/right as the | |
730 | father relation | |
731 | ]] | |
732 | [:[' | |
733 | 5. We solve the problem using more memory than sizeof(pair<A,B>). | |
734 | ]] | |
735 | [:[' | |
736 | In any case, I would say that the only really unacceptable option is the last one. | |
737 | ]] | |
738 | ||
739 | [*Matias] | |
740 | [:[' | |
741 | Lets see. | |
742 | ]] | |
743 | [:[' | |
744 | 1. I want the "standard compliant" label in the library. | |
745 | ]] | |
746 | [:[' | |
747 | 2. This is the natural choice, but knowing that there is another option | |
748 | that always works and it is more efficient is awful. | |
749 | ]] | |
750 | [:[' | |
751 | 3. I have also tried to play with unions, the problem is that the union members | |
752 | must be POD types. | |
753 | ]] | |
754 | [:[' | |
755 | 4. This option implies a big lost to the library. | |
756 | ]] | |
757 | [:[' | |
758 | 5. Totally agree. | |
759 | ]] | |
760 | [:[' | |
761 | I want to add another option to this list. Using metaprogramming, | |
762 | the relation class checks if the compiler supports the mutant idiom. | |
763 | If it supports it then it uses it and obtains zero overhead | |
764 | plus LValue iterators, but if it do not supports it then uses | |
765 | const_reference_pair and obtains minimum overhead with ReadWrite iterators. | |
766 | This might be controversial but the advantages that mutant offers are very big | |
767 | and the truth is that I do not believe that in any actual compiler this idiom is | |
768 | not supported. This scheme would adjust perfectly to the present standard | |
769 | since we are not supposing anything. The only drawback here is that although | |
770 | the mutant approach allows to make LValue iterators we have to degrade they | |
771 | to Read Write in both cases, because we want that the same code can be | |
772 | compiled in any standard compliant compiler. | |
773 | ]] | |
774 | ||
775 | ||
776 | [^- Hopefully we find our way out of the problem -] | |
777 | ||
778 | [*Joaquin] | |
779 | [:[' | |
780 | Changing the subject, I believe that the general concept of hooking data | |
781 | is good, but I do not like the way you implement it. It has to be easy | |
782 | to migrate to B.MI to anticipate the case in that Boost.Bimap becomes insufficient. | |
783 | It is more natural for a B.MI user that the data is accessed without the indirection | |
784 | of `.data`. I do not know how this can be articulated in your framework. | |
785 | ]] | |
786 | ||
787 | [*Matias] | |
788 | [:[' | |
789 | I have a technical problem to implement the data_hook in this way. | |
790 | If the standard would let us use the mutant idiom directly, I can implement it | |
791 | using multiple inheritance. But as we must use const_reference_pair too, It becomes | |
792 | impossible for me to support it. We have three options here: | |
793 | ]] | |
794 | [:[' | |
795 | 1) relation { left, right, data } and pair_view { first, second, data } | |
796 | ]] | |
797 | [:[' | |
798 | - This is more intuitive within the bimap framework, since it does not | |
799 | mix the data with the index, as a table in a data base does, but gives more importance to | |
800 | the index. | |
801 | ]] | |
802 | [:[' | |
803 | - It is not necessary that the user puts the mutable keyword in each member of | |
804 | the data class. | |
805 | ]] | |
806 | [:[' | |
807 | - This moves away just a little bit from B.MI because the model | |
808 | of it is similar to a table, but it continues to exist a clear path of migration. | |
809 | ]] | |
810 | [:[' | |
811 | 2) relation { left,right, d1,d2... dn } and pair_view { first, second, data } | |
812 | ]] | |
813 | [:[' | |
814 | - The path to B.MI is the one you have proposed. | |
815 | ]] | |
816 | [:[' | |
817 | - It is very asymmetric. It is necessary to explain that the views are | |
818 | handled different that the relation. | |
819 | ]] | |
820 | [:[' | |
821 | - The user must place the mutable keyboards in the data class. | |
822 | ]] | |
823 | [:[' | |
824 | 3) Only relation { left,right, d1,d2... dn } | |
825 | ]] | |
826 | [:[' | |
827 | - Simple migration path to B.MI. | |
828 | ]] | |
829 | [:[' | |
830 | - You are not able to access the hooked data from the views. | |
831 | ]] | |
832 | [:[' | |
833 | My vote goes to the first proposal. | |
834 | ]] | |
835 | ||
836 | ||
837 | [*Joaquin] | |
838 | [:[' | |
839 | Yes, the first option is the one that less surprises hold to the user. | |
840 | I also vote for 1. | |
841 | ]] | |
842 | ||
843 | [^- The third week was over -] | |
844 | ||
845 | [*Matias] | |
846 | [:[' | |
847 | There is still one problem that I have to solve. I need to | |
848 | know if it is necessary to create a map_view associated to nothing. If | |
849 | it is necessary there are two options: that it behaves as an empty container or | |
850 | that it throws an exception or assert when trying to use it. If it is not necessary, | |
851 | the map_view is going to keep a reference instead of a pointer. | |
852 | To me, the map_view always must be viewing something. In the case of the iterators | |
853 | being able to create them empty, makes them easy to use in contexts that require | |
854 | constructors by default, like being the value_type of a container, but I do not | |
855 | believe that this is the case of map_view. | |
856 | ]] | |
857 | ||
858 | [*Joaquin] | |
859 | [:[' | |
860 | How would an empty map_view be useful? My intuition is like yours, | |
861 | map_view would have to be always associate to something. If we wished to obtain | |
862 | the semantics "is associated or not" we can use a pointer to a map_view. | |
863 | ]] | |
864 | ||
865 | [*Matias] | |
866 | [:[' | |
867 | OK, then you agree to that map_views stores a reference instead | |
868 | of a pointer? | |
869 | ]] | |
870 | ||
871 | [*Joaquin] | |
872 | [:[' | |
873 | It depends on the semantics you want to give to map_views, and in | |
874 | concrete to the copy of map_views. | |
875 | ]] | |
876 | `` | |
877 | map_view x=...; | |
878 | map_view y=...; | |
879 | x=y; | |
880 | `` | |
881 | [:[' | |
882 | What is supposed to do this last line? | |
883 | ]] | |
884 | [:[' | |
885 | 1. Rebinding of x, that is to say, x points at the same container that y. | |
886 | ]] | |
887 | [:[' | |
888 | 2. Copy of the underlying container. | |
889 | ]] | |
890 | [:[' | |
891 | If you want to implement 1, you cannot use references internally. | |
892 | If you want to implement 2, it is almost the same to use a reference or a pointer. | |
893 | ]] | |
894 | ||
895 | [*Matias] | |
896 | [:[' | |
897 | If I want that they behave exactly as std::maps then I must go for 2. | |
898 | But if I think they as "views" of something, I like 1. The question is complicated. | |
899 | I add another option: | |
900 | ]] | |
901 | [:[' | |
902 | 3. Error: operator= is declare as private in boost::bimap::map_view std_container | |
903 | ]] | |
904 | [:[' | |
905 | Also What happens with `std_container = view;`? and with `view = std_container;`? | |
906 | ]] | |
907 | ||
908 | [endsect] | |
909 | ||
910 | [endsect] | |
911 | ||
912 | ||
913 | ||
914 |