Re: [boost] [bimap] Review of Bimap

From: Jeff Garland (jeff_at_[hidden])
Date: 2007-02-25 13:40:32

Matias Capeletto wrote:
> Hi jeff,
> 
> On 2/24/07, Jeff Garland <jeff_at_[hidden]> wrote:

>> 6) More on std::map compatibility.
>>
 >...snip details...
 >
>> 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.

Yes, I second thought I agree with this view.  I'd rather see bimap take the 
minimal approach now and avoid the confusion.  Also, I suspect that if *I'm* 
really interested in providing the 'left' view as default standard I can 
simply derive  from bimap and provide the needed types.  Given this, you 
should probably remove some of the public typdefs because things like

   bimap::value_type

compile and hence may be confusing.  I should have to say bimap::left_value_type.

> 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;
>>    }

Yep.

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

My experiments do indeed confirm at some level that .left and .right look 
pretty much like std::map...hardly exhaustive, but still I was happy about that.

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

Ok, I missed those.  But still I'm still left wondering about these questions:

  >> Do these allow duplicated keys for that side?  Why no bi-multimap?

I didn't see a duplicated key test and perhaps I missed it, but I didn't see 
that explained in the docs.  Also, there's no example code AFAICS for most of 
these advanced mappings.

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

Ok, it's probably my pre-conceived notion of what bi-map is that clouded my 
understanding.

>> 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's possible for the more complex features to distract from the usability for 
the simple reason that there's more documentation for users to consume and 
understand.  Sometimes as a new user when there's a problem it's hard to tell 
where the answer lies.  Anyway, I think most of this can be solved with 
additional tutorial docs/examples showing the use of these more advanced features.

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

Ok, if I'm not mistaken this will change the interface behavior in that now:

    bm_type b;
    typedef bm_type::right_value_type vtype;
    b.insert(vtype(1, "foo"));
    b.insert(vtype(1, "foo"));

will succeed.  I definitely wasn't sure about this after reading the docs.

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

Sure, I can certainly see the power of this.  Again, the one that seems to be 
conspicuously absent is multimap_of which would presumably be unordered and 
not require a hash function.  So why no multimap_of?

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

Sure, I can see the utility of this feature -- I"m actually working on 
something now that has exactly these sort of requirements supported thru code 
generation.  As I said, above I think at a minimum it needs a bit more 
attention in the tutorial docs/examples.  My suggestion about 'leaving it out 
for now'  is based on the simple point that you can always expand the library 
easily later (even without review), but once it's out there it's really, 
really hard to take back or radically change things.  So if there's any doubt 
it would be better to keep things simpler now and add later.

Jeff