passing operator== to set in c++

Question

I want to have a set<double> S; and insert some doubles into it. but I want the set to consider 1.0000001 == 1.0000000 (comparing doubles using epsilon) (I mean if I insert both of the numbers to the set, set.size() should equal to one). I know how to pass the operator() (for comparing) to the set but I don't know how to pass the function:

const double eps = 1e-8;
bool operator==(double a, double b)
{
    return abs(a - b) < eps;
}

to the set.

P.S: Thanks to Sid. @Sid: I found out that: operator== is not used by std::set. Elements a and b are considered equal iff !(a < b) && !(b < a).

I am not a C++ specialist but I am pretty sure that you are expected to use a transitive relation as comparison for sets. Your `operator==` is not transitive. — Pascal Cuoq, Feb 06 '12 at 18:34
@Complicatedseebio it doesn't matter which of the two numbers are in the set. It is important that one of them is in the set. — Farzam, Feb 06 '12 at 18:37
possible duplicate of [How do I initialize a std::set comparator?](http://stackoverflow.com/questions/3782702/how-do-i-initialize-a-stdset-comparator) — Bo Persson, Feb 06 '12 at 18:39
This definition of equality smells like trouble, as you are breaking the transitive property of the equality (if A==B and B==C then A==C). Take A=1, B=1+eps and C=1+2*eps, A==B, B==C, but A!=C. I wouldn't be surprised if this could break the implementation of the std::set in unpredictable ways. — Krzysztof Kozielczyk, Feb 06 '12 at 18:39
You probably want fabs( ) instead of abs( ). And the comparison function of interest will be less(). — Mark Taylor, Feb 06 '12 at 18:46

score 3 · Answer 1 · answered Feb 06 '12 at 18:57

The simple answer is that you can't, at least not that easily. You have to define a comparison operator which defines a strict weak ordering. If you have something like:

bool
cmpDouble( double lhs, double rhs )
{
    return abs( lhs - rhs ) < eps
        ? false
        : lhs < rhs;
}

then ! (a < b) && ! (b < a) doesn't define an equivalence relationship, so a major requirement isn't met.

It's possible to use something like:

bool
cmpDouble( double lhs, double rhs )
{
    double iLhs;
    modf( 1e8 * lhs, &iLhs );
    double iRhs;
    modf( 1e8 * rhs, &iRhs );
    return iLhs < iRhs;
}

But frankly, I suspect that if the source of your doubles requires this sort of thing, they probably aren't appropriate for storing in a set.

score 2 · Accepted Answer · edited May 23 '17 at 12:31

2

If you have the comparison function then why do you need operator== ? Take a look at the following thread.

std::set with user defined type, how to ensure no duplicates

Look at Mehrdad's answer.

edited May 23 '17 at 12:31

Community

1
1

answered Feb 06 '12 at 18:39

Sid

7,511
2
28
41

see the P.S I have a question – Farzam Feb 06 '12 at 18:52
Yes it's true. But you can control that behavior in your compare function. For example if a=1.0000000 and b=1.0000001 you can check if fabs(a-b) is less than 1e-6 (or whatever precision you want) then you return a false (that is neither is a less than b nor is b less than a) hence telling the that a and b are considered equal. – Sid Feb 06 '12 at 18:55
That won't fulfill the requirements of the comparator function, since `!comp(k1, k2) && !comp(k2, k1)` won't define an equivalence relationship, and the relationship isn't transitive: `comp(k1, k2) && comp(k2, k3)` can return false even if `comp(k1, k3)` is true. – James Kanze Feb 06 '12 at 18:59
@JamesKanze You are right - this will break transitivity. Thinking of a better solution. – Sid Feb 06 '12 at 19:09
@Farzam Here's an existing discussion on the topic. Farzam using the method I suggested may have pitfalls: http://stackoverflow.com/questions/4816156/are-ieee-floats-valid-key-types-for-stdmap-and-stdset – Sid Feb 06 '12 at 19:19
Also, it would be useful to look at the discussion in this newsgroup on this very topic. Seems like this is a known and widely debated problem: http://groups.google.com/group/comp.lang.c++.moderated/browse_thread/thread/f3439f6267f06250 – Sid Feb 06 '12 at 19:23
Right now, there is no "answer with 12 upvotes." Please be more descriptive. Maybe you could say "the answer from Paul." In addition, you can link directly to the answer you mean; use the "link" item inside that answer to get the permalink for it; it will remain valid even when the vote counts change or if a user changes his or her user name. – Rob Kennedy Feb 06 '12 at 21:12
@RobKennedy Was referring to the answer by Mehrdad Afshari on that thread. But link is really what I need. Here goes: http://stackoverflow.com/a/1114867/559095 Thanks for pointing out. – Sid Feb 06 '12 at 21:16
I see. I've edited your answer to make that clear. What's odd is that Mehrdad's answer has not had 12 up votes in the time since you answered this question. (It has 11 now, with no down votes. And it hasn't been edited recently, either, which is the only way a prior up-voter could have rescinded a vote.) – Rob Kennedy Feb 06 '12 at 21:22
@RobKennedy Thanks for that. Well, then it was probably an error on my part. I guess my ++ operator is hyper-active today. – Sid Feb 06 '12 at 21:25

