最好的辦法湊頂點

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