Itérer et modifier simultanément un ensemble non ordonné?

Question

Considérons le code suivant:

unordered_set<T> S = ...;

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

C'est cassé correct? Si nous insérer quelque chose dans S alors les itérateurs peuvent être invalidé (due à une resucée), ce qui va casser la fourchette, car sous le capot, c'est à l'aide de S. begin ... S. fin.

Est-il un motif pour traiter ce problème?

Une façon est:

unordered_set<T> S = ...;

vector<T> S2;

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

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

Cela semble maladroit. Est-il un meilleur moyen que je suis absent?

(Plus précisément, si j'ai été en utilisant un roulé à la main de la table de hachage et j'ai pu le bloquer à partir de ressasser jusqu'à la fin de la boucle, il serait plus sûr d'utiliser la première version).

Mise à jour:

À partir de http://en.cppreference.com/w/cpp/container/unordered_map/insert

Si ressasser se produit en raison de l'insertion, tous les itérateurs sont invalidés. Sinon les itérateurs ne sont pas affectés. Les références ne sont pas invalidées. Ressasser se produit uniquement si le nouveau nombre d'éléments est supérieur max_load_factor() * bucket_count().

Pourrait vous gâcher max_load_factor d'une certaine manière à l'empêcher de ressasser?

Answer 1

Pourriez-vous mess avec max_load_factor en quelque sorte à l'empêcher de ressasser?

Oui, vous pouvez définir l' max_load_factor() à l'infini pour s'assurer qu'aucun ressasser se produit:

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

Notez que la simple définition d'un nouveau facteur de charge n'est pas de ressasser, de sorte que ceux-ci sont bon marché des opérations.

L' rehash(0) bits fonctionne parce que c'est une demande que: 1) je reçois au moins n seaux, et 2) j'ai assez de seaux pour satisfaire ma max_load_factor(). Nous utilisons tout simplement zéro pour indiquer que nous n'avons pas de soins pour un montant minimum, on a juste envie de ressasser pour satisfaire notre "nouveau" facteur, comme si il n'a jamais été modifiée à l'infini.

Bien sûr, ce n'est pas une exception-safe; si quoi que ce soit jette entre les appels à l' max_load_factor(), notre ancien facteur est perdu à jamais. Facilement résolu avec votre favori de la portée de la garde-utilitaire ou une classe utilitaire.

Notez que vous n'obtenez pas de garanties si vous allez effectuer une itération sur les éléments nouveaux. Vous allez effectuer une itération sur les éléments existants, mais vous peut ou ne peut pas effectuer une itération sur les éléments nouveaux. Si c'est correct (qui, de par notre discussion, il devrait l'être), puis ce sera le travail.

Par exemple, considérez-vous effectuer une itération sur un non-ordonnée ensemble d'entier et pour chaque entier pair x, insérez x * 2. Si ces toujours obtenir inséré juste après votre actuel position (à l'occasion de la mise en œuvre du détail et de l'etat du conteneur), vous n'aurez plus jamais fermer la boucle, sauf par le biais d'exceptions.

Si vous avez besoin de certaines garanties, vous devez fournir une autre solution de stockage.

Answer 2

La modification de n'importe quel conteneur pendant que vous êtes à parcourir, il a tendance à s'arracher les cheveux - même si c'est une structure plus simple que d'une table de hachage, ou même si vous pouvez l'empêcher de re-hachage, ré-équilibrage ou de quoi que ce soit.

Même si il ne le travail, par le façon, il y a une ambiguïté: si votre nouvellement insérée membres être itéré ou pas? Est-il ok pour les inclure dans cette itération seulement parfois (c'est à dire, que si elles se produisent à la fin après l'itérateur actuel)?

Si vous avez besoin de faire beaucoup, vous pourriez utilement envelopper le récipient dans un générique adaptateur qui reporte tous les inserts jusqu'à la fin, mais vous êtes vraiment trouver un moyen de cacher le code que vous avez déjà.

Answer 3

Je me suis rendu compte que c'était conceptuellement le même que ce que vous proposiez, mais je pense que cela semble en fait assez lisse:

 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()));