Czy przesunięcie wektora unieważnia Iteratory?

Jeśli mam iterator do wektora a, to move-construct lub move-assign wektor b z a, Czy iterator nadal wskazuje na ten sam element (teraz wektor b)? Oto co mam na myśli w kodzie: 

#include <vector>
#include <iostream>

int main(int argc, char *argv[])
{
    std::vector<int>::iterator a_iter;
    std::vector<int> b;
    {
        std::vector<int> a{1, 2, 3, 4, 5};
        a_iter = a.begin() + 2;
        b = std::move(a);
    }
    std::cout << *a_iter << std::endl; // Is a_iter valid here?
    return 0;
}

Czy a_iter jest nadal ważne, ponieważ a zostało przeniesione do b, czy iterator jest unieważniony przez ruch? W celach informacyjnych, std::vector::swap nie unieważnia iteratorów .

Author: David Brown, 2012-06-13
Source

4 answers

Chociaż rozsądne byłoby założenie, że iterators są nadal ważne po move, nie sądzę, aby Standard faktycznie to gwarantował. Dlatego Iteratory są w stanie nieokreślonym po move.

Nie ma odniesienia, które można znaleźć w standardzie, który wyraźnie stwierdza, że Iteratory istniejące przed move są nadal ważne po move.

Na pozór, wydaje się całkiem rozsądne założenie, że iterator jest zazwyczaj zaimplementowane jako wskaźniki do kontrolowanej sekwencji. Jeśli tak jest, to Iteratory nadal będą ważne po move.

Ale implementacja iterator jest zdefiniowana jako implementacja. Oznacza to, że o ile iterator na danej platformie spełnia wymagania określone w standardzie, może być zaimplementowana w dowolny sposób. Teoretycznie może być zaimplementowany jako kombinacja WSKAŹNIKA z powrotem do klasy vector wraz z indeks. Jeśli jest to , Iteratory staną się nieważne po move.

To, czy iterator jest faktycznie zaimplementowane w ten sposób, nie ma znaczenia. Można to zaimplementować w ten sposób, więc bez określonej gwarancji ze standardu, że Iteratory post-move są nadal ważne, nie można zakładać, że są. Należy również pamiętać, że istnieje taka gwarancja dla iteratorów po swap. Zostało to wyraźnie wyjaśnione z poprzedniej normy. Być może było to po prostu niedopatrzenie Komisji ds. chorób wenerycznych, aby nie dokonywać podobnych wyjaśnień dla iteratorów po move, ale w każdym razie nie ma takiej gwarancji.

Dlatego, długim i krótkim jest to, że nie można założyć, że Twoje Iteratory są nadal dobre po move.

EDIT:

23.2.1 / 11 W projekcie N3242 stwierdza, że:

O ile nie określono inaczej (jawnie lub definiując funkcji pod względem innych funkcji), wywołując kontener członek funkcja lub przekazanie kontenera jako argumentu do funkcji bibliotecznej nie unieważnia iteratorów ani nie zmienia wartości obiektów w tym pojemniku.

To może prowadzić do wniosku, że Iteratory są ważne po move, ale nie zgadzam się. W przykładowym kodzie a_iter był iteratorem w vector a. Po move, pojemnik, a z pewnością został zmieniony. Mój wniosek jest taki, że powyższa klauzula nie ma zastosowania w tym przypadku.

 23
Author: John Dibling,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-06-15 13:19:40

Myślę, że edycja, która zmieniła konstrukcję move, aby przenieść przypisanie, zmienia odpowiedź.

Przynajmniej jeśli dobrze czytam tabelę 96, złożoność konstrukcji ruchu jest podana jako "Uwaga B", która jest stałą złożonością dla czegokolwiek z wyjątkiem std::array. Złożoność przyporządkowania ruchu jest jednak podawana jako liniowa.

Jako taka, konstrukcja move nie ma zasadniczo wyboru, jak tylko skopiować wskaźnik ze źródła, w którym to przypadku trudno jest zobaczyć, jak Iteratory może stać się nieważny.

Dla przypisania move, jednak złożoność liniowa oznacza, że Może wybrać przeniesienie poszczególnych elementów ze źródła do miejsca docelowego, w którym to przypadku Iteratory prawie na pewno staną się nieważne.

Możliwość przypisania elementów do ruchu jest wzmocniona opisem: "wszystkie istniejące elementy a są albo przypisane do ruchu, albo zniszczone". Część "zniszczona" odpowiadałaby zniszczeniu istniejącej treści, a "kradzież" wskaźnika ze źródła -- ale "przesunięcie przypisane do" wskazywałoby na przeniesienie poszczególnych elementów ze źródła do miejsca docelowego.

 10
Author: Jerry Coffin,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-06-13 19:36:50

Ponieważ nic nie powstrzyma iteratora przed utrzymaniem odniesienia lub wskaźnika do oryginalnego kontenera, powiedziałbym, że nie możesz polegać na tym, że Iteratory pozostaną ważne, chyba że znajdziesz wyraźną gwarancję w standardzie.

 3
Author: Mark Ransom,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-06-13 19:49:45

Tl; dr : tak, przeniesienie a std::vector<T, A> prawdopodobnie unieważnia Iteratory

częstym przypadkiem (z std::allocator na miejscu) jest to, że unieważnienie nie ma miejsca, ale nie ma gwarancji i zmiana kompilatorów lub nawet kolejna aktualizacja kompilatora może sprawić, że kod będzie zachowywał się nieprawidłowo, jeśli polegasz na fakcie, że Twoja implementacja obecnie nie unieważnia iteratorów.

:

Pytanie czy std::vector Iteratory w rzeczywistości może pozostać ważne po przeniesieniu-przypisanie jest związane ze świadomością alokatora szablonu wektorowego i zależy od typu alokatora (i ewentualnie jego odpowiednich instancji).

W każdej implementacji jaką widziałem, move-assignment of a std::vector<T, std::allocator<T>>1 w rzeczywistości nie unieważni iteratorów ani wskaźników. Istnieje jednak problem, jeśli chodzi o wykorzystanie tego standardu, ponieważ standard po prostu nie może zagwarantować, że Iteratory pozostaną ważne dla każde przeniesienie instancji std::vector w ogóle, ponieważ kontener jest świadomy alokatora.

Niestandardowe alokatory mogą mieć stan i jeśli nie propagują się przy przypisaniu ruchu i nie porównują się równo, wektor musi przydzielić pamięć dla przeniesionych elementów za pomocą własnego alokatora.

Niech: 

std::vector<T, A> a{/*...*/};
std::vector<T, A> b;
b = std::move(a);

Teraz jeśli

  1. std::allocator_traits<A>::propagate_on_container_move_assignment::value == false &&
  2. std::allocator_traits<A>::is_always_equal::value == false && (prawdopodobnie od c++17)
  3. a.get_allocator() != b.get_allocator()

Wtedy b przydzieli nowe przechowywanie i przenoszenie elementów a jeden po drugim do tego magazynu, unieważniając w ten sposób wszystkie Iteratory, wskaźniki i odwołania.

Powodem jest spełnienie powyższego warunku 1. zakazuje przenoszenia przypisania alokatora przy przenoszeniu kontenera. Dlatego mamy do czynienia z dwoma różnymi instancjami alokatora. Jeśli te dwa obiekty alokatora nie zawsze są równe ( 2.) ani faktycznie porównywać równe, wtedy oba alokatory mają inny stan. Na alokator x może nie być w stanie dealokować pamięci innego alokatora y o innym stanie i dlatego kontener z alokatorem x nie może po prostu ukraść pamięci z kontenera, który przydzielił jej pamięć przez y.

Jeśli alokator propaguje się przy przypisaniu move lub jeśli oba alokatory są równe, implementacja najprawdopodobniej wybierze po prostu utworzenie b własnych danych aS, ponieważ może być pewna, że będzie w stanie dealokować pamięć masową jak należy.

1: std::allocator_traits<std::allocator<T>>::propagate_on_container_move_assignment i std::allocator_traits<std::allocator<T>>::is_always_equal są typdefami dla std::true_type (dla dowolnych niewyspecjalizowanych std::allocator).

W trakcie budowy : 

std::vector<T, A> a{/*...*/};
std::vector<T, A> b(std::move(a));

Konstruktor move kontenera świadomego alokatora przeniesie-zbuduje instancję alokatora z instancji alokatora kontenera, z którego przenosi się obecne wyrażenie. W ten sposób zapewniona jest odpowiednia zdolność dealokacji i pamięć może (i w rzeczywistości będzie) zostać skradziona, ponieważ konstrukcja ruchu jest (z wyjątkiem std::array) zobowiązana do stałej złożoności.

Uwaga: nadal nie ma gwarancji, że Iteratory pozostaną ważne nawet dla konstrukcji move.

na zamianie :

Wymaganie, aby Iteratory dwóch wektorów pozostały ważne po swapie (teraz tylko wskazanie na odpowiedni kontener swapped) jest łatwe, ponieważ swapowanie ma zdefiniowane zachowanie tylko wtedy, gdy

  1. std::allocator_traits<A>::propagate_on_container_swap::value == true ||
  2. a.get_allocator() == b.get_allocator()

Tak więc, jeśli alokatory nie propagują się przy swapie i jeśli nie porównują sobie równych, Zamiana kontenerów jest w pierwszej kolejności niezdefiniowanym zachowaniem.

 1
Author: Pixelchemist,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-11-06 15:22:15