Re: [boost] [Review][bimap]

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

On 2/23/07, Thorsten Ottosen <thorsten.ottosen_at_[hidden]> wrote:
> 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.

The above view it is not provided to work smoothly with std::maps. It
is a new way of viewing a mapping using set semantics. That is why I
think we are not forced to use first/second for it. What is more, we
should use a notation that express the difference between the above
and side views.
Side views are signature compatible with standard map containers. In
side views we use first/second notation. That is why I said you can
reuse your algorithms and generic code.

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

sorry for the missed words...
I feel that this change will make the interface of the above view be
confused with the side views.

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

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

In this particular case I think that the shortcut is worthy.

> >>- operator()[] seems way to complicatedly specified and does not follow
> >>the promise of mirroring STL.
> >
> > (...)
> >
> > 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.

I am starting to think that you are right about this.

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

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.

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

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

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

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.

Best Regards
Matias