I encountered the problem of trying to put custom data structures into the key of an unordered map and found different answers all over the Internet. The same question came up on the sparsehash mailing list so I thought I’d put an example up here:
#include <cstdlib>
#include <iostream>
#include <google/dense_hash_map>
using google::dense_hash_map;
using namespace std;
struct Vector3D{
uint32_t x;
uint32_t y;
uint32_t z;
Vector3D(const uint32_t x,const uint32_t y,const uint32_t z):
x(x),y(y),z(z)
{}
Vector3D():
x(0),y(0),z(0)
{}
};
typedef struct{
inline size_t operator() (const Vector3D& v) const {
return (v.x*73856093)^(v.y*19349663)^(v.z*83492791);
}
} Vector3DHash;
typedef struct{
inline bool operator() (const Vector3D& lhs, const Vector3D &rhs) const {
return (lhs.x==rhs.x)&&(lhs.y==rhs.y)&&(lhs.z==rhs.z);
}
} Vector3DEq;
typedef dense_hash_map<Vector3D,uint32_t,Vector3DHash,Vector3DEq> vector_map_t;
int main(int argc, char** argv) {
const uint32_t MAX_DISTANCE = 1000;
const size_t LOOP_COUNT = 100000;
vector_map_t vectors;
// This assumes a vector with x:0 y:0 z:0 will never exist
// If this is not true use tr1/unordered_map !!!
vectors.set_empty_key(Vector3D());
// Fill with some random vectors and keys
for(size_t i=0;i<LOOP_COUNT;i++){
Vector3D v(rand()%MAX_DISTANCE+1,rand()%MAX_DISTANCE+1,rand()%MAX_DISTANCE+1);
vectors[v]=rand();
}
// Display whole map
for(vector_map_t::const_iterator it=vectors.begin(),ite=vectors.end();it!=ite;++it){
cout << "Vector with x: " << it->first.x <<" y: " << it->first.y << " z: " << it->first.z << " has value: " << it->second << endl;
}
// Do some random lookups
for(size_t i=0;i<LOOP_COUNT;i++){
Vector3D v(rand()%MAX_DISTANCE+1,rand()%MAX_DISTANCE+1,rand()%MAX_DISTANCE+1);
vector_map_t::const_iterator it=vectors.find(v);
if (it!=vectors.end()){
cout << "Found vector with x: " << it->first.x <<" y: " << it->first.y << " z: " << it->first.z << " value: " << it->second << endl;
}
}
return 0;
}
The trick is to define both a hash and an equality function for the custom data structure. The prime numbers in the 3D vector hash function come from this paper . The “correct” hash function depends a lot on the distribution of the keys and only real world benchmarking will give a satisfactory answer as to what works best for your data.
The output of the above code would be something like:
$g++ vector_map.cpp -o vector_test && ./vector_test
Vector with x: 645 y: 413 z: 958 has value: 1312704908
Vector with x: 496 y: 358 z: 749 has value: 1988979514
Vector with x: 223 y: 868 z: 203 has value: 141221503
Vector with x: 345 y: 350 z: 869 has value: 1678149073
Vector with x: 565 y: 366 z: 722 has value: 1934444366
Vector with x: 934 y: 419 z: 619 has value: 560261625
Vector with x: 426 y: 92 z: 351 has value: 427818382
Vector with x: 24 y: 263 z: 407 has value: 760253072
...
...
...
Vector with x: 124 y: 98 z: 792 has value: 1145850991
Vector with x: 907 y: 710 z: 889 has value: 765247744
Vector with x: 779 y: 248 z: 943 has value: 976951297
Vector with x: 917 y: 929 z: 736 has value: 112463024
Found vector with x: 744 y: 492 z: 624 value: 1436855325
Found vector with x: 587 y: 110 z: 825 value: 24739836
Found vector with x: 707 y: 356 z: 243 value: 1515119730
Found vector with x: 610 y: 194 z: 331 value: 19997493
Found vector with x: 693 y: 59 z: 907 value: 502595634
Found vector with x: 57 y: 128 z: 923 value: 100460565
Found vector with x: 15 y: 512 z: 879 value: 248460847
Found vector with x: 256 y: 434 z: 859 value: 313975801
Found vector with x: 388 y: 42 z: 542 value: 473907356
Found vector with x: 409 y: 822 z: 963 value: 100666490