Re: [boost] associative_vector: request for formal review

From: David Abrahams (abrahams_at_[hidden])
Date: 2000-06-04 21:37:22

----- Original Message -----
From: "John E. Potter" <jpotter_at_[hidden]>

> On searching associative_vector, the current code will only work
> when Key and Value are the same type.  Consider
> associative_vector<int, pair<int, int>, FirstOfPair, less<int> >
> where FirstOfPair operator()(pair) returns first.  Any function
> which has a Key parameter must be treated differently.

Good catch, John.

> For find, you do not want KeyOfValue used on x.
>
> For lower_bound, use
>    compose_f_gx_hy(m_key_compare, std::identity(), KeyOfValue()));
> For upper_bound, use
>    compose_f_gx_hy(m_key_compare, KeyOfValue(), std::identity()));
>
> These will work for reasonable implementations of lower/upper_bound.
>
> In case of unreasonable implementations or for binary_search, both
> members are needed.

Actually, I think according to the standard they must work for all
conforming implementations. The standard gives no leeway to compute
lower_bound with comparisons other than as specified by:

2 Effects: Finds the first position into which value can be inserted without
violating the ordering.

3 Returns: The furthermost iterator i in the range [ first, last] such that
for any iterator j in the

range [ first, i) the following corresponding conditions hold: *j < value or
comp(*j,

value) != false

As far as binary_search is concerned, well, I don't ever really need to use
that, do I? lower_bound makes so much more sense...

> template <class Key, class Value, class KeyOfValue, class Compare>
> struct GeneralCompare {
>    bool operator() (Key const& k, Value const& v) const {
>       return Compare()(k, KeyOfValue()(v));
>       }
>    bool operator() (Value const& v, Key const& k) const {
>       return Compare()(KeyOfValue()(v), k);
>       }
>    };
>
> I don't think one of these can be generated by compose.

You mean a "GeneralCompare" object? Probably not ;)

> I guess that you could leave the code as is and demand that
> KeyOfValue have an identity member for Key as well as the
> member for Value.  However, it seems strange to me that
> KeyOfValue would be used on a Key.

I *think* I understand what you're saying here, but no, it was never my
intention that it should work that way. I just got a little
over-enthusiastic with my application of KeyOfValue(), that's all.

-Dave