I have the following struct:
array<int, 2> map_size;
struct Node{
int id;
array<int, 2> pos;
vector<Node*> nbs;
bool in_open;
bool in_closed;
};
Every Node has a position (pos) that is in range of map_size (global variable).
And I'm using the following unordered map
struct PosHash{
public:
size_t operator()(array<int, 2> const& pos) const{
return pos[1] + pos[0]*map_size[1];
}
};
struct PosCompare{
bool operator()(const array<int, 2>& pos1, const array<int, 2>& pos2) const{
if (pos1[0] == pos2[0] and pos1[1] == pos2[1]){
return true;
}
else{
return false;
}
}
};
unordered_map<array<int, 2>, Node*, PosHash, PosCompare> nodes;
map_size is a global variable used in the hash function and allows me to get a perfect hash. However, I would like to pass map_size as a parameter to PosHash and this way, avoid using global variables. How can I do this?
PD: map_size value is determined in execution time
Here's a complete program showing how to construct a PosHash
object storing a specific value. Note that you don't need a custom comparison - std::array
s are compared the same way anyway.
#include <iostream>
#include <array>
#include <unordered_map>
using Pos = std::array<int, 2>;
struct PosHash {
PosHash(int m) : m_{m} { }
size_t operator()(const Pos& pos) const {
return pos[1] + pos[0] * m_;
}
int m_;
};
int main()
{
static constexpr size_t initial_bucket_count = 5;
// for illustrative purposes, will just map to ints
std::unordered_map<Pos, int, PosHash> m{initial_bucket_count, PosHash{4}};
m[Pos{2, 3}] = 23;
m[Pos{1, 1}] = 11;
m[Pos{3, 1}] = 11;
m[Pos{3, 2}] = 32;
for (const auto& x : m)
std::cout << x.first[0] << ',' << x.first[1] << '=' << x.second << '\n';
}
More generally, this is a "weak" hash function. It may be "perfect" in producing hash values spread out enough to avoid collisions in the hash value space, but that doesn't mean you won't get collisions if you're folding that space into a lesser number of buckets.