Re: [Boost-users] [Unordered] [Multi-Index] Set lookup from something else than key_type

Subject: Re: [Boost-users] [Unordered] [Multi-Index] Set lookup from something else than key_type
From: joaquin_at_[hidden]
Date: 2009-09-02 06:27:27

Daniel James escribió:
> 2009/9/2  <joaquin_at_[hidden]>:
>   
>> Yep, the hash function and equality predicate the user provides have to have
>> overloads of
>> operator() for the compatible key as well as the key, as shown in the
>> example at:
>>
>> http://www.boost.org/libs/multi_index/doc/tutorial/indices.html#hash_lookup
>>
>> This way no key is unnecessarily constructed, which is the point of the
>> compatible key
>> idea.
>>     
>
> I don't think I can require custom functions to comply with that.
> There'd have to be some kind of type trait to indicate support for the
> type. It might be possible to detect that using SFINAE.
>   

You don't need SFINAE in order to implement compatible keys, it's much 
simpler
than that, let me sketch how it goes. Say for instance we want to extend 
your find member
function to support compatible keys. Currently this member function 
looks like:

  const_iterator find(const key_type& k) const
  {
    // uses hash_function()(k), key_eq()(k,x), key_eq()(x,k)
  }

Now you only have to templatize find (and the internal member functions this
relies on) on the key type, while leaving the code itself untouched:

  template<typename CompatibleKey>
  const_iterator find(const CompatibleKey& k) const
  {
    // uses hash_function()(k), key_eq()(k,x), key_eq()(x,k)
  }

When the user calls find with a regular key_type value, everything works as
it used to. When the value passed is of some other type, the code will
automatically use the correct overloads of hash_function and key_eq, 
provided
the user has supplied the overloaded stuff as required. So, no need to
distinguish compatible from regular keys and no need to play SFINAE.

Additionally, Boost.MultiIndex has overloads of the lookup functions
where the user can provide specific versions of the hash and predicate
functors:

  template<
    typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
  >
  iterator find(
    const CompatibleKey& k,
    const CompatibleHash& hash,const CompatiblePred& eq)const;

Having this is also trivial: the code is basically the same as the 
regular find except
that the objects passed are used instead of the internal hash and 
equality functors.
You can then make the old lookup member functions forward to the new ones:

  template<
    typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
  >
  iterator find(
    const CompatibleKey& k,
    const CompatibleHash& hash,const CompatiblePred& eq)const
  {
    // uses hash(k), eq(k,x), eq(x,k)
  }

  template<typename CompatibleKey>
  const_iterator find(const CompatibleKey& k) const
  {
    return find(k,hash_function(),key_eq());
  }

I hope the subject is a little clearer now. Please come back if it's not.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo