Re: [boost] Bimap Review

From: Matias Capeletto (matias.capeletto_at_[hidden])
Date: 2007-02-25 23:13:44

On 2/25/07, John Maddock <john_at_[hidden]> wrote:
> 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.

Great!

> 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.

Ok, will added it.

> 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.

I have started a new thread so we can all talk together about this.

> 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 see "tagging" as "attach a label". We are sticking labels to both
views so we can access them with autodocumented code.

> 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.

You will have to provide map_by, iterator_by, get, pair_by...
They are too many to code they by hand every time you need a bimap.

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

I like this section too. I have found a problem with Boost.Assign, so
I think that this feature will be removed at this time, and
re-introduce later.

> 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! :-)

Errr... I thought that word has a different meaning.

> 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.

Yep... I do not know if in every M. But I have to introduce links to
that section.

> 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?

The tests are fine, the test_relation.cpp test the appropriate
relation (mutant_relation or standard_relation). But we should discuss
about the relation implementation.
It is explained in the rationale here:
http://cablemodem.fibertel.com.ar/mcape/boost/libs/bimap/boost_bimap/rationale.html#boost_bimap.rationale.general_design.relation_implementation

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

There were typo errors in the examples. Sorry about that.

> 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 :-(

I noticed that too. I don't know how to make it faster either.

Thanks for your review, and for running the test cases
Best Regards
Matias