std::unordered_set第32769次插入返回空迭代器问题排查

问题场景 #

你遇到的这个问题是VS2017标准库实现std::unordered_set时的一个特定bug：当往存储自定义类实例的std::unordered_set中大量插入元素时，前10000次插入、查找都完全正常，但在第32769次、2¹⁶+1次、2¹⁷+1次插入时，insert返回的std::pair会出现异常——迭代器是nullptr，但bool标记为true（表示插入成功）。更诡异的是，元素其实已经成功存入集合了：后续可以正常查找到它，重复插入也会返回“元素已存在”的结果。

问题根源 #

通过调试VS2017的标准库源码能明确原因：当集合的元素数量恰好等于当前桶数（比如初始扩容到32768桶时），下一次插入会触发_Check_size方法启动重哈希流程。在扩容完成、元素被重新分配到新桶后，标准库错误地使用了旧桶的失效指针作为返回的迭代器，导致返回了空指针，但插入操作本身是成功完成的。

临时修复方案 #

要绕过这个bug，我们可以在插入前主动检查元素数量和桶数的关系，在临界条件到来前手动触发重哈希：

// 在插入元素前执行这段检查
if (mySet.size() == mySet.bucket_count()) {
    mySet.rehash(mySet.bucket_count() * 2);
}

这段代码会在元素数量即将等于桶数时，提前将桶数扩容为原来的2倍，这样后续的插入操作就不会触发那个有问题的自动重哈希流程，也就不会出现返回空迭代器的情况了。

内容的提问来源于stack exchange，提问作者Aganju