插入大量NaN值时std::unordered_set的insert操作导致程序挂起

嘿，这个问题我之前也踩过坑，本质是NaN的特殊比较规则和std::unordered_set的底层实现逻辑撞在一起了，咱们慢慢拆解：

问题根源：NaN的反直觉特性 #

C++里的NaN（非数值）有个违背常识的规则：任何NaN和自身的相等比较结果都是false——比如std::numeric_limits<float>::quiet_NaN() == std::numeric_limits<float>::quiet_NaN()会返回false。

再看std::unordered_set的插入逻辑：

1. 先计算元素的哈希值，找到对应的桶
2. 遍历桶里的现有元素，和待插入元素做相等性比较
3. 如果没找到相等元素，就把新元素加入桶中

当你插入大量NaN时，会触发两个致命的叠加效应：

• std::hash<float>对所有NaN会返回相同的哈希值（不同编译器细节可能有差异，但大多是这样），所以所有NaN都会被塞到同一个桶里
• 每次插入新NaN时，程序会遍历桶里已有的所有NaN做相等比较，但因为NaN和任何NaN都不相等，所以每次都会认为这是新元素，把它加到桶的链表末尾

当n达到1e5时，这个桶的链表长度会变成1e5，每次插入都要遍历整个链表，时间复杂度从O(1)直接飙升到O(n²)——1e5个元素就是1e10次比较操作，这会让程序看起来像“挂起”，实际上是在做极其耗时的遍历。而插入非NaN值时，相等比较正常，重复值会被去重，桶不会无限变长，所以速度很快。

解决方案 #

根据你的需求，有两种常用处理方式：

1. 自定义哈希和相等判断，把所有NaN视为同一个元素

如果你希望所有NaN在集合里只保留一个，可以自定义哈希函数和相等比较器：

#include <cmath>
#include <unordered_set>
#include <vector>
#include <limits>

struct FloatHash {
    size_t operator()(float f) const {
        if (std::isnan(f)) {
            // 给所有NaN分配同一个哈希值
            return std::hash<int>()(0);
        }
        return std::hash<float>()(f);
    }
};

struct FloatEqual {
    bool operator()(float a, float b) const {
        if (std::isnan(a) && std::isnan(b)) {
            // 所有NaN视为相等
            return true;
        }
        return a == b;
    }
};

// 使用自定义的哈希和比较器
std::unordered_set<float, FloatHash, FloatEqual> s;

这样插入大量NaN时只会保留一个，插入速度会恢复正常。

2. 改用std::set

std::set底层是红黑树，依赖<比较而非==。虽然NaN和任何值比较（包括另一个NaN）都会返回false，但红黑树的插入时间复杂度是O(logn)，1e5个元素大约是1.7e6次操作，远快于unordered_set的O(n²)，不会出现“挂起”的情况。不过要注意，std::set会保留所有插入的NaN（因为它们的比较结果不满足有序性，会被当成不同元素），如果需要去重NaN，还是得自定义比较器。

补充验证 #

你提到1e3/1e4个NaN时程序能正常运行，这是因为O(n²)复杂度在n=1e4时是1e8次操作，现代CPU勉强能在几秒内完成，但n=1e5时就是1e10次操作，耗时会拉长到几分钟甚至更久，看起来就像程序挂起了。

备注：内容来源于stack exchange，提问作者Tom McLean