robin-hood-hashing
robin-hood-hashing copied to clipboard
martinus
Heterogeneous lookup
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
}
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!
@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.
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 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());
}