Czy zmiana rozmiaru wektora powoduje unieważnienie iteratorów?

Question

Uważam, że ten C++ kod:

vector<int> a; 
a.push_back(1); 
a.push_back(2); 
vector<int>::iterator it = a.begin(); 
a.push_back(4); 
cout << *it; 

drukowania niektórych dużych liczb losowych; ale jeśli dodasz a.push_back(3) między trzecią a czwartą linią, wydrukuje 1. Czy możesz mi to wyjaśnić?

Answer 1

Zmieniano bardziej ostrożne sformułowanie

tak, zmiana rozmiaru wektor może unieważnić wszystkie iteratory wskazujące do wektora.

Wektor jest realizowany poprzez wewnętrzną alokację tablicy, w której przechowywane są dane. Gdy wektor rośnie, tablica ta może zabraknąć miejsca, a gdy to zrobi, wektor przydzieli nową, większą tablicę, skopiuje dane do tego, a następnie usunie starą tablicę.

Więc twoje stare iteratory, które wskazują na stare wspomnienia, nie są już ważne. Jeśli wektor zostanie zmieniony na w dół (na przykład przez pop_back()), jednak używana jest ta sama tablica. Tablica nigdy nie jest automatycznie zmniejszana.

Jednym ze sposobów uniknięcia tej realokacji (i unieważnienia wskaźnika) jest najpierw zadzwonić pod numer vector::reserve(), aby zarezerwować wystarczająco dużo miejsca, aby ta kopia nie była konieczna. W twoim przypadku, jeśli wywołałeś a.reserve(3) przed pierwszą operacją push_back(), to wewnętrzna tablica byłaby wystarczająco duża, aby można było wykonać push_back 'bez konieczności ponownego przydzielania tablicy, więc twoje iteratory pozostaną ważne.

Answer 2

Iteratory wektorowe są unieważniane tylko, gdy wektor wykonuje ponowną realokację.

Wywołanie push_back(4) powoduje, że wektor alokuje nowy blok pamięci - to powoduje, że iterator staje się nieważny. Jeśli używasz również push_back(3), nie jest dokonywana żadna realokacja dla push_back(4), więc iterator pozostaje ważny.

Answer 3

Tak, każda akcja, która może zmienić rozmiar wektora, może unieważnić iteratory.

Edytuj: obejmuje operacje (na przykład erase(), resize()), które zmniejszają rozmiar kontenera. erase() nie unieważnia Iteratorów dla wszystkich iteratorów, ale unieważnia wszelkie iteratory odnoszące się do dowolnego punktu po usuniętym elemencie (elementach). resize() jest zdefiniowany w kategoriach insert() i erase(), więc ma ten sam potencjał.

Answer 4

Reguły dotyczące unieważniania iteratora są specyficzne dla kontenera.

teraz unieważnianie może mieć 2 znaczenia wektorem:

1. unieważnieniu = punkt poza zakresem określonym przez [rozpoczęciem end]
2. Unieważnienie = wartość do innego obiektu, z pierwotnego

Jak widać, drugi jest znacznie bardziej rygorystyczne:

std::vector<int> myVector; 
myVector.push_back(0); 
myVector.push_back(1); 

std::vector<int>::iterator it = myVector.begin(); // it points to 0 
myVector.erase(it); // it points to 1 
myVector.erase(it); // it == myVector.end() 

W tym przypadku jest "ważny" pod tym względem, że zawsze znajduje się w zakresie włączającym [początek, koniec] i dlatego może być bezpiecznie użyty do każdej operacji na myVector. Z drugiej strony wyrażenie (* it) ciągle się zmienia: najpierw zwraca 0, potem 1, następnie ma niezdefiniowane zachowanie ...

Ogólnie rzecz biorąc, ludzie będą raczej mówić o drugim wymogu, a unieważnianie iteratora po prostu oznacza, że ​​(* it) może nie dać takiego samego wyniku jak poprzednio.

---

Teraz to się mówi, istnieje kilka sposobów, aby unieważnić iterator na wektor (w rzeczywistości, to jest mniej stabilna struktura STL).

Podczas dodawania elementów:

