31

次のコードを検討してください。

unordered_set<T> S = ...;

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

これは壊れていますよね？S に何かを挿入すると、イテレータが (再ハッシュのために) 無効になる可能性があり、内部では S.begin ... S.end を使用しているため、range-for が壊れます。

これに対処するパターンはありますか？

1 つの方法は次のとおりです。

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 に答える