Search code examples
c++stdset

std::set with personal comparison function have identical values


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!


Solution

  • 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).