Was sind die Iterator-Ungültigkeitsregeln für C ++ - Container?
Vorzugsweise in einem Zusammenfassungslistenformat.
(Hinweis: Dies ist als Eintrag in die C ++ - FAQ von Stack Overflow gedacht . Wenn Sie die Idee kritisieren möchten, eine FAQ in dieser Form bereitzustellen, ist die Veröffentlichung auf Meta, mit der all dies begonnen hat , der richtige Ort dafür. Antworten auf Diese Frage wird im C ++ - Chatroom überwacht, in dem die FAQ-Idee ursprünglich begann, sodass Ihre Antwort sehr wahrscheinlich von denjenigen gelesen wird, die auf die Idee gekommen sind.)
Antworten:
C ++ 17 (Alle Referenzen stammen aus dem endgültigen Arbeitsentwurf von CPP17 - n4659 )
Einfügen
Sequenzcontainer
vector
: Die Funktioneninsert
,emplace_back
,emplace
,push_back
Ursache Zu , wenn die neue Größe größer ist als die alte Kapazität ist. Durch die Neuzuweisung werden alle Referenzen, Zeiger und Iteratoren ungültig, die auf die Elemente in der Sequenz verweisen. Wenn keine Neuzuweisung erfolgt, bleiben alle Iteratoren und Referenzen vor der Einfügemarke gültig. [26.3.11.5/1]In Bezug auf die
reserve
Funktion macht die Neuzuweisung alle Referenzen, Zeiger und Iteratoren ungültig, die auf die Elemente in der Sequenz verweisen. Während Einfügungen, die nach einem Aufruf von erfolgen, darf keine Neuzuweisung erfolgen,reserve()
bis eine Einfügung die Größe des Vektors größer als den Wert von machen würdecapacity()
. [26.3.11.3/6]deque
: Eine Einfügung in der Mitte der Deque macht alle Iteratoren und Verweise auf Elemente der Deque ungültig. Ein Einfügen an beiden Enden der Deque macht alle Iteratoren der Deque ungültig, hat jedoch keine Auswirkung auf die Gültigkeit von Verweisen auf Elemente der Deque. [26.3.8.4/1]list
: Beeinflusst nicht die Gültigkeit von Iteratoren und Referenzen. Wenn eine Ausnahme ausgelöst wird, gibt es keine Auswirkungen. [26.3.10.4/1].Die
insert
,emplace_front
,emplace_back
,emplace
,push_front
,push_back
Funktionen unter dieser Regel fallen.forward_list
: Keine der Überladungen voninsert_after
darf die Gültigkeit von Iteratoren und Referenzen beeinträchtigen [26.3.9.5/1]array
: In der Regel werden Iteratoren eines Arrays während der gesamten Lebensdauer des Arrays niemals ungültig. Man sollte jedoch beachten, dass der Iterator während des Austauschs weiterhin auf dasselbe Array-Element zeigt und somit seinen Wert ändert.Assoziative Container
All Associative Containers
: Dieinsert
undemplace
Mitglieder haben keinen Einfluss auf die Gültigkeit von Iteratoren und Verweisen auf den Container [26.2.6 / 9].Ungeordnete assoziative Container
All Unordered Associative Containers
: Durch erneutes Aufbereiten werden Iteratoren ungültig, die Reihenfolge zwischen Elementen wird geändert und Änderungen, in denen Bucket-Elemente angezeigt werden, Zeiger oder Verweise auf Elemente werden jedoch nicht ungültig. [26.2.7 / 9]Die
insert
undemplace
Mitglieder haben keinen Einfluss auf die Gültigkeit von Verweisen auf Containerelemente, können jedoch alle Iteratoren für den Container ungültig machen. [26.2.7 / 14]Die
insert
undemplace
Mitglieder bleiben die Wirksamkeit von Iteratoren beeinflussen , wenn(N+n) <= z * B
, in demN
die Anzahl der Elemente in dem Behälter vor dem Einfügevorgang ist,n
ist die Anzahl der Elemente eingesetzt ist ,B
ist der Eimer Zähler des Behälters, undz
ist die maximaler Ladefaktor des Containers. [26.2.7 / 15]All Unordered Associative Containers
: Im Falle einer Zusammenführungsoperation (z. B.a.merge(a2)
) werden Iteratoren, die sich auf die übertragenen Elemente beziehen, und alle Iteratoren, auf die verwiesena
wird, ungültig, aber Iteratoren auf verbleibende Elementea2
bleiben gültig. (Tabelle 91 - Anforderungen für ungeordnete assoziative Container)Behälteradapter
stack
: vom zugrunde liegenden Container geerbtqueue
: vom zugrunde liegenden Container geerbtpriority_queue
: vom zugrunde liegenden Container geerbtLöschen
Sequenzcontainer
vector
: Die Funktionenerase
undpop_back
ungültigen Iteratoren und Referenzen am oder nach dem Löschpunkt. [26.3.11.5/3]deque
: Eine Löschoperation, die das letzte Element einesdeque
ungültig macht, macht nur den Past-the-End-Iterator und alle Iteratoren und Verweise auf die gelöschten Elemente ungültig. Eine Löschoperation, die das erste Element eines,deque
aber nicht das letzte Element löscht , macht nur Iteratoren und Verweise auf die gelöschten Elemente ungültig. Eine Löschoperation, die weder das erste noch das letzte Element eines Elements löschtdeque
, macht den Past-the-End-Iterator und alle Iteratoren ungültig und verweist auf alle Elemente desdeque
. [Hinweis:pop_front
undpop_back
sind Löschvorgänge. —Ende Anmerkung] [26.3.8.4/4]list
: Ungültig macht nur die Iteratoren und Verweise auf die gelöschten Elemente. [26.3.10.4/3]. Dies gilt fürerase
,pop_front
,pop_back
,clear
Funktionen.remove
undremove_if
Elementfunktionen: Löscht alle Elemente in der Liste, auf die von einem Listeniterator verwiesen wird,i
für den die folgenden Bedingungen gelten:*i == value
,pred(*i) != false
. Ungültig macht nur die Iteratoren und Verweise auf die gelöschten Elemente [26.3.10.5/15].unique
Elementfunktion - Löscht alle bis auf das erste Element aus jeder aufeinanderfolgenden Gruppe gleicher Elemente, auf die der Iteratori
in dem Bereich verweist,[first + 1, last)
für den*i == *(i-1)
(für die Version von unique ohne Argumente) oderpred(*i, *(i - 1))
(für die Version von unique mit einem Prädikatargument) gilt. Ungültig macht nur die Iteratoren und Verweise auf die gelöschten Elemente. [26.3.10.5/19]forward_list
: machterase_after
nur Iteratoren und Verweise auf die gelöschten Elemente ungültig. [26.3.9.5/1].remove
undremove_if
Elementfunktionen - Löscht alle Elemente in der Liste, auf die von einem Listeniterator i verwiesen wird, für den die folgenden Bedingungen gelten:*i == value
(fürremove()
),pred(*i)
ist wahr (fürremove_if()
). Ungültig macht nur die Iteratoren und Verweise auf die gelöschten Elemente. [26.3.9.6/12].unique
Elementfunktion - Löscht alle bis auf das erste Element aus jeder aufeinanderfolgenden Gruppe gleicher Elemente, auf die der Iterator i im Bereich [first + 1, last] verweist, für die*i == *(i-1)
(für die Version ohne Argumente) oderpred(*i, *(i - 1))
(für die Version mit einem Prädikat) Argument) gilt. Ungültig macht nur die Iteratoren und Verweise auf die gelöschten Elemente. [26.3.9.6/16]All Sequence Containers
: machtclear
alle Referenzen, Zeiger und Iteratoren ungültig, die auf die Elemente von a verweisen, und macht möglicherweise den Iterator nach dem Ende ungültig (Tabelle 87 - Anforderungen an Sequenzcontainer). Aber fürforward_list
,clear
macht Past-the-End-Iteratoren nicht ungültig. [26.3.9.5/32]All Sequence Containers
: machtassign
alle Verweise, Zeiger und Iteratoren ungültig, die auf die Elemente des Containers verweisen. Fürvector
und machtdeque
auch den Iterator nach dem Ende ungültig. (Tabelle 87 - Anforderungen an Sequenzcontainer)Assoziative Container
All Associative Containers
: Dieerase
Mitglieder dürfen nur Iteratoren und Verweise auf die gelöschten Elemente ungültig machen [26.2.6 / 9].All Associative Containers
: Dieextract
Mitglieder machen nur Iteratoren für das entfernte Element ungültig. Zeiger und Verweise auf das entfernte Element bleiben gültig [26.2.6 / 10]Behälteradapter
stack
: vom zugrunde liegenden Container geerbtqueue
: vom zugrunde liegenden Container geerbtpriority_queue
: vom zugrunde liegenden Container geerbtAllgemeine Containeranforderungen in Bezug auf die Ungültigmachung des Iterators:
Sofern nicht anders angegeben (entweder explizit oder durch Definieren einer Funktion in Bezug auf andere Funktionen), darf das Aufrufen einer Containerelementfunktion oder das Übergeben eines Containers als Argument an eine Bibliotheksfunktion die Iteratoren für Objekte in diesem Container nicht ungültig machen oder deren Werte ändern . [26.2.1 / 12]
Keine
swap()
Funktion macht Verweise, Zeiger oder Iteratoren ungültig, die auf die Elemente der ausgelagerten Container verweisen. [Hinweis: Der end () - Iterator verweist nicht auf ein Element, daher kann er ungültig werden. —Ende Anmerkung] [26.2.1 / (11.6)]Als Beispiele für die oben genannten Anforderungen:
transform
Algorithmus: Die Funktionenop
undbinary_op
dürfen Iteratoren oder Unterordnungen nicht ungültig machen oder Elemente in den Bereichen modifizieren [28.6.4 / 1].accumulate
Algorithmus: Im Bereich [first, last]binary_op
dürfen weder Elemente geändert noch Iteratoren oder Unterbereiche ungültig gemacht werden [29.8.2 / 1].reduce
Algorithmus: binary_op darf weder Iteratoren oder Unterordnungen ungültig machen noch Elemente im Bereich [first, last] modifizieren. [29.8.3 / 5]und so weiter...
quelle
std::string
? Ich denke, es ist anders alsstd::vector
wegen SSOstring
schlägt die zweite oben aufgeführte allgemeine Anforderung fehl. Also habe ich es nicht aufgenommen. Es wurde auch versucht, das gleiche Muster wie in den vorherigen FAQ-Einträgen beizubehalten."invalidated" can mean "no longer points to what it used to", not just "may not point to any valid element"
@Marshall Clow in dieser Antwort beschrieben wird ? Oder zeigt es nur 1 der 2 Bedingungen an?C ++ 03 (Quelle: Iterator-Invalidierungsregeln (C ++ 03) )
Einfügen
Sequenzcontainer
vector
: Alle Iteratoren und Referenzen vor dem Einfügepunkt bleiben unberührt, es sei denn, die neue Containergröße ist größer als die vorherige Kapazität (in diesem Fall sind alle Iteratoren und Referenzen ungültig) [23.2.4.3/1]deque
: Alle Iteratoren und Verweise sind ungültig, es sei denn, das eingefügte Element befindet sich am Ende (vorne oder hinten) der Deque (in diesem Fall sind alle Iteratoren ungültig, Verweise auf Elemente sind jedoch nicht betroffen) [23.2.1.3/1]list
: Alle Iteratoren und Referenzen sind nicht betroffen [23.2.2.3/1]Assoziative Container
[multi]{set,map}
: Alle Iteratoren und Referenzen nicht betroffen [23.1.2 / 8]Behälteradapter
stack
: vom zugrunde liegenden Container geerbtqueue
: vom zugrunde liegenden Container geerbtpriority_queue
: vom zugrunde liegenden Container geerbtLöschen
Sequenzcontainer
vector
: Jeder Iterator und jede Referenz nach dem Löschpunkt ist ungültig [23.2.4.3/3]deque
: Alle Iteratoren und Verweise sind ungültig, es sei denn, die gelöschten Elemente befinden sich am Ende (vorne oder hinten) der Deque (in diesem Fall werden nur Iteratoren und Verweise auf die gelöschten Elemente ungültig gemacht) [23.2.1.3/4]list
: Nur die Iteratoren und Verweise auf das gelöschte Element sind ungültig. [23.2.2.3/3]Assoziative Container
[multi]{set,map}
: Nur Iteratoren und Verweise auf die gelöschten Elemente werden ungültig gemacht [23.1.2 / 8]Behälteradapter
stack
: vom zugrunde liegenden Container geerbtqueue
: vom zugrunde liegenden Container geerbtpriority_queue
: vom zugrunde liegenden Container geerbtGrößenänderung
vector
: gemäß Einfügen / Löschen [23.2.4.2/6]deque
: gemäß Einfügen / Löschen [23.2.1.2/1]list
: gemäß Einfügen / Löschen [23.2.2.2/1]Anmerkung 1
Anmerkung 2
In C ++ 2003 ist nicht klar, ob "End" -Iteratoren den oben genannten Regeln unterliegen . Sie sollten sowieso davon ausgehen, dass dies der Fall ist (wie dies in der Praxis der Fall ist).
Notiz 3
Die Regeln für die Ungültigmachung von Zeigern sind die gleichen wie die Regeln für die Ungültigmachung von Referenzen.
quelle
C ++ 11 (Quelle: Iterator-Invalidierungsregeln (C ++ 0x) )
Einfügen
Sequenzcontainer
vector
: Alle Iteratoren und Referenzen vor dem Einfügepunkt bleiben unberührt, es sei denn, die neue Containergröße ist größer als die vorherige Kapazität (in diesem Fall sind alle Iteratoren und Referenzen ungültig) [23.3.6.5/1]deque
: Alle Iteratoren und Referenzen sind ungültig, es sei denn, das eingefügte Element befindet sich am Ende (vorne oder hinten) der Deque (in diesem Fall sind alle Iteratoren ungültig, aber Verweise auf Elemente sind nicht betroffen) [23.3.3.4/1]list
: Alle Iteratoren und Referenzen nicht betroffen [23.3.5.4/1]forward_list
: Alle Iteratoren und Referenzen sind nicht betroffen (gilt fürinsert_after
) [23.3.4.5/1]array
: (n / a)Assoziative Container
[multi]{set,map}
: alle Iteratoren und Referenzen nicht betroffen [23.2.4 / 9]Unsortierte assoziative Container
unordered_[multi]{set,map}
: Alle Iteratoren, die beim erneuten Aufwärmen ungültig werden, verweisen jedoch nicht [23.2.5 / 8]. Wiederkäuen nicht auftritt , wenn das Einfügen nicht Ursache die Größe des Behälters zu überschreiten ,z * B
wennz
der maximale Lastfaktor ist undB
die aktuelle Anzahl der Schaufeln. [23.2.5 / 14]Behälteradapter
stack
: vom zugrunde liegenden Container geerbtqueue
: vom zugrunde liegenden Container geerbtpriority_queue
: vom zugrunde liegenden Container geerbtLöschen
Sequenzcontainer
vector
: Jeder Iterator und jede Referenz am oder nach dem Löschpunkt ist ungültig [23.3.6.5/3]deque
: Das Löschen des letzten Elements macht nur Iteratoren und Verweise auf die gelöschten Elemente und den Past-the-End-Iterator ungültig. Das Löschen des ersten Elements macht nur Iteratoren und Verweise auf die gelöschten Elemente ungültig. Durch das Löschen anderer Elemente werden alle Iteratoren und Referenzen ungültig (einschließlich des Iterators nach dem Ende) [23.3.3.4/4]list
: Nur die Iteratoren und Verweise auf das gelöschte Element sind ungültig. [23.3.5.4/3]forward_list
: Nur die Iteratoren und Verweise auf das gelöschte Element sind ungültig (gilt fürerase_after
) [23.3.4.5/1]array
: (n / a)Assoziative Container
[multi]{set,map}
: Nur Iteratoren und Verweise auf die gelöschten Elemente werden ungültig gemacht [23.2.4 / 9]Ungeordnete assoziative Container
unordered_[multi]{set,map}
: Nur Iteratoren und Verweise auf die gelöschten Elemente werden ungültig gemacht [23.2.5 / 13]Behälteradapter
stack
: vom zugrunde liegenden Container geerbtqueue
: vom zugrunde liegenden Container geerbtpriority_queue
: vom zugrunde liegenden Container geerbtGrößenänderung
vector
: gemäß Einfügen / Löschen [23.3.6.5/12]deque
: gemäß Einfügen / Löschen [23.3.3.3/3]list
: gemäß Einfügen / Löschen [23.3.5.3/1]forward_list
: gemäß Einfügen / Löschen [23.3.4.5/25]array
: (n / a)Anmerkung 1
Anmerkung 2
Notiz 3
Anders als die oben Vorbehalt in Bezug auf
swap()
, ist es nicht klar , ob „end“ Iteratoren sind unter den genannten pro-Container Regeln aufgelistet ; Sie sollten sowieso annehmen, dass sie es sind.Anmerkung 4
vector
und alle ungeordneten assoziativen Container unterstützen,reserve(n)
was garantiert, dass zumindest bis zur Größe des Containers keine automatische Größenänderung erfolgtn
. Bei ungeordneten assoziativen Containern ist Vorsicht geboten, da in einem künftigen Vorschlag ein Mindestladefaktor festgelegt werden kann, der ein erneutes Aufwärmeninsert
nach ausreichendenerase
Vorgängen ermöglicht, um die Containergröße unter das Minimum zu reduzieren. Die Garantie sollte nach einemerase
.quelle
swap()
, was die Regeln für Iterator Gültigkeit auf Kopieren / Verschieben Zuordnung?std::basic_string
nicht als Container gezählt zu werden scheint und sicherlich nicht als Container in dem Abschnitt des Standards, für den dieser Hinweis gilt. Doch wo steht, dass SSO nicht erlaubt ist (ich weiß, dass COW ist)?Es ist wahrscheinlich hinzuzufügen , dass ein Insert - Iterator jeglicher Art (
std::back_insert_iterator
,std::front_insert_iterator
,std::insert_iterator
) wird so lange gültig bleiben garantiert , da alle Einfügungen durch diesen Iterator ausgeführt werden und kein anderes unabhängiges Iterator-entkräftet Ereignis eintritt.Zum Beispiel, wenn Sie eine Reihe von Einfügeoperationen in ein durchführen ,
std::vector
indem Siestd::insert_iterator
es ist durchaus möglich , dass diese Einfügungen Vektor Umschichtung auslösen, die alle Iteratoren ungültig wird , dass „Punkt“ in diesem Vektor. Der betreffende Einfügeiterator bleibt jedoch garantiert gültig, dh Sie können die Reihenfolge der Einfügungen sicher fortsetzen. Sie müssen sich überhaupt keine Gedanken über das Auslösen einer Vektorumverteilung machen.Dies gilt wiederum nur für Einfügungen, die über den Einfügeiterator selbst ausgeführt werden. Wenn ein iteratorinvalidierendes Ereignis durch eine unabhängige Aktion für den Container ausgelöst wird, wird der Einfügeiterator gemäß den allgemeinen Regeln ebenfalls ungültig.
Zum Beispiel dieser Code
Es wird garantiert, dass eine gültige Folge von Einfügungen in den Vektor ausgeführt wird, selbst wenn der Vektor "entscheidet", irgendwo in der Mitte dieses Prozesses neu zuzuweisen. Iterator
it
wird offensichtlich ungültig,it_ins
bleibt aber weiterhin gültig.quelle
Da diese Frage so viele Stimmen erhält und zu einer Art FAQ wird, ist es wahrscheinlich besser, eine separate Antwort zu schreiben, um einen signifikanten Unterschied zwischen C ++ 03 und C ++ 11 in Bezug auf die Auswirkungen der
std::vector
Einfügeoperation auf die zu erwähnen Gültigkeit von Iteratoren und Verweisen in Bezug aufreserve()
undcapacity()
, die die am besten bewertete Antwort nicht bemerkte.C ++ 03:
C ++ 11:
In C ++ 03 ist es also nicht "
unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated)
", wie in der anderen Antwort erwähnt, sondern "greater than the size specified in the most recent call to reserve()
". Dies ist eine Sache, die C ++ 03 von C ++ 11 unterscheidet. Wenn in C ++ 03 ainsert()
bewirkt , dass die Größe des Vektors den im vorherigenreserve()
Aufruf angegebenen Wert erreicht (der durchaus kleiner als der aktuelle Wert sein kann,capacity()
da areserve()
zu einem größeren Wert führen kanncapacity()
als gewünscht), kann jeder nachfolgende Wertinsert()
eine Neuzuweisung verursachen und ungültig machen alle Iteratoren und Referenzen. In C ++ 11 wird dies nicht passieren und Sie können immer darauf vertrauencapacity()
, dass die nächste Neuzuweisung nicht erfolgt, bevor die Größe überschritten wirdcapacity()
.Wenn Sie mit einem C ++ 03-Vektor arbeiten und sicherstellen möchten, dass beim Einfügen keine Neuzuweisung erfolgt
reserve()
, sollten Sie die Größe überprüfen, anhand derer Sie die Größe überprüfen sollten den Rückgabewert eines Anrufs ancapacity()
, andernfalls können Sie sich über eine " vorzeitige " Neuzuweisung wundern .quelle
Hier ist eine schöne Übersichtstabelle von cppreference.com :
Hier bezieht sich das Einfügen auf eine Methode, die dem Container ein oder mehrere Elemente hinzufügt, und das Löschen auf eine Methode, die ein oder mehrere Elemente aus dem Container entfernt.
quelle