使用quicksort对可能包含无穷大的容器进行排序是否安全？

Question

我已经意识到,为了使快速排序工作,所有的无限性都必须是平等的.

换句话说,这样的标准是不够的:

class Entity
{
public: 
   float value() const;
   bool valueIsInfinite() const;
};

class Criterium
{
    bool operator()(Entity left, Entity right)const
    {
        if (left.valueIsInfinite())
            return false;
        return left.value() < right.value();
    }
}

const Criterium criterium;
QVector<Entity> container;

qSort<container.begin(), container .end(), criterium>

这种排序失败了,因为根据标准并非所有无穷大都是相等的.不平等取决于实体进入运营商的顺序.我发现,这样的排序失败了.

我需要这样的东西:

class Criterium
{
    bool operator()(Entity left, Entity right)const
    {
        if (left.valueIsInfinite() && right.valueIsInfinite())
            return false;
        if (left.valueIsInfinite() && !right.valueIsInfinite())
            return false;
        if (!left.valueIsInfinite() && right.valueIsInfinite())
            return true;
        return left.value() < right.value();
    }
}

但是假设不是

   float Entity::value() const;
   bool Entity::valueIsInfinite() const;

方法,我想用

   float Entity::value() const;

让它回归

std::numeric_limits<float>::infinity();

在哪些情况下

bool Entity::valueIsInfinite() const;

会回归真实.

现在我测试了这种方法,它似乎工作.但我担心其他可能出现无限的方式.例如:

float otherInfinity = exp(std::numeric_limits<float>::infinity());

这种无穷大似乎是一样的.但我想确定.我知道C++标准没有提到浮点运算实现的细节,但是如果我使用gcc,它在所有情况下都是安全的吗？我的意思是在gcc中创建的所有无穷大都是相同的吗？对一个浮子容器进行分类是否安全,这些浮子可能包含在不同场合出现的无穷大？

Answer 1

如果没有NaNs,常规运算符就会产生无穷大<:

• +∞<+∞是假的:<是无反射的;
• 如果+∞<x为真,那么对于非无穷大值,x <+∞为假:<是反对称的;
• 如果+∞<x为真且x <y为真,那么+∞<y为真:<是可传递的;
• 如果+∞与x无法比较(不小于,不大于),而x与y无法比较,那么+∞与y无法比较:<显示等价的转换.

(类似属性对-∞有效)

鉴于没有 NaN的浮点数operator<上的那些属性是严格的弱排序,因此适用于标准库样式排序操作.

然而,对于NaNs,反对称性被破坏:NaN <1是假的,1 <NaN也是假的.您可以通过在所有非NaN之前或之后订购所有NaN来解决此问题,方式与您提出的策略类似:

struct Criterion
{
    bool operator()(Entity left, Entity right)const
    {
        // NaNs come before non-NaNs
        if (isnan(left.value()) && isnan(right.value()))
            return false;
        if (!isnan(left.value()) && isnan(right.value()))
            return false;
        if (isnan(left.value()) && !isnan(right.value()))
            return true;
        return left.value() < right.value();
    }
}

(isnan可以在C++ 11标准库中找到,或者很容易实现return x != x;)

有了这个,我们得到NaN <1为真,1 <NaN为假,而其他属性仍然成立.