[boost] [bimap] Review of Bimap

From: Jeff Garland (jeff_at_[hidden])
Date: 2007-02-24 16:52:10

First, I'd like to congratulate Matias and by proxy Joaquín for their work on 
this library --
I think it should be accepted into boost.  I've used similar constructs in 
several real-world
projects and have used my own variant of the 'recommended bi-map' wrapper from 
the MI library
examples.  This new wrapper is better.

First some detailed comments/questions:

1) Tutorial docs are wrong --  namespace should be boost::bimap not 'bimap'

2) I'd suggest that we should have a top level boost header -- boost/bimap.hpp 
the simply
includes the bimap/bimap.hpp.  Not all libs have these top level headers, but 
most do.  It's
handy to just do '#include "boost/<libname>.hpp"'

3) Why not discuss bimap in terms of value_type?  Here's the example from the 
tutorial:

     typedef bimap<std::string,int> results_bimap;
     typedef results_bimap::relation position;

     results_bimap results;

Now normally when dealing with std::map I'd do something like this

     typedef std::map<std::string, int> regular_map;
     typedef regular_map::value_type val_type;

     regular_map rm;
     rm.insert(val_type("foo", 1));

Turns out the same thing works for bimap -- which is good :-)

     typedef results_bimap::value_type bm_val_type;
     results_bimap rbm;
     rbm.insert(bm_val_type("foo", 1));

So, I would suggest that the first example should leverage this similarity 
instead of introduce
the set<relation> stuff.

4) more tutorial -- const_iterators

Since the example doesn't modify the returned objects const_iterator's might 
be more appropriate.
Luckily, just as expected the following were available:

     results_bimap::right_const_iterator i  = rbm.right.begin();
     results_bimap::left_const_iterator i  = rbm.left.begin();

5) Please add something to the tutorial to show the behavior of trying to 
insert when a key is
already in the map:

  //like std::map if one of the keys is duplicated insert fails
  results.insert( position("Somewhere"       ,4) ); //no effect!
  results.insert( position("France"          ,5) ); //no effect!

6) More on std::map compatibility.

Ok, here's what I'm wondering.  For a simple bimap if I access it like an 
std::map shouldn't
I just see the bimap.left?  That is, I'd like to be able to seamlessly use 
bimap in place of
std::map and have the 'left view' work pretty much like a std::map where 
feasible.  Here's
where this would come up.  I have a little algorithm I use to simplify map 
coding called
'exists'.  This simplifies the usual code need to find a particular key in a 
collection,
check against the end, and then do something.  Here's what it looks like:

template<class CollectionType>
inline
bool
exists(const CollectionType& c,
        const typename CollectionType::key_type& key,
        typename CollectionType::const_iterator& outItr)
{
   typename CollectionType::const_iterator itr = c.find(key);
   if (itr != c.end()) {
     outItr = itr;
     return true;
   }
   return false;
}

And it's used like this:

   regular_map rm;
   regular_map::const_iterator rmci;
   if (exists(rm, "foo", rmci)) {
     std::cout << rmci->second << std::endl;
   }
   else { //do something else

Of course if I try this with bimap it fails because key_type doesn't exist 
among other
things.  Luckily, this works:

   results_bimap rbm;
   results_bimap::left_iterator bmci;
   if (exists(rbm.left, "bar", bmci)) {
     std::cout << "exists test left:" << bmci->second << std::endl;
   }

So, my question is, why should the bimap give me a me the .left for the 
standard map methods?

7) More tutorial/example docs please!!

As beautiful as the docs are, I'm like alot of programmers hate reading docs. 
  What I want to
find is an example of the code I'm trying to write so I can cut it from the 
docs drop it into
my code and start modifying.  Then if I hit a roadblock I'll go back to the 
docs.  By the time
I go back to the docs I'll already have a 'feel' for the lib.  Bottom line is 
that there needs
to be lots of examples -- there aren't enough examples in the docs.

8) I'm confused about the model when bi-map uses a 'multi-set' or 
'unordered-multiset'.  Do
these allow duplicated keys for that side?  Why no bi-multimap? Overall I'm 
inclined to suggest
that some of these features should be removed from the library for now.  The 
examples and tests
seem to be lacking (just typedefs that don't test anything AFAICT).

9) Should it be bi-collections instead of bi-map?
There's a ton of other features in the library that allow for creation of 
different bi-directional
relations.  In fact, this probably constitutes the bulk of the library.  Thus, 
I'm wondering if
the library should be renamed to account for these or they should be removed 
and the library stripped
down to the bimap essence?

******************

Some standard question responses...

What is your evaluation of the design?

--> Good -- it's built on top of an already solid Boost library.

What is your evaluation of the implementation?

--> Didn't look long enough to comment.

What is your evaluation of the documentation?

--> It's very complete with reference docs -- a few missing elements: 1) 
compiler notes (discusses
any special rules/issues for various compilers), 2) design decisions -- 
documents any important
tradeoffs and issues, 3) change log -- after it's accepted this will record 
bug fixes, etc.

What is your evaluation of the potential usefulness of the library?

--> Quite useful.

Did you try to use the library? With what compiler? Did you have any problems?

--> Yes, g++-4.0 on ubuntu 64 bit Linux.

How much effort did you put into your evaluation? A glance? A quick reading? 
In-depth study?

--> 3 hours now -- looked at preliminary versions of the library in the past. 
  I read thru the docs
and compiled some examples to test out that the library works as I would expect.

Are you knowledgeable about the problem domain?

--> Yes

Jeff