用于插入 std::unordered_set 的 3D 整数坐标的唯一键
Unique key for 3D interger coordinates to insert into a std::unordered_set
我有一个 3D 整数坐标流，对应于体素，因此在网格上对齐。我想弄清楚当前处理的三元组是否已经存在，以便过滤重复项。我能够使用 std::set 构建一个简单的解决方案来解决我的问题。设 x y z 为 3 int，registry 为 std::set< std::array<int, 3> >。我做了一个 return 和 bool 一样的函数
std::array<int, 3> key = {x, y, z};
return registry.insert(key).second;
但这在计算时间方面还有待优化。阅读文档和 SO 主题我明白 unordered_set 应该更合适。事实上，这里没有必要对任何东西进行排序。此外，我猜想使用 array<int,3> 作为键在 insert 时间进行比较效率不高。
一个unordered_set需要一个散列函数。研究哈希函数我发现 boost::hash_combine 以及其他选项。
如何在我的情况下有效地使用 unordered_set？关键点是尽可能快。我不需要访问值，也不需要进行任何特殊计算。
哇哦不要为这样的事情使用矢量。它动态分配。您正在消灭 您程序的缓存潜力。
只有三个 int，所以只需制作一个包含三个 int 的 struct。或者传递一个std::array<int, 3> around.
然后再次测量，看看会发生什么。您可能会发现该集合现在没问题了。如果没有，那么，您可以为三个 int 创建一个散列。不过，不要费心尝试提出一个始终提供唯一值的哈希函数，因为这实际上违背了哈希函数的目的。
如果仍然太慢，那么您可能需要考虑为此提出一个合适的算法，因为 set 和 unordered_set 仍将动态分配节点。这只是一个间接级别，而不是你现在拥有的两个级别，但零比 none.
更好
我回答我自己的问题。我最初的问题是错误的，但感谢@Damien，我理解了如何将散列用于 std::unordered_*。我用了 boost
#include <boost/functional/hash.hpp>
然后我将 registry 定义如下
typedef std::array<I32,3> Array;
std::unordered_set<Array, boost::hash<Array> >
我获得了大约 33% 的计算时间。
我有一个 3D 整数坐标流，对应于体素，因此在网格上对齐。我想弄清楚当前处理的三元组是否已经存在，以便过滤重复项。我能够使用 std::set 构建一个简单的解决方案来解决我的问题。设 x y z 为 3 int，registry 为 std::set< std::array<int, 3> >。我做了一个 return 和 bool 一样的函数
std::array<int, 3> key = {x, y, z};
return registry.insert(key).second;
但这在计算时间方面还有待优化。阅读文档和 SO 主题我明白 unordered_set 应该更合适。事实上，这里没有必要对任何东西进行排序。此外，我猜想使用 array<int,3> 作为键在 insert 时间进行比较效率不高。
一个unordered_set需要一个散列函数。研究哈希函数我发现 boost::hash_combine 以及其他选项。
如何在我的情况下有效地使用 unordered_set？关键点是尽可能快。我不需要访问值，也不需要进行任何特殊计算。
哇哦不要为这样的事情使用矢量。它动态分配。您正在消灭 您程序的缓存潜力。
只有三个 int，所以只需制作一个包含三个 int 的 struct。或者传递一个std::array<int, 3> around.
然后再次测量，看看会发生什么。您可能会发现该集合现在没问题了。如果没有，那么，您可以为三个 int 创建一个散列。不过，不要费心尝试提出一个始终提供唯一值的哈希函数，因为这实际上违背了哈希函数的目的。
如果仍然太慢，那么您可能需要考虑为此提出一个合适的算法，因为 set 和 unordered_set 仍将动态分配节点。这只是一个间接级别，而不是你现在拥有的两个级别，但零比 none.
更好我回答我自己的问题。我最初的问题是错误的，但感谢@Damien，我理解了如何将散列用于 std::unordered_*。我用了 boost
#include <boost/functional/hash.hpp>
然后我将 registry 定义如下
typedef std::array<I32,3> Array;
std::unordered_set<Array, boost::hash<Array> >
我获得了大约 33% 的计算时间。