When should we provide our own Hash function for `std::unordered_set`

Question

When I compile the following code, I saw the errors that are related to Hash.

int F_no_meaningA(unordered_set<vector<int>>& setVec, vector<int>& vec) 
{
    setVec.insert(vec);
    return 1;
}

int main()
{
  vector<int> W{2, 3, 7}; 
  unordered_set<vector<int>> setVec; 
}

$ g++ --version
g++ (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

$ g++ $1.cpp -o $1 -g -Wall -Weffc++ -pedantic -std=c++0x

/tmp/ccCQFQ4N.o: In function `std::__detail::_Hash_code_base

, std::vector >, std::_Identity > >, std::equal_to > >, std::hash > >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, false>::_M_hash_code(std::vector > const&) const': /usr/include/c++/4.6/bits/hashtable_policy.h:753: undefined reference to std::hash<std::vector<int, std::allocator<int> > ::operator()(std::vector<int, std::allocator<int> >) const' /tmp/ccCQFQ4N.o: In functionstd::__detail::_Hash_code_base , std::vector >, std::_Identity > >, std::equal_to > >, std::hash > >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, false>::_M_bucket_index(std::__detail::_Hash_node >, false> const*, unsigned int) const': /usr/include/c++/4.6/bits/hashtable_policy.h:763: undefined reference to `std::hash > ::operator()(std::vector >) const' collect2: ld returned 1 exit status

Then, I introduce the following own Hash and the problem is solved.

Question 1> When should we provide our own Hash for std::unordered_set? When should we provide our own Equivalent Function for std::unordered_set?

struct HashVector : unary_function<vector<int>, vector<int>::size_type> {
  vector<int>::size_type operator()(const vector<int>& vec) const {
    vector<int>::size_type sum = 0;
    for(int i : vec) {
      sum = sum*37 + hash<int>()(i);
    }
    return sum;
  }
};

int F_no_meaningB(unordered_set<vector<int>, HashVector>& setVec, vector<int>& vec) 
{
    setVec.insert(vec);
    return 1;
}

int main()
{
  vector<int> W{2, 3, 7}; 
  unordered_set<vector<int>, HashVector> setVec; 
}

warning: base class ‘struct std::unary_function, unsigned int>’ has a non-virtual destructor [-Weffc++]

Question 2> Why the g++ complain about the struct HashVector with the above warning?

Thank you

So you mean the compiler is not smarter enough to use std::hash<int> to iteratively go through all elements in vector? — q0987
It's not a matter of "smart" or "not smart". Your solution is a solution, not the solution for hashing containers. You might as well want any other behaviour. BTW, check out Boost.Hash and hash_combine and hash_range. — Bartek Banachewicz
@q0987 You need to provide your own hash function whenever the type stored in the container is not one which the standard provides a specialization for. If you can use Boost, it provides hash_range which will iterate over a container and generate a hash. — Praetorian

Mike Seymour Mike Seymour · Accepted Answer · 2013-07-17T16:42:55

When should we provide our own Hash for std::unordered_set?

When you're using a type that doesn't have a hash provided by the standard library. For example, it doesn't provide hash functions for the standard containers, including vector<int>.

Why the g++ complain about the struct HashVector with the above warning?

Because you've used -Weffc++ to request a (slightly over-zealous) warning to tell you whenever you inherit from a class with no virtual destructor. For most uses of inheritance (i.e. for polymorphism), you don't want to do that. However, in this case, inheritance is just used (or, some might say, abused) to inject some definitions into the class, so the warning does not indicate a problem.

Classes like std::unary_function are deprecated, so the best solution is not to inherit from it at all.

When should we provide our own Hash function for `std::unordered_set`

2 Answers