Re: [boost] [bimap] Review of Bimap

From: Matias Capeletto (matias.capeletto_at_[hidden])
Date: 2007-02-24 23:00:45

Hi jeff,

On 2/24/07, Jeff Garland <jeff_at_[hidden]> wrote:
> 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.

Thanks!

> First some detailed comments/questions:
>
> 1) Tutorial docs are wrong --  namespace should be boost::bimap not 'bimap'

Yes, you are right.

> 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"'

That can be done.

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

That can be confusing. But the docs will be need to be polish to help
people understand the real nature of bimap.

First of all. The ::relation typedef will be eliminated, it is equal
to ::value_type and has only bring noise til now.
I will change the first example so it only use the side views of the
bimap ( .left and .right) that are the most important ones.
The above view, the set of relations one must be introduced later with
a whole section dedicated to it.
If you want to insert elements from the left you have to use it like:

typedef results_bimap::left_map_type::value_type left_val_type;

// or
// typedef results_bimap::left_value_type left_val_type;

results_bimap rbm;
rbm.left.insert(left_val_type("foo", 1));

and if you want to insert elements from the right you have to use it like:

rbm.right.insert(right_value_type(1,"foo"));

> 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();

Ok, you are right.

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

Ok, will be added.

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

A
bimap<X,Y> bm
allows you to view the bidirectional mapping as a std::map<X,Y> using
bm.left and as a std::map<Y,X> using bm.right.
You can work with this container using only this two views.

For bm (the above view) we have some options:

1) bm can be left without any special function and so force the user
to write .left or .right to refer to it.
2) bm can be the same as bm.left. This IMHO introduce an asymmetry to
the interface. The left view became the more important than the right
view.
3) bm can be used for something new. Give the user a new view of the
mapping: a set of relations. This design is symmetric. It forces the
user to write .left to refer to the std::map<X,Y> view but this is a
good thing, because is documented in the code what view is being used.
This option is more elegant and powerful that the other ones.

Your algorithm will work with the right view too:

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

As far as I can see the std::map compatibility is very good, for both
bm.left and bm.right. The only place where this compatibility could
failed is in the conversion between std::pair and the pairs used in
the bimap. But if we use generic code this is not a limitation.

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

More examples will be added.

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

These features are tested in the same way that the simpler bimap.
See:

test_bimap_ordered.cpp
   Test set_of and multiset_of

test_bimap_unordered.cpp
   Test unordered_set_of and unordered_multiset_of

test_bimap_sequenced.cpp
   Test list_of and vector_of

> 9) Should it be bi-collections instead of bi-map?

bimap is a shortcut for bidirectional mapping. The library offers a
framework to create many types of containers, but all of them are
about the mapping between two collection of elements...

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

IMO these features make this library more powerful with out
compromising easy of use.

It is necessary to have the option to change the set type of each
side. Users must have a way to specify different constrains. For
example between the current framework it is very simple to specify
that one of the collections can have repeated elements, aka is a
multiset.

typedef bimap< int, multiset_of< std::string > > bm_type;

The user is allow to choose if elements in each side need to be
ordered, if not he can use an unordered_set for that side and gain in
look up performance.

typedef bimap< unordered_set_of<int>, std::string > bm_type;

We have to discuss about other features, for example, the possibility
of changing the set type of relations, the above view. Because the
library was build on top of Boost.MultiIndex, this feature was there
waiting to be implemented. I think that there are many use cases for
a:

typedef
bimap< unordered_set_of<A>, unordered_set_of<B>, list_of_relation >
bm_type;

bm_type bm;
...

bm_type::right_iterator r_iter = bm.right.find(b);
if( r_iter != bm.right.begin() ) { ... r_iter->second == a ... }

bm_type::left_iterator l_iter = bm.left.find(a);
if( l_iter != bm.left.begin() ) { ... l_iter->second == b ... }

for( bm_type::const_iterator i = bm.begin(), e = bm.end(); i != e ; i++ )
{
   std::cout << i->left << "<--->" << " i->right << std::endl;
}

Where you trade insertion time with the possibility of a fast search
from both sides  with out loosing iteration capability.
What do you think about this kind of bimap?

Thanks for the review
Best regards
Matias