Re: [boost] [intrusive] advanced lookup/insertion suggestion

Subject: Re: [boost] [intrusive] advanced lookup/insertion suggestion
From: Rei Thiessen (rei.thiessen_at_[hidden])
Date: 2012-02-15 19:29:19

On Wed, 15 Feb 2012 12:01:25 +0100, Ion Gaztañaga wrote:

> 
> Then for an element we have only one possible hash and comparison type,
> and that's not acceptable. A user might want to use a better hash
> function or just compare some set fields for equality but not all of
> them.
> 
> Ion

Then the "key_value_trait" binary type operator can be a container option.

The only use case that the new signatures is disallowing (old signatures 
are still retained so it's not impossible) is where there are multiple  
instances of key_type associated with a single instance of value_type for 
a given instance of a container. That means that, given only an instance 
k of type key_type and a container, we don't have enough information to 
perform advanced lookup because we don't know which association that 
instance k has with value_type:

value_type x(...);
c.insert( x );

key_type k1 = derive1( x ); // one derivation such that eq1(k1,x)
...
c.find( k1, eq1, h1 ); // finds x

key_type k2 = derive2( x ); // a different derivation such that
...                        // eq2(k2,x) but !eq1(k2,x)
c.find( k2, eq2, h2 ); // finds x
c.find( k2, eq1, h1 ); // undefined
c.find( k1, eq2, h2 ); // undefined

void find_element( container_type c<value_type>, key_type k )
{
    // how was k derived?
}

This means that an instance of key_type has a "hidden type" that the 
programmer is maintaining instead of the compiler. If this is required, 
then I'd recommend creating two empty derived classes from key_type:

struct key1_type : key_type {};
struct key2_type : key_type {};

// The types for c and k can now be erased in these functions
void find_element( 
    container_type<value_type,key_value_trait<my_trait>> c, 
    key1_type k )
{
    // OK. Algorithm uses 
    // my_trait<value_type,key1_type>::eq_type
    // and my_trait<value_type,key1_type>::hash_type
    c.find( k );
}

void find_element( 
    container_type<value_type,key_value_trait<my_trait>> c, 
    key2_type k )
{
    // OK. Algorithm uses 
    // my_trait<value_type,key2_type>::eq_type
    // and my_trait<value_type,key2_type>::hash_type
    c.find( k );
}

Rei