Open NIKEA-SOFT opened 4 years ago
It's more or less a bug, it's not yet implemented for emplace()
.
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:
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.
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?
Clang 13.0.0
@ivan-volnov Thank you for your report! I could find the bug. There are two reasons why your code is not working.
WHash::operator()(key)
does not workThis is due to this library, and will be addressed in PR #144.
WKeyEqual::operator()(key, mKeyVals[idx].getFirst())
does not workThis 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());
}
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.