STL-Vektor vs. Kartenlöschung
https://stackoverflow.com/questions/52714
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Im STL verfügen fast alle Container über eine Löschfunktion.Die Frage, die ich habe, ist, dass die Löschfunktion in einem Vektor einen Iterator zurückgibt, der auf das nächste Element im Vektor zeigt.Der Kartencontainer tut dies nicht.Stattdessen wird eine Lücke zurückgegeben.Weiß jemand, warum es diese Inkonsistenz gibt?
Lösung
Sehen http://www.sgi.com/tech/stl/Map.html
MAP verfügt über die wichtige Eigenschaft, die ein neues Element in eine Karte einfügt, die Iteratoren nicht ungültig machen, die auf vorhandene Elemente hinweisen.Wenn Sie ein Element aus einer Karte löschen, werden auch keine Iteratoren ungültig, außer für Iteratoren, die tatsächlich auf das Element hinweisen, das gelöscht wird.
Der Grund für die Rückgabe eines Iterators beim Löschen besteht darin, dass Sie die Liste durchlaufen und dabei Elemente löschen können.Wenn durch das Löschen eines Elements vorhandene Iteratoren nicht ungültig werden, ist dies nicht erforderlich.
Andere Tipps
erase gibt eine zurück iterator in C++11.Das ist wegen Mängelbericht 130:
Tabelle 67 (23.1.1) besagt, dass container::erase(iterator) einen Iterator zurückgibt.Tabelle 69 (23.1.2) besagt, dass assoziative Container zusätzlich zu dieser Anforderung auch sagen, dass container::erase(iterator) void zurückgibt.Das ist keine Ergänzung;Es handelt sich um eine Änderung der Anforderungen, die dazu führt, dass assoziative Container die Anforderungen für Container nicht mehr erfüllen.
Der Normenausschuss hat dies akzeptiert:
Die LWG stimmt zu, dass der Rückgabetyp „Iterator“ und nicht „void“ sein sollte.(Alex Stepanov stimmt auch zu.)
(LWG = Bibliotheksarbeitsgemeinschaft).
Die Inkonsistenz ist gebrauchsbedingt. vector ist eine Folge mit einer Ordnung über die Elemente.Zwar stimmt es, dass die Elemente in a map auch nach einem Vergleichskriterium geordnet sind, ist diese Reihenfolge aus der Struktur nicht ersichtlich.Es gibt keinen effizienten Weg, von einem Element zum nächsten zu gelangen (effizient = konstante Zeit).Tatsächlich ist die Iteration über die Karte ziemlich teuer;entweder die Erstellung des Iterators oder der Iterator selbst erfordert einen Spaziergang durch den gesamten Baum.Dies ist nicht möglich Ö(N), es sei denn, es wird ein Stapel verwendet, dann ist der Platzbedarf nicht mehr konstant.
Alles in allem gibt es einfach keine kostengünstige Möglichkeit, nach dem Löschen das „nächste“ Element zurückzugeben.Für Sequenzen, dort Ist weg.
Außerdem hat Rob recht.Es ist nicht erforderlich, dass die Map einen Iterator zurückgibt.
Nebenbei bemerkt bietet die mit MS Visual Studio C++ (Dinkumware IIRC) gelieferte STL eine Kartenimplementierung mit einer erase Funktion, die einen Iterator zum nächsten Element zurückgibt.
Sie stellen fest, dass es nicht den Standards entspricht.
Ich habe keine Ahnung, ob das die Antwort ist, aber ein Grund könnte in den Kosten für die Suche nach dem nächsten Element liegen.Das Durchlaufen einer Karte ist von Natur aus „langsam“.
