Re: [boost] Boost.Bimap - Informal Review Request

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2006-08-09 11:07:42

----- Mensaje original -----
De: Matias Capeletto <matias.capeletto_at_[hidden]>
Fecha: Miércoles, Agosto 9, 2006 7:32 am
Asunto: [boost]  Boost.Bimap - Informal Review Request

> Hello,
> 
> Boost.Bimap, my SoC project is ready to confront the list.
[...]
> * Do you like the usage interface?

Very much. I like the fact that in its most basic usage

  typedef bimap<A,B> bm_type;

the syntax is as simple as it can get, yet the library
allows for much more elaborated instantiations.

> * In relation with Boost.MultiIndex, Do you think that it is
>  worth to have a bidirectional map library in Boost, that trades
>  generality for a better specialized user interface?
>  (Because this library was encouraged by the boost mentors the
>  answer will surely be yes, but it is a nice discussion to have)

I think the barrier entry for Boost.Bimap is much lower that
for Boost.MultiIndex, which is one of the main goals of the
project.
I also like the fact that Boost.Bimap is introduced without
references to B.MI: many potential users of Boost.Bimap need
not know anything about B.MI, so B.B can be regarded as a
solution on its own in those cases rather than a transition
stage to B.MI.
 
> * Do you like the extended mapping framework?
>  Do you think it is intuitive for someone with a stl background?

I think the framework is sound. I've got some doubts as to
the understability of the part where the set of relation type is
specified, this being perhaps the most unconventional aspect
of the framework.

> * What do you think of the design of operator[]?
>  Is there a better way to be coherent with the stl that does not 
> imply  throwing exceptions?

I think the current design of operator[] is almost dictated
by the peculiarities of B.B: the semantics is as close as
possible to that of std::map, but not closer.

> * What is your evaluation of the implementation?
>  I am very interested in your reaction to the zero-overhead achieved
>  by the almost-standard mutant_relation class, and the standard
>  compliant label that this library acquires by including the
>  standard_relation class.

Standardwise this is the most controversial part of the
design. My personal opinion is that it's a deviation worth
commiting to in order to achieve zero overhead. Others may
dissent, though.

Just to bring this issue forward to the list, let me state
the problem in simple terms. Currently, Boost.Bimap is
relying on the following three classes being layout-compatible
for the same choice of arguments X and Y (actual names do
not match those used inside B.B):

template<typename X,typename Y>
struct relation
{
  X left;
  y right;
};

template<typename X,typename Y>
struct pair_by_left
{
  X first;
  Y second;
};

template<typename X,typename Y>
struct pair_by_right
{
  X second;
  Y first;
};

Assuming layout compatibility allows us to "see" the
elements of a bimap as pair_by_left's in the left view
and pair_by_right's in the right view, thus matching the
(first=key,second=data) syntax of a regular std::map.
Needless to say all C++ compilers we know of do in fact
provide such a layout compatibility.
If we adhered strictly to the C++ standard, this kind
of mirroring could only be achieved with non-zero
overhead --for instance, holding references to
left and right properly named "first" and "second"
accordingly to the view.

If I'm not wrong B.B assumes layout compatibility
by default but can decay to a standard compliant solution
for those (as of yet unknown) compilers where it could
be needed.

What do others think about this issue?

>  A big part of the library implementation is ContainerAdaptor.
>  Do you deem Boost.ContainerAdaptor worth eventually proposing to
>  Boost?

Maybe the following can be tried to assess the power of this
component: what about trying to implement Boost.PointerContainer
using ContainerAdaptor, if only as a proof of concept? Would this
result in a significant reduction in code size?

> Looking forward to getting your feedback,

I've got a feature request about list_of and vector_of. When
writing for instance:

bimap<set_of<X>,list_of<Y> >

we know (unlike in Boost.MultiIndex) that the Y part does not
belong to any index key and thus can be freely mutated. Could it
be possible that, in those cases, the associated relation
class held a mutable Y allowing for direct manipulation of
that member?
 
> Matias Capeletto

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo