| [/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 Rationale] |
| |
| This section assumes that you have read all other sections, the most of |
| important of which being ['tutorial], ['std::set theory] and the ['reference], |
| and that you have tested the library. A lot of effort was invested in |
| making the interface as intuitive and clean as possible. If you |
| understand, and hopefully like, the interface of this library, it will |
| be a lot easier to read this rationale. The following section is little |
| more than a rationale. This library was coded in the context of the |
| Google SoC 2006 and the student and mentor were in different continents. |
| A great deal of email flowed between Joaquin and Matias. The juiciest |
| parts of the conversations where extracted and rearranged here. |
| |
| [note To browse the code, you can use the [@doxydoc/index.html ['Bimap Complete Reference]], a |
| doxygen-powered document targeted at developers. |
| ] |
| |
| [section General Design] |
| |
| The initial explanation includes few features. This section aims to |
| describe the general design of the library and excludes details of those |
| features that are of lesser importance; these features will be |
| introduced later. |
| |
| The design of the library is divided into two parts. The first is the |
| construction of a [^relation] class. This will be the object stored and |
| managed by the [^multi_index_container] core. The idea is to make this |
| class as easy as possible to use, while making it efficient in terms of |
| memory and access time. This is a cornerstone in the design of |
| [*Boost.Bimap] and, as you will see in this rationale, the rest of the |
| design follows easily. |
| |
| The following interface is necessary for the [^relation] class: |
| |
| typedef -unspecified- TA; typedef -unspecified- TB; |
| |
| TA a, ai; TB b, bi; |
| |
| typedef relation< TA, TB > rel; |
| STATIC_ASSERT( is_same< rel::left_type , TA >::value ); |
| STATIC_ASSERT( is_same< rel::right_type, TB >::value ); |
| |
| rel r(ai,bi); |
| assert( r.left == ai && r.right == bi ); |
| |
| r.left = a; r.right = b; |
| assert( r.left == a && r.right == b ); |
| |
| typedef pair_type_by< member_at::left , rel >::type pba_type; |
| STATIC_ASSERT( is_same< pba_type::first_type , TA >::value ); |
| STATIC_ASSERT( is_same< pba_type::second_type, TB >::value ); |
| |
| typedef pair_type_by< member_at::right, rel >::type pbb_type; |
| STATIC_ASSERT( is_same< pbb_type::first_type , TB >::value ); |
| STATIC_ASSERT( is_same< pbb_type::second_type, TA >::value ); |
| |
| pba_type pba = pair_by< member_at::left >(r); |
| assert( pba.first == r.left && pba.second == r.right ); |
| |
| pbb_type pbb = pair_by< member_at::right >(r); |
| assert( pbb.first == r.right && pbb.second == r.left ); |
| |
| |
| __RELATION__ |
| |
| Although this seems straightforward, as will be seen later, it is the |
| most difficult code hack of the library. It is indeed very easy if we |
| relax some of the efficiency constraints. For example, it is trivial if |
| we allow a relation to have greater size than the the sum of those of |
| its components. It is equally simple if access speed is not important. |
| One of the first decisions made about [*Boost.Bimap] was, however, that, in |
| order to be useful, it had to achieve zero overhead over the wrapped |
| [*Boost.MultiIndex] container. Finally, there is another constraint that |
| can be relaxed: conformance to C++ standards, but this is quite |
| unacceptable. Let us now suppose that we have coded this class, and it |
| conforms to what was required. |
| |
| The second part is based on this [^relation] class. We can now view the |
| data in any of three ways: `pair<A,B>`, `relation<A,B>` and `pair<B,A>`. |
| Suppose that our bimap supports only one-to-one relations. (Other |
| relation types are considered additional features in this design.) |
| The proposed interface is very simple, and it is based heavily on the |
| concepts of the STL. Given a `bimap<A,B> bm`: |
| |
| # `bm.left` is signature-compatible with a `std::map<A,B>` |
| # `bm.right` is signature-compatible with a `std::map<B,A>` |
| # `bm` is signature-compatible with a `std::set<relation<A,B> >` |
| |
| __SIMPLE_BIMAP__ |
| |
| This interface is easily learned by users who have a STL background, as |
| well as being simple and powerful. This is the general design. |
| |
| [heading Relation Implementation] |
| |
| This section explains the details of the actual [^relation] class implementation. |
| |
| The first thing that we can imagine is the use of an [^union]. Regrettably, |
| the current C++ standard only allows unions of POD types. For the views, |
| we can try a wrapper around a `relation<A,B>` that has two references |
| named first and second that bind to `A` and `B`, or to `B` and `A`. |
| |
| relation<TA,TB> r; |
| |
| const_reference_pair<A,B> pba(r); |
| const_reference_pair<B,A> pbb(r); |
| |
| It is not difficult to code the relation class using this, but two |
| references are initialized at every access and using of `pba.first` will |
| be slower in most compilers than using `r.left` directly . There is |
| another hidden drawback of using this scheme: it is not |
| iterator-friendly, since the map views iterators must be degraded to |
| ['Read Write] instead of ['LValue]. This will be explained later. |
| |
| At first, this seems to be the best we can do with the current C++ |
| standard. However there is a solution to this problem that does not |
| conform very well to C++ standards but does achieve zero overhead in |
| terms of access time and memory, and additionally allows the view |
| iterators to be upgraded to ['LValue] again. |
| |
| In order to use this, the compiler must conform to a |
| layout-compatibility clause that is not currently in the standard but is |
| very natural. The additional clause imposes that if we have two classes: |
| |
| struct class_a_b |
| { |
| Type1 name_a; |
| Type2 name_b; |
| }; |
| |
| struct class_b_a |
| { |
| Type1 name_b; |
| Type2 name_a; |
| }; |
| |
| then the storage layout of [^class_a_b] is equal to the storage layout of |
| [^class_b_a]. If you are surprised to learn that this does not hold in a |
| standards-compliant C++ compiler, welcome to the club. It is the natural |
| way to implement it from the point of view of the compiler's vendor and |
| is very useful for the developer. Maybe it will be included in the |
| standard some day. Every current compiler conforms to this. |
| |
| If we are able to count on this, then we can implement an idiom called |
| [^mutant]. The idea is to provide a secure wrapper around [^reinterpret_cast]. |
| A class can declare that it can be viewed using different view classes |
| that are storage-compatible with it. Then we use the free function |
| [^mutate<view>(mutant)] to get the view. The `mutate` function checks at |
| compile time that the requested view is declared in the mutant views list. |
| We implement a class name `structured_pair` that is signature-compatible |
| with a `std::pair`, while the storage layout is configured with a third |
| template parameter. Two instances of this template class will provide |
| the views of the relation. |
| |
| The thing is that if we want to be standards-compliant, we cannot use |
| this approach. It is very annoying not to be able to use something that |
| we know will work with every compiler and that is far better than |
| alternatives. So -- and this is an important decision -- we have to find |
| a way to use it and still make the library standards-compliant. |
| |
| The idea is very simple. We code both approaches: the |
| const_reference_pair-based and the mutant-based, and use the mutant |
| approach if the compiler is compliant with our new layout-compatible |
| clause. If the compiler really messes things up, we degrade the |
| performance of the bimap a little. The only drawback here is that, while |
| the mutant approach allows to make ['LValue] iterators, we have to degrade |
| them to ['Read Write] in both cases, because we require that the same code |
| be compilable by any standards-compliant compiler. |
| |
| [note |
| Testing this approach in all the supported compilers indicated that the |
| mutant idiom was always supported. The strictly compliant version was |
| removed from the code because it was never used. |
| ] |
| |
| |
| [heading Bimap Implementation] |
| |
| The core of bimap will be obviously a `multi_index_container`. The basic |
| idea to tackle the implementation of the bimap class is to use |
| [^iterator_adaptor] to convert the iterators from Boost.MultiIndex to the |
| `std::map` and `std::set` behaviour. The `map_view` and the `set_view` can be |
| implemented directly using this new transformed iterators and a wrapper |
| around each index of the core container. However, there is a hidden |
| idiom here, that, once coded, will be very useful for other parts of |
| this library and for Boost.MRU library. Following the ideas from |
| `iterator_adaptor`, Boost.Bimap views are implemented using a |
| [^container_adaptor]. There are several template classes (for example |
| `map_adaptor` and `set_adaptor`) that take a `std::map` signature-conformant |
| class and new iterators, and adapt the container so it now uses this |
| iterators instead of the originals. For example, if you have a |
| `std::set<int*>`, you can build other container that behaves exactly as a |
| `std::set<int>` using `set_adaptor` and [^iterator_adaptor]. The combined use |
| of this two tools is very powerful. A [^container_adaptor] can take classes |
| that do not fulfil all the requirements of the adapted container. The |
| new container must define these missing functions. |
| |
| [endsect] |
| |
| [section Additional Features] |
| |
| [heading N-1, N-N, hashed maps] |
| |
| This is a very interesting point of the design. The framework introduced |
| in ['std::set theory] permits the management of the different constraints |
| with a very simple and conceptual approach. It is easy both to remember |
| and to learn. The idea here is to allow the user to specify the collection type |
| of each key directly. In order to implement this feature, we have to |
| solve two problems: |
| |
| * The index types of the `multi_index_container` core now depends on |
| the collection type used for each key. |
| * The map views now change their semantics according to the collection type |
| chosen. |
| |
| Boost.Bimap relies heavily on Boost.MPL to implement all of the |
| metaprogramming necessary to make this framework work. By default, if |
| the user does not specify the kind of the set, a `std::set` type is used. |
| |
| __BIMAP_STRUCTURES__ |
| |
| [heading Collection type of relation constraints] |
| |
| The constraints of the bimap set view are another very important |
| feature. In general, Boost.Bimap users will base the set view type on |
| one of the two collection types of their keys. It may be useful however to give |
| this set other constraints or simply to order it differently. By |
| default, Boost.Bimap bases the collection type of relations on the left collection |
| type, but the user may choose between: |
| |
| * left_based |
| * right_based |
| * set_of_relation<> |
| * multiset_of_relation<> |
| * unordered_set_of_relation<> |
| * unordered_multiset_of_relation<> |
| * list_of |
| * vector_of |
| |
| In the first two cases, there are only two indices in the |
| `multi_index_core`, and for this reason, these are the preferred options. |
| The implementation uses further metaprogramming to define a new index if |
| necessary. |
| |
| [/ |
| [heading Hooking Data] |
| |
| This is one of the things that makes Boost.Bimap very appealing in |
| tackling a problem. In general, programmers use maps to access |
| information quickly. Boost.Bimap allows the user to hook data inside the |
| bimap so that it is not necessary to maintain another map. The |
| implementation is based heavily on metaprogramming. |
| ] |
| |
| [heading Tagged] |
| |
| The idea of using tags instead of the [^member_at::side] idiom is very |
| appealing since code that uses it is more readable. The only cost is |
| compile time. ['boost/bimap/tagged] is the implementation of a non-invasive |
| tagged idiom. The [^relation] class is built in such a way that even when |
| the user uses tags, the [^member_at::side] idiom continues to work. This is |
| good since an user can start tagging even before completing the coding |
| of the algorithm, and the untagged code continues to work. The |
| development becomes a little more complicated when user-defined tags are |
| included, but there are many handy metafunctions defined in the [^tagged] |
| idiom that help to keep things simple enough. |
| |
| __TAGGED__ |
| |
| [endsect] |
| |
| [section Code] |
| |
| You can browse the code using the [@doxydoc/index.html [*Boost.Bimap doxygen docs]]. |
| |
| The code follows the [@http://www.boost.org/more/lib_guide.htm Boost Library Requirement and Guidelines] as |
| closely as possible. |
| |
| [table folders in boost/bimap |
| [[name][what is inside?]] |
| [[/ ][user level header files ]] |
| [[tagged/ ][tagged idiom ]] |
| [[relation/ ][the bimap data ]] |
| [[container_adaptor/ ][easy way of adapting containers ]] |
| [[views/ ][bimap views ]] |
| [[property_map/ ][support for property map concept ]] |
| ] |
| |
| [table folders in each folder |
| [[name][what is inside?]] |
| [[ ][class definitions]] |
| [[support/ ][optional metafunctions and free functions]] |
| [[detail/ ][things not intended for the user's eyes]] |
| ] |
| |
| [endsect] |
| |
| [section The student and the mentor] |
| |
| [tip It is a good idea to read the original |
| [@http://h1.ripway.com/mcape/boost/libs/misc/ Boost.Misc SoC proposal] first.] |
| |
| [:[^- The discussion starts with Joaquin trying to strip out the "misc" name out of the library -]] |
| |
| __JOAQUIN_PHOTO__ |
| |
| [*Joaquin] |
| [:[' |
| Thinking about it, the unifying principle of MISC containers is perhaps |
| misleading: certainly all miscs use multi-indexing internally, but this does |
| not reflect much in the external interface (as it should be, OTOH). So, from |
| the user's point of view, miscs are entirely heterogeneous beasts. Moreover, |
| there isn't in your proposal any kind of global facility common to all miscs. |
| What about dropping the misc principle and working on each container as a |
| separate library, then? You'd have boost::bimap, boost::mru, etc, and no common |
| intro to them. This also opens up the possibility to add other containers to |
| the suite which aren't based on B.MI. What's your stance on this? Do you see a |
| value in keeping miscs conceptually together? |
| ]] |
| |
| __MATIAS_PHOTO__ |
| |
| [*Matias] |
| [:[' |
| As the original proposal states only two containers (bimap and mru set) both |
| based in B.MI, it was straight forward to group them together. When I was |
| writing the SoC proposal I experienced a similar feeling when the two families |
| begin to grow. As you say, the only common denominator is their internal |
| implementation. I thought a bit about a more general framework to join this two |
| families (and other internally related ones) and finally came up with an idea: |
| Boost.MultiIndex! So I think that it is not a good idea to try to unify the two |
| families and I voted in favor of get rid of the misc part of boost::misc::bimap |
| and boost::misc::mru. Anyway, for my SoC application it seems OK to put the |
| two families in the same project because although from the outside they are |
| completely unrelated, the work I will have to do in order to build the libraries |
| will be consistent and what I will learn coding the bimap family will be used |
| when I start to code the mru family. When the mru family is in place, I will |
| surely have learnt other things to improve the bimap group. |
| ]] |
| [:[' |
| On the other hand, I think it will be useful for the general user to |
| have at least some document linked in the B.MI documentation that |
| enumerates the most common cases of uses (a bimap and an mru set for |
| example) and points where to find clean implementation for this useful |
| containers. For now, a link to boost::bimap and other one to boost::mru |
| will suffice. If you think about the title of such a document, |
| you will probably come up with something like: Common Multi Index |
| Specialized Containers, and we are back to our misc proposal. |
| So, to order some ideas: |
| ]] |
| [:['- A new family of containers that can be accessed by both key will |
| be created. (boost::bimap)]] |
| [:['- A new family of time aware containers will see the light. |
| (boost::mru)]] |
| [:['- A page can be added to B.MI documentation, titled misc that links |
| this new libraries.]] |
| [:[' |
| This is a clearer framework for the user. They can use a mru container |
| without hearing about Boost.MultiIndex at all. |
| And B.MI users will get some of their common containers already |
| implemented with an STL friendly interface in other libraries. |
| And as you stated this is more extensible because opens the door to use |
| other libraries in bimap and mru families than just Boost.MultiIndex |
| without compromising the more general boost framework. |
| The word "misc" it is going to disappear from the code and |
| the documentation of bimap and mru. From now on the only use for it will be to |
| identify our SoC project. I am thinking in a name for the bimap library. |
| What about Boost.BidirectionalMap? Ideas? |
| ]] |
| |
| [*Joaquin] |
| [:[' |
| Yes, Boost.Bimap. In my opinion, bimap is a well known name |
| in the Boost and even in the C++ community. It sounds and is short. Why not to |
| vindicate yourself as the owner of this name? |
| ]] |
| |
| [^- Then after a week of work -] |
| |
| [*Matias] |
| [:[' |
| Now that Boost.Bimap is getting some shape, I see that as |
| you have told me, we must offer a "one_to_many_map" and a "multi_bimap" |
| as part of the library. The framework I am actually working allowed to |
| construct this kind of bidirectional maps and it is easy to understand from |
| the user side. |
| ]] |
| |
| [*Joaquin] |
| [:[' |
| OK, I am glad we agree on this point. |
| ]] |
| |
| [*Matias] |
| [:[' |
| With respect to the symmetry of the key access names, I have to |
| agree that there is not much a difference between the following ones: |
| ]] |
| [:['- to - from]] |
| [:['- to - b]] |
| [:['- 0 - 1]] |
| [:['- left - right]] |
| [:[' |
| In my opinion it is a matter of taste, but left/right sounds more symmetrical than |
| the others. |
| ]] |
| |
| [*Joaquin] |
| [:[' |
| I like very much the left/right notation, it is very simple to |
| remember and it is a lot more symmetrical than to/from. |
| ]] |
| |
| [*Matias] |
| [:[' |
| At first my idea was to obtain ease of use hiding the B.MI |
| core, making it more STL-intuitive. Nevertheless I have realized |
| that B.MI is a lot more coherent and easy to use that I had imagined. This |
| makes me think again in the problem. In the design that I am coding now, bimap |
| *is-a* multi_index_container specializes with a data type very comfortable |
| called bipair, that can be seen like any of the two maps that integrates it |
| using map views. This scheme has great benefits for users: |
| ]] |
| [:[' |
| - If the user already knows B.MI, he can take advantage of the tools that |
| it provides and that are not present in the STL containers. In addition, in some |
| cases the use to indices to see the data can be very useful. |
| ]] |
| [:[' |
| - If the user does not know anything about B.MI but have an STL framework, |
| the learning curve is reduced to understand the bimap instantiation and how a |
| is obtained the desired map view. |
| ]] |
| [:[' |
| Another very important benefit holds: All the algorithms done for |
| B.MI continues to work with Boost.Bimap and if B.MI continues growing, bimap |
| grow automatically. |
| ]] |
| |
| [*Joaquin] |
| [:[' |
| Umm... This is an interesting design decision, but |
| controversial in my opinion. Basically you decide to expose the |
| implementation of bimap; that has advantages, as you stated, but also |
| a nonsmall disadvantage: once *you have documented* the implementation, |
| it is not possible to change it anymore. It is a marriage with B.MI without |
| the chance of divorce. The other possibility, to hide the implementation and |
| to duplicate and document the provided functionality, explicitly or |
| implicitly due to the same characteristics of the implementation, is |
| of course heavier to maintain, but it gives a degree of freedom to change |
| the guts of your software if you need to. Do not take this like a frontal |
| objection, but I think that it is quite important design decision, not only |
| in the context of bimap but in general. |
| ]] |
| |
| [*Matias] |
| [:[' |
| You are quite right here. I think we have to choose the hardest |
| path and hide the B.MI core from the user. I am sending you the first draft of |
| bimap along with some documentation. |
| ]] |
| |
| [^- This completes the second week, the documentation was basically the first |
| section of this rationale -] |
| |
| [*Joaquin] |
| [:[' |
| I must confess that I am beginning to like what I see. |
| I am mathematical by vocation, and when I see symmetry in a formulation |
| I believe that it is in the right track. |
| ]] |
| |
| [*Matias] |
| [:[' |
| We are two mathematicians by vocation then. |
| ]] |
| |
| [*Joaquin] |
| [:[' |
| I think that the part of std::set theory is very clear. |
| To me, it turns out to me somewhat strange to consider the rank of a map |
| (values X) like a std::set, but of course the formulation is consistent. |
| ]] |
| |
| [*Matias] |
| [:[' |
| I like it very much, it can be a little odd at first, but |
| now that I have get used to it, it is very easy to express in the code my |
| contrains on the data, and I believe that if somebody reads the code and |
| sees the bimap instantiation he is not going to have problems understanding |
| it. Perhaps it is easier to understand it if we use your notation: |
| ordered_nonunique, unordered_unique, but this goes against our STL facade. |
| In my opinion the user that comes from STL must have to learn as less as possible. |
| ]] |
| |
| [*Joaquin] |
| [:[' |
| Considering a relation like a `struct {left, right}` |
| is clean and clear. If I understand it well, one relation has views of type |
| `pair{first, second}`, is this correct? |
| ]] |
| |
| [*Matias] |
| [:[' |
| Yes, I believe that the left/right notation to express symmetry |
| is great. I believe that to people is going to love it. |
| ]] |
| |
| [*Joaquin] |
| [:[' |
| OK, perfect. I likes this very much: |
| ]] |
| [:['- bm.left is compatible with std::map<A,B>]] |
| [:['- bm.right is compatible with std::map<B,A>]] |
| [:['- bm is compatible with std::set<relation<A,B>>]] |
| [:[' |
| It is elegant and symmetric. I feel good vibrations here. |
| ]] |
| |
| [*Matias] |
| [:[' |
| Great! |
| ]] |
| |
| [*Joaquin] |
| [:[' |
| Moving on, the support for N-1, N-N, and hashed index is very easy |
| to grasp, and it fits well in framework. |
| However I do not finish to understand very well the "set<relation> constraints" section. |
| Will you came up with some examples of which is the meaning of the different |
| cases that you enumerate? |
| ]] |
| |
| [*Matias - ] |
| [:[' |
| Yes, I mean: |
| ]] |
| [:['- based on the left]] |
| [:['- based on the right]] |
| [:[' |
| The bimap core must be based on some index of multi index. If the index |
| of the left is of the type hash, then in fact the main view is going |
| to be an unordered_set< relation<A,B> >. Perhaps this is not what the user |
| prefers and he wants to base its main view on the right index. |
| ]] |
| [:['- set_of_relation ]] |
| [:['- multiset_of_relation ]] |
| [:['- unordered_set_of_relation ]] |
| [:['- unordered_multiset_of_relation ]] |
| [:[' |
| However, if both of them are hash indexes, the user may want the main view |
| to be ordered. As we have a B.MI core this is very easy to support, we just have |
| to add another index to it. |
| ]] |
| |
| [*Joaquin] |
| [:[' |
| I understand it now. OK, I do not know if we have to include this |
| in the first version, is going to be a functionality avalanche! |
| ]] |
| |
| [*Matias] |
| [:[' |
| The user is not affected by the addition of this functionality, |
| because by default it will be based on the left index that is a very natural |
| behaviour. I do not think that this is functionality bloat, but I agree with |
| you that it is a functionality avalanche. |
| ]] |
| |
| [*Joaquin] |
| [:[' |
| There are restrictions between the left and right set types |
| and the possible main view set types. For example if some of the index is |
| of unique type, then the main view cannot be of type multiset_of_relation. |
| To the inverse one, if the main view is of type set_of_relation the left and |
| the right index cannot be of type multi_set. All this subject of the unicity |
| constrictions and the resulting interactions between indexes is one of the subtle |
| subjects of B.MI. |
| ]] |
| |
| [*Matias] |
| [:[' |
| This can be checked at compile time and informed as an error |
| in compile time. |
| ]] |
| |
| [*Joaquin] |
| [:[' |
| It can be interesting. |
| ]] |
| |
| [^- And right when everything seems to be perfect... - ] |
| |
| [*Joaquin] |
| [:[' |
| I have some worse news with respect to mutant, it is very a |
| well designed and manageable class, unfortunately, C++ does not guarantee |
| layout-compatibility almost in any case. For example, the C++ standard does |
| not guarantee that the classes `struct{T1 a; T2 b;}` and `struct{T1 b; T2 a;}` |
| are layout-compatible, and therefore the trick of reinterpret_cast is an |
| undefined behavior. I am with you in which that in the 100% of the cases |
| this scheme will really work, but the standard is the standard. If you can |
| look the layout-compatibility subject in it (http://www.kuzbass.ru/docs/isocpp/). |
| As you see, sometimes the standard is cruel. Although mutant seems a lost case, |
| please do not hurry to eliminate it. We will see what can be done for it. |
| ]] |
| |
| [*Matias] |
| [:[' |
| I read the standard, and you were right about it. Mutant was an implementation |
| detail. It is a pity because I am sure that it will work perfect in any compiler. |
| Perhaps the standard becomes more strict some day and mutant returns to life... |
| We can then try a wrapper around a relation<A,B> that have two references named |
| first and second that bind to A and B, or B and A. |
| ]] |
| `` |
| relation<TA,TB> r; |
| const_reference_pair<A,B> pba(r); |
| const_reference_pair<B,A> pbb(r); |
| `` |
| [:[' |
| It is not difficult to code the relation class in this way but two references |
| are initialized with every access and the use of `pba.first` will be slower |
| than `r.left` in most compilers. It is very difficult to optimize this kind of |
| references. |
| ]] |
| |
| [*Joaquin] |
| [:[' |
| This workaround is not possible, due to technical problems with |
| the expected behavior of the iterators. If the iterators of bm.left are of |
| bidirectional type, then standard stated that it have to return an object of type |
| const value_type& when dereferenced. You will have to return a const_reference_pair |
| created in the flight, making it impossible to return a reference. |
| ]] |
| |
| [*Matias] |
| [:[' |
| I understand... I have workaround for that also but surely |
| the standard will attack me again! We must manage to create the class relation |
| that responds as we want, the rest of the code will flow from this point. |
| This clear separation between the relation class and the rest of the library, |
| is going to help to us to separate the problems and to attack them better. |
| ]] |
| |
| [*Joaquin] |
| [:[' |
| What workaround? It already pricks my curiosity,I have dedicated |
| a long time to the subject and I do not find any solution except that we |
| allow the relation class to occupy more memory. |
| ]] |
| |
| [*Matias] |
| [:[' |
| We must achieve that the relation<A,B> size equals the pair<A,B> size |
| if we want this library to be really useful. I was going to write my workaround and |
| I realized that It does not work. Look at this: |
| http://www.boost.org/libs/iterator/doc/new-iter-concepts.html |
| Basically the problem that we are dealing is solved if we based our iterators on |
| this proposal. The present standard forces that the bidirectional iterators also |
| are of the type input and output. Using the new concepts there is no inconvenient |
| in making our iterators "Readable Writable Swappable Bidirectional Traversal". |
| Therefore the const_reference_pair returns to be valid. |
| ]] |
| |
| [*Joaquin] |
| [:[' |
| It is correct in the sense that you simply say that |
| your iterators are less powerful than those of the std::map. It is |
| not that it is wrong, simply that instead of fixing the problem, you |
| confess it. |
| ]] |
| |
| [*Matias] |
| [:[' |
| OK, but in our particular case; What are the benefits |
| of offering a LValue iterator against a Read Write iterator? |
| It does not seem to me that it is less powerful in this case. |
| ]] |
| |
| [*Joaquin] |
| [:[' |
| The main problem with a ReadWrite is that the following thing: |
| `value_type * p=&(*it);` |
| fails or stores a transitory direction in p. Is this important in the real life? |
| I do not know. How frequently you store the direction of the elements of a map? |
| Perhaps it is not very frequent, since the logical thing is to store the |
| iterators instead of the directions of the elements. |
| Let us review our options: |
| ]] |
| [:[' |
| 1. We used mutant knowing that is not standard, but of course it is |
| supported in the 100% of the cases. |
| ]] |
| [:[' |
| 2. We used const_reference_pair and we declared the iterators not LValue. |
| ]] |
| [:[' |
| 3. We found some trick that still we do not know. I have thus been playing |
| with unions and things, without much luck. |
| ]] |
| [:[' |
| 4. We leverage the restriction that views have to support the first, second |
| notation. If we made this decision, there are several possibilities: |
| ]] |
| [:[' |
| ''' '''a. The left map has standard semantics first/second while the right map |
| has the inverse semantics. |
| ]] |
| [:[' |
| ''' '''b. Instead of first and second we provide first() and second(), with |
| which the problem is trivial. |
| ]] |
| [:[' |
| ''' '''c. The map view do not support first/second but left/right as the |
| father relation |
| ]] |
| [:[' |
| 5. We solve the problem using more memory than sizeof(pair<A,B>). |
| ]] |
| [:[' |
| In any case, I would say that the only really unacceptable option is the last one. |
| ]] |
| |
| [*Matias] |
| [:[' |
| Lets see. |
| ]] |
| [:[' |
| 1. I want the "standard compliant" label in the library. |
| ]] |
| [:[' |
| 2. This is the natural choice, but knowing that there is another option |
| that always works and it is more efficient is awful. |
| ]] |
| [:[' |
| 3. I have also tried to play with unions, the problem is that the union members |
| must be POD types. |
| ]] |
| [:[' |
| 4. This option implies a big lost to the library. |
| ]] |
| [:[' |
| 5. Totally agree. |
| ]] |
| [:[' |
| I want to add another option to this list. Using metaprogramming, |
| the relation class checks if the compiler supports the mutant idiom. |
| If it supports it then it uses it and obtains zero overhead |
| plus LValue iterators, but if it do not supports it then uses |
| const_reference_pair and obtains minimum overhead with ReadWrite iterators. |
| This might be controversial but the advantages that mutant offers are very big |
| and the truth is that I do not believe that in any actual compiler this idiom is |
| not supported. This scheme would adjust perfectly to the present standard |
| since we are not supposing anything. The only drawback here is that although |
| the mutant approach allows to make LValue iterators we have to degrade they |
| to Read Write in both cases, because we want that the same code can be |
| compiled in any standard compliant compiler. |
| ]] |
| |
| |
| [^- Hopefully we find our way out of the problem -] |
| |
| [*Joaquin] |
| [:[' |
| Changing the subject, I believe that the general concept of hooking data |
| is good, but I do not like the way you implement it. It has to be easy |
| to migrate to B.MI to anticipate the case in that Boost.Bimap becomes insufficient. |
| It is more natural for a B.MI user that the data is accessed without the indirection |
| of `.data`. I do not know how this can be articulated in your framework. |
| ]] |
| |
| [*Matias] |
| [:[' |
| I have a technical problem to implement the data_hook in this way. |
| If the standard would let us use the mutant idiom directly, I can implement it |
| using multiple inheritance. But as we must use const_reference_pair too, It becomes |
| impossible for me to support it. We have three options here: |
| ]] |
| [:[' |
| 1) relation { left, right, data } and pair_view { first, second, data } |
| ]] |
| [:[' |
| - This is more intuitive within the bimap framework, since it does not |
| mix the data with the index, as a table in a data base does, but gives more importance to |
| the index. |
| ]] |
| [:[' |
| - It is not necessary that the user puts the mutable keyword in each member of |
| the data class. |
| ]] |
| [:[' |
| - This moves away just a little bit from B.MI because the model |
| of it is similar to a table, but it continues to exist a clear path of migration. |
| ]] |
| [:[' |
| 2) relation { left,right, d1,d2... dn } and pair_view { first, second, data } |
| ]] |
| [:[' |
| - The path to B.MI is the one you have proposed. |
| ]] |
| [:[' |
| - It is very asymmetric. It is necessary to explain that the views are |
| handled different that the relation. |
| ]] |
| [:[' |
| - The user must place the mutable keyboards in the data class. |
| ]] |
| [:[' |
| 3) Only relation { left,right, d1,d2... dn } |
| ]] |
| [:[' |
| - Simple migration path to B.MI. |
| ]] |
| [:[' |
| - You are not able to access the hooked data from the views. |
| ]] |
| [:[' |
| My vote goes to the first proposal. |
| ]] |
| |
| |
| [*Joaquin] |
| [:[' |
| Yes, the first option is the one that less surprises hold to the user. |
| I also vote for 1. |
| ]] |
| |
| [^- The third week was over -] |
| |
| [*Matias] |
| [:[' |
| There is still one problem that I have to solve. I need to |
| know if it is necessary to create a map_view associated to nothing. If |
| it is necessary there are two options: that it behaves as an empty container or |
| that it throws an exception or assert when trying to use it. If it is not necessary, |
| the map_view is going to keep a reference instead of a pointer. |
| To me, the map_view always must be viewing something. In the case of the iterators |
| being able to create them empty, makes them easy to use in contexts that require |
| constructors by default, like being the value_type of a container, but I do not |
| believe that this is the case of map_view. |
| ]] |
| |
| [*Joaquin] |
| [:[' |
| How would an empty map_view be useful? My intuition is like yours, |
| map_view would have to be always associate to something. If we wished to obtain |
| the semantics "is associated or not" we can use a pointer to a map_view. |
| ]] |
| |
| [*Matias] |
| [:[' |
| OK, then you agree to that map_views stores a reference instead |
| of a pointer? |
| ]] |
| |
| [*Joaquin] |
| [:[' |
| It depends on the semantics you want to give to map_views, and in |
| concrete to the copy of map_views. |
| ]] |
| `` |
| map_view x=...; |
| map_view y=...; |
| x=y; |
| `` |
| [:[' |
| What is supposed to do this last line? |
| ]] |
| [:[' |
| 1. Rebinding of x, that is to say, x points at the same container that y. |
| ]] |
| [:[' |
| 2. Copy of the underlying container. |
| ]] |
| [:[' |
| If you want to implement 1, you cannot use references internally. |
| If you want to implement 2, it is almost the same to use a reference or a pointer. |
| ]] |
| |
| [*Matias] |
| [:[' |
| If I want that they behave exactly as std::maps then I must go for 2. |
| But if I think they as "views" of something, I like 1. The question is complicated. |
| I add another option: |
| ]] |
| [:[' |
| 3. Error: operator= is declare as private in boost::bimap::map_view std_container |
| ]] |
| [:[' |
| Also What happens with `std_container = view;`? and with `view = std_container;`? |
| ]] |
| |
| [endsect] |
| |
| [endsect] |
| |
| |
| |
| |