将参数传递给 unordered_map（或设置）哈希结构

Question

我有以下结构：

array<int, 2> map_size;

struct Node{
    int id;
    array<int, 2> pos;
    vector<Node*> nbs;
    bool in_open;
    bool in_closed;
};

每个节点都有一个在 map_size（全局变量）范围内的位置 (pos)。

我正在使用以下无序映射

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 是散列函数中使用的全局变量，可以让我得到一个完美的散列。但是，我想将 map_size 作为参数传递给 PosHash，这样可以避免使用全局变量。我该怎么做？

PD: map_size 值在执行时确定

Answer 1

您可以将 map_size 作为 PosHash 结构中的数据成员。

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
};

然后你可以用需要的map_size数组构造一个PosHash对象。将此对象传递给您的 unordered_map

PosHash myPosHash({1, 2});

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

查看 std::unordered_map here 的不同可用构造函数。您需要在 hasher 参数之前明确指定所有参数。这些将取决于您的需要。我能想到的最简单的是

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

Answer 2

这是一个完整的程序，展示了如何构造一个 PosHash 对象来存储特定值。请注意，您不需要自定义比较 - std::array 无论如何都以相同的方式进行比较。

#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';
}

更一般地说，这是一个“弱”散列函数。它在生成散列值足以避免散列值 space 中的冲突方面可能是“完美的”，但这并不意味着如果将 space 折叠成散列值就不会发生冲突较少数量的桶。

将参数传递给 unordered_map（或设置）哈希结构

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

c++

unordered-map

hash-function

unordered-set