Heterogeneous lookup #80

NIKEA-SOFT · 2020-07-02T18:04:19Z

Hello, first of all I would like to thank you for your library.
I noticed that you added a “Heterogeneous lookup” in the latest updates, however, I still couldn’t get it working.

struct string_hash
{
	using is_transparent = void;
	
	std::size_t operator()(const std::string& key)	const { return robin_hood::hash_bytes(key.c_str(), key.size()); }
	std::size_t operator()(std::string_view key)	const { return robin_hood::hash_bytes(key.data(), key.size()); }
	std::size_t operator()(const char* key)		const { return robin_hood::hash_bytes(key, std::strlen(key)); }
};

struct string_equal
{
	using is_transparent = int;

	bool operator()(std::string_view lhs, const std::string& rhs) const {
		const std::string_view view = rhs;
		return lhs == view;
	}

	bool operator()(const char* lhs, const std::string& rhs) const {
		return std::strcmp(lhs, rhs.c_str()) == 0;
	}

	bool operator()(const std::string& lhs, const std::string& rhs) const {
		return lhs == rhs;
	}
};

int main()
{
	robin_hood::unordered_flat_map<std::string, uint64_t, string_hash, string_equal> map;
	std::string_view key = "key";
	map.emplace(key, 100);
	const auto it = map.find(key); // fail
}

The text was updated successfully, but these errors were encountered:

martinus · 2020-07-02T19:24:04Z

It's more or less a bug, it's not yet implemented for emplace().

NIKEA-SOFT · 2020-07-03T21:03:27Z

It's more or less a bug, it's not yet implemented for emplace().

Thanks for your answer, this also applies to the find method.
Thank's!

acd1034 · 2021-12-11T15:27:48Z

@NIKEA-SOFT
The heterogeneous lookup should be defined in the following member functions:

find
count
contains

Reference: P0919R3 Heterogeneous lookup for unordered containers, Working Draft, Standard for Programming Language C++ — ISO C++ standards committee

I believe that robin-hood-hashing defines these member functions correctly.
In fact, I have confirmed that the sample code you posted works correctly in the following environments.

GCC 11.1.0
GCC 12.0.0 202
Clang 11.1.0
Clang 13.0.0
Apple clang 12.0.5

If you still think that robin-hood-hashing is not working properly, could you please let us know the detail of the problem and the environment in which you can reproduce the problem?

Best regards.

ivan-volnov · 2022-01-21T16:48:53Z

Hello, I also find it weird. Please check my example:

template<size_t N>
using String = boost::beast::static_string<N>;

namespace std
{
    template<size_t N>
    struct hash<String<N>>
    {
        std::size_t operator()(const String<N> &str) const
        {
            return robin_hood::hash_bytes(str.data(), str.size());
        }

        std::size_t operator()(const char *str) const noexcept
        {
            return robin_hood::hash_bytes(str, std::strlen(str));
        }

        std::size_t operator()(string_view str) const noexcept
        {
            return robin_hood::hash_bytes(str.data(), str.size());
        }

        using is_transparent = void;
    };

// Also tried this with std::equal_to<Key>
template <size_t N>
    struct equal_to<String<N>>
    {
//        bool operator()(const char *lhs,
//                        const String<N> &rhs) const noexcept
//        {
//            return lhs == rhs;
//        }

//        bool operator()(const String<N> &lhs,
//                        const char *rhs) const noexcept
//        {
//            return lhs == rhs;
//        }

        bool operator()(const std::string_view &lhs,
                        const String<N> &rhs) const noexcept
        {
            return lhs == rhs;
        }

//        bool operator()(const String<N> &lhs,
//                        const std::string_view &rhs) const noexcept
//        {
//            return lhs == rhs;
//        }

//        template<size_t M>
//        bool operator()(const String<N> &lhs,
//                        const String<M> &rhs) const noexcept
//        {
//            return lhs == rhs;
//        }

        template<size_t M>
        bool operator()(const String<M> &lhs,
                        const String<N> &rhs) const noexcept
        {
            return lhs == rhs;
        }

        using is_transparent = void;
    };
}


template <typename Key,
          typename T,
          typename Hash = robin_hood::hash<Key>,
          typename KeyEqual = std::equal_to<>>
using UnorderedMap = robin_hood::unordered_flat_map<
                                    Key, T, Hash, KeyEqual>;

