Daniel James escribió:

2009/9/1 Joaquin M Lopez Munoz :

...

Dominique Devienne writes:

...

Any reason why unordered cannot allow similar "compatible key" lookups?

There is no technical reason why Boost.Unordered couldn't provide the compatible key functionality. It just happens not to be a feature condidered in the standard, but if you convince the author to add it as an extension implementing it should be trivial.

AFAICT if the hash function doesn't support the type that you supply it will implicitly construct a key for every call to the hash function and equality predicate. Which is a problem.

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. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

Daniel James escribió:

2009/9/2 :

...

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

Daniel James escribió:

2009/9/2 :

...

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

But those overloads don't always exist. A simple example is:

struct hash { std::size_t operator()(std::string const&) const; };

struct equals { bool operator()(std::string const&, std::string const&) const; };

boost::unordered_map map; // .... map.find("char array");

A single string object should be created in this case.

Correct, but it's the user's responsibility, not yours, to make sure the hash and equality functors used have the appropriate overloads. It's the user whose violating the member function usage interface --strictly speaking she is not violating it, as hash accepts a const char* through the construction of a temporary string, and similarly for equals, but of course this is not the intended behavior. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

Daniel James escribió:

2009/9/2 :

...

Daniel James escribió:

...

...

But those overloads don't always exist. A simple example is:

struct hash { std::size_t operator()(std::string const&) const; };

struct equals { bool operator()(std::string const&, std::string const&) const; };

boost::unordered_map map; // .... map.find("char array");

A single string object should be created in this case.

Correct, but it's the user's responsibility, not yours, to make sure the hash and equality functors used have the appropriate overloads.

I disagree, I'd see what I wrote as reasonable use of the STL.

Yep, I now see your POV and this is admittedly something people can disagree on. Another possibility is that Boost.Unordered provide const_iterator find(const key_type& k) const; template< typename CompatibleKey,typename CompatibleHash,typename CompatiblePred

iterator find( const CompatibleKey& k, const CompatibleHash& hash,const CompatiblePred& eq)const; which is a pure extension without backwards compatibility problems. This is seemingly what Boost.Intrusive is doing. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

On Wed, Sep 2, 2009 at 7:23 AM, Daniel James wrote:

...

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

which is a pure extension without backwards compatibility problems. This is seemingly what Boost.Intrusive is doing.

Yes, I think I'll add that to the new version which should be released in 1.41 or 1.42.

This would indeed cleanly solve my problem. FTR, I tend to lean on Joaquín's side of the argument. If the provided explicit Hash/Pred template parameters of unordered_set do provide overloads for compatible keys, then it's "by design" that find() should use them. If previous code that was relying on an implicit conversion to key_type starts using added overload on Pred/Hash, this simply means that the container designer made this choice explicitly, and I don't see why that a bad thing. After all the overloads were added for avoiding the key creation, which is exactly what I was trying to do here. In Joaquín's proposal, all clients using find() implicitly start using the optimized find() avoiding the key_type conversion once the container is modified and the client code is recompiled. No code necessary. That's a good thing to me. But that's just me ;) --DD

On Wed, Sep 2, 2009 at 2:17 PM, Joaquin M Lopez Munoz wrote:

[...] The net effect is that we pass from one implicit conversion when invoking find() to multiple implicit conversions inside find() code.

Ah yes, that's unfortunate. Thanks for making that clear. A "simple" solution is to not overload, and rename the find() overload into find_compatible_key(another_type) to remove this possibility, while not having to provide explicitly the hash/pred to find(ckey,hash,pred): typedef boost::unordered_set< my_type, hash_by_uid, compare_by_uid

my_type_set;

my_type::uid_t some_uid = ...; const my_type_set& set = ...; my_type_set::iterator found1 = set.find( some_uid, my_type_set::hasher(), my_type_set::key_equal() ); my_type_set::iterator found2 = set.find_compatible_key(some_uid); assert(found1 == found2); The 1-arg find_compatible_key(compatible_key_t) assumes appropriate overloads for compatible_key_t in hash/pred, and delegates to the containers hash/pred and the 3-arg find(). Can even be a free template function in fact. --DD