I was looking at this post C unordered_map using a custom class type as the key
- I understand that we need to redefine
equalityandhash codefor a custom type key. - I know how the operator overloading works in general.
However, what does operator() have to do with the hash code?
Does unordered_map internally evaluate a key with () operator somewhere?
CodePudding user response：
The std::unordered_map uses an std::hash object to calculate the hash-values.
It will use the hash-object like a function, calling the operator() to do the calculation.
As a simple example, for an int key, it will be something like this:
int key = 123; // Or whatever value...
std::hash<int> hash_object;
auto hash_value = hash_object(key); // Calls hash_object.operator()(key)
CodePudding user response：
std::unordered_map in its full definition looks like the below according to cpp-reference:
template<
class Key,
class T,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;
As you can see, it has template arguments for the has function, the equality checker and the allocater. We will not look at the allocator in this answer.
As you can see, it needs hasing capability for the key-type and and equal_to functionality for the key-type.
So, in order to use it, we could specialize both structs used as default, so std::hash and std::equal_to.
In order to do that, we need to open the std namespace which is basically not that nice.
However, we could do:
#include <iostream>
#include <unordered_map>
#include <functional>
struct Test {
char a{};
char b{};
char c{};
};
namespace std {
template <>
struct hash<Test> {
size_t operator()(const Test& t) const {
return (((size_t)t.a) << 16) (((size_t)t.b) << 8) ((size_t)t.c);
}
};
template <>
struct equal_to<Test> {
bool operator()(const Test& lhs, const Test& rhs) const {
return lhs.a == rhs.a and lhs.b == rhs.b and lhs.c == rhs.c;
}
};
}
int main() {
std::unordered_map<Test, int> test{};
Test t1{ 'a', 'b', 'c' };
Test t2{ 'd', 'e', 'f' };
test[t1] = 1;
test[t2] = 2;
for (const auto& [key, value] : test)
std::cout << key.a << ' ' << key.b << ' ' << key.c << " --> " << value << '\n';
}
With the above Functor specializations, we can use the class, without any further template parameter.
But of course we could also define dedicated Functors. But then we need to hand in the names of the functors as template parameters
This could then look like:
#include <iostream>
#include <unordered_map>
#include <functional>
struct Test {
char a{};
char b{};
char c{};
};
struct hashTest {
size_t operator()(const Test& t) const {
return (((size_t)t.a) << 16) (((size_t)t.b) << 8) ((size_t)t.c);
}
};
struct equal_toTest {
bool operator()(const Test& lhs, const Test& rhs) const {
return lhs.a == rhs.a and lhs.b == rhs.b and lhs.c == rhs.c;
}
};
int main() {
std::unordered_map<Test, int, hashTest, equal_toTest> test{};
Test t1{ 'a', 'b', 'c' };
Test t2{ 'd', 'e', 'f' };
test[t1] = 1;
test[t2] = 2;
for (const auto& [key, value] : test)
std::cout << key.a << ' ' << key.b << ' ' << key.c << " --> " << value << '\n';
}
This is not so nice any longer, because of the additional template parameter, but anyway.
Next, we could also use Lambdas.
But, you can't directly pass the closure type as a template argument and need to construct the containers member from another closure object. (Closure types don't have a default constructor!). For a block-scope std::unorderd_map this is somehow ok. But in general it is somhow clumsy.
Please see for yourself:
#include <iostream>
#include <unordered_map>
#include <functional>
struct Test {
char a{};
char b{};
char c{};
};
struct equal_toTest {
bool operator()(const Test& lhs, const Test& rhs) const {
return lhs.a == rhs.a and lhs.b == rhs.b and lhs.c == rhs.c;
}
};
int main() {
auto equalTest = [](const Test& lhs, const Test& rhs) -> bool { return lhs.a == rhs.a and lhs.b == rhs.b and lhs.c == rhs.c; };
auto hasher = [](const Test& t)->size_t {return (((size_t)t.a) << 16) (((size_t)t.b) << 8) ((size_t)t.c); };
std::unordered_map < Test, int, decltype(hasher), decltype(equalTest)> test{};
Test t1{ 'a', 'b', 'c' };
Test t2{ 'd', 'e', 'f' };
test[t1] = 1;
test[t2] = 2;
for (const auto& [key, value] : test)
std::cout << key.a << ' ' << key.b << ' ' << key.c << " --> " << value << '\n';
}
Ok, hard to understand, and maybe not that useful.
Next, if we read about std::equal here it will call:
bool operator()( const T& lhs, const T& rhs ) const;
And this we can also directly implement in our "Test" struct. Then we can omit one template parameter.
#include <iostream>
#include <unordered_map>
#include <functional>
struct Test {
char a{};
char b{};
char c{};
bool operator==(const Test& t) const { return a == t.a and b == t.b and c == t.c; }
};
struct hashTest {
size_t operator()(const Test& t) const {
return (((size_t)t.a) << 16) (((size_t)t.b) << 8) ((size_t)t.c);
}
};
int main() {
std::unordered_map<Test, int, hashTest> test{};
Test t1{ 'a', 'b', 'c' };
Test t2{ 'd', 'e', 'f' };
test[t1] = 1;
test[t2] = 2;
for (const auto& [key, value] : test)
std::cout << key.a << ' ' << key.b << ' ' << key.c << " --> " << value << '\n';
}
Of course this will also work with a class external bool comparison operator for our type "Test"
#include <iostream>
#include <unordered_map>
#include <functional>
struct Test {
char a{};
char b{};
char c{};
};
bool operator==(const Test& l, const Test& r) { return l.a == r.a and l.b == r.b and l.c == r.c; }
struct hashTest {
size_t operator()(const Test& t) const {
return (((size_t)t.a) << 16) (((size_t)t.b) << 8) ((size_t)t.c);
}
};
int main() {
std::unordered_map<Test, int, hashTest> test{};
Test t1{ 'a', 'b', 'c' };
Test t2{ 'd', 'e', 'f' };
test[t1] = 1;
test[t2] = 2;
for (const auto& [key, value] : test)
std::cout << key.a << ' ' << key.b << ' ' << key.c << " --> " << value << '\n';
}
Unfortunately that is not possible with the hash function. You can add the function to calculate the hash to your class "Test", but you need to name it as template parameter.
#include <iostream>
#include <unordered_map>
#include <functional>
struct Test {
char a{};
char b{};
char c{};
bool operator==(const Test& t) const { return a == t.a and b == t.b and c == t.c; }
size_t operator()(const Test& t) const { return (((size_t)t.a) << 16) (((size_t)t.b) << 8) ((size_t)t.c); }
};
struct hashTest {
};
int main() {
std::unordered_map<Test, int, Test> test{};
Test t1{ 'a', 'b', 'c' };
Test t2{ 'd', 'e', 'f' };
test[t1] = 1;
test[t2] = 2;
for (const auto& [key, value] : test)
std::cout << key.a << ' ' << key.b << ' ' << key.c << " --> " << value << '\n';
}
There are more potential solutions by mixing up the methods above.
But you should now get a better understanding.