c++ - 散列 2D 点的有效方法

Question

好的，所以任务是这样的，我会得到 (x, y) 点的坐标，其中 (x, y) 的范围从 -10^6 到 10^6(含)。我必须检查某个特定点是否(x, y) 元组是否给了我。简而言之，我如何回答是否设置了特定点(2D)的查询。到目前为止，我能想到的最好的方法是维护 std::map<std::pair<int,int>, bool>每当给出一个点时，我都会将其标记为 1。虽然这必须以对数时间运行并且是回答查询的相当优化的方式，但我想知道是否有更好的方法来做到这一点。

此外，如果有人能说出如果我将上述数据结构用作散列，实际复杂度是多少，我将很高兴。我的意思是 std::map 的复杂度无论键的结构如何，元素的大小都将是 O(log N)？

Answer 1

为了使用 HashMap ，您需要使用 std::unordered_map而不是 std::map .使用它的限制是您的值类型需要有一个为其定义的哈希函数，如所述 in this answer .或者只是使用 boost::hash为此:

std::unordered_map<std::pair<int, int>, boost::hash<std::pair<int, int> > map_of_pairs;

我想到的另一种方法是将 32 位 int 值存储在 64 位整数中，如下所示:

uint64_t i64;
uint32_t a32, b32;
i64 = ((uint64_t)a32 << 32) | b32;

如 this answer 中所述. x 和 y 分量可以存储在整数的高字节和低字节中，然后您可以使用 std::unordered_map<uint64_t, bool> .尽管我很想知道这是否比以前的方法更有效，或者它是否会生成不同的代码。