同时迭代和修改unordered_set？ [英] Simultaneously iterating over and modifying an unordered_set?

问题描述

请考虑以下代码：

  unordered_set< T> S = ...; 
 
 for（const auto& x：S）
 if（...）
 S.insert（...）; 
  

这是破碎正确吗？如果我们插入一个东西到S中，那么迭代器可能会失效（由于rehash），这将打破范围，因为在引擎下，它使用S.begin ... S.end。

有没有一些模式来处理这个问题？

一种方法是：

  unordered_set< T> S = ...; 
 
矢量< 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 混淆吗？

解决方案

是的，您可以设置 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 =>永远不需要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）; 
} 
 
 //恢复负载因子，验证同一桶数
 S.max_load_factor（oldLoadFactor）; 
 std :: cout<< buckets：< S.bucket_count（）<< std :: endl; 
 
 //现在强制rehash 
 S.rehash（0）; 
 std :: cout<< buckets：< S.bucket_count（）<< std :: endl; 
} 
  

请注意，简单地设置一个新的载荷因子不会重新散列，操作。

rehash（0）位工作，因为它是一个请求：1） em> n buckets，以及2）我有足够的存储桶来满足我的 max_load_factor（）。我们只是使用零来表示我们不在乎最低金额，我们只是想重新哈希以满足我们的新因素，好像它从来没有改变为无穷大。

当然，这不是异常安全的;如果任何抛出之间 max_load_factor（）的调用，我们的旧因素永远丢失。使用您最喜欢的范围保护实用程序或实用程序类轻松修复。

请注意，如果您将迭代新元素，则不能保证。 strong>你将迭代现有的元素，但是你可能或不会迭代新的元素。如果这是好的（这是我们的聊天应该是），那么这将工作。

例如，考虑你迭代一个无序的整数，整数 x ，插入 x * 2 。如果那些总是在你的currrent位置之后插入（通过实现的机会 - 容器状态），你永远不会终止循环，除非通过异常。

需要一些保证，您需要使用备用存储解决方案。

Consider the following code:

unordered_set<T> S = ...;

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

This is broken correct? If we insert something into S then the iterators may be invalidated (due to a rehash), which will break the range-for because under the hood it is using S.begin ... S.end.

Is there some pattern to deal with this?

One way is:

unordered_set<T> S = ...;

vector<T> S2;

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

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

This seems clunky. Is there a better way I'm missing?

(Specifically if I was using a hand-rolled hash table and I could block it from rehashing until the end of the loop, it would be safe to use the first version.)

Update:

From 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().

Could you mess with max_load_factor somehow to prevent rehashing?

解决方案

Could you mess with max_load_factor somehow to prevent rehashing?

Yes, you can set the max_load_factor() to infinity to ensure no rehashing occurs:

#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;
}

Note that simply setting a new load factor does no rehashing, so those are cheap operations.

The rehash(0) bit works because it's a request that: 1) I get at least n buckets, and 2) I have enough buckets to satisfy my max_load_factor(). We just use zero to indicate we don't care for a minimum amount, we just want to rehash to satisfy our "new" factor, as if it was never changed to infinity.

Of course, this isn't exception-safe; if anything throws between the calls to max_load_factor(), our old factor is lost forever. Easily fixed with your favorite scope-guard utility or a utility class.

Note that you get no guarantees if you'll iterate over the new elements. You will iterate over the existing elements, but you may or may not iterate over the new elements. If that is okay (which per our chat it should be), then this will work.

For example, consider you iterate over an unordered set of integer and for each even integer x, insert x * 2. If those always get inserted just after your currrent position (by chance of implementation-detail and container state), you will never terminate the loop except through exceptions.

If you do need some guarantees, you need to with an alternate storage solution.

这篇关于同时迭代和修改unordered_set？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！