Re: [boost] [Review][bimap]

From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2007-02-24 09:37:13

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

>>Maybe I missed how one would use this view. How exactly (and which page
>>in the documentation?)
> 
> 
> Maybe I have introduce noise here. The left view is the bidirectional mapping
> view from the left, the one obtained with bm.left
> 
> bimap<X,Y>::left_map_type is signature compatible with std::map<X,Y>.
> bimap<X,Y>::left_map_type::value_type is signature-compatible with
> std::pair<X,Y> and
> bimap<X,Y>::right_map_type::value_type is signature-compatible with
>  std::pair<Y,X>
> 
> So you can use this view or the right one with generic algorithms that need
> first/second members.

I missed that. It seems like there is less to worry about then :-)

I'm still slightly sceptical about the benefit of having both

   typedef bimap::relation relation;

and

   typedef bimap::left_value_type;

is the potential confusion really worth the trouble?

Take this example:

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

     results_bimap results;
     results.insert( position("Argentina"    ,1) );
     results.insert( position("Spain"        ,2) );
     results.insert( position("Germany"      ,3) );
     results.insert( position("France"       ,4) );

I could not find any documentation on direct members of
a bimap. Should it read results.left.insert()???

>>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.
> 
> 
> Ok, you are right.
> I think we can provide the non-mutable version of at() without any problem.
> The mutable version of at() can be provided only for bimaps where the other
> view is a list_of, vector_of or unconstrained_set_of because the mapped
> elements can be modified with out breaking invariants.

Seems right.

>>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 felt it odd that the following line could throw duplicate_value.
> if( bm.left[1] != "two" ) { ... }
> But it is wrong because at() has to be used here instead of operator[].
> 
> The non-mutable version of operator[] will be eliminated.
> 
> 
>>I think I'm leaning slightly towards not providid operatot[]() at all.
>>?
> 
> 
> I have to think which will be the destiny of the mutable one, IMO users
> will expect it to be there.
> Now that at() will be included it maybe easier to convince them that they are
> better with out operator[].
> It is a big decision, let me think about it.

Right, it's a rather important decision. At least consider not making
the proxy convertible to mapped_type& (that requires an independent 
lookup, right).

> 
>>Perhaps you can simply add
>>
>>   mapped_type& insert( const key_type& key, const mapped_type& value );
>>
> 
> 
> This function will be dificult to specifie too, it may throw for example.
> IMO it is not necesary to include anything else if we decided to eliminate
> operator[].
> 
> 
>>>>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 :-)
> 
> 
> That will not be possible, because Boost.MultiIndex works with general
> structures not with two values. :(

I would like to hear Joaquin's  take on this. I have trouble 
understanding why you can't delay construction/assignment of a pair 
until it is actually needed.

> This maybe one of the exotic places of bimap where you feel the price
> of wrapping a generic component. But it is a very small price to pay.
> 
> 
>>>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.
> 
> 
> But std::make_pair can not be used with bimaps.

Right.

> The pairs that bimap uses in its side views have a member named first
> and a member named second, so they can be used in generic
> algorithms/code/functions that works with map iterators or generic
> pairs.
> To be sure we are talking about the same thing, it does not impose that
> std::pairs and bimap pairs can be converted between each other.

Right.

std::make_pair() aside, you are often forced to
constructing a pair object, only to copy its data once again upon
insertion into the map.

This is justification enough for me to add the function.

Further justification is then ease of use, the main justification of
operator[]().

>>>>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.er der 
>>>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.
> 
> 
> Do you want to put all the free functions inside bimap?
> map_by<>()
> xxx_iterator_by<>()
> 
> We have functions like reverse_iterator_by<Side>(Bimap)
> that have no meaning in all the cases, and may be trickier
> to implement.
> 
> If we go down this way, we will maybe think that it is better
> to write rel.get<id>() instead of get<id>(rel)
> 
> In this case the get function works for relations and for the
> pairs of the bimap views.
> 
> You can write:
> get<id>( *bm.begin() )
> get<id>( *bm.left.begin() )
> get<id>( *bm.right.begin() )
> 
> In the end, it may be simpler to implement it with member
> function instead of free functions. I do not think that the
> interface is cleaner with them, but it is an idea we can play
> with.

I don't feel strongly about it. I did however always find it slightly 
harder to locate members. But the free-standing are more generic in the 
sense that they accept a bimap concept, should snybody implement their 
own compatible bimap.

-Thorsten