Re: [boost] [bimap] Review of Bimap

From: Jeff Garland (jeff_at_[hidden])
Date: 2007-02-27 00:17:54

Matias Capeletto wrote:

>> 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.
> 
> I have not followed you here. Can you reword it?

I was just saying that when I use bm.left of bm.right I got behavior that 
looked like an std::map.  I only did a few tests, so it isn't 'proof' of 
compatibility, but I did find any problems.  Bottom line is it work as I 
expected and well :-)

>>   >> 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.
> 
> Boost.MultiIndex have extensive testing on these kind of things.
> Boost.Bimap tests make sure that each function calls the appropriate
> B.MI function.

I see. Well, that makes me a bit uncomfortable in case there is a change to MI 
that breaks your behavior silently.  So I'd like to see a few tests at least.

> There are some in the "examples" section but it has to be extended.
> (They can not compilable because I make some typos that I have to
> correct)

Ok, I'll assume that's on your todo list.

>>> 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.
> 
> In order to understand how this works we have to understand the bimap
> as a bidirectional mapping between two collections of elements (I must
> add a section with a careful explanation). Each collection can have
> different constraints. By default the collections are set_of the
> elements. So they are ordered and unique. The constraints works in the
> same way as the standard containers. (set, multiset, unorderd_set,
> unordered_multiset, list and vector)

Well, at the end of the day, this is a request for doc clarification.  Again 
mostly to do with a lack of tutorial/examples showing the advanced features 
here.  The docs were clear enough that I was able to guess, but I'd have to 
write a program to be 100% sure.  I shouldn't have to do that.

>>> 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 are controlling each collections constraints.
> Can you tell me what kind of bimap you are looking for?

Well after some additional thinking I guess it's 'almost the same'.  That is, 
I think the type requirements for set and map are the same.  Only thing is set 
provides and ordering which map does not.  So actually, this is one small 
departure from what I was expecting.  Anyway, I guess multimap_of is not 
required because it's really covered by multiset_of.

>> 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.
> 
> Ok. It may be better to start with a smaller interface. Lets see how
> things evolve in the next days.

I'm ok either way -- up to you -- after all, you get to maintain it ;-)

Jeff