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

From: Matias Capeletto (matias.capeletto_at_[hidden])
Date: 2006-08-10 10:07:21

On 8/10/06, John Maddock <john_at_[hidden]> wrote:
> JOAQUIN LOPEZ MU?Z wrote:
> > 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?
>
> Hmmm, if those classes are POD's then layout compatibilty is guarenteed,
> otherwise it's an assumption.  Can it be verified with asserts or
> static_asserts ?

There are actually two relation classes: "mutant_relation", that uses
this almost-standard
guarantee when possible and "standard_relation" that is standard
compliant. You can
read more about this here:

http://cablemodem.fibertel.com.ar/mcape/boost/libs/bimap/boost_bimap/rationale.html#boost_bimap.rationale.general_design.relation_implementation

The idea is to switch between this two classes at compile time using a
conservative approach, so the library can get the standard compliant
label. You can see the switching mechanism here:

http://cablemodem.fibertel.com.ar/mcape/boost/libs/bimap/doxydoc/relation_8hpp-source.html

At this point it is very conservative, and I think it is downgrading
to the slower relation in cases where this can be avoided (for
example, if you do not have 1 byte alignment). Less conservative
checks can be developed in the future.

Best regards
Matias Capeletto