Jakie są reguły unieważniania iteratora dla kontenerów C ++?

Najlepiej w formie listy podsumowującej.

_{(Uwaga: ma to być wpis do często zadawanych pytań na temat C ++ w programie Stack Overflow . Jeśli chcesz skrytykować pomysł podania w tym formularzu odpowiedzi na najczęściej zadawane pytania, to miejsce na meta, które to wszystko rozpoczęło, byłoby odpowiednim miejscem. Odpowiedzi na to pytanie jest monitorowane w czacie C ++ , gdzie pomysł FAQ powstał w pierwszej kolejności, więc twoje odpowiedzi prawdopodobnie zostaną przeczytane przez tych, którzy wpadli na ten pomysł).}

C ++ 17 (Wszystkie odniesienia pochodzą z ostatecznej wersji roboczej CPP17 - n4659 )

Wprowadzenie

Pojemniki z sekwencjami

• vector: Funkcje insert, emplace_back, emplace, push_backprzyczyna realokacja jeśli nowy rozmiar jest większy niż stary pojemności. Realokacja unieważnia wszystkie odwołania, wskaźniki i iteratory odnoszące się do elementów w sekwencji. Jeśli nie nastąpi ponowny przydział, wszystkie iteratory i referencje przed punktem wstawienia pozostają ważne. [26.3.11.5/1]
  W odniesieniu do reservefunkcji, realokacja unieważnia wszystkie odwołania, wskaźniki i iteratory odnoszące się do elementów w sekwencji. Przeniesienie nie może nastąpić podczas wstawiania, które następuje po wywołaniu, reserve()aż do momentu, gdy wstawienie zwiększy rozmiar wektora niż wartość capacity(). [26.3.11.3/6]

• deque: Wstawienie w środku deque unieważnia wszystkie iteratory i odniesienia do elementów deque. Wstawienie na każdym końcu deque unieważnia wszystkie iteratory deque, ale nie ma wpływu na ważność odwołań do elementów deque. [26.3.8.4/1]

• list: Nie wpływa na ważność iteratorów i referencji. Jeśli zostanie zgłoszony wyjątek, nie ma żadnych efektów. [26.3.10.4/1]. , , , , , Funkcje są objęte tą zasadą.
  insertemplace_frontemplace_backemplacepush_frontpush_back

• forward_list: Żadne przeciążenie insert_afternie wpłynie na ważność iteratorów i odniesień [26.3.9.5/1]

• array: Z reguły iteratory tablicy nigdy nie są unieważniane przez cały okres istnienia tablicy. Należy jednak pamiętać, że podczas wymiany iterator będzie nadal wskazywał ten sam element tablicy, a tym samym zmieni jego wartość.

Pojemniki asocjacyjne

• All Associative Containers: Członkowie inserti emplacenie mają wpływu na ważność iteratorów i odniesień do kontenera [26.2.6 / 9]

Nieuporządkowane pojemniki asocjacyjne

• All Unordered Associative Containers: Ponowneashowanie unieważnia iteratory, zmiany kolejności elementów i zmiany, w których elementy segmentu pojawiają się, ale nie unieważnia wskaźników ani odwołań do elementów. [26.2.7 / 9]
  Członkowie inserti emplacenie mają wpływu na ważność odniesień do elementów kontenera, ale mogą unieważnić wszystkie iteratory kontenera. [26.2.7 / 14]
  Elementy inserti emplacenie mają wpływu na ważność iteratorów, jeżeli (N+n) <= z * B, gdzie, gdzie Nliczba elementów w pojemniku przed operacją wstawiania, njest liczbą wstawionych elementów, Bjest liczbą pojemników pojemnika i zjest współczynnik maksymalnego obciążenia kontenera. [26.2.7 / 15]

• All Unordered Associative Containers: W przypadku operacji scalania (np. a.merge(a2)), Iteratory odnoszące się do przesłanych elementów i wszystkie iteratory odnoszące się azostaną unieważnione, ale iteratory do pozostałych elementów a2pozostaną ważne. (Tabela 91 - Nieuporządkowane wymagania dotyczące kontenerów asocjacyjnych)

Adaptery pojemników

• stack: odziedziczony z podstawowego kontenera
• queue: odziedziczony z podstawowego kontenera
• priority_queue: odziedziczony z podstawowego kontenera

Skasowanie

Pojemniki z sekwencjami

• vector: Funkcje erasei pop_backunieważniają iteratory i odwołania w punkcie kasowania lub po nim. [26.3.11.5/3]

• deque: Operacja wymazywania, która usuwa ostatni element elementu dequenieważnego, unieważnia tylko iterator przeszłości i wszystkie iteratory oraz odniesienia do wymazanych elementów. Operacja wymazywania, która usuwa pierwszy element, dequeale nie ostatni element, unieważnia tylko iteratory i odwołania do usuniętych elementów. Operacja wymazywania, która nie usuwa ani pierwszego elementu, ani ostatniego elementu a, dequeunieważnia iterator przeszłości i wszystkie iteratory oraz odwołania do wszystkich elementów deque. [Uwaga: pop_fronti pop_backsą operacjami usuwania. —Wskazówka] [26.3.8.4/4]

• list: Unieważnia tylko iteratory i odwołania do usuniętych elementów. [26.3.10.4/3]. Odnosi się to do erase, pop_front, pop_back, clearfunkcje.
  removei remove_iffunkcje składowe: Usuwa wszystkie elementy z listy, do której odwołuje się iterator listy, idla którego spełnione są następujące warunki: *i == value, pred(*i) != false. Unieważnia tylko iteratory i odwołania do usuniętych elementów [26.3.10.5/15].
  uniquefunkcja członka - usuwa wszystkie oprócz pierwszego elementu z każdej kolejnej grupy równych elementów, do których odwołuje się iterator, iw zakresie, [first + 1, last)dla którego *i == *(i-1)(dla wersji unikalnej bez argumentów) lubpred(*i, *(i - 1))(dla wersji unikatowej z argumentem predykatu). Unieważnia tylko iteratory i odwołania do wymazanych elementów. [26.3.10.5/19]

• forward_list: erase_afterunieważnia tylko iteratory i odniesienia do usuniętych elementów. [26.3.9.5/1].
  removei remove_iffunkcje składowe - usuwa wszystkie elementy z listy, do których odwołuje się iterator listy i, dla których spełnione są następujące warunki: *i == value(for remove()), pred(*i)true (for remove_if()). Unieważnia tylko iteratory i odwołania do wymazanych elementów. [26.3.9.6/12].
  uniquefunkcja członka - usuwa wszystkie oprócz pierwszego elementu z każdej kolejnej grupy równych elementów, do których odwołuje się iterator i, w zakresie [pierwszy + 1, ostatni), dla którego *i == *(i-1)(dla wersji bez argumentów) lub pred(*i, *(i - 1))(dla wersji z predykatem argument). Unieważnia tylko iteratory i odwołania do wymazanych elementów. [26.3.9.6/16]

• All Sequence Containers: clearunieważnia wszystkie odwołania, wskaźniki i iteratory odnoszące się do elementów a i może unieważnić iterator przeszłości (Tabela 87 - Wymagania dotyczące kontenera sekwencji). Ale dla forward_list, clearnie unieważnia iteratorów przeszłości. [26.3.9.5/32]

• All Sequence Containers: assignunieważnia wszystkie odniesienia, wskaźniki i iteratory odnoszące się do elementów kontenera. For vectori deque, także unieważnia iterator przeszłości. (Tabela 87 - Wymagania dotyczące kontenera sekwencji)

Pojemniki asocjacyjne

• All Associative Containers: eraseCzłonkowie unieważniają tylko iteratory i odniesienia do usuniętych elementów [26.2.6 / 9]

• All Associative Containers: extractCzłonkowie unieważniają tylko iteratory usuniętego elementu; wskaźniki i odniesienia do usuniętego elementu pozostają ważne [26.2.6 / 10]

Adaptery pojemników

• stack: odziedziczony z podstawowego kontenera
• queue: odziedziczony z podstawowego kontenera
• priority_queue: odziedziczony z podstawowego kontenera

Ogólne wymagania dotyczące kontenera dotyczące unieważnienia iteratora:

• O ile nie określono inaczej (jawnie lub przez zdefiniowanie funkcji w kategoriach innych funkcji), wywołanie funkcji elementu kontenera lub przekazanie kontenera jako argumentu do funkcji biblioteki nie unieważnia iteratorów ani nie zmienia wartości obiektów w tym kontenerze . [26.2.1 / 12]

