Heterogeneous lookup in unordered containers

[Roman Orlov]

Hello,

I'd like to search for elements in a key-based container via std::string_view without construction of std::string instance. It is possible for std::map/std::set if I explicitly declare geterogeneous (or transparent) compare function.

std::map<std::string, std::less<>> m;
m.find(std::string_view{"hello"});

It is done via generic lookup functions which are enabled if a compare function is transparent. Unfortunately, there are now such functions for unordered containers.

I've found a proposal for fixing this http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3573.html

But it's rather old and I don't like it for several reasons. I believe the C++ committee dislikes it too)

1) It proposes heterogeneous hash function which forwards type T as std::decay<T>. I consider this a bad practice because std::decay can destroy initial type (remember array-to-pointer conversion).

2) Heterogeneous lookup is enabled by default

template<typename T, typename Hash = std::hash<>, typename Eq = std::equal_to<>>
iterator find(T t, Hash h = Hash(), Eq e = Eq());

That's wrong and breaks an old code

some_map.find({100, 'A'});

Also it makes the functions ugly.

  

Now I work on my own proposal to make heterogeneous lookup in unordered containers better. 

Instead of implementing std::hash<> via std::decay<T> I propose more safe approach

template <>
struct hash<void> {
    template <typename T>
    size_t operator()(T&& v) const noexcept {
        return hash<typename remove_cv<typename remove_reference<T>::type>::type>{}(v);
    }
    typedef void is_transparent;
};

If an unordered container is declared with transparent hash then the default compare function should be transparent too. It may look like this

template <class _Value, class _Hash>
struct _default_pred {
    typedef equal_to<_Value> type;
};

template <class _Value>
struct _default_pred< _Value, hash<> > {
    typedef equal_to<> type;
};

template <class _Value, class _Hash = hash<_Value>,
          class _Pred = typename _default_pred<_Value, _Hash>::type,
          class _Alloc = allocator<_Value> >
class  unordered_set

Then the heterogeneous lookup functions may be enabled via SFINAE if the hash and compare functions are both transparent.

template <class _K2, class _Rt>
using __enable_if_transparent = typename enable_if<
    __is_transparent<_Hash, _K2>::value &&
    __is_transparent<_Pred, _K2>::value, _Rt>::type;
   
template <class _K2>
__enable_if_transparent<_K2, iterator> find(const _K2& __k);

I have implemented this for std::unordered_set in libc++ https://github.com/compmaniak/libcxx/pull/1/files

The solution is the same for unordered set/multiset/map/multimap.

What do you think about all of this? Any thoughts would be appreciated.

Or maybe somebody has already done it better.

Thanks,

[T. C.]

On Friday, April 7, 2017 at 8:28:56 AM UTC-4, Roman Orlov wrote:

If an unordered container is declared with transparent hash then the default compare function should be transparent too. It may look like this

template <class _Value, class _Hash>
struct _default_pred {
    typedef equal_to<_Value> type;
};

template <class _Value>
struct _default_pred< _Value, hash<> > {
    typedef equal_to<> type;
};

template <class _Value, class _Hash = hash<_Value>,
          class _Pred = typename _default_pred<_Value, _Hash>::type,
          class _Alloc = allocator<_Value> >
class  unordered_set

This has all the same ABI-breaking problems as default_order. 

[Roman Orlov]

суббота, 8 апреля 2017 г., 20:51:13 UTC+3 пользователь T. C. написал:

Could you show the code that will be broken?

Consider the simple case when only Value template parameter is defined

std::unordered_set<std::string> s;

The code will work because the hash function is std::hash<std::string> and compare function is std::equal_to<std::string>

The code will work if a custom hash function is provided

std::unordered_set<std::string, &my_hash_func> s;

In this case the compare function is still std::equal_to<std::string>.

ABI might be broken in the following code

std::unordered_set<std::string, std::hash<>> s;

In this case the compare function will be std::equal_to<> instead of std::equal_to<std::string>. But std::hash<> is not a valid hash function until this proposal.