
Boost : 
From: David Abrahams (abrahams_at_[hidden])
Date: 20000604 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
overenthusiastic with my application of KeyOfValue(), that's all.
Dave
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk