使用 unordered_map with key 仅存储指针（忽略值）
Using unordered_map with key only to store pointers (dismiss value)
我正在实施一种算法，用于检查网格中节点的特定值。要存储关于我已经检查过的节点的信息，我想使用 unordered_map 并将指向该节点的指针作为键。然后我可以简单地使用 umap.find(pointer) 来查看节点是否已经被检查并跳过它。这样我就可以在 O(n) 时间内完成。
但是我不需要实际存储地图的值。密钥本身就是足够的信息。 std::unordered_map 是正确的解决方案吗？如果是这样，我应该为“值”字段最大化性能添加什么？我有一个 32 位嵌入式系统，所以我想把 uint32_t 或 uint_fast32_t 放在那里。
tl;博士：
- std::unordered_map 是存储没有值的键的正确工具吗？
- 本机哈希函数是否适用于指针？或者您会建议使用不同的哈希算法吗？
- 如果使用 std::unordered_map 来优化性能，我应该将什么作为地图的“价值”？
Is std::unordered_map the right tool to store keys without values?
在这些情况下我会使用 std::unordered_set。
Will the native hash function work well for pointers?
是的。它很可能只是从指针到 std::size_t.
的转换
What do I put as "value" for the map if using std::unordered_map to optimize for performance?
如果您改用 std::unordered_set，则没有任何值，只有指针。
Is std::unordered_map the right tool to store keys without values?
否 - std::unordered_set 是当您没有不同的键和值时使用的。
Will the native hash function work well for pointers? Or would you suggest a different hashin algorithm?
“本机”编译器提供的散列函数可能会将指针值转换为 size_t - 一种 身份散列 。根据您的标准库选择的折衷方案，这可能会或可能不会很好地工作。 GCC 和 clang 在散列 table 中使用素数的桶，因此它可以正常工作。 Visual C++（以及许多非标准哈希 table 实现）使用 2 的幂（即 128、256、512...）。使用 2 的幂是因为将它们映射到桶上的速度非常快 - 只需使用按位掩码 (127, 255, 511) AND 来保留你需要的许多不太重要的位。使用指针这样做的问题是指向的对象通常有一些对齐方式，所以它们可能都是例如的倍数。 4 或 8。8 的倍数始终将三个最低有效位设置为 0：这些位不会影响桶中值的随机放置。相反，只有每第 8 个桶将接收任何份额的被散列的元素。如果您有这样的实现，那么您最好使用更好的散列函数。至少，您可以说将指针值右移足以删除已知的零。
What do I put as "value" for the map if using std::unordered_map to optimize for performance?
同样，您应该使用 std::unordered_set，因此不必担心值。
我正在实施一种算法，用于检查网格中节点的特定值。要存储关于我已经检查过的节点的信息，我想使用 unordered_map 并将指向该节点的指针作为键。然后我可以简单地使用 umap.find(pointer) 来查看节点是否已经被检查并跳过它。这样我就可以在 O(n) 时间内完成。
但是我不需要实际存储地图的值。密钥本身就是足够的信息。 std::unordered_map 是正确的解决方案吗？如果是这样，我应该为“值”字段最大化性能添加什么？我有一个 32 位嵌入式系统，所以我想把 uint32_t 或 uint_fast32_t 放在那里。
tl;博士：
- std::unordered_map 是存储没有值的键的正确工具吗？
- 本机哈希函数是否适用于指针？或者您会建议使用不同的哈希算法吗？
- 如果使用 std::unordered_map 来优化性能，我应该将什么作为地图的“价值”？
Is
std::unordered_mapthe right tool to store keys without values?
在这些情况下我会使用 std::unordered_set。
Will the native hash function work well for pointers?
是的。它很可能只是从指针到 std::size_t.
What do I put as "value" for the map if using std::unordered_map to optimize for performance?
如果您改用 std::unordered_set，则没有任何值，只有指针。
Is std::unordered_map the right tool to store keys without values?
否 - std::unordered_set 是当您没有不同的键和值时使用的。
Will the native hash function work well for pointers? Or would you suggest a different hashin algorithm?
“本机”编译器提供的散列函数可能会将指针值转换为 size_t - 一种 身份散列 。根据您的标准库选择的折衷方案，这可能会或可能不会很好地工作。 GCC 和 clang 在散列 table 中使用素数的桶，因此它可以正常工作。 Visual C++（以及许多非标准哈希 table 实现）使用 2 的幂（即 128、256、512...）。使用 2 的幂是因为将它们映射到桶上的速度非常快 - 只需使用按位掩码 (127, 255, 511) AND 来保留你需要的许多不太重要的位。使用指针这样做的问题是指向的对象通常有一些对齐方式，所以它们可能都是例如的倍数。 4 或 8。8 的倍数始终将三个最低有效位设置为 0：这些位不会影响桶中值的随机放置。相反，只有每第 8 个桶将接收任何份额的被散列的元素。如果您有这样的实现，那么您最好使用更好的散列函数。至少，您可以说将指针值右移足以删除已知的零。
What do I put as "value" for the map if using std::unordered_map to optimize for performance?
同样，您应该使用 std::unordered_set，因此不必担心值。