• żadna swap()funkcja nie unieważnia żadnych odniesień, wskaźników ani iteratorów odnoszących się do elementów wymienianych kontenerów. [Uwaga: Iterator end () nie odnosi się do żadnego elementu, więc może zostać unieważniony. —Wskazówka] [26.2.1 / (11.6)]

Jako przykłady powyższych wymagań:

• transformalgorytm: Funkcje opi binary_opnie mogą unieważniać iteratorów lub podzakresów ani modyfikować elementów w zakresach [28.6.4 / 1]

• accumulatealgorytm: w zakresie [pierwszy, ostatni] binary_opnie może modyfikować elementów ani unieważniać iteratorów ani podzakresów [29.8.2 / 1]

• reducealgorytm: binary_op nie unieważnia iteratorów ani podzakresów, ani nie modyfikuje elementów w zakresie [pierwszy, ostatni]. [29.8.3 / 5]

i tak dalej...

C ++ 03 (Źródło: Iterator Invalidation Rules (C ++ 03) )

Wprowadzenie

Pojemniki z sekwencjami

• vector: wszystkie iteratory i referencje przed punktem wstawienia pozostają niezmienione, chyba że nowy rozmiar kontenera jest większy niż poprzednia pojemność (w którym to przypadku wszystkie iteratory i referencje są unieważnione) [23.2.4.3/1]
• deque: wszystkie iteratory i referencje są unieważniane, chyba że wstawiony element znajduje się na końcu (przednim lub tylnym) deque (w którym to przypadku wszystkie iteratory są unieważniane, ale odniesienia do elementów pozostają nienaruszone) [23.2.1.3/1]
• list: niezmienione wszystkie iteratory i referencje [23.2.2.3/1]

Pojemniki asocjacyjne

• [multi]{set,map}: niezmienione wszystkie iteratory i referencje [23.1.2 / 8]

Adaptery pojemników

• stack: odziedziczony z podstawowego kontenera
• queue: odziedziczony z podstawowego kontenera
• priority_queue: odziedziczony z podstawowego kontenera

Skasowanie

Pojemniki z sekwencjami

• vector: każdy iterator i odwołanie po punkcie kasowania są unieważnione [23.2.4.3/3]
• deque: wszystkie iteratory i odniesienia są unieważniane, chyba że usunięte elementy znajdują się na końcu (z przodu lub z tyłu) deque (w takim przypadku unieważnione są tylko iteratory i odniesienia do usuniętych elementów) [23.2.1.3/4]
• list: tylko iteratory i odwołania do usuniętego elementu są unieważniane [23.2.2.3/3]

Pojemniki asocjacyjne

• [multi]{set,map}: tylko iteratory i odniesienia do usuniętych elementów są unieważniane [23.1.2 / 8]

Adaptery pojemników

• stack: odziedziczony z podstawowego kontenera
• queue: odziedziczony z podstawowego kontenera
• priority_queue: odziedziczony z podstawowego kontenera

Zmiana rozmiaru

• vector: zgodnie z wstawką / kasowanie [23.2.4.2/6]
• deque: jak we wstawieniu / skasowaniu [23.2.1.2/1]
• list: zgodnie z wstawieniem / usunięcie [23.2.2.2/1]

Notatka 1

O ile nie określono inaczej (jawnie lub przez zdefiniowanie funkcji w kategoriach innych funkcji), wywołanie funkcji elementu kontenera lub przekazanie kontenera jako argumentu do funkcji biblioteki nie unieważnia iteratorów ani nie zmienia wartości obiektów w tym kontenerze . [23.1 / 11]

Uwaga 2

W C ++ 2003 nie jest jasne, czy iteratory „end” podlegają powyższym regułom ; i tak powinieneś założyć, że są (tak jak ma to miejsce w praktyce).

Uwaga 3

Reguły unieważniania wskaźników są takie same jak reguły unieważniania odwołań.

C ++ 11 (Źródło: Iterator Invalidation Rules (C ++ 0x) )

Wprowadzenie

Pojemniki z sekwencjami

• vector: wszystkie iteratory i referencje przed punktem wstawienia pozostają niezmienione, chyba że nowy rozmiar kontenera jest większy niż poprzednia pojemność (w którym to przypadku wszystkie iteratory i referencje są unieważnione) [23.3.6.5/1]
• deque: wszystkie iteratory i odniesienia są unieważnione, chyba że wstawiony element znajduje się na końcu (przednim lub tylnym) deque (w którym to przypadku wszystkie iteratory są unieważnione, ale odniesienia do elementów pozostają nienaruszone) [23.3.3.4/1]
• list: wszystkie iteratory i odwołania nie uległy zmianie [23.3.5.4/1]
• forward_list: niezmienione wszystkie iteratory i referencje (dotyczy insert_after) [23.3.4.5/1]
• array: (nie dotyczy)

