Jak pyta tytuł.Dlaczego funkcja push_back lub push_front powoduje unieważnienie iteratorów deque?
Moje rozumienie księgi było takie, że przydzieliło "bloki". Nie rozumiem, w jaki sposób przydzielanie większej ilości miejsca unieważnia iteratory, a jeśli już, to można by pomyśleć, że iteratory deque miałyby więcej gwarancji niż wektory, a nie mniej.
Standard C++ nie określa sposobu implementacji deque. Nie jest wymagane przydzielanie nowej przestrzeni przez przydzielanie nowej porcji i łączenie jej z poprzednimi, wszystko, co jest wymagane, to to, że wstawienie na każdym końcu jest amortyzowane stałym czasem.
Tak więc, chociaż łatwo jest zobaczyć, jak wprowadzić deque w taki sposób, że daje gwarancję, którą chcesz [*], nie jest to jedyny sposób, aby to zrobić.
[*] Iteratory mają odniesienie do elementu, a także odnośnik do bloku, w którym mogą się poruszać w przód/w tył od końca bloku, gdy do niego dojdą. Dodatkowo przypuszczam, że odniesienie do samej pamięci, tak aby operator+ mogła być stała, zgodnie z oczekiwaniami dla iteratorów o dostępie swobodnym - po łańcuchach łączy od bloku do bloku nie jest wystarczająco dobra.
Deque nie jest listą, bloki nie są powiązane! – curiousguy
Nawet przy alokowaniu w porcje wstawka spowoduje, że konkretny fragment zostanie ponownie przydzielony, jeśli brakuje miejsca (jak w przypadku wektorów).
Realistyczna jest tutaj realokacja. – curiousguy
Kluczową sprawą jest, aby nie przyjmować żadnych założeń, traktując iterator tak, jakby został unieważniony.
Nawet jeśli teraz działa dobrze, może pojawić się nowsza wersja kompilatora lub kompilatora dla innej platformy i złamać kod. Ewentualnie, kolega może przyjść i zdecydować się przekształcić swój deque w wektor lub połączoną listę.
Co bardziej interesujące jest to, że push_back i push_front będzie nie unieważnić jakiekolwiek referencje do elementów danego deque użytkownika. Tylko iteratory mają być uznane za nieważne.
Standard, według mojej wiedzy, nie podaje przyczyny. Jednakże, jeśli implementowano iterator, który był świadomy swoich bezpośrednich sąsiadów - jak wykaz jest - iterator stałby się nieważny, gdyby wskazywał na element znajdujący się zarówno na krawędzi klocka, jak i na krawędzi bloku.
Innym powodem moim zdaniem jest to, że iterator może zostać wdrożony poprzez zachowanie indeksu elementu. Jeśli coś jest wstawione na początku/końcu deque, ten indeks jest już nieważny (off-by-one), chociaż jakikolwiek wskaźnik/odniesienie do tego elementu, który wskazywał jest nadal ważny, ponieważ nie nastąpiła żadna realokacja kierunek). To samo, gdy trzymamy indeks w tablicy wskaźników blokowych (jak się domyślałem w moim komentarzu do pytania). –
Zobacz mój [odpowiedź] (http://stackoverflow.com/a/39420347/3903076) wyjaśnienie tego w oparciu o prostą implementację. – filipos
Ponieważ standard mówi, że może. Nie nakłada wymogu, aby księgę wprowadzono jako listę części. Nakazuje określony interfejs z określonymi warunkami wstępnymi i końcowymi oraz określoną minimalną złożonością algorytmiczną.
Wdrażanie może realizować wszystko w dowolny sposób, o ile spełnia wszystkie te wymagania. Rozsądna implementacja może wykorzystywać listy fragmentów lub może wykorzystywać inną technikę z różnymi kompromisami.
Prawdopodobnie niemożliwe jest stwierdzenie, że jedna technika jest ściśle lepsza od innej dla wszystkich użytkowników we wszystkich sytuacjach. Z tego powodu standard daje wykonawcom pewną swobodę wyboru.
Nie sądzę, że masz na myśli listę (np. Std :: list) fragmentów, ponieważ wtedy iteratory dostępu losowego nie mogą być O (1). –
Rzut oka na jedną implementację sugeruje, że deque jest bardziej jak std :: vector
Zgaduję. push_back/push_front może przydzielić nowy blok pamięci. Przelicznik deque musi wiedzieć, kiedy operator inkrementacji/dekrementacji powinien przeskoczyć do następnego bloku. Implementacja może przechowywać tę informację w samym iteratorze. Inkrementowanie/dekrementowanie starego iteratora po push_back/push_front może nie działać zgodnie z przeznaczeniem.
Ten kod może, ale nie musi zakończyć się niepowodzeniem z błędem czasu wykonywania. W moim Visual Studio nie udał się w trybie debugowania, ale uruchomił się do zakończenia w trybie zwolnienia. W systemie Linux spowodował błąd segmentacji.
#include <iostream>
#include <deque>
int main() {
std::deque<int> x(1), y(1);
std::deque<int>::iterator iterx = x.begin();
std::deque<int>::iterator itery = y.begin();
for (int i=1; i<1000000; ++i) {
x.push_back(i);
y.push_back(i);
++iterx;
++itery;
if(*iterx != *itery) {
std::cout << "increment failed at " << i << '\n';
break;
}
}
}
Iterator to nie tylko odniesienie do danych. Musi wiedzieć, jak zwiększać itp.
W celu wspierania dostępu losowego, implementacje będą miały dynamiczną tablicę wskaźników do porcji. Przelicznik deque wskaże tę dynamiczną tablicę. Kiedy wzrasta objętość, może być konieczne przydzielenie nowej porcji. Szereg dynamiczny będzie rósł, unieważniając jego iteratory, a w konsekwencji iteratory deque'a.
Nie chodzi o to, że porcje są ponownie przydzielane, ale tablica wskaźników do tych fragmentów może być. Rzeczywiście, jak zauważył Johannes Schaub, referencje nie są unieważniane.
Należy również zauważyć, że gwarancja na iterację deque jest nie mniejsza niż liczba wektorów, które są również unieważniane, gdy pojemnik rośnie.
iirc, implementacja deque'a utrzymuje tablicę wskaźników do tych bloków ... Jeśli tablica musi zostać ponownie przydzielona, iteratory mogą stać się nieważne. Może to jest powód? Nie jestem pewien ... To przynajmniej wyjaśnia, dlaczego wstawienia do obu końców unieważniają iteratory, ale nie odwołania/wskaźniki do elementów. –