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