CODEWITHSUNDEEP
c++unordered-mapunordered-sethash-function
BMarin
BMarin

Reputation: 55

Pass a parameter to an unordered_map (or set) hash struct

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

Upvotes: 0

Views: 1012

Answers (2)

Tony Delroy
Tony Delroy

Reputation: 106116

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::arrays 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.

Upvotes: 1

User 10482
User 10482

Reputation: 1012

You can have map_size as a data member inside PosHash struct.

struct PosHash{
    public:
    size_t operator()(array<int, 2> const& pos) const{
        return pos[1] + pos[0]*map_size[1];
    }

    // Contructor that initializes the data member
    PosHash(std::intializer_list<int> map_dim) : map_size(map_dim) {
      // Other stuff
    };
    
    std::array<int, 2> map_size; // data member of the struct
};

Then you can construct a PosHash object with required map_size array. Pass this object to your unordered_map

PosHash myPosHash({1, 2});

std::unordered_map<array<int, 2>, Node*, PosHash, PosCompare> nodes(\\intial args\\, myPosHash);

Check out the different available constructors for std::unordered_map here. You need to explicitly specify all the arguments before the hasher argument. Those would depend on your needs. The simplest I can think of is

nodes(0, myPosHash);  //initial #buckets, hasher object

Upvotes: 1

Related Questions