Heterogeneous lookup

[NIKEA-SOFT]

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
}

[martinus]

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

[NIKEA-SOFT]

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]

@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]

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]

Clang 13.0.0

[acd1034]

@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());
}