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 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 double
s 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).