[intrusive] advanced lookup/insertion suggestion
Something that has bothered me with the advanced lookup and insertion functions is that I have to specify the hash/equality functors at every invocation site: c.find(key,key_hash(),key_equality()); c.insert_check(key,key_hash(),key_equality(),cd); If we don't consistently use the same (key_hash,key_equality) pair for a given (element_type,key_type) pair, the container invariant will likely be broken. Thus, I think it's very un-"C++ like" to have to specify these two types at every invocation site. Assuming that we don't want to embed (key_type,key_hash,key_equality) directly into the type of a container, the library could use a type operator to automatically deduce the appropriate hash/equality functions given an element/key type pair at the find/insert member function instantiation point: // library template<typename ElementType, typename KeyType> struct element_key_info {}; // different name to avoid overload confusion. // instantiation succeeds only when // element_key_info is properly specialized template<typename KeyType> iterator unordered_set::find_key( KeyType const& k ) {...} ... // user namespace intrusive{ template<> struct element_key_info<element_type,key_type> { typedef key_hash hash_type; typedef key_equality equality_type; }; } element_type e(...); c.insert( e ); key_type k(...); ... = c.find_key( k ); These new signatures do not allow non-default-constructible hash/equality functors, but the original signatures that do are still available. I think this makes the code simpler and safer in exchange for some additional type declarations. Would this be a worthwhile addition to the intrusive associative containers?
El 15/02/2012 0:27, Rei Thiessen escribió:
// library template<typename ElementType, typename KeyType> struct element_key_info {};
// different name to avoid overload confusion. // instantiation succeeds only when // element_key_info is properly specialized template<typename KeyType> iterator unordered_set::find_key( KeyType const& k ) {...} // user namespace intrusive{ template<> struct element_key_info<element_type,key_type> { typedef key_hash hash_type; typedef key_equality equality_type; }; }
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
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
participants (2)
-
Ion Gaztañaga -
Rei Thiessen