4

我已经意识到，为了使快速排序起作用，所有的无穷大都需要相等。

换句话说，这样的标准是不够的：

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;

将返回 true。

现在我测试了这种方法，它似乎有效。但我担心无限可能出现的其他方式。例如：

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

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

4

2 回答 2

10

在没有 NaN 的情况下，正则运算符的无穷大是可以的<：

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

（类似的性质对 -∞ 有效）

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

但是，对于 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 为假，而其他属性仍然成立。

于 2012-07-25T02:17:38.057 回答
0

如果你使用这个：

bool operator()(Entity left, Entity right)const
{
    return !(left.valueIsInfinite() && right.valueIsInfinite())
        && left.value() < right.value();
}

然后无限被认为是相同的顺序，因为没有一个在另一个之前......

于 2012-07-25T02:10:20.243 回答