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 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_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

Answer 1

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.