Iterator-Ungültigkeitsregeln

543

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.)

Leichtigkeitsrennen im Orbit
quelle
Sollten die Antworten dasselbe Format haben wie Ihre Antwort?
PW
@PW IMO, die aus Symmetriegründen bevorzugt würde, aber ich kann sie nicht durchsetzen: P
Lightness Races in Orbit
Was ist mit C ++ 20?
Walter
1
@ Walter existiert noch nicht;)
Leichtigkeitsrennen im Orbit
Diese Frage ist, um Leela aus Futurama zu zitieren, aus dem dummen Zeitalter und sollte meiner bescheidenen Meinung nach offen gelassen werden.
Roman Luštrik

Antworten:

111

C ++ 17 (Alle Referenzen stammen aus dem endgültigen Arbeitsentwurf von CPP17 - n4659 )


Einfügen

Sequenzcontainer

  • vector: Die Funktionen insert, emplace_back, emplace, push_backUrsache 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 reserveFunktion 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ürde capacity(). [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_backFunktionen unter dieser Regel fallen.

  • forward_list: Keine der Überladungen von insert_afterdarf 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: Die insertund emplaceMitglieder 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 insertund emplaceMitglieder 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 insertund emplaceMitglieder bleiben die Wirksamkeit von Iteratoren beeinflussen , wenn (N+n) <= z * B, in dem Ndie Anzahl der Elemente in dem Behälter vor dem Einfügevorgang ist, nist die Anzahl der Elemente eingesetzt ist , Bist der Eimer Zähler des Behälters, und zist 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 verwiesen awird, ungültig, aber Iteratoren auf verbleibende Elemente a2bleiben gültig. (Tabelle 91 - Anforderungen für ungeordnete assoziative Container)

Behälteradapter

  • stack: vom zugrunde liegenden Container geerbt
  • queue: vom zugrunde liegenden Container geerbt
  • priority_queue: vom zugrunde liegenden Container geerbt

Löschen

Sequenzcontainer

  • vector: Die Funktionen eraseund pop_backungültigen Iteratoren und Referenzen am oder nach dem Löschpunkt. [26.3.11.5/3]

  • deque: Eine Löschoperation, die das letzte Element eines dequeungü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, dequeaber 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öscht deque, macht den Past-the-End-Iterator und alle Iteratoren ungültig und verweist auf alle Elemente des deque. [Hinweis: pop_frontund pop_backsind 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ür erase, pop_front, pop_back, clearFunktionen.
    removeund remove_ifElementfunktionen: Löscht alle Elemente in der Liste, auf die von einem Listeniterator verwiesen wird, ifü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].
    uniqueElementfunktion - Löscht alle bis auf das erste Element aus jeder aufeinanderfolgenden Gruppe gleicher Elemente, auf die der Iterator iin 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: macht erase_afternur Iteratoren und Verweise auf die gelöschten Elemente ungültig. [26.3.9.5/1].
    removeund remove_ifElementfunktionen - 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ür remove()), pred(*i)ist wahr (für remove_if()). Ungültig macht nur die Iteratoren und Verweise auf die gelöschten Elemente. [26.3.9.6/12].
    uniqueElementfunktion - 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) oder pred(*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: macht clearalle 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ür forward_list, clearmacht Past-the-End-Iteratoren nicht ungültig. [26.3.9.5/32]

  • All Sequence Containers: macht assignalle Verweise, Zeiger und Iteratoren ungültig, die auf die Elemente des Containers verweisen. Für vectorund macht dequeauch den Iterator nach dem Ende ungültig. (Tabelle 87 - Anforderungen an Sequenzcontainer)

Assoziative Container

  • All Associative Containers: Die eraseMitglieder dürfen nur Iteratoren und Verweise auf die gelöschten Elemente ungültig machen [26.2.6 / 9].

  • All Associative Containers: Die extractMitglieder 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 geerbt
  • queue: vom zugrunde liegenden Container geerbt
  • priority_queue: vom zugrunde liegenden Container geerbt

Allgemeine 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:

  • transformAlgorithmus: Die Funktionen opund binary_opdürfen Iteratoren oder Unterordnungen nicht ungültig machen oder Elemente in den Bereichen modifizieren [28.6.4 / 1].

  • accumulateAlgorithmus: Im Bereich [first, last] binary_opdürfen weder Elemente geändert noch Iteratoren oder Unterbereiche ungültig gemacht werden [29.8.2 / 1].

  • reduceAlgorithmus: binary_op darf weder Iteratoren oder Unterordnungen ungültig machen noch Elemente im Bereich [first, last] modifizieren. [29.8.3 / 5]

und so weiter...

PW
quelle
7
Oh PW du Held!
Leichtigkeitsrennen im Orbit
2
@LightnessRacesinOrbit: Versucht, dies gemäß Ihrem ursprünglichen Antwortformat zu tun. :)
PW
1
Können wir auch eine Auflistung für haben std::string? Ich denke, es ist anders als std::vectorwegen SSO
sp2danny
1
@ sp2danny: Aufgrund von SSO stringschlä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.
PW
@ LightnessRaceswithMonica Vielen Dank für die harte Arbeit. Ich habe eine Frage, die mich tagelang verwirrt. Was bedeutet "ungültig" in diesen Kontexten genau? Bedeutet es, dass "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?
Rick
410

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 geerbt
  • queue: vom zugrunde liegenden Container geerbt
  • priority_queue: vom zugrunde liegenden Container geerbt

