Re: [boost] associative_vector: request for formal review

From: John E. Potter (jpotter_at_[hidden])
Date: 2000-06-04 16:02:40

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.

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.

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.

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.

Later,
John