C++ STL make_heap and priority_queue gives different output

Question

This is my Code:

std::priority_queue<SimpleCycle, std::vector<SimpleCycle>, SimpleCycle> pq; pq.push(cycle1); pq.push(cycle2); pq.push(cycle4); std::cout << pq.top().to_string() << std::endl; std::vector<SimpleCycle> pq2{ cycle1, cycle2, cycle4 }; std::make_heap(pq2.begin(), pq2.end(), SimpleCycle()); std::cout << pq2.front().to_string() << std::endl;

Comparator for SimpleCycle is as follows:

const bool SimpleCycle::operator()(SimpleCycle& L, SimpleCycle& R) const { float a = L.avg_latency(); float b = R.avg_latency(); //Allow an error rate of 0.0000000001 //Ref. The Art of Computer Programming: Seminumerical algorithms(Page 128) return (b - a) > ((fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * (0.0000000001)); }

The function avg_latency() return a float. But I get different output for the same same input cases. What is possibly wrong ?

I haven't gone through and generated the counterexample but offhand it looks like your comparison operator may not provide the strict weak ordering mandated by the standard, thus any behavior could be expected. — Mark B
– Mark B, Commented Sep 13, 2016 at 16:40

Martin J. · Accepted Answer · 2016-09-14 02:45:25Z

Since your comparison operator "allows an error rate of 0.0000000001", it's not a strict weak ordering as defined by C++ concepts (e.g. http://en.cppreference.com/w/cpp/concept/Compare).

In particular, the symmetry requirement of the strict weak ordering is not fulfilled. E.g. if we call e the error threshold (in your case, 0.0000000001), we see that:

SimpleCycle()(1 / e, 1 / e + 1) returns false
SimpleCycle()(1 / e + 1, 1 / e) returns false

Another problem, pointed out by Igor Tandenik in the comments, is that the equivalence relation it induces is not transitive: it's possible that a is close enough to b, and b is close enough to c, but a is not close enough to c.

Depending on the data in your cycle variables, this may cause the priority_queue and make_heap approaches to return slightly different maximum elements

There may also be rounding errors at play...

Can you please elaborate or provide references on how I can over come this ?
It's perfectly fine for comp(a, b) and comp(b, a) to both return false - that just means that two elements are considered equivalent. The real problem with this predicate is that the equivalence relation it induces is not transitive: it's possible that a is close enough to b, and b is close enough to c, but a is not close enough to c.
@IgorTandetnik. Good point about the transitivity requirement. Having a weak ordering is fine from an algorithmic perspective, however, it would lead to the problem described in the question: "I get different output for the same same input cases", assuming the output code produces different output for equivalent results
Thank You for your time. I will try b - a > 0 for the above.
Tested with `return b - a > 0;' ,ended up with the same result.

Collectives™ on Stack Overflow

C++ STL make_heap and priority_queue gives different output

1 Answer 1

5 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Related