按总顺序对 IEEE 754 浮点数进行排序

Question

我编写了一个算法，其中涉及排序和调用

std::lower_bound

和

std::upper_bound

。

如果值类型

float

或

double

所有

NaNs

比较不相等，我的算法就会失败。

为了提供 IEEE 754 浮点数的强排序，我使用

std::memcpy

将数字复制到相同字节大小的有符号整数。如果是负数，我也会反转数字（

x = INT_MIN - x - 1;

）。排序后，我以类似的方式恢复原始浮点数。

生成的代码运行良好，并且其运行性能与浮点比较完全相同。

在 C++ 中是否有更好的方法来获得

float

和

double

的总排序？

编辑：我应该提到，total ordering是一个关键字，在 IEEE 754 中进行了描述。 请参阅：https://en.wikipedia.org/wiki/IEEE_754#Total-ordering_predicate

Answer 1

您需要编写一个自定义比较器来实现严格弱排序。

例如，这使得 NaN 比其他数字更大：

#include <vector>
#include <iostream>
#include <limits>
#include <algorithm>
#include <cmath>

int main()
{
    std::vector<float> values = {2,4,std::numeric_limits<float>::quiet_NaN(),3,7,1,5,7,2,2, std::numeric_limits<float>::quiet_NaN()};
    std::sort(values.begin(), values.end(), [](float a, float b) { 
        bool aNan = std::isnan(a);
        bool bNan = std::isnan(b);
        if (aNan && bNan) {
            // a and b are "equal", return false
            return false;
        }
        if (aNan || bNan) {
            // return true if NaN is on the right, i.e. NaNs are larger than all other numbers
            return bNan;
        }
        return a < b;
        });
    for (auto i : values)
    {
        std::cout << i << "\n";
    }
}

https://godbolt.org/z/8W7vd818E

如果您想将 NaN 放在数据更改的开头，请从

return bNan

更改为

return aNan