TEST_CASE("UnorderedMap<String<N>,T>")
{
    UnorderedMap<String<10>, int> map;

    const auto &cmap = map;

    REQUIRE(map.count("123") == 0);
    REQUIRE(map.count("0") == 0);
    REQUIRE(!map.contains("123"));
    REQUIRE(!map.contains("0"));
    REQUIRE(map.find("123") == map.end());
    REQUIRE(map.find("0") == map.end());
    REQUIRE(cmap.find("123") == map.cend());
    REQUIRE(cmap.find("0") == map.cend());

    REQUIRE(map.count(std::string_view{"123"}) == 0); // it fails here
//    REQUIRE(map.count(std::string_view{"0"}) == 0);
//    REQUIRE(!map.contains(std::string_view{"123"}));
//    REQUIRE(!map.contains(std::string_view{"0"}));
//    REQUIRE(map.find(std::string_view{"123"}) == map.end());
//    REQUIRE(map.find(std::string_view{"0"}) == map.end());
//    REQUIRE(cmap.find(std::string_view{"123"}) == map.cend());
//    REQUIRE(cmap.find(std::string_view{"0"}) == map.cend());

    map["123"];

    REQUIRE(map.count("123") == 1);
    REQUIRE(map.count("0") == 0);
    REQUIRE(map.contains("123"));
    REQUIRE(!map.contains("0"));
    REQUIRE(map.find("123") == map.begin());
    REQUIRE(map.find("0") == map.end());
    REQUIRE(cmap.find("123") == map.cbegin());
    REQUIRE(cmap.find("0") == map.cend());

//    REQUIRE(map.count(std::string_view{"123"}) == 1);
//    REQUIRE(map.count(std::string_view{"0"}) == 0);
//    REQUIRE(map.contains(std::string_view{"123"}));
//    REQUIRE(!map.contains(std::string_view{"0"}));
//    REQUIRE(map.find(std::string_view{"123"}) == map.begin());
//    REQUIRE(map.find(std::string_view{"0"}) == map.end());
//    REQUIRE(cmap.find(std::string_view{"123"}) == map.cbegin());
//    REQUIRE(cmap.find(std::string_view{"0"}) == map.cend());
}

The output:

src/include/robin_hood.h:1347:42: error: no viable conversion from 'const std::string_view' to 'const boost::beast::static_string<10>'
        auto h = Mix{}(WHash::operator()(key));
                                         ^~~
src/include/robin_hood.h:1412:9: note: in instantiation of function template specialization 'robin_hood::detail::Table<true, 80, boost::beast::static_string<10>, int, robin_hood::hash<boost::beast::static_string<10>>, std::equal_to<boost::beast::static_string<10>>>::keyToIdx<const std::string_view &>' requested here
        keyToIdx(key, &idx, &info);
        ^
src/include/robin_hood.h:1817:30: note: in instantiation of function template specialization 'robin_hood::detail::Table<true, 80, boost::beast::static_string<10>, int, robin_hood::hash<boost::beast::static_string<10>>, std::equal_to<boost::beast::static_string<10>>>::findIdx<std::string_view>' requested here
        auto kv = mKeyVals + findIdx(key);
                             ^
utility.cpp:472:17: note: in instantiation of function template specialization 'robin_hood::detail::Table<true, 80, boost::beast::static_string<10>, int, robin_hood::hash<boost::beast::static_string<10>>, std::equal_to<boost::beast::static_string<10>>>::count<std::string_view, robin_hood::detail::Table<true, 80, boost::beast::static_string<10>, int, robin_hood::hash<boost::beast::static_string<10>>, std::equal_to<boost::beast::static_string<10>>>>' requested here
    REQUIRE(map.count(std::string_view{"123"}) == 0);
                ^
boost/beast/core/static_string.hpp:118:5: note: candidate constructor not viable: no known conversion from 'const std::string_view' to 'const char *' for 1st argument
    static_string(CharT const* s);
    ^
boost/beast/core/static_string.hpp:125:5: note: candidate constructor not viable: no known conversion from 'const std::string_view' to 'const boost::beast::static_string<10> &' for 1st argument
    static_string(static_string const& other);
    ^
boost/beast/core/static_string.hpp:132:5: note: candidate constructor not viable: no known conversion from 'const std::string_view' to 'std::initializer_list<char>' for 1st argument
    static_string(std::initializer_list<CharT> init);
    ^
boost/beast/core/static_string.hpp:129:5: note: candidate template ignored: could not match 'static_string' against 'basic_string_view'
    static_string(static_string<M, CharT, Traits> const& other);
    ^
boost/beast/core/static_string.hpp:136:5: note: explicit constructor is not a candidate
    static_string(string_view_type sv);
    ^
src/include/robin_hood.h:753:32: note: passing argument to parameter 'obj' here
    size_t operator()(T const& obj) const

Any ideas?

ivan-volnov · 2022-01-21T16:50:20Z

Clang 13.0.0

acd1034 · 2022-01-25T07:25:30Z

@ivan-volnov
Thank you for your report! I could find the bug.
There are two reasons why your code is not working.

1. `WHash::operator()(key)` does not work

This is due to this library, and will be addressed in PR #144.

2. `WKeyEqual::operator()(key, mKeyVals[idx].getFirst())` does not work

This is because both std and boost do not support operator== between std::string_view and boost::beast::static_string<N>.
Your code needs to be rewritten as follows:

// This code can be compiled once PR #144 is merged.
#include <algorithm> // std::lexicographical_compare
#include <string_view>

#include <boost/beast/core/static_string.hpp>
#include <robin_hood.h>

template <size_t N>
using String = boost::beast::static_string<N>;

namespace std {
template <size_t N>
struct hash<String<N>> {
    std::size_t operator()(const String<N>& str) const {
        return robin_hood::hash_bytes(str.data(), str.size());
    }

