Overloading operator for set

Question

I am using a std::set to implement a specific algorithm. The set had duplicates in it, so I assume I had to overload the operator. The overload looks like this.

class Vec3f {
    ...

    bool operator () ( const Vector3f& v0, const Vector3f& v1 ) const {
    float epsilon = 1e-7;
    return ((v1[0] - v0[0]) > epsilon) &&  ((v1[1] - v0[1]) > epsilon) && ((v1[2] - v0[2]) > epsilon);
}       ...


"Vec3f.h"

int main(){
    ...
    std::set<Vec3f,Vec3f> visited;
    ...
}

I overloaded it so I could use the < operator needed in std::set. This function returns true if v0 < v1 to some margin. It removes the duplicates, but it also removes valid values in the set. I know my set is supposed have to 12 Vec3fs. With the duplicates, it has 24 Vec3fs. With my comparison function, it only has 3 Vec3f. I considered using absolute difference, but that violates strict weak ordering criterion. My question is: how do I write the comparison function to remove duplicates and keepd only the unique items?

Answer 1

As you have it now, every component in v0 needs to be less than every component in v1. This is not a strict weak ordering. You should check one component at a time. Only checking subsequent components if the component you are currently checking is equal. Also, you should drop the epsilon. While that's useful for checking equivalence of results of floating point calculations, it is not useful for ordering, because it too violates strict weak ordering. The easiest way to do this is to use operator< for std::tuple

return std::tie(v0[0], v0[1], v0[2]) < std::tie(v1[0], v1[1], v1[2]);

Otherwise, if you want to implement this manually, it's something like this:

if (v0[0] < v1[0]) return true;
if (v0[0] > v1[0]) return false;
if (v0[1] < v1[1]) return true;
if (v0[1] > v1[1]) return false;
if (v0[2] < v1[2]) return true;
if (v0[2] > v1[2]) return false;
return false;

Answer 2

Use std::abs to compare the difference from epsilon, like

if(std::abs(v1[0]-v0[1]) > epsilon && ...){...} // not zero

Otherwise you may get negative results which will always be smaller than your epsilon, and the norm test will fail.

PS: in general it is a bad idea to try to order vectors, as there is no intuitive mathematical oredering, and you may get into whole lots of weird and counterintuitive situations.

Answer 3

You mentioned that you simply want to use a set, not necessarily an implementation of a set which requires an ordering. You might consider using std::unordered_set, which doesn't require you to define an ordering, just hash/equality functions.