Qualified's blog

By Qualified, 7 weeks ago, In English

I was trying out custom hashes for unordered_map from USACO-Guide and neal's custom hash on 855A - Дневник Тома Реддла. Take a look at this code

struct chash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);

int n;
unordered_map<string, int, chash> cnt;

int main() {

	cin >> n;
	for(int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		if(cnt.count(s)) {
			cout << "YES\n";
		} else {
			cout << "NO\n";

It spits out this nasty error

In file included from c:\mingw\include\c++\9.2.0\bits\hashtable.h:35,
                 from c:\mingw\include\c++\9.2.0\unordered_map:46,
                 from c:\mingw\include\c++\9.2.0\functional:61,
                 from c:\mingw\include\c++\9.2.0\pstl\glue_algorithm_defs.h:13,
                 from c:\mingw\include\c++\9.2.0\algorithm:71,
                 from stdc++.h:65:
c:\mingw\include\c++\9.2.0\bits\hashtable_policy.h: In instantiation of 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::__hash_code std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::_M_hash_code(const _Key&) const [with _Key = std::__cxx11::basic_string<char>; _Value = std::pair<const std::__cxx11::basic_string<char>, int>; _ExtractKey = std::__detail::_Select1st; _H1 = chash; _H2 = std::__detail::_Mod_range_hashing; std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::__hash_code = long long unsigned int]':
c:\mingw\include\c++\9.2.0\bits\hashtable.h:1449:19:   required from 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::size_type std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::count(const key_type&) const [with _Key = std::__cxx11::basic_string<char>; _Value = std::pair<const std::__cxx11::basic_string<char>, int>; _Alloc = std::allocator<std::pair<const std::__cxx11::basic_string<char>, int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::__cxx11::basic_string<char> >; _H1 = chash; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>; std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::size_type = long long unsigned int; std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::key_type = std::__cxx11::basic_string<char>]'
c:\mingw\include\c++\9.2.0\bits\unordered_map.h:939:30:   required from 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::count(const key_type&) const [with _Key = std::__cxx11::basic_string<char>; _Tp = int; _Hash = chash; _Pred = std::equal_to<std::__cxx11::basic_string<char> >; _Alloc = std::allocator<std::pair<const std::__cxx11::basic_string<char>, int> >; std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type = long long unsigned int; std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::key_type = std::__cxx11::basic_string<char>]'
C:\Users\Home-T410\Desktop\Vim\B.cpp:30:17:   required from here
c:\mingw\include\c++\9.2.0\bits\hashtable_policy.h:1382:16: error: static assertion failed: hash function must be invocable with an argument of key type
 1382 |  static_assert(__is_invocable<const _H1&, const _Key&>{},
      |                ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
c:\mingw\include\c++\9.2.0\bits\hashtable_policy.h:1384:16: error: no match for call to '(const chash) (const std::__cxx11::basic_string<char>&)'
 1384 |  return _M_h1()(__k);
      |         ~~~~~~~^~~~~
C:\Users\Home-T410\Desktop\Vim\B.cpp:13:12: note: candidate: 'size_t chash::operator()(uint64_t) const'
   13 |     size_t operator()(uint64_t x) const {
      |            ^~~~~~~~
C:\Users\Home-T410\Desktop\Vim\B.cpp:13:32: note:   no known conversion for argument 1 from 'const std::__cxx11::basic_string<char>' to 'uint64_t' {aka 'long long unsigned int'}
   13 |     size_t operator()(uint64_t x) const {
      |                       ~~~~~~~~~^
shell returned 1

I also tried out the custom hash from Benq's article on USACO-Guide. It spits out the same error. However, taking away the chash in the unordered_map removes the error.

Somebody please help.

  • Vote: I like it
  • -1
  • Vote: I do not like it

7 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

You are trying to hash strings, but the function object you provided hashes longs.