    std::size_t operator()(const char* str) const noexcept {
        return robin_hood::hash_bytes(str, std::strlen(str));
    }

    std::size_t operator()(string_view str) const noexcept {
        return robin_hood::hash_bytes(str.data(), str.size());
    }

    using is_transparent = void;
};

// Also tried this with std::equal_to<Key>
template <size_t N>
struct equal_to<String<N>> {
    bool operator()(const char* lhs, const String<N>& rhs) const noexcept {
        return lhs == rhs;
    }

    bool operator()(const String<N>& lhs, const char* rhs) const noexcept {
        return lhs == rhs;
    }

    // vvv implement on your own
    bool operator()(const std::string_view& lhs, const String<N>& rhs) const noexcept {
        return std::lexicographical_compare(std::begin(lhs), std::end(lhs), std::begin(rhs),
                                            std::end(rhs)) == 0;
    }

    bool operator()(const String<N>& lhs, const std::string_view& rhs) const noexcept {
        return this->operator()(rhs, lhs);
    }

    // vvv added
    bool operator()(const String<N>& lhs, const String<N>& rhs) const noexcept {
        return lhs == rhs;
    }

    template <size_t M>
    bool operator()(const String<N>& lhs, const String<M>& rhs) const noexcept {
        return lhs == rhs;
    }

    template <size_t M>
    bool operator()(const String<M>& lhs, const String<N>& rhs) const noexcept {
        return lhs == rhs;
    }

    using is_transparent = void;
};
} // namespace std

template <typename Key, typename T, typename Hash = robin_hood::hash<Key>,
          typename KeyEqual = std::equal_to<String<10>>>
//                                          ^~~~~~~~~~ added
using UnorderedMap = robin_hood::unordered_flat_map<Key, T, Hash, KeyEqual>;

TEST_CASE("UnorderedMap<String<N>,T>") {
    UnorderedMap<String<10>, int> map;

    const auto& cmap = map;

    REQUIRE(map.count("123") == 0);
    REQUIRE(map.count("0") == 0);
    REQUIRE(!map.contains("123"));
    REQUIRE(!map.contains("0"));
    REQUIRE(map.find("123") == map.end());
    REQUIRE(map.find("0") == map.end());
    REQUIRE(cmap.find("123") == map.cend());
    REQUIRE(cmap.find("0") == map.cend());

    REQUIRE(map.count(std::string_view{"123"}) == 0); // it fails here
    REQUIRE(map.count(std::string_view{"0"}) == 0);
    REQUIRE(!map.contains(std::string_view{"123"}));
    REQUIRE(!map.contains(std::string_view{"0"}));
    REQUIRE(map.find(std::string_view{"123"}) == map.end());
    REQUIRE(map.find(std::string_view{"0"}) == map.end());
    REQUIRE(cmap.find(std::string_view{"123"}) == map.cend());
    REQUIRE(cmap.find(std::string_view{"0"}) == map.cend());

    map["123"];

    REQUIRE(map.count("123") == 1);
    REQUIRE(map.count("0") == 0);
    REQUIRE(map.contains("123"));
    REQUIRE(!map.contains("0"));
    REQUIRE(map.find("123") == map.begin());
    REQUIRE(map.find("0") == map.end());
    REQUIRE(cmap.find("123") == map.cbegin());
    REQUIRE(cmap.find("0") == map.cend());

    REQUIRE(map.count(std::string_view{"123"}) == 1);
    REQUIRE(map.count(std::string_view{"0"}) == 0);
    REQUIRE(map.contains(std::string_view{"123"}));
    REQUIRE(!map.contains(std::string_view{"0"}));
    REQUIRE(map.find(std::string_view{"123"}) == map.begin());
    REQUIRE(map.find(std::string_view{"0"}) == map.end());
    REQUIRE(cmap.find(std::string_view{"123"}) == map.cbegin());
    REQUIRE(cmap.find(std::string_view{"0"}) == map.cend());
}

martinus self-assigned this Jul 2, 2020

martinus added the bug label Jul 2, 2020

acd1034 mentioned this issue Jan 25, 2022

Make hash<T> accept types other than T #144

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Heterogeneous lookup #80

Heterogeneous lookup #80

NIKEA-SOFT commented Jul 2, 2020

martinus commented Jul 2, 2020

NIKEA-SOFT commented Jul 3, 2020

acd1034 commented Dec 11, 2021

ivan-volnov commented Jan 21, 2022

ivan-volnov commented Jan 21, 2022

acd1034 commented Jan 25, 2022

Heterogeneous lookup #80

Heterogeneous lookup #80

Comments

NIKEA-SOFT commented Jul 2, 2020

martinus commented Jul 2, 2020

NIKEA-SOFT commented Jul 3, 2020

acd1034 commented Dec 11, 2021

ivan-volnov commented Jan 21, 2022

ivan-volnov commented Jan 21, 2022

acd1034 commented Jan 25, 2022

1. WHash::operator()(key) does not work

2. WKeyEqual::operator()(key, mKeyVals[idx].getFirst()) does not work

1. `WHash::operator()(key)` does not work

2. `WKeyEqual::operator()(key, mKeyVals[idx].getFirst())` does not work