散列顶点的最佳方式

Question

我有以下代码，我想将其输入到一个无序集合中，以便根据其三维坐标进行最快的访问。

struct MeshVertex {
float x;
float y;
float z;
std::vector<MeshVertex*> links;
float& operator [](int i) {
switch (i) {
case 0:
return x;
case 1:
return y;
case 2:
return z;
default:
throw std::out_of_range("");
}
}
MeshVertex& operator=(const STLFileVertex& other)
{
x = other.x;
y = other.y;
z = other.z;
return *this;
}
bool operator<(const MeshVertex& other) const
{
if (x == other.x) {
if (y == other.y)
return z < other.z;
return y < other.y;
}
return x < other.x;
}
bool operator==(const MeshVertex& other) const {
if (x == other.x && y == other.y && z == other.z)
return true;
return false;
}
bool operator!=(const MeshVertex& other) const {
if (x == other.x && y == other.y && z == other.z)
return false;
return true;
}
double distance(const MeshVertex& other) const {
return hypot(hypot(x - other.x, y - other.y), z - other.z);
}
};

不出所料，我得到了以下错误：

The C++ Standard doesn't provide a hash for this type.

如何实现性能良好的哈希？它只需要包含成员x、y和z，并且哈希和比较的组合必须100%无冲突，这意味着只有当新插入的顶点具有完全相同的值时，才能替换顶点。请考虑顶点是用float类型表示的。这意味着正常的比较可能会产生误导。

编辑：

我真正做的是读取STL(立体光刻)二进制文件。熟悉STL格式的人会知道三角形在文件中是这样写的：

float normals[3];
float vertex[3][3];
uint16_t attributes;

这意味着在读取文件时，顶点会被复制得更多。我想规范化顶点(删除重复项)并应用链接来重新创建三角形。

我的目标是通过广度优先搜索映射图中的所有顶点。如前所述，链接在三角形中可用。在获得所有链接后，三角形将成为可丢弃的。

如果我没有删除重复顶点的完美方法，链接将断开，映射将失败。

Answer 1

有5个简单的步骤可以结束您的std::hash困境。

TL；DR—尽早转储std::hash并使用boost。就像自c++11以来强加给我们的许多标准库一样，它是之前(并且优于)它的boost库的一个暗淡的影子。

#include <boost/functional/hash.hpp>
#include <unordered_map>
#include <tuple>
#include <type_traits>
struct MeshVertex {
float x;
float y;
float z;
// step one - make your life easier and provide an as_tuple
// method
auto as_tuple() const {
return std::tie(x, y, z);
}
};
// step 2 all operators in terms of tuple
bool operator == (MeshVertex const& l, MeshVertex const& r)
{
return l.as_tuple() == r.as_tuple();
}
// step 2 all operators in terms of tuple
bool operator < (MeshVertex const& l, MeshVertex const& r)
{
return l.as_tuple() < r.as_tuple();
}
// step 3 - use the boost::hash protocol of providing a free function
// called hash_value in the namespace of MeshVertex. std::hash sucks.
std::size_t hash_value(MeshVertex const& arg)
{
std::size_t seed = 0;
boost::hash_combine(seed, arg.as_tuple());
return seed;
}
// step 4 - define your own hash algo to escape from the
// std::hash fiasco.
struct universal_hash
{
template<class T> std::size_t operator()(T&& arg) const
{
// note - boost::hash. A thousand times better.
using hasher_type = boost::hash<std::decay_t<T>>;
auto hasher = hasher_type();
return hasher(arg);
}
};

int main()
{
// step 5 - never under any circumstances allow your containers
// to inflict std::hash on you 
std::unordered_map<int, MeshVertex, universal_hash> mymap;
mymap[1] = { 1, 3, 4 };
}