Boost logo

Boost :

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

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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at