最好的办法凑顶点

Question

我有以下的代码，我想输入的基础上其3D最快访问可能的unordered_set坐标。

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