Re: [boost] [Review][bimap]

From: Matias Capeletto (matias.capeletto_at_[hidden])
Date: 2007-02-24 12:17:22

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

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

No, there is some confusion here. The documentation will have to be
changed to help grasp the essence of bimap easier. Fernando Cacciola
has proposed some useful changes to the docs.

A bimap is a data structure that can be used from various point of view.
Suppose we have:

typedef bimap<X,Y> bm_type;
bm_type bm;

The whole idea of bimap is to be able to use the container as a
std::map<X,Y> *and* a std::map<Y,X>. To use the bimap as a directed
mapping you use "bm.left" and "bm.right". As an additional feature,
you can use bm directly to view the mapping as a std::set<
relation<X,Y> >.

(1) bm.left - The "left side view", that is compatible with
std::map<X,Y>. It uses first/second notation. You are viewing the
mapping from the left, the first element you see is the left one and
the second one is right one.

bm.left.insert( bm_type::left_map_type::value_type(x,y) );
...
for(bm_type::left_map_type::iterator i = bm.left.begin(), e = bm..left.end() ;
i != e ; i++ )
{
    std::cout << (*i).first << "---->" << (*i).second << std::endl;
}

This will output

x1 ----> y1
x2 ----> y2
x3 ----> y3
x4 ----> y4

(2) bm.right - The "right side view", that is compatible with
std::map<Y,X>. It uses first/second notation too, but now you are
viewing the mapping from the right, the first element you see is the
right one and the second one is left one.

bm.left.insert( bm_type::right_map_type::value_type(x,y) );
...
for(bm_type::right_map_type::iterator i = bm.left.begin(), e = bm..left.end() ;
i != e ; i++ )
{
    std::cout << (*i).first << "---->" << (*i).second << std::endl;
}

This will output

y1 ----> x1
y2 ----> x2
y3 ----> x3
y4 ----> x4

(3) bm - The "above view", that behaves as a set< relation<X,Y> >.

This is a complementary way of working with the mapping. This view
works with left/right notation to show in the code that we are using
the mapped values in a way where both are equally important.

bm.insert( bm_type::value_type(x,y) );
bm.size()
...
for(bm_type::iterator i = bm.begin(), e = bm.end() ; i != e ; i++ )
{
    std::cout << (*i).left << "<--->" << (*i).right << std::endl;
}

This will output

x1 <---> y1
x2 <---> y2
x3 <---> y3
x4 <---> y4

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

Do you still see confusion here?

bimap_type::relation is the same as bimap_type::value_type.

bimap_type::left_value_type is a shortcut for
bimap_type::left_map_type::value_type.

They are very different from each other
bimap_type::value_type ------------------> relation<X,Y>
bimap_type::left_map_type::value_type ---> pair<X,Y>

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

Can you give an example?

> This is justification enough for me to add the function.
>
> Further justification is then ease of use, the main justification of
> operator[]().

Easy-of-use is out of the question.

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

In this case it will be a little difficult that other bimap appear in
the game, but it is true that it is more generic. If there is a strong
argument against free functions we can convert them to member
functions.

Best Regards
Matias