Best way to hash a vertex

Question

I have the following code which I would like to input in an unordered_set for the fastest access possible based on its 3D coordinates.

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

As expected, I get the following error:

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

How do I implement a well performing hash for this? It only has to contain the members x, y and z and the combination of hash and comparison must be 100% free of collisions, meaning a vertex can only be replaced if the newly inserted one has exactly the same values. Please consider that the vertexes are represented by float type. Which means a normal comparison could be misleading.

Edit:

What I'm really doing is reading an STL (stereolithography) binary file. Those familiar with the STL format will know that triangles are written like this in the file:

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

That means vertexes will be duplicated more than often when reading the file. I want to normalize vertexes (removing duplicates) and apply links to recreate the triangles.

My goal is mapping all the vertexes in a graph, through Breadth-first search. The links, as previously mentioned, are available in the triangles. After getting all the links, the triangles become disposable.

If I don't have a perfect mean to remove duplicated vertexes, links will become broken and my mapping will fail.

Answer 1

There are 5 easy steps to end all your std::hash woes.

TL;DR - dump std::hash at the earliest opportunity and use boost. Like much of the standard library inflicted on us since c++11, it's a lacklustre shadow of the boost library that preceded (and outperforms) it.

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