hashmap为2d（3d）坐标（即向量的双精度）？ [英] hashmap for 2d(3d) coordinates (i.e. vector of doubles)?

问题描述

我想知道对于坐标（在2d或3d，即双精度向量）中哈希映射是否有一个全面的解决方案？

示例此处演示如何为 pair< int，int> ，
创建一个自定义哈希映射，但它似乎并不重要，从 pair< double，double> （可代表2d坐标）到 size_t 。

我知道我可以通过提供比较器对象使用有序映射，但是对于我的应用程序，没有必要排序它们，哈希映射似乎更快。
然而，因为我是所有这个 hash 的新手，我有点失去了如何继续。

p / s / i使用c ++ 11。

解决方案

为了避免额外的依赖，您可以使用 std :: hash 。下面是一个使用您发布的链接的代码的示例，并更新为使用 std :: pair< double，double> ：

  #include< unordered_map> 
 #include< cassert> 
 
 using namespace std; 
 
 class TPoint3D {
 public：
 TPoint3D（double x，double y，double z）：x（x），y​​（y），z（z）{}; 
 
 double x，y，z; 
}; 
 
 struct hashFunc {
 size_t operator（）（const TPoint3D& k）const {
 size_t h1 = std :: hash< double>（k.x） 
 size_t h2 = std :: hash< double>（）（k.y）; 
 size_t h3 = std :: hash< double>（）（k.z）; 
 return（h1 ^（h2 <1））^ h3; 
} 
}; 
 
 struct equalsFunc {
 bool operator（）（const TPoint3D& lhs，const TPoint3D& rhs）const {
 return（lhs.x == rhs.x）&& ; （lhs.y == rhs.y）&& （lhs.z == rhs.z）; 
} 
}; 
 
 typedef unordered_map< TPoint3D，int，hashFunc，equalsFunc> TPoint3DMap; 
 
 int main（）{
 TPoint3DMap myMap; 
 
 // test equalsFunc 
 myMap [TPoint3D（10.0，20.0，30.0）] = 100; 
 myMap [TPoint3D（10.0，20.0，30.0）] = 200; 
 
 assert（myMap [TPoint3D（10.0，20.0，30.0）] == 200）; 
 
 //测试如果hashFunc在TPoint3D内处理很好的重复值
 myMap [TPoint3D（10.0，10.0，10.0）] = 1; 
 myMap [TPoint3D（10.0，20.0，10.0）] = 2; 
 myMap [TPoint3D（10.0，10.0，20.0）] = 3; 
 myMap [TPoint3D（20.0，10.0，10.0）] = 4; 
 
 assert（myMap [TPoint3D（10.0，10.0，10.0）] == 1）; 
 assert（myMap [TPoint3D（10.0，20.0，10.0）] == 2）; 
 assert（myMap [TPoint3D（10.0，10.0，20.0）] == 3）; 
 assert（myMap [TPoint3D（20.0，10.0，10.0）] == 4）; 
 
 return 0; 
} 
  

如前所述，如果你想使用另一个结构， pairHash 类和 pairEquals struct operator（）

编辑：

• 使用自定义TPPoint3D类和统一函子类定义（均使用struct）的修改代码。


• 添加了简单的测试来验证哈希和equals函数。

I wonder if there is a general all-around solution for a hash map for coordinates (in 2d or 3d, i.e. a vector of doubles)?

An example here demonstrates how to create a custom hash-map for pair<int,int>, but it does not seem to be trivial to come-up with an unique map from pair<double,double> (which could represent a 2d coordinate) to size_t.

I know that i can use ordered maps by providing comparator object, but for my application there is no need to order them and hash-maps seems to be faster anyway. However since i'm a newcomer to all this hash stuff, i am kind of lost on how to proceed.

p/s/ i use c++11.

解决方案

To avoid extra dependencies, you can use std::hash. Here's an example using the code from the link you posted, and updated to use a std::pair<double,double>:

#include <unordered_map>
#include <cassert>

using namespace std;

class TPoint3D{
public:
    TPoint3D(double x, double y, double z) : x(x), y(y), z(z){};

    double x, y, z;
};

struct hashFunc{
    size_t operator()(const TPoint3D &k) const{
    size_t h1 = std::hash<double>()(k.x);
    size_t h2 = std::hash<double>()(k.y);
    size_t h3 = std::hash<double>()(k.z);
    return (h1 ^ (h2 << 1)) ^ h3;
    }
};

struct equalsFunc{
  bool operator()( const TPoint3D& lhs, const TPoint3D& rhs ) const{
    return (lhs.x == rhs.x) && (lhs.y == rhs.y) && (lhs.z == rhs.z);
  }
};

typedef unordered_map<TPoint3D, int, hashFunc, equalsFunc> TPoint3DMap;

int main(){
  TPoint3DMap myMap;

  // test equalsFunc
  myMap[TPoint3D(10.0, 20.0, 30.0)] = 100;
  myMap[TPoint3D(10.0, 20.0, 30.0)] = 200;

  assert(myMap[TPoint3D(10.0, 20.0, 30.0)] == 200);

  // test if hashFunc handles well repeated values inside TPoint3D
  myMap[TPoint3D(10.0, 10.0, 10.0)] = 1;
  myMap[TPoint3D(10.0, 20.0, 10.0)] = 2;
  myMap[TPoint3D(10.0, 10.0, 20.0)] = 3;
  myMap[TPoint3D(20.0, 10.0, 10.0)] = 4;

  assert(myMap[TPoint3D(10.0, 10.0, 10.0)] == 1);
  assert(myMap[TPoint3D(10.0, 20.0, 10.0)] == 2);
  assert(myMap[TPoint3D(10.0, 10.0, 20.0)] == 3);
  assert(myMap[TPoint3D(20.0, 10.0, 10.0)] == 4);

  return 0;
}

As I said before, if you wish to use another structure you have to adapt both the pairHash class and pairEquals struct operator() to appropriately hash and compare the new keys, respectively.

Cheers

EDIT :

• Modified code to use custom TPPoint3D class and uniform functor classes definitions (both using struct).
• Added simple tests to validate the hash and equals functors.

这篇关于hashmap为2d（3d）坐标（即向量的双精度）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！