add subtree-ish sources for 12.0.3

[ceph.git] / ceph / src / boost / libs / bimap / doc / rationale.qbk

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