123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914 |
- [/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]
|