Hi,

I have an array of structs, each containing three elements:

class A { public: unsigned int x, y, z; };
//...
A* long_list; //Has at least 250,000 elements

. . . and I need to find a set of the unique structs in long_list.

I try to construct the set as follows:

unordered_set<A> mapping(/*passing in long_list's length to preallocate*/);
//Now .insert(...) each struct into the set

The problem is that this takes a ridiculously long amount of time (like 30 seconds in debug mode, 0.5 in release).

Also, the following:

namespace std {

template<> struct hash<typename my::A> {
	std::size_t operator()(const my::A& vr) const {
		std::hash<unsigned int> func;
		size_t h1 = func(vr.x);
		size_t h2 = func(vr.y);
		size_t h3 = func(vr.z);
		return h1+h2+h3;
	}
};

}

And:

bool operator==(const A& a, const A& b) {
	if (a.x!=b.x) return false;
	if (a.y!=b.y) return false;
	if (a.z!=b.z) return false;
	return true;
}

Maybe the hashing combination is leading to a lot of collisions? Anyway, why is this so slow?

Thanks,
-G

Computing the hash function as:

size_t h  = func(vr.x);
size_t h2 = func(vr.y);
size_t h3 = func(vr.z);
hash_combine(h,h2);
hash_combine(h,h3);
return h;

or:

size_t h = 0u;
hash_combine(h,vr.x);
hash_combine(h,vr.y);
hash_combine(h,vr.z);
return h;

. . . seems to give no noticeable improvement.
Thanks,

Oops. Well, removing the "preallocation" doesn't seem to do much. If anything, it's a bit faster, but not enough.