Lö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 geerbt
  • queue: vom zugrunde liegenden Container geerbt
  • priority_queue: vom zugrunde liegenden Container geerbt

Größ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

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 . [23.1 / 11]

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.

Leichtigkeitsrennen im Orbit
quelle
5
Gute Idee, nur um zu bemerken: Ich denke, dass die assoziativen Container in einer einzigen Zeile zusammengefasst werden könnten, und es könnte sich lohnen, dann eine weitere Zeile der ungeordneten assoziativen hinzuzufügen , obwohl ich nicht sicher bin, wie der Aufwärmteil sein könnte Wissen Sie, wie Sie beim Einfügen / Löschen überprüfen können, ob eine erneute Aufbereitung ausgelöst wird oder nicht?
Matthieu M.
1
IIRC, irgendwo sagt die Spezifikation, dass der Enditerator kein Iterator "für Objekte in diesem Container" ist. Ich frage mich, wie diese Garantien jeweils für den Enditerator aussehen.
Johannes Schaub - litb
1
@MuhammadAnnaqeeb: Diese Antwort macht zwar nicht klar, da ich eine Verknüpfung gewählt habe, aber die Absicht ist zu sagen, dass das Ändern der Größe das Einfügen / Löschen ist, als ob eine Neuzuweisung erforderlich wäre. Sie können dies als das Gleiche wie das Löschen betrachten Fügen Sie dann alle betroffenen Elemente erneut ein. Dieser Abschnitt der Antwort könnte sicherlich verbessert werden.
Leichtigkeitsrennen im Orbit
1
@ Yakk: Aber das tut es nicht; siehe den zitierten Standardtext. Sieht so aus, als wäre das in C ++ 11 behoben worden. :)
Leichtigkeitsrennen im Orbit
1
@metamorphosis: deque speichert Daten in nicht zusammenhängenden Blöcken. Das Einfügen am Anfang oder Ende kann einen neuen Block zuweisen, bewegt sich jedoch nie um vorherige Elemente herum, sodass Zeiger gültig bleiben. Die Regeln für den Übergang zum nächsten / vorherigen Element ändern sich jedoch, wenn ein neuer Block zugewiesen wird, sodass Iteratoren ungültig werden.
Nick Matteo
357

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ür insert_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 * Bwenn zder maximale Lastfaktor ist und Bdie aktuelle Anzahl der Schaufeln. [23.2.5 / 14]

Behälteradapter

  • stack: vom zugrunde liegenden Container geerbt
  • queue: vom zugrunde liegenden Container geerbt
  • priority_queue: vom zugrunde liegenden Container geerbt

Lö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ür erase_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 geerbt
  • queue: vom zugrunde liegenden Container geerbt
  • priority_queue: vom zugrunde liegenden Container geerbt

Größ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

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 . [23.2.1 / 11]

Anmerkung 2

Keine swap () -Funktion macht alle Referenzen, 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] [23.2.1 / 10]

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

vectorund alle ungeordneten assoziativen Container unterstützen, reserve(n)was garantiert, dass zumindest bis zur Größe des Containers keine automatische Größenänderung erfolgt n. Bei ungeordneten assoziativen Containern ist Vorsicht geboten, da in einem künftigen Vorschlag ein Mindestladefaktor festgelegt werden kann, der ein erneutes Aufwärmen insertnach ausreichenden eraseVorgängen ermöglicht, um die Containergröße unter das Minimum zu reduzieren. Die Garantie sollte nach einem erase.

Leichtigkeitsrennen im Orbit
quelle
Neben swap(), was die Regeln für Iterator Gültigkeit auf Kopieren / Verschieben Zuordnung?
Wiedersehen
@LightnessRacesinOrbit: Wie das Einfügen, Löschen, Ändern der Größe und Austauschen sind auch die Zuweisungen zum Kopieren / Verschieben Mitgliedsfunktionen von std :: vector. Ich denke, Sie könnten auch die Regeln für die Gültigkeit des Iterators für sie bereitstellen.
Wiedersehen
@goodbyeera: Du meinst kopieren / verschieben ein Element zuweisen? Dies wirkt sich nicht auf Iteratoren aus. Warum sollte es? Sie treffen Note 1 oben.
Leichtigkeitsrennen im Orbit
1
Ich glaube, ich habe einen Fehler gemacht, weil er std::basic_stringnicht 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)?
Deduplikator
2
Sind diese Regeln in C ++ 14 alle gleich? C ++ 17 (soweit bekannt)?
Einpoklum
40

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::vectorindem Sie std::insert_iteratores 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

std::vector<int> v(10);
std::vector<int>::iterator it = v.begin() + 5;
std::insert_iterator<std::vector<int> > it_ins(v, it);

for (unsigned n = 20; n > 0; --n)
  *it_ins++ = rand();

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 itwird offensichtlich ungültig, it_insbleibt aber weiterhin gültig.

Ameise
quelle
22

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::vectorEinfügeoperation auf die zu erwähnen Gültigkeit von Iteratoren und Verweisen in Bezug auf reserve()und capacity(), die die am besten bewertete Antwort nicht bemerkte.

C ++ 03:

Durch die Neuzuweisung werden alle Referenzen, Zeiger und Iteratoren ungültig, die auf die Elemente in der Sequenz verweisen. Es wird garantiert, dass während Einfügungen, die nach einem Aufruf von Reserve () erfolgen, keine Neuzuweisung stattfindet, bis eine Einfügung die Größe des Vektors größer machen würde als die Größe, die im letzten Aufruf von Reserve () angegeben wurde .

C ++ 11:

Durch die Neuzuweisung werden alle Referenzen, Zeiger und Iteratoren ungültig, die auf die Elemente in der Sequenz verweisen. Es wird garantiert, dass während Einfügungen, die nach einem Aufruf von Reserve () erfolgen, keine Neuzuweisung stattfindet, bis eine Einfügung die Größe des Vektors größer als den Wert von Kapazität () machen würde .

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 a insert()bewirkt , dass die Größe des Vektors den im vorherigen reserve()Aufruf angegebenen Wert erreicht (der durchaus kleiner als der aktuelle Wert sein kann, capacity()da a reserve()zu einem größeren Wert führen kann capacity()als gewünscht), kann jeder nachfolgende Wert insert()eine Neuzuweisung verursachen und ungültig machen alle Iteratoren und Referenzen. In C ++ 11 wird dies nicht passieren und Sie können immer darauf vertrauen capacity(), dass die nächste Neuzuweisung nicht erfolgt, bevor die Größe überschritten wird capacity().

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 an capacity(), andernfalls können Sie sich über eine " vorzeitige " Neuzuweisung wundern .

Neverhoodboy
quelle
14
Ich würde jedoch jeden Compiler erschießen, der mir das angetan hat, und keine Jury im Land würde mich verurteilen.
Yakk - Adam Nevraumont
9
Ich habe das nicht "übersehen"; Es war ein redaktioneller Fehler in C ++ 03, der in C ++ 11 korrigiert wurde. Kein Mainstream-Compiler nutzt den Fehler aus.
Leichtigkeitsrennen im Orbit
1
@ Yakk Ich denke, gcc macht Iteratoren in solchen Situationen bereits ungültig.
ShreevatsaR
2

Hier ist eine schöne Übersichtstabelle von cppreference.com :

Geben Sie hier die Bildbeschreibung ein

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.

DarioP
quelle