Jak iteratory aktualizacji po wektora realokacji

Question

Oto fragment kodu, że szukałem w:

vector<int> iv = {1,2,3,4,5,6,7,8,9,10}; 
auto iter = iv.begin(), mid = iv.begin() + iv.size()/2; 
for(int count = 100; count; --count) { 
    iter = iv.insert(iter, - 1); 
    cout << "capacity = " << iv.capacity() << "*mid = " << *mid << endl; 

} 

zgodnie zasad unieważniania, iterator:
Vector: wszystkie iteratory oraz odniesienia przed punktem wstawiania są nienaruszone, chyba że nowy rozmiar kontenera jest większy niż poprzednia pojemność (w tym przypadku wszystkie iteratory i odwołania są unieważniane) [23.2.4.3/1] Iterator invalidation rules

Rozumiem, że ponieważ ponownie przypisuję wartość "iter" w każdej wstawce operacja, być może jestem w stanie utrzymać jego ważność (popraw mnie, jeśli się mylę). Jednak iterator "w połowie" zachowuje ważność w tym przypadku, nawet jeśli nie manipuluję nim w pętli, a także gdy zmienia się pojemność wektora.

W jaki sposób "w połowie" jest w stanie zaktualizować się po realokacji?

Aby dowiedzieć się, czy w połowie zmienia się w ogóle lub nie, zmieniłem linii 4 w kodzie:

iv.insert(iter, -1); // Did not assign it back to iter. 

Drukowanie wyników dereferencing wartość w połowie sugeruje zmianę i być może również, że ITER jest unieważniony . (Ponownie, popraw mnie, jeśli się mylę).

Answer 1

Twoje zrozumienie jest prawidłowe. Po zwiększeniu pojemności dowolny iterator staje się nieważny. Iterator mid traci ważność, nawet jeśli pojemność nie uległa zmianie, ale zasadniczo wskazuje na poprzedni element.

Tak więc oryginalny kod zadziała co najmniej dla iter, jednak mid stanie się bezużyteczny przy pierwszym wstawieniu. Po modyfikacji kod jest całkowicie nieważny.

Zwykle implementacja iteratora vector jest po prostu prostym wskaźnikiem wskazującym element do tablicy. Dlatego przy zmianie pojemności i ponownym przydzieleniu tablicy, każdy taki iterator nie jest już ważny, ponieważ wskaźnik wskazuje na niepoprawną pamięć. W rezultacie możesz zobaczyć albo śmieci, możesz dostać błąd segmentacji lub losowo zobaczyć prawidłowe wartości. Gdy pojemność nie ulegnie zmianie, elementy tablicy mogą być przesunięte do przodu, aby można było zobaczyć poprzedni element w iteratorach po punkcie wstawienia, ale tylko w przypadku, gdy na początku tablicy nie było pustych elementów (np. start był większy następnie zero). Ale wszystkie te są specyficzne dla implementacji i dlatego standard jasno określa, że ​​większość z powyższych jest niezdefiniowane zachowanie.