c++ - 为什么第32769个插入在std::unordered_set中失败？

Question

我生成了大量的类实例，并将它们存储在std::unordered_set中。我已经定义了一个哈希函数和一个相等关系，到目前为止，一切都可以正常进行-我用unordered_set::insert插入了10000个实例，并且可以使用unordered_set::find找到它们。所有对象均未损坏，也没有暗示内存损坏或任何其他问题。

但是，当我继续插入时，第32769次插入失败-它不会抛出，但会返回一个迭代器为== nullptr(0x00000000)的对。 insert定义为:

pair<iterator, bool> insert(const value_type& Val);

通常， *iterator是我插入的键， bool(boolean) 值是 true。
如果我(在错误之后)尝试找到该对象，则该对象已存在。如果我尝试再次插入，它会告诉我它已经在那里；因此插入似乎效果很好。只是返回的值是 pair<nullptr,true>而不是 pair<iterator,bool>。
请注意，如果我手动填充迭代器并继续在调试器中运行，则相同的问题会在65536之后的第一个插入处再次发生，然后在131072等处发生(以此类推(对于2 ^ 15 + 1、2 ^ 16 + 1、2 ^ 17 + 1，...)-但不是3 * 32768 + 1等。

对我来说，这看起来像 short溢出。也许我的哈希值真的很糟糕，导致水桶装满不均匀，而在32768时，它用完了水桶？谷歌搜索时，我找不到关于此限制的任何更详细的信息，并且我对平衡树或内部的任何事物都不了解。
尽管如此，std库代码应该能够处理错误的哈希，我知道它是否变慢且效率低下，但它不会失败。

问题:为什么2 ^ 15th + 1、2 ^ 16th + 1等插入失败，如何避免？

这是Microsoft Visual Studio 2017 V15.7.1(最新版本截至2018-05-15)。编译器被设置为使用C++ 2017规则，但我怀疑它是否会产生影响。
我无法粘贴完整的代码以寻求最小可行的解决方案，因为对象生成跨多个类和方法很复杂，并且有数百行代码，因此生成的哈希显然取决于对象的细节，并且在以下情况下不易复制伪代码。

###一天后更新### :(我无法将其放在答案中，因为q处于保留状态)
在对标准库进行了广泛的调试(包括大量的抓头工作)之后，@ JamesPoag的答案原来指向正确的东西。
插入 n后，我得到:

  n     load_factor  max_load_factor  bucket_count  max_bucket_count
32766   0.999938965  1.00000000       32768         536870911 (=2^29-1)
32767   0.999969482  1.00000000       32768         536870911
32768   1.000000000  1.00000000       32768         536870911
32769   0.500000000  1.00000000       65536         536870911

毫不奇怪，插入32768后，负载系数已达到最大值。第32769次插入会在内部方法_Check_Size内部触发对更大表的重新哈希处理:

void _Check_size()
        {    // grow table as needed
        if (max_load_factor() < load_factor())

            {    // rehash to bigger table
            size_type _Newsize = bucket_count();

            if (_Newsize < 512)
                _Newsize *= 8;    // multiply by 8
            else if (_Newsize < _Vec.max_size() / 2)
                _Newsize *= 2;    // multiply safely by 2
            _Init(_Newsize);
            _Reinsert();
            }
        }

最后，调用 _Reinsert()并将所有32769键填充到新存储区中，并_set相应地设置所有 _next和 _prev指针。很好
但是，调用这两个代码的代码如下所示( Plist是我的集合的名称，该代码从模板生成):

_Insert_bucket(_Plist, _Where, _Bucket);

_TRY_BEGIN
_Check_size();
_CATCH_ALL
erase(_Make_iter(_Plist));
_RERAISE;
_CATCH_END

return (_Pairib(_Make_iter(_Plist), true));
}

关键点在最后一行-_Plist用于构建该对，但它现在包含指向 _next的死指针，因为所有存储区的地址都已在 _Check_size()中进行了重建，有些行之前。
我认为这是std库中的错误-在这里它需要在新集中找到 _Plist，看起来像一样，但是具有有效的 _next指针。

一个简单的“修复程序”(已验证能正常工作)，可以在关键 insert之前扩展集合: if (mySet.size() == mySet.bucket_count()) mySet.rehash(mySet.bucket_count() * 2);。

###进一步更新:###
我已经进行了广泛的尝试(超过16个小时)，以产生可重现该问题的最小代码，但是我还没有能力。我将尝试记录现有大代码的实际计算出的哈希值。
我发现的一件事是，其中一个键的一个哈希值在插入和重新哈希之间发生了更改(无意间)。这可能是根本原因。如果我将重新哈希处理移到了插入内容之外，问题就消失了。
我不确定是否有一定的规则必须保持哈希值不变，但这可能是有道理的，您又怎么能找到 key 。

Answer 1

我将一些简单的代码插入到godbolt.org中，以查看输出是什么，但是没有任何反应。

我怀疑已插入Value并创建了迭代器，但是插入超出了max_load_factor并触发了重新哈希。在Rehash上，先前的迭代器无效。在这种情况下，返回迭代器可能被清零(或从不设置)(再次在反汇编中找不到它)。

在有问题的插入之前和之后检查load_value()，max_load_value()和bucket_count()。