c++ - 使用快速排序对可能包含无穷大的容器进行排序是否安全？

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

在没有 NaN 的情况下，无穷大可以使用常规运算符 < :

• +∞ < +∞ 为假:<是反身的；
• 如果 +∞ < x 为真，则 x < +∞ 对于非无穷大值为假:<是反对称的；
• 如果 +∞ < x 为真且 x < y 为真，则 +∞ < y 为真:<具有传递性；
• 如果 +∞ 与 x 不可比(不小于，不大于)，并且 x 与 y 不可比，则 +∞ 与 y 不可比:<显示等价的传递性。

(类似的性质对-∞有效)

鉴于这些属性 operator<在没有 NaN 的 float 上 是严格的弱排序，因此适用于标准库样式的排序操作。

但是，对于 NaN，反对称性被打破: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 为假，而其他属性仍然成立。