std::set with personal comparison function have identical values

Question

I want to store a std::set of Point3D object, my comparison function is defined as follows (lexicographic order):

bool operator<(const Point3D &Pt1, const Point3D &Pt2)
{
    const double tol = 1e-5;

    if(fabs(Pt1.x() - Pt2.x()) > tol)
    {
        return Pt1.x() < Pt2.x();
    }    
    else if(fabs(Pt1.y() - Pt2.y()) > tol)
    {
        return Pt1.y() < Pt2.y();
    }
    else if(fabs(Pt1.z() - Pt2.z()) > tol)
    {
        return Pt1.z() < Pt2.z();
    }
    else
    {
        return false;
    }
}

In some case the set contains identical point, I think the problem come from the comparison function, but I don't find exactly the problem. Any help would be appreciated!

Your comparison operator needs to implement strict weak ordering: http://stackoverflow.com/questions/979759/operator-and-strict-weak-ordering — EdChum, Jun 09 '14 at 10:41
So the question is: how to implement strict weak ordering with `double` and tolerance? — nathanael, Jun 09 '14 at 10:53
Well your code currently only tests each x,y,z coords individually, you'd need to test if all are less than epsilon and then return false — EdChum, Jun 09 '14 at 10:57
@EdChum but if all three differences are less than epsilon, operator returns false as it is. — undermind, Jun 09 '14 at 11:02
These seem to be points in space. Have you considered using Euclidean distance for ordering? The tolerance would be simpler to implement. — , Jun 09 '14 at 11:12

Mankarse · Accepted Answer · 2014-06-09T11:21:47.773

Your tolerance concept does not correctly establish a strict weak ordering, since it is not transitive. For the sake of example, imagine the tolerance were 1. Now consider:

a = 1
b = 2
c = 3

here: !(a<b) and !(b<c), but a<c. This is a clear violation of the transitivity requirement for a strict weak ordering.

If you want to implement a comparison that has tolerance, but which also is a strict weak ordering, you have to round every value in a consistent fashion (eg, 1.5 => 2, 0.75 => 1, 2.3 => 2, etc) and then compare the rounded values.

Doing this seems very pointless, as doubles already do this, but at the maximum possible precision. You'll still get strange behaviour when you find that 1.4999999... != 1.5.

You should just write your comparator as follows, and abandon the tolerance concept:

bool operator<(const Point3D &Pt1, const Point3D &Pt2)
{
    //This can be replaced with a member/free function if it is used elsewhere
    auto as_tie = [](Point3D const &Pt) {
        //assumes the member functions return references
        //to the internal `Point3D` values.
        return std::tie(Pt.x(), Pt.y(), Pt.z());
    };
    return as_tie(Pt1) < as_tie(Pt2);
}

If you absolutely must have a tolerance, round the values as soon as they are put into the Point3D, or round the values immediately before the comparison (depending on the other requirements in your system).

In my case I need use of tolerance and round value just before comparison: `static_cast(xDouble*std::pow(10,nbDecimal)+0.5)` for each coords. — nathanael, Jun 09 '14 at 19:41

std::set with personal comparison function have identical values

1 Answers1