Können wir unordered_map <T> :: Iterator speichern?

Referenz http://www.careercup.com/question?id=17188673 von chetan.j9Können wir unordered_map <T> :: Iterator speichern?

void Insert(string s) { 
    if(IsElementPresent(s)) 
     return; 

    myMap[s] = myMapVector.size(); 
    unordered_map<string,int>::iterator it = myMap.find(s); 
    myMapVector.push_back(it);  
}

Frage> Können wir speichern die Iterator von unordered_map für einen späteren Abruf? Nach meinem Verständnis wird der Iterator nach dem Einfügen oder Löschen eines Elements ungültig gemacht.

Danke

Quelle

2013-05-27 q0987

Eine nette Referenz für die Iterator-Invalidierung für alle Container ist http: // stackoverflow.com/questions/6438086/iterator-invalidation-rules – JRG

Insertion eines Artikels alle Iteratoren ungültig nur, wenn ein Wiederkäuen auftritt (dh., Wenn die neue Anzahl der Elemente größer oder gleich max_load_factor()*bucket_count() ist). Andernfalls werden keine Iteratoren ungültig gemacht.

Durch das Entfernen eines Elements werden die Iteratoren nur für die entfernten Elemente ungültig, nicht für die anderen nicht verwandten Elemente.

Quelle: std::unordered_map::insert und std::unordered_map::erase.

Natürlich gelten diese Regeln nur für std::unordered_map. Für andere Container gelten möglicherweise andere Regeln für die Ungültigkeitserklärung. Es liegt an Ihnen, dies in der Dokumentation nachzuschlagen.

Quelle

2013-05-27 23:45:34 syam

Da wir nicht wissen, wann die Invalidierung stattfindet, ist die Implementierung von 'insert' NICHT korrekt. Recht? – q0987

@ q0987 Wir wissen tatsächlich, wann die Entwertung eintritt (die Regel ist ziemlich klar). Wenn Sie die maximale Anzahl von Elementen im Voraus kennen, können Sie vorher einfach "reservieren" (http://en.cppreference.com/w/cpp/container/unordered_map/reserve) und dann Iteratoren sicher speichern, selbst wenn Sie fügen ein, solange Sie das reservierte Maximum nicht überschreiten. Aber natürlich, wenn Sie eine unbekannte Anzahl von Elementen einfügen möchten, ist das eine ganz andere Geschichte und das Speichern von Iteratoren wäre in der Tat eine schlechte Idee, während Sie immer noch Elemente einfügen. – syam

Streng genommen ist die Bedingung für die Wiedererhebung, dass die Anzahl der neuen Elemente größer ist als _oder gleich der von Ihnen angegebenen Formel (oder, da wir Fließkommazahlen sprechen, verwenden Sie besser less-than und die Negation der Anweisung) . – jogojapan

@ syam Antwort korrekt ist (1), aber ich denke, dass es nützlich ist, von der nur maßgeblichen Quelle zu zitieren, die C++ 11 Standard:

(§23.2.5/13) Die insert und emplace Mitglieder dürfen die Gültigkeit von Verweisen auf Containerelemente nicht beeinflussen, können jedoch alle Iteratoren für den Container ungültig machen. Die Löschelemente sollen nur Iteratoren und Referenzen auf die gelöschten Elemente ungültig machen.

(§23.2.5/14) Die insert und emplace Mitglieder bleiben die Wirksamkeit von Iteratoren beeinflussen, wenn (N + n) < z * B, wobei N die Anzahl der Elemente in dem Behälter vor dem Einfügevorgang ist , n ist die Anzahl der eingefügten Elemente, B ist die Bucket-Anzahl des Containers und z ist der maximale Ladefaktor des Containers.

(dies in Zusammenhang zu bringen. §23.2.5 der Abschnitt über ungeordneten assoziativen Container ist, so gilt sie für std::unordered_set, std::unordered_map, std::unordered_multiset und std::unordered_multimap) Das bedeutet:

Wenn Sie n Elemente in eine unordered_map genannt hash, können Sie überprüfen, ob
```
hash.size() + n < hash.max_load_factor() * hash.bucket_count() 
```
einfügen 210
ist wahr. Wenn es falsch ist, werden alle Iteratoren während des Einfügens ungültig gemacht. Wenn dies der Fall ist, bleiben Iteratoren gültig.
Auch wenn Iteratoren in diesem Vorgang ungültig gemacht werden, bleiben Verweise auf die Elemente selbst gültig.
Wenn Sie erase Elemente verwenden, werden nur Iteratoren, die auf diese verweisen, ungültig; Andere Iteratoren bleiben gültig.

Quelle

2013-05-28 01:25:20 jogojapan

Ich habe Probleme, Punkt 2 zu verstehen. Können Sie mir ein Beispiel geben? Vielen Dank – q0987

@ q0987 Wenn Sie beispielsweise einen Verweis auf einen im Hash gespeicherten Wert erhalten haben, z. 'int & val = myMap [" hello "];', selbst wenn Sie so viele Elemente einfügen, wie nötig sind, um eine Neuzuweisung auszulösen, ist 'val' immer noch ein gültiger Verweis auf die ganze Zahl, die für die Zeichenfolge' "hallo" gespeichert ist. '. Dasselbe gilt, wenn Sie die Referenz von einem Iterator erhalten. Der Iterator kann später ungültig gemacht werden, aber die Referenz auf einen Wert bleibt gültig. – jogojapan

Überprüfen Sie http://stackoverflow.com/questions/6438086/iterator-invalidation-rules Einfügung für Vektor. vector: Alle Iteratoren und Referenzen vor dem Einfügepunkt sind nicht betroffen, es sei denn, die neue Containergröße ist größer als die vorherige Kapazität (in diesem Fall werden alle Iteratoren und Referenzen ungültig) [23.2.4.3/1] – q0987

Können wir unordered_map <T> :: Iterator speichern?

Antwort

Verwandte Themen