C++ STL make_heap 和 priority_queue 给出不同的输出

Question

这是我的代码:

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;

SimpleCycle 的比较器如下:

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));
}

avg_latency() 函数返回一个float。但是对于相同的输入案例，我得到了不同的输出。可能有什么问题？

Answer 1

由于您的比较运算符“允许 0.0000000001 的错误率”，因此它不是 C++ 概念定义的严格弱排序(例如 http://en.cppreference.com/w/cpp/concept/Compare )。

特别是，不满足严格弱序的对称性要求。例如。如果我们将 e 称为错误阈值(在您的情况下为 0.0000000001)，我们会看到:

• SimpleCycle()(1/e, 1/e + 1) 返回 false
• SimpleCycle()(1/e + 1, 1/e) 返回 false

Igor Tandenik 在评论中指出的另一个问题是，它导出的等价关系是不可传递的:可能 a 与 b 足够接近，b 与 c 足够接近，但 a 不够接近到 c.

根据 cycle 变量中的数据，这可能会导致 priority_queue 和 make_heap 方法返回略微不同的最大元素

也可能存在舍入误差......