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 ?

Answer 1

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