c++ - 同时迭代和修改 unordered_set？

Question

考虑以下代码:

unordered_set<T> S = ...;

for (const auto& x : S)
   if (...)
       S.insert(...);

这是坏的吗？如果我们在 S 中插入一些东西，那么迭代器可能会失效(由于重新散列)，这将破坏范围，因为在引擎盖下它使用的是 S.begin ... S.end。

有什么模式可以解决这个问题吗？

一种方法是:

unordered_set<T> S = ...;

vector<T> S2;

for (const auto& x : S)
   if (...)
       S2.emplace_back(...);

for (auto& x : S2)
    S.insert(move(x));

这看起来很笨重。我错过了更好的方法吗？

(特别是如果我使用的是手动哈希表，并且我可以阻止它重新哈希直到循环结束，那么使用第一个版本是安全的。)

更新:

来自 http://en.cppreference.com/w/cpp/container/unordered_map/insert

If rehashing occurs due to the insertion, all iterators are invalidated. Otherwise iterators are not affected. References are not invalidated. Rehashing occurs only if the new number of elements is higher than max_load_factor() * bucket_count().

您能以某种方式弄乱 max_load_factor 以防止重新散列吗？

Answer 1

Could you mess with max_load_factor somehow to prevent rehashing?

是的，您可以将 max_load_factor() 设置为无穷大，以确保不会发生重新散列:

#include <iostream>
#include <limits>
#include <unordered_set>

int main()
{
    // initialize
    std::unordered_set<int> S;

    for (int i = 0; i < 8; ++i)
        S.insert(i);

    std::cout << "buckets: " << S.bucket_count() << std::endl;

    // infinite max load factor => never need to rehash
    const auto oldLoadFactor = S.max_load_factor();
    S.max_load_factor(std::numeric_limits<float>::infinity());

    for (const auto& x : S)
    {
        if (x > 2)
            S.insert(x * 2);
    }

    // restore load factor, verify same bucket count
    S.max_load_factor(oldLoadFactor);
    std::cout << "buckets: " << S.bucket_count() << std::endl;

    // now force rehash
    S.rehash(0);
    std::cout << "buckets: " << S.bucket_count() << std::endl;
}

请注意，简单地设置一个新的负载因子不会重新散列，所以这些操作很便宜。

rehash(0) 位有效，因为它要求:1) 我至少获得 n 个存储桶，2) 我有足够的存储桶来满足我的 max_load_factor()。我们只是使用零来表示我们不关心最小数量，我们只是想重新哈希以满足我们的"new"因素，就好像它从未更改为无穷大一样。

当然，这不是异常安全的；如果在对 max_load_factor() 的调用之间出现任何问题，我们的旧因子将永远丢失。使用您最喜欢的范围保护实用程序或实用程序类轻松修复。

请注意，如果您将迭代新元素，则无法保证。您将迭代现有元素，但您可能会也可能不会迭代新元素。如果没问题(根据我们的聊天应该是这样)，那么这将起作用。

例如，假设您对一组无序整数进行迭代，并为每个偶数 x 插入 x * 2。如果那些总是在您当前位置之后插入(通过实现细节和容器状态的机会)，您将永远不会终止循环，除非通过异常。

如果您确实需要一些保证，则需要使用备用存储解决方案。