Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk