Pytanie Zamieszanie w przypadku unieważnienia iteratorów w systemie deque


Jestem nieco zdezorientowany odnośnie do unieważnienia iteratora w Deque. (W kontekście to pytanie)

Poniżej znajdują się fragmenty - The C ++ Standard Library: A Tutorial and Reference, Autor: Nicolai M. Josuttis

Dowolne wstawianie lub usuwanie elementów    inny niż na początku lub na końcu   unieważnia wszystkie wskaźniki, odniesienia,   i iteratory, które odnoszą się do elementów   z deque.

Oto fragmenty z SGI teren:

Semantyka unieważnienia iteratora   dla deque jest następujący. Wstawić   (włącznie z push_front i push_back)   unieważnia wszystkie powtarzające się iteratory   do deque. Wymaż w środku   Deque unieważnia wszystkie iteratory   odnoszą się do deque. Wymaż na   początek lub koniec deque (w tym    pop_front i pop_back) unieważnia   iterator tylko wtedy, gdy wskazuje na   wymazany element.

IMHO, deque to zbiór bloków z pierwszym blokiem rosnącym w jednym kierunku i ostatnim blokiem w przeciwnym kierunku.

  -   -  -  
  -   -  -
  |   -  -  ^
  |   -  -  |
  V   -  -  |
      -  -  -
      -  -  -

push_back, push_front nie powinien mieć żadnego wpływu na deque iteratory (zgadzam się z Josuttisem).

Jakie jest prawidłowe wyjaśnienie? co standard mówi na ten temat?


14
2018-05-27 04:47


pochodzenie




Odpowiedzi:


Od standardowy projekt roboczy

szablon <class InputIterator>       void insert (pozycja iteratora,                       InputIterator pierwszy, InputIterator ostatni);

1 Efekty: Wstaw w środku   z deque unieważnia wszystkie   iteratory i odniesienia do elementów   z deque. Wkładka na każdym końcu   z deque unieważnia wszystkie   iteratory do deque, ale nie ma   wpływ na ważność referencji   do elementów deque. "

Więc obie są poprawne. Jak wskazuje Josuttis, wstawienie z przodu lub z tyłu nie unieważnia odniesień do elementów księgi, a tylko iteratory do deque się.

EDYCJA: A bardziej aktualny projekt mówi zasadniczo to samo (sekcja 23.2.2.3)


13
2018-05-27 05:06





IMHO, deque to zbiór bloków z pierwszym blokiem rosnącym w jednym kierunku i ostatnim blokiem w przeciwnym kierunku.

Twoja opinia jest twoją prerogatywą, ale jest zła. :)

deque jest takim pojemnikiem semantycznie, ale pod względem implementacji jest zaprojektowany do implementacji przez jeden lub więcej bloków pamięci. Reguły unieważnienia iteratora C ++ pochodzą z wdrożenia, dlatego właśnie. Prawdopodobnie jest to niewielki wyciek z abstrakcji, ale cóż, cokolwiek.

Dokumentacja SGI STL nie jest odpowiednią dokumentacją do przeczytania, ponieważ SGI STL nie jest Biblioteką Standardową C ++. Niestety, Josuttis jest jedną z osób, które nazywają to "STL", a to doprowadziło do zamieszania.


Poniżej znajdują się fragmenty - The Standard Library C ++: A Tutorial and Reference, autor: Nicolai M. Josuttis

Dowolne wstawianie lub usuwanie elementów inny niż na początku lub na końcu unieważnia wszystkie wskaźniki, odniesienia i iteratory odnoszące się do elementów deque.

Mówiąc prościej, ten fragment z Josuttis jest zwodniczysugerując, że wprowadzanie lub usuwanie elementów, które  na początku lub na końcu nie unieważniaj wskaźniki, odniesienia lub iteratory ... choć warto zauważyć, że nigdy nie wychodzi i twierdzi wprost.


Oto prawdziwe, właściwe, oficjalne zasady dotyczące std::deque:

C ++ 03

  • Wprowadzenie: wszystkie iteratory i odnośniki są unieważniane, chyba że wstawiany element znajduje się na końcu (przód lub tył) maski (w takim przypadku wszystkie iteratory są unieważnione, ale odniesienia do elementów pozostają nienaruszone) [23.2.1.3/1]

  • Skasowanie: wszystkie iteratory i referencje są unieważniane, chyba że usunięci członkowie są na końcu (z przodu lub z tyłu) księcia (w takim przypadku unieważnione są tylko iteratory i odwołania do wymazanych członków) [23.2.1.3/4]

  • Zmiana rozmiaru: wg insertu / kasowania [23.2.1.2/1]

C ++ 11

  • Wprowadzenie: wszystkie iteratory i odnośniki są unieważniane, chyba że wstawiany element znajduje się na końcu (przód lub tył) maski (w takim przypadku wszystkie iteratory są unieważnione, ale odniesienia do elementów pozostają nienaruszone) [23.3.3.4/1]

  • Skasowanie: kasowanie ostatniego elementu powoduje unieważnienie tylko iteratorów i odwołań do wymazanych elementów i iteratora końca; kasowanie pierwszego elementu unieważnia tylko iteratory i odwołania do wymazanych elementów; kasowanie jakichkolwiek innych elementów unieważnia wszystkie iteratory i odnośniki (w tym iterator typu koniec-koniec) [23.3.3.4/4]

  • Zmiana rozmiaru: wg insertu / kasowania [23.3.3.4/1]


Dalsze czytanie

Nie jestem pewien, jakie dalsze odniesienia do wiarygodnych źródeł szukasz - odpowiednie standardowe fragmenty zostały już cytowane i cytowane.


11
2018-01-05 14:31



Ach tak, właśnie to miałem nadzieję, dzięki. Istniejące odpowiedzi były naprawdę mylące (np. "Iteratory do deque samo"naprawdę mnie wyrzuciło), to wyjaśniło to. :) - Mehrdad
@Mehrdad: Zasadniczo it.begin() vs *it.begin() ;) - Lightness Races in Orbit
Masz na myśli deque.begin() vs. *deque.begin()? : P - Mehrdad
Dlaczego jednak? Object &obj = deque[5]; obj.foo(); deque.push_back(Object()); obj.bar(); wydaje mi się całkowicie uzasadnione. - Mehrdad
@Mehrdad, w porównaniu do stable_vector, deque poświęca integralność iteratora w zamian za brak dodania jeszcze jednego kierunku. ZA stable_vector implementacja musi utrzymywać odwołania zwrotne do tablicy kontrolnej wraz z danymi, a jej iterator musi przeglądać to odwołanie do tyłu, aby odkryć, gdzie znajduje się tablica, zamiast bezpośrednio zapisywać wskaźnik w tablicy. - filipos


Implementacja SGI prawdopodobnie wykorzystuje tablicę, którą można uzyskać, więc jeśli insert powoduje wzrost macierzy, iteratory wskazujące na starą tablicę są nieprawidłowe.

EDYTOWAĆ:

W rozdziale 17.2.3 podręcznika C ++ Programming Language Third Edition nie widzę niczego w opisie deque, który wskazuje, jakie operacje zachowują lub unieważniają iteratory. Być może patrzę w niewłaściwym miejscu lub zachowanie może być nieokreślone.


0
2018-05-27 05:05