c++ - 预测 std::unordered_set 或 std::unordered_map 的调整大小/重新散列

Question

是否有可能可靠地预测对 std::unordered_set 或 std::unordered_map 的插入何时会调整底层存储的大小并重新散列项目？

我的程序维护着一个不断增长的 unordered_set 项，但有些项可能会“过期”，我可以从集合中删除这些项以节省空间。最好在插入项目之前执行此操作，以防插入会导致集合调整大小和重新散列。该集合无论如何都需要扫描它的所有元素，我什至可能会阻止它调整大小)。

但到目前为止，我还没有找到一种方法来预测将跨标准库实现工作的调整大小。下面的代码揭示了 Microsoft 的实现与 libstdc++ 之间的差异。

std::unordered_set<int> set;
for (int i=0; i < 1000; ++i) {
    size_t bucketsBefore = set.bucket_count();
    set.emplace(i);
    size_t bucketsAfter = set.bucket_count();
    bool resized = bucketsAfter > bucketsBefore;
    if (resized)
        printf("Size from %zu to %zu, buckets from %zu to %zu.\n", set.size() - 1, set.size(), bucketsBefore, bucketsAfter);
}

在 Windows 中使用 MSVC 编译时，打印

Size from 8 to 9, buckets from 8 to 64.
Size from 64 to 65, buckets from 64 to 512.
Size from 512 to 513, buckets from 512 to 1024.

在 Linux 中使用 g++ 编译时，打印

Size from 0 to 1, buckets from 1 to 3.
Size from 2 to 3, buckets from 3 to 7.
Size from 6 to 7, buckets from 7 to 17.
Size from 16 to 17, buckets from 17 to 37.
Size from 36 to 37, buckets from 37 to 79.
Size from 78 to 79, buckets from 79 to 167.
Size from 166 to 167, buckets from 167 to 337.
Size from 336 to 337, buckets from 337 to 709.
Size from 708 to 709, buckets from 709 to 1493.

就加载因子而言，这意味着当加载因子超过 1 时，Microsoft 实现将调整集合的大小，但 libstdc++ - 当加载因子达到 1 时。

现在我想知道有什么好的解决方法。有选项。

1. 在调整大小后删除过期项目。更强大的选项，但这样你就永远无法阻止调整大小。这就是我现在所做的。
2. 在 libstdc++ 执行调整大小时删除过期项目。这个想法还不错，但如果存在第三个实现甚至可以更早地调整大小，例如，当负载因子达到 1-epsilon 时，那么对于该实现，我永远不会删除过期的项目。鉴于 Microsoft 和 libstdc++ 已经对负载因子进行了不同的处理，我看不出为什么这种第三种实现不会出现的原因。或者有什么原因吗？

Answer 1

您可以考虑使用 boost::intrusive::unordered_set 并根据负载因子和 过期 项的数量重新哈希。