Pojemniki asocjacyjne

• [multi]{set,map}: niezmienione wszystkie iteratory i referencje [23.2.4 / 9]

Niesortowane pojemniki asocjacyjne

• unordered_[multi]{set,map}: wszystkie iteratory zostały unieważnione po ponownym skróceniu, ale odniesienia nie uległy zmianie [23.2.5 / 8]. Ponowne podkasowanie nie nastąpi, jeśli wstawienie nie spowoduje, że rozmiar pojemnika przekroczy wartość, z * Bgdzie zjest maksymalny współczynnik obciążenia i Bbieżąca liczba segmentów. [23.2.5 / 14]

Adaptery pojemników

• stack: odziedziczony z podstawowego kontenera
• queue: odziedziczony z podstawowego kontenera
• priority_queue: odziedziczony z podstawowego kontenera

Skasowanie

Pojemniki z sekwencjami

• vector: każdy iterator i odwołanie w punkcie kasowania lub po nim jest unieważniony [23.3.6.5/3]
• deque: kasowanie ostatniego elementu unieważnia tylko iteratory i odniesienia do skasowanych elementów i iteratora past-the-end; kasowanie pierwszego elementu unieważnia tylko iteratory i odniesienia do skasowanych elementów; usunięcie innych elementów unieważnia wszystkie iteratory i referencje (w tym iterator past-the-end) [23.3.3.4/4]
• list: tylko iteratory i odwołania do usuniętego elementu są unieważniane [23.3.5.4/3]
• forward_list: tylko iteratory i odniesienia do usuniętego elementu są unieważniane (dotyczy erase_after) [23.3.4.5/1]
• array: (nie dotyczy)

Pojemniki asocjacyjne

• [multi]{set,map}: tylko iteratory i odniesienia do usuniętych elementów są unieważniane [23.2.4 / 9]

Nieuporządkowane kontenery asocjacyjne

• unordered_[multi]{set,map}: tylko iteratory i odniesienia do usuniętych elementów są unieważniane [23.2.5 / 13]

Adaptery pojemników

• stack: odziedziczony z podstawowego kontenera
• queue: odziedziczony z podstawowego kontenera
• priority_queue: odziedziczony z podstawowego kontenera

Zmiana rozmiaru

• vector: zgodnie z wstawką / kasowanie [23.3.6.5/12]
• deque: zgodnie z wstawką / kasowanie [23.3.3.3/3]
• list: zgodnie z wstawieniem / usunięcie [23.3.5.3/1]
• forward_list: zgodnie z wstawką / kasowanie [23.3.4.5/25]
• array: (nie dotyczy)

Notatka 1

O ile nie określono inaczej (jawnie lub przez zdefiniowanie funkcji w kategoriach innych funkcji), wywołanie funkcji elementu kontenera lub przekazanie kontenera jako argumentu do funkcji biblioteki nie unieważnia iteratorów ani nie zmienia wartości obiektów w tym kontenerze . [23.2.1 / 11]

Uwaga 2

żadna funkcja swap () nie unieważnia żadnych odniesień, wskaźników ani iteratorów odnoszących się do elementów wymienianych kontenerów. [Uwaga: Iterator end () nie odnosi się do żadnego elementu, więc może zostać unieważniony . —Wskazówka] [23.2.1 / 10]

Uwaga 3

Inne niż powyższe zastrzeżenie dotyczące swap(), że nie jest jasne, czy „koniec” iteratory podlegają wyżej wymienionych zasad per-kontenera ; i tak powinieneś założyć, że są.

Uwaga 4

vectori obsługuje wszystkie nieuporządkowane pojemniki asocjacyjne,reserve(n) co gwarantuje, że nie nastąpi automatyczne zmiana rozmiaru przynajmniej do momentu, aż rozmiar kontenera wzrośnie n. Należy zachować ostrożność w przypadku nieuporządkowanych kontenerów asocjacyjnych, ponieważ przyszła propozycja pozwoli na określenie minimalnego współczynnika obciążenia, co pozwoliłoby na ponowne użycie insertpo wystarczającej liczbie eraseoperacji zmniejszających rozmiar kontenera poniżej minimum; gwarancję należy uznać za potencjalnie nieważną po erase.

