31

考虑以下代码：

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

如果由于插入而发生重新散列，则所有迭代器都将失效。否则迭代器不受影响。引用不会失效。仅当新元素数高于 时才会发生重新散列max_load_factor() * bucket_count()。

你能以max_load_factor某种方式搞砸以防止重新散列吗？

4

3 回答 3

22

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

是的，您可以将其设置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(). 我们只是使用零来表示我们不关心最小数量，我们只是想重新散列以满足我们的“新”因素，就好像它从未更改为无穷大一样。

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

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

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

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

于 2012-12-21T00:21:43.620 回答
5

在迭代任何容器时修改它往往会变得很麻烦——即使它是一个比散列更简单的结构，或者即使你可以阻止它重新散列、重新平衡或其他任何事情。

顺便说一句，即使它确实有效，也有一个歧义：是否应该迭代新插入的成员？是否可以仅在某些时候将它们包含在此迭代中（即，仅当它们恰好在当前迭代器之后结束时）？

如果您经常需要这样做，您可以将容器包装在一个通用适配器中，该适配器将所有插入延迟到最后，但您确实在找到一种方法来隐藏您已经拥有的代码。

于 2012-12-20T23:39:16.193 回答
2

我意识到它在概念上与您提出的相同，但我认为它看起来实际上相当漂亮：

std::vector<T> tmp;
std::copy_if(S.begin(), S.end(), std::back_inserter(tmp),
             [](T const& value) { return ...; });
S.insert(std::make_move_iterator(tmp.begin()),
         std::make_move_iterator(tmp.end()));
于 2012-12-20T23:47:32.110 回答