• To może wywołać realokacji (1) jeśli myVector.size() == myVector.capacity(), ponieważ kontrola ta jest podatna na błędy, zwykle pod uwagę że jakiekolwiek dodanie spowoduje unieważnienie iteratorów
• Jeśli chcesz być "wybredny" i wie, że realokacja nie zostanie uruchomiona, to musisz się jeszcze martwić o insert. Wstawienie elementu unieważnia Iteratory wskazujące bieżące położenie i wszystkie następne, ponieważ elementy są przesuwane o jeden krok w kierunku końca wektora.

Podczas usuwania elementów:

• Nie ma realokacja, nawet jeśli bufor jest teraz znacznie większe niż jest to potrzebne. Możliwe jest jednak wymuszenie tego przy użyciu skurczu , aby dopasować go do formatu (2).
• Wszystkie iteratory wskazujące obok usuniętego elementu są unieważniane. W szczególności, poprzedni iterator "końca" jest teraz poza zakresem [początek, koniec] i nie może być bezpiecznie użyty na przykład w algorytmach STL.

(1) Struktura wewnętrzna std :: wektora jest tablica T, to ze względu na zgodność z-c (z użyciem programów & myVector.front() jako adresu tablicy) i ponieważ gwarantuje on przyleganie i minimalny narzut przestrzeni (tj. ilość miejsca zajmowanego przez własne dane wektorowe a ilość zajmowanej przez obiekt przestrzeni)

W każdej chwili możesz dowiedzieć się, ile obiektów może pomieścić wektor przy użyciu metody .capacity().

Jeśli chcesz wstawić obiekt, a wektor nie ma wymaganej pojemności, wywoływane jest wywołanie metody .reserve (size_t). Ta metoda, jeśli wymagana liczba elementów przewyższa bieżącą pojemność, wyzwala realokację.

Wektor następnie przydziela nową tablicę elementów (jej rozmiar to zazwyczaj 2 * n + 1, gdzie n jest bieżącą pojemnością), kopiuje elementy bieżącej tablicy do nowej tablicy, odrzuca bieżącą tablicę.

Ponieważ odrzuca bieżącą tablicę, iteratory są unieważniane, ponieważ iteratory wektorowe są na ogół prostymi wskaźnikami (dla wydajności).

Zauważ, że jeśli iteratory zostały zaimplementowane jako: odwołanie do wektora + liczba, a dereferencja faktycznie była * (& m_vector.front() + n) realokacja nie unieważnia ich ... ale byłyby one mniej wydajny.

(2) Zmniejsz, aby dopasować: Ostrzeżenie, to wyzwala KOPIĘ elementów i unieważnia Iteratory.

// myVector has 10 elements, but myVector.capacity() == 1000 
myVector.swap(std::vector<int>(myVector)); 

Najpierw tworzy tymczasowy wektor, który będzie przeznaczyć tylko tyle pamięci, ile potrzeba (minimum w zależności od biblioteki), a następnie skopiować elementy myvector. Następnie operacja wymiany wymienia bufory z myVector i tej kopii, a tym samym myVector buforuje teraz pamięć o minimalnej wymaganej ilości pamięci. Pod koniec operacji plik tymczasowy zostaje zniszczony, a pamięć zostaje zwolniona.

Answer 5

Dla przyszłości, wszystkich rodzajów STL o smakołyki, takie jak ten są na stronie SGI: http://www.sgi.com/tech/stl/Vector.html

Jeśli potrzebujesz iteratory pozostać ważne po dodaniu lub usuwać do kolekcji, spojrzeć na innego rodzaju kolekcja, jak lista.

Najlepszą rzeczą do zrobienia jest identyfikacja z matrycy funkcji, które chcesz z kolekcji (dostęp losowy, itp.), A następnie wybierz odpowiedni pojemnik.

Zobacz artykuł Wikipedii o kontenerach Standard_Template_Library dla punktu wyjścia. Jeśli masz gotówkę, gorąco polecam "Efektywne STL: 50 sposobów, aby poprawić korzystanie ze standardowej biblioteki szablonów" - Scott Meyer.

Przepraszam za brak linków pomocniczych, jestem tu początkującym i nie mam reputacji, aby opublikować to z więcej niż jednym.