score 1 · Answer 3 · answered Feb 06 '12 at 18:53

1

Going off the link provided by @Sid, it seems that (however well- or ill-advised it is), you can do this by defining your comparison operators as follows:

const double eps = 1e-8;
bool less_than(double a, double b)
{
    return a < b - eps;
}

bool greater_than(double a, double b)
{
    return a > b + eps;
}

answered Feb 06 '12 at 18:53

Matt Phillips

9,465
8
44
75

Which doesn't define an equivalence relationship, and isn't transitive, so it doesn't define a strict weak ordering. (Which means that using it as a comparison function for `std::set` is undefined behavior.) – James Kanze Feb 06 '12 at 19:02

score 1 · Answer 4 · answered Feb 06 '12 at 19:22

You need to quantize your doubles before inserting them into the set.

If you consider all numbers in the range 1.0000000 <= x < 1.0000002 to be identical, simply replace all numbers in this range by 1.0000000 before inserting them into the set. Likewise for 1.0000002 <= x < 1.0000004 etc.

This approach avoids all issues with comparison operators and transitivity.

score 0 · Answer 5 · answered Feb 06 '12 at 18:46

This seems like a bad idea. Consider the case of the numbers 1.0000000, 1.0000001, 1.0000002. If you insert 1.0000001 first then neither of the other numbers would be allowed to be added to the set. If you add 1.0000000 or 1.0000002 first then the other could be added later.

Additionally, set uses operator< to define its relationship, NOT equality. I can't see a way of writing a strict weak ordering that relies on an epsilon, it's just not going to result in a properly sorted container. The container relies just on operator< or other comparison and there's no way of specifying an equality operation.

Better is to just use the normal < comparison and do post-processing after you've built the set to clean up the elements you don't want anymore. If you give us more information about the real problem you're trying to solve we may be able to help.

You can always define a set of discrete ranges using `modf` (or probably other things as well), and then use a characteristic element in each range for the comparison. But your last suggestion is probably better. — James Kanze, Feb 06 '12 at 19:04

TimW · Answer 6 · 2012-02-06T18:52:21.963

-1

const double eps = 1e-8;
bool compare(double a, double b)
{
    return (abs(a - b) > eps) ? (a < b) : false;
}

set<int,bool(*)(double,double)> set (compare);

struct Compare
{
    bool operator()(double a, double b) const
    {
        return (abs(a - b) > eps) ? (a < b) : false;
    }
};

set<int,Compare> set;

edited Feb 06 '12 at 18:52

answered Feb 06 '12 at 18:36

TimW

8,351
1
29
33

1

Ahm, shouldn't the comparison function define a "less than" relationship, rather than "is equal to"? – Niklas B. Feb 06 '12 at 18:38
but this passes operator<, I want to pass operator==. – Farzam Feb 06 '12 at 18:39
@Farzam `std::set` orders its elements using an ordering relationship, `std::less` by default. It does not test for equality, but counts on `!cmp(lhs, rhs) && !cmp(rhs, lhs)` defining an equivalence relation. (Which the proposed function doesn't.) – James Kanze Feb 06 '12 at 19:07

passing operator== to set in c++

6 Answers6