[boost] Bimap Review

From: John Maddock (john_at_[hidden])
Date: 2007-02-25 05:15:37

Bimap Review
~~~~~~~~~~~~

First off, I'm pleased to see the first of our Google Summer of Code student 
projects come up for review, and I think Matias should be congratulated for 
persevering though to this stage.

The headline for this review, is that I think the library should be accepted 
into Boost, it's a very convenient specialisation of Multi-Index that will 
no doubt find many uses.

Documentation and design
~~~~~~~~~~~~~~~~~~~~~~~~

First off I like the docs: they are, as others have noted more colourful 
than most Boost docs, but I rather like them.  In fact I think I prefer the 
code-boxouts used to the usual Boost style for these :-)

The one minute tutorial is pretty straightforward, but I would like to see a 
slightly longer description of what a Bimap is, off the top of my head:

"A bimap is an associative container, that contains two types, with objects 
of either type usable as a key to find a matching object of the other type. 
Therefore a bimap has three views: a set of pairs of elements that are 
related to each other, and two map views that allow either type to be used 
as a lookup key."

Still not perfect by any means, but perhaps something along these lines 
before your existing code example?  Or else cut and paste something from the 
longer tutorial where I see you do have a nice description.

Looking at this again, I think I see the issue about left/right now that 
other reviewers have raised.  The relation type is not a generalisation of 
std::pair (or even a std::tr1::tuple).  Wait a minute, I'm confused 
actually, the docs say: "The relation class is a generalization of 
std::pair. The two values are named left and right to express the symmetry 
of this type."  But then the examples that follow access the two members of 
the relation by "first" and "second", so which is it?  Ah, double checking, 
the relation class uses left and right, but if you dereference a left or 
right view iterator you get a pair-compatible type with first and second? 
Is that right?  If so folks are going to get really confused,  it's got to 
be either left/right or first/second everywhere I think.  So I think I'm 
beginning to lean towards the first/second names as suggested by others.

Other than that the one minute tutorial is very useful I think.

Extended tutorial
~~~~~~~~~~~~~~~~~

Everything is very good as far as the section on tagging.  When I scanned 
this section at the end of the SOC period, I didn't really "get" it, and 
reading in depth now, it's still taken me a while.

It's taken me time to try and put my finger on the problem though, I think 
it's this: tagging isn't what the user wants to do, tagging is just the 
means to and end.  What the user wants to do is access the bimap through 
meaningful names rather than the generic left/right names.  So the title and 
introduction of the section needs to reflect that, and then everything else 
will make more sense I think (I hope anyway!).  Maybe calling the section 
"Assigning user defined names to views and types" or something would do it, 
it's sort of like "named parameters", except they're not parameters, so I'm 
struggling for good terminology.  Anyone have any better suggestions?

I have to confess as well, I'm not completely convinced that the tagging 
mechanism is worth the effort: I can well imagine just writing my own 
accessor functions so I can write:

get_people(my_bimap);

rather than:

get<people>(my_bimap);

But I don't feel strongly enough to argue against providing it.

I liked the "Bimap and Boost" section, an excellent idea IMO.

The dependencies section has "Clearly Boost.MultiIndex has been abused by 
this library." I don't think you meant to use the word "abused" here! :-)

The reference section I've mostly just skimmed though I'm afraid, but one 
thing I did notice is that your complexity notation - things like O(M(n)) - 
really needs to be linked to the explanation of the terms.  If you define 
some quickbook templates for the links and then search and replace for "M" 
etc it shouldn't take too long to link up.

Test Programs
~~~~~~~~~~~~~

I'm happy that Matias has fixed these now, however I did notice some 
commented out tests:

    # Enable this to force the mutant_relation test
    # Warning: it may fail in some standard compliant compilers, because the
    # mutant idiom uses need that struct { TA f; TB s; }; be layout 
compatible
    # with struc { TA s; TB f; }; and this is not in the standard.
    # However, most modern compiler support it.
    #
    #[ run 
                ]
    #[ run 
                         ]

    # Enable this to force the standard_relation test
    # It is not always enabled because if the mutant idiom is supported, 
then it
    # is not needed and if not, it is tested in test_relation.cpp.
    #
    #[ run 
                           ]

    [ run 
                  ]
    ;

Should we be concerned about this?

I also tried to compile the programs in the examples folder, but got quite a 
few errors (logfiles attached).

Other than that I like the library's design, it's well documented, and it 
fulfils a genuine need, so providing the compiler-issues can be sorted out, 
then it should be accepted into Boost.  Incidentally, I also noticed that 
Intel/Win32 compiles took a very long time to complete indeed: many times 
longer than msvc or gcc.  Not sure there's anything can be done about that 
though unfortunately :-(

John Maddock.