Re: [boost] [Review][bimap]

From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2007-02-23 11:44:46

Matias Capeletto wrote:
> On 2/22/07, Thorsten Ottosen <thorsten.ottosen_at_[hidden]> wrote:

>>Here's a list of things I feel strongly about changing (see below for info):
>>
>>- relation should have the same members as std::pair
> 
> 
> What are the use cases where left/right will not be appropriate?

It all boils down to reuse of existing algorithms/code/functions that 
assumes the existing of .first/.second etc.

All this code has to wrap code from this library.

I personally don't feel the use of std::pair in the standard is very 
well-thought out, but it is standard, and it is is easier for users to 
remember one ugly way than one ugly way and N good ways.

>>- types should lie with members, so
>>
>>   map::left_type::iterator i = m.left.begin()
>>
>>instead of
>>
>>   map::left_iterator i = m.left.begin()
> 
> 
> It is implemented in this way.
> 
>     typedef bimap<int, float> bm_type;
>     bm_type bm;
>     ...
>     bm_type::left_map_type::iterator i = bm.left.begin();
> 
> bimap defines shortcuts to make life easier.
> 
>     bm_type::left_iterator i = bm.left.begin();
> 
> ¿Do you see this as interface bloat?

I was slightly thinking that. Whenever I meet a new name, I'm
certain that it requires a look into the documentation to see if this is 
a new type of iterator or whatever it it is.
> 
>>- operator()[] seems way to complicatedly specified and does not follow
>>the promise of mirroring STL.
> 
> 
> I repost some thoughts about this:
> 
> "In the STL unique associative containers (like std::map), operator[]
> first makes an insertion if the key element was not in the container.
> In addition, the container has no constraints in the data types, so it
> is an operation that never fails.
> We want to maintain a coherent behaviour between the extended mapping
> framework and the quite established STL one-side-oriented one, and
> that imply respecting in the best possible way each operation. For
> example, an insertion in a map view of a bimap may failed because the
> there are conflicts with the constraints from the other side. The
> standard insertion returns false when it fails, so it is very straight
> forward to extend it to the new framework.
> operator[] on the other hand, is quite a challenge. There are several
> possible ways to extend it. We (In fact, my mentor make me change
> my original implementation) opted for the most conservative
> implementation. When operator[] does not behaves exactly as the
> original counterpart, an exception is thrown."
> 
> What are the things about it you feel complicated?

The fact that return types are very different from mutable to const 
version. And the specification of the operator seems way too complicated.

> If you try to add a new relation to the bimap using:
> 
>     bm.left[a] = b;
> 
> If b breaks the invariants in the right set, you have
> various options:
> 1) reject the new relation and don´t let the user know about that.
> 2) insert the new relation and eliminate others to fulfill the bimap
> invariants. The user is not informed of this.
> 3) throw a "duplicate_value" exception.
> 
> Either of this option are compatible with the STL behaviour and
> the last one is the only one where the user is not allowed to use
> the bimap in a way different from the standard maps.
> 
> If you try to use it with a value that is not present in the bimap,
> if you follow the STL and add a default value there are chances
> that you get a "duplicate_value" exception which would be very
> confusing.

I think I'm ok with your mutable version of operator[](). Keep that,
but seek to simplify .... more below.

> 
>>Keep the mutable operator()[] and then add
>>
>>   value&       map.at( const key& );
>>   const value& map.at( const key& ) const;
> 
> 
>>which throws on lookup failure.
> 
> 
> Ok, this function must be added but I think that in the case of
> bimap operator[]() and at() will work in the same way.

Well, the standard did not add

  const_reference operator[]( key ) const

because it can't behave the same way as the mutable version. Neither
can it in the bimap. But the lookup function is useful, so therefore
the stdnard draft added st(). If the mutable version of at()
is impossible/breaks invariants in bimap, then only provide non-mutable 
at() that throws value_not_found.

Now for operator[](). It might be ok to return a proxy "reference" for 
the mutable version.
But the more I look at it, the less inelegant I find the specification.

Reading should be taken care of by at(), so the conversion is
not needed anymore. That leaves only assignment. This makes me wonder
why you said this:

 > if you follow the STL and add a default value there are chances
 > that you get a "duplicate_value" exception which would be very
 > confusing.

Why is that particularly confusing compared to the whole proxy-reference
business?

I think I'm leaning slightly towards not providid operatot[]() at all.
Perhaps you can simply add

   mapped_type& insert( const key_type& key, const mapped_type& value );

?

>>General comments
>>----------------
>>
>>1. This statement:
>>"The relation class is a generalization of std::pair. The two values are
>>named left and right to express the symmetry of this type."
>>
>>It might be better to stay signature compatible with std::pair if you
>>can. Boost.PtrMap initially started out without signature compatibility,
>>but is now fixed to be that after user complaints.
> 
> 
> In general you can use the left view to achieve std::pair compatibility.
> I feel that this change will make the interface

bad?

Maybe I missed how one would use this view. How exactly (and which page 
in the documentation?)

>>3. consider adding
>>
>>      insert( const key&, const key2& )
>>
>>   for performance and ease-of-use reasons.
> 
> 
> It may be a good idea but to insert the the relation I have to use
> Boost.MultiIndex functions, so the performance will be the same.

Well, not if Boost.MultiIndex adds this function too :-)

> About ease-of-use, I agree with you.
> bm.insert( 1 , "one" );
> bm.insert( bm_t::relation(1,"one") );
> But we must ask ourselves why standard maps do not define this
> function.

In some sense it is redundant, and you can do without it.
The standard tried to minimize such redundacy for easy of specification,
not for ease of use IMO. Thus they don't provide

   container.contains( value );

, but only

   container.count( value );

I also assume that the most frequent types are built-in ones
where the penalty is not high for copying. But it certainly
is for many user-defined types.

To make matters worse, std::make_pair() takes it's arguments
by value.

>>6. Consider adding support for lookup/inserttion with types that are
>>convertible to the key type (as a performance improvement).
> 
> 
> That is in my TODO (and wish) list but it is not easy.

I can imagine :-)

>>10. Could
>>
>>   map_by<id>(people)[28928546]
>>
>>be spelled
>>
>>   people.by<id>()[28928546]
>>
>>? It seems simpler to use and specify to me.
> 
> 
> Maybe we can provided both of them.
> mmmm... It can be interface bloat.

It would be kinda bloat if both are provided.

> I prefer the use of free functions.
> Let see what other people think about this.

Right. I just asked myself what other
arguments than a bimap does this function takes?
If the answer is none, then it serves no purpose
to make it a free function.

-Thorsten