When should we provide our own Hash function for `std::unordered_set`
c++, c++11, stl
Solution
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.
Problem
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