Re: [boost] [Review][bimap]

From: Matias Capeletto (matias.capeletto_at_[hidden])
Date: 2007-02-23 09:06:10

On 2/22/07, Thorsten Ottosen <thorsten.ottosen_at_[hidden]> wrote:
> Hi Matias,
>
> First of all I would like to say it's nice to see how well the SoC went.
> Since  I was one who pushed for this library, I guess I should do a
> review. And it has been a pleasure to do so. I think this library
> really shows the benefit of wrapping a fairly difficult library
> (now we just need someone to do it for boost.graph :-)).

I am pleased you enjoy it.

> ********************************************************
> ** I think this library should be accepted into boost! *
> ********************************************************

Nice vote!

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

> - 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?
You can use the following metafunction too:

   iterator_type_by<menber_at::left,bm_type>::type i = bm.left.begin();

This is very handy with the aid of tags

   iterator_type_by<phone_number,bm_type>::type i =
       map_by<phone_number>(bm).begin();

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

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.

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

> - reconsider modify/replace design: I suggest that you provide three
> functions:
>
>    replace( it, key, value );
>    replace_key( it, key );
>    replace_value( it, value );
>
> the last two should be optimally efficient and strongly exception-safe.

Let me think about how you they can be implemented.

> 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

> Subsequently there is no need for a relation nested type as one can
> simply use value_type.

That is true and it can be eliminated. It is another shortcut.
I like how this code looks

bm.insert( bm_t::relation(1,"one") );

But the other way is not that bad either

bm.insert( bm_t::value_type(1,"one") );

  > 2. using namespace bimap; should be boost::bimap.

Ok.

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

> 4. In "Standard mapping framework"
>
> "Note that the type of the collection of X is a set because we have
> chosen a map for the example"
>
> This is somewhat comfusing to use "type". "The X (key) values form a set
>     of unique values" or something. The terminology could be sharper here.

Yes, maybe -type of the collection- could be replaced by -set type-

> 5. "The two collections are then at the same level, so it is incorrect
> to name them as first`second` or `a`b. These names clearly impose an
> ordering on the two values." Again, I think it is more imporant for
> generic algortihms ect to stay with the std::pair layout.

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

> 7. "HashFunctor converts a T object into an integer value". Shouldn't
> that be "unsigned integer"?

It has to be size_t, that will be corrected.

> 8. "The code produced in this fashion tends ". It is not explained what
> "this fasion means". Put the definition earlier.

Yep, It will be changed.

> 9. I find it somewhat assymetrical that in
>
>    people.right.insert( People::right_value_type("Marta Smith",30215692) );
>
>   the types come from People, but the function is called from .right.
>
> Why are these types not avaiable as
>
> People::LeftType::value_type

You can write it as:

people.right.insert(
    People::right_map_type::value_type("Marta Smith",30215692)
);

The other way is provided as a shortcut.

> 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.
I prefer the use of free functions.
Let see what other people think about this.

> 11. In
>
> "    // Search the queried word on the from index (Spanish) */
>
>      iterator_type_by<spanish,translator_bimap>::type is =
> map_by<spanish>(d).find(word);
> "
>
> where is d declared???

It is a typo. I will correct it.

> 12. Should
>
>      bool operator()(Rel ra, Rel rb)
>
> not be
>
>      bool operator()(Rel ra, Rel rb) const

Yes. Will correct it.

> 13. In
>
>    set_of_relation< RelOrder<_relation> >
>
> _relation is not explained?
>
> 14. Consider addding
>
>    value&       map.at( const key& );
>    const value& map.at( const key& );
>
> to complement operator[]() (The C++ language draft already has these)

Ok.

> 15.  Should
>
>    typedef bimap< int, std::string > bm_type;
>    bm_type bm;
>    bm[1] = "one";
>    bm[2] = "two";
>
>
> not be
>
>    bm.left[1] = ...;
>
> etc??

Yes, thanks for spotting that typo.

> 16. replace:
>
> "The complexity is constant time if the changed element retains its
> original order with respect to all views; it is logarithmic otherwise."
>
> Does the cimplexity not depend on the left and right type???

That statement is about the bidirectional map of the example.
It is confusing to leave it that way.
The complexity depends on the selected set types, I will include a
pointer to the following section where it is explained how to
calculate the complexity of
an operation:
http://cablemodem.fibertel.com.ar/mcape/boost/libs/bimap/boost_bimap/reference/bimap_reference.html#boost_bimap.reference.bimap_reference.view_concepts

For example, when you insert an element in a left set_of view you have
O(I(n)) complexity, where I(n) = i_lelf(n) + i_right(n)

i_left(n) = log(n) because it is a set_of
i_right(n) depends on the other side.

> 17. use namespace prefix foe boost::assign::list_of to avoid confusion.

Ok. That is a good idea.

Thanks a lot for your review
Best Regards
Matias