Wie verhindere ich, dass beim Entfernen von Elementen eine std :: unordered_map erneut geöffnet wird?

Question

Ich habe eine std :: unordered_map, von der ich Elemente durch Iteration entfernen werde.

auto itr = myMap.begin(); 
while (itr != myMap.end()) { 
    if (/* removal condition */) { 
     itr = myMap.erase(itr); 
    } else { 
     ++itr; 
    } 
} 

Ich mag würde die Karte für die Durchführung keine teure Operationen verhindern, bis ich alle Elemente fertig bin zu entfernen, die ich entfernen müssen. Habe ich eine berechtigte Sorge? Missverstehe ich, wie der interne Speicher funktioniert?

Answer 1

Die ungeordnete Behälter werden aus Aufguß während einer erase verboten:

[unord.req]/p14:

Die erase Mitglieder nur Iteratoren und Verweise auf die gelöschten Elemente ungültig sind, und die relative Reihenfolge der Elemente bewahren , die nicht gelöscht werden.

[unord.req]/P9:

Wiederkäuen entkräftet Iteratoren, Bestelländerungen zwischen den Elementen und ...

Der Code ist in Ordnung, wie es ist.

Answer 2

Soweit ich sagen kann, wird auf std::unordered_maperase(itr) wieder aufwärmen gelassen:

C++ 11 Tabelle 103 - Anforderungen Ungeordnete assoziativen Container

a.erase(q)

löscht das Element spitz zu von . Rückgabewert ist der Iterator unmittelbar nach q vor dem Löschen.

Durchschnittliche Fall O(1), schlimmsten Fall O(a.size())

Es scheint daher, dass Sie ein berechtigtes Anliegen haben zu tun. Um es zu adressieren, kann ich mehrere Wege vorschlagen:

1. Stellen Sie sicher, dass es ein tatsächliches Problem eher als ein hypothetisches ist. Profilieren Sie die Anwendung, schauen Sie sich den Quellcode für Ihre C++ - Bibliothek an usw.
2. Wenn es sich um ein tatsächliches Problem handelt, sollten Sie einen anderen Container oder einen anderen Algorithmus verwenden.
3. Betrachten Sie einfach markieren Sie die Elemente zum Löschen durch ein Boolesches Flag für jedes Element, und kehren Sie die gelöschten Elemente von Zeit zu Zeit, wodurch die Kosten amortisieren.
4. Experimentieren Sie mit dem Ladefaktor, wie von @amit in den Kommentaren vorgeschlagen. Auch wenn der Container noch O(a.size()) Mal zum Löschen von Elementen verwenden darf, kann sich ein anderer Ladefaktor auf die tatsächliche Leistung Ihrer Anwendung auswirken.

Answer 3

Ich bin nicht sicher, ob es funktioniert, ich habe keine Bestätigung dafür in der Dokumentation - aber wenn die unordered_map ist Wiederkäuen nach der klassischen Hash-Tabellendatenstruktur, könnten Sie set the max_load_factor zu einem sehr hohen value und setze es auf normal zurück, wenn du fertig bist (was eine erneute Wiederherstellung auslöst) (oder zu einem vorhergesagten Wert, wenn du vorhersagen kannst, wie viele Elemente entfernt werden).

In Bezug auf die klassische Hash-Tabelle sollte es seit dem erneuten Aufräumen funktionieren, wenn die Tabelle verkleinert wird, wenn die Größe niedriger als 1/max_load_factor ist.

(nicht sicher, es ist der Fall in C++, aber ich nehme an, es ist der Versuch, da es wirklich einfach zu implementieren ist).