To chyba warto dodać, że iterator insert dowolnego rodzaju ( std::back_insert_iterator, std::front_insert_iterator,std::insert_iterator ) gwarantuje, że pozostaną ważne tak długo, jak wszystkie wstawki są wykonywane przez ten iterator i żadna inna niezależna impreza iterator-unieważniania występuje.

Na przykład, gdy wykonujesz serię operacji wstawiania do std::vectorza pomocąstd::insert_iterator , jest całkiem możliwe, że wstawienia te spowodują realokację wektora, co unieważni wszystkie iteratory, które „wskazują” ten wektor. Jednak iterator wstawiania, o którym mowa, gwarantuje, że pozostanie ważny, tzn. Możesz bezpiecznie kontynuować sekwencję wstawiania. W ogóle nie musisz się martwić o uruchomienie wektorowej alokacji.

Dotyczy to również wstawek wykonywanych przez sam iterator wstawek. Jeśli zdarzenie unieważniające iterator zostanie wywołane przez jakieś niezależne działanie na kontenerze, iterator wstawiania również zostanie unieważniony zgodnie z ogólnymi zasadami.

Na przykład ten kod

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();

gwarantuje się, że wykona prawidłową sekwencję wstawek do wektora, nawet jeśli wektor „zdecyduje” o przeniesieniu gdzieś w środku tego procesu. Iterator itoczywiście stanie się nieważny, ale it_insnadal będzie ważny.

Ponieważ to pytanie przyciąga tyle głosów, a rodzaj pytania staje się często zadawanym pytaniem, lepiej byłoby napisać osobną odpowiedź, aby wspomnieć o jednej znaczącej różnicy między C ++ 03 i C ++ 11 dotyczącej wpływu std::vectoroperacji wstawiania na ważność iteratorów i odniesień do reserve()icapacity() , których najbardziej pozytywna odpowiedź nie została zauważona.

C ++ 03:

Realokacja unieważnia wszystkie odwołania, wskaźniki i iteratory odnoszące się do elementów w sekwencji. Zagwarantowane jest, że podczas wstawiania, które następuje po wywołaniu zarezerwowania (), nie nastąpi żadna realokacja, aż do momentu, gdy wstawienie zwiększy rozmiar wektora niż rozmiar określony w ostatnim wywołaniu zarezerwowanym () .

C ++ 11:

Realokacja unieważnia wszystkie odwołania, wskaźniki i iteratory odnoszące się do elementów w sekwencji. Zagwarantowane jest, że podczas wstawiania, które następuje po wywołaniu funkcji zarezerwować (), nie nastąpi żadna realokacja, dopóki czas wstawienia nie zwiększy wielkości wektora niż wartość pojemność () .

Tak więc w C ++ 03 nie jest to „ unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated)”, jak wspomniano w innej odpowiedzi, zamiast tego powinno być „ greater than the size specified in the most recent call to reserve()”. Jest to jedna rzecz, którą C ++ 03 różni się od C ++ 11. W C ++ 03, gdy jeden raz insert()spowoduje, że rozmiar wektora osiągnie wartość określoną w poprzednim reserve()wywołaniu (która może być mniejsza niż bieżąca, capacity()ponieważ reserve()wynik może być większy capacity()niż wymagany), każde następne insert()może spowodować realokację i unieważnienie wszystkie iteratory i referencje. W C ++ 11 tak się nie stanie i zawsze możesz mieć capacity()pewność, że będziesz mieć pewność, że następna realokacja nie nastąpi przed przekroczeniem rozmiaru capacity().

Podsumowując, jeśli pracujesz z wektorem C ++ 03 i chcesz mieć pewność, że przeniesienie nie nastąpi podczas wykonywania wstawiania, jest to wartość argumentu, który wcześniej przekazałeś reserve(), że powinieneś sprawdzić rozmiar, a nie wartość zwrotną połączenia do capacity(), w przeciwnym razie możesz być zaskoczony „ przedwczesną ” realokacją.

Oto ładna tabela podsumowań z cppreference.com :

W tym przypadku wstawianie odnosi się do dowolnej metody, która dodaje jeden lub więcej elementów do pojemnika, a kasowanie odnosi się do dowolnej metody, która usuwa jeden lub więcej elementów z pojemnika.