Co się stanie, jeśli użyję wektora :: begin() zamiast std :: back_inserter (wektor) dla wyjścia set_intersection?

Question

I używa się składni C bardzo zwięzły i intuicyjny ++ znajdowania przecięcia dwóch sortowane vector S i wkłada wynik w trzecim vector:

vector<bar> a,b,c; 
//... 
std::set_intersection(a.begin(),a.end(),b.begin(),b.end(), 
         std::back_inserter(c)); 

ten powinien ustawić c do przecięcia (a, b) zakładając, że a i b są posortowane.

Ale co, jeśli po prostu użyć c.begin() (myślałem Widziałem gdzieś przykładem tego, co jest, dlaczego to zrobiłem):

std::set_intersection(a.begin(),a.end(),b.begin(),b.end(), 
         c.begin()); 

set_intersection oczekuje OutputIterator w tym parametrze. Standard, jak sądzę, wymaga tylko, aby c.begin() zwrócił wartość forward iterator, która może być lub może nie być wartością OutputIterator.

W każdym razie kod z c.begin() skompilowany pod klang.

Co jest gwarantowane w ramach standardu? Jeśli to się kompiluje, co może się wydarzyć - to znaczy, kiedy iterator zwrócony przez c.begin() zostanie w końcu zwiększony poza koniec wektora, a próba dostępu do wskazanego elementu, co musi/może się stać? Czy zgodna implementacja w tym przypadku w milczeniu może rozciągnąć wektor, tak że begin() jest w rzeczywistości dołączanym OutputIterator, takim jak back_inserter?

Pytam o to przede wszystkim, aby zrozumieć, w jaki sposób standard współpracuje z iteratorami: co naprawdę się dzieje, więc mogę wyjść poza kopiowanie i wklejanie przy użyciu STL.

Answer 1

Ważnym wymogiem dla iteratora wyjściowego jest to, że jest ważna i pisać-stanie dla zakresu
[out, out+wielkości produkcji).

Przechodząc c.begin() doprowadzi do wartości będących nadpisane który działa tylko wtedy, gdy pojemnik c posiada wystarczającą ilość elementów do zastępowania. Wyobraź sobie, że c.begin() zwraca wskaźnik do tablicy o rozmiarze 0 - wtedy zobaczysz problem podczas pisania *out++ = 7;.

back_inserterdodaje każda przypisana wartość do vector (przez push_back) i zawiera zwięzły sposób wykonania STL algorytmy rozszerzyć zakres - to przeciążenia operatora, które są wykorzystywane do iteratorami odpowiednio.

Zatem

std::set_intersection(a.begin(),a.end(),b.begin(),b.end(), 
         c.begin()); 

wywołuje niezdefiniowanej zachowanie raz set_intersection pisze coś na jego iteratora wyjściowego, to znaczy, gdy zbiór przecięcie a i b nie jest pusta.

Czy Wykonanie zgodne cicho przedłużyć wektor w tym przypadku, tak aby rozpocząć() jest w istocie dodanie OutputIterator jak back_inserter jest?

Oczywiście. To niezdefiniowane zachowanie. (To jest humorystyczne podejście mówiące, że nie powinieneś nawet rozważać używania tego, bez względu na efekty na jakiejkolwiek implementacji.)

Answer 2

back_inserter wstawia element w zakresie przez wywołanie push_back (dlatego nie można używać back_inserter z zakresu, który nie przewiduje push_back operacja).

Tak więc, nie dbasz o to, że przechodzi obok końca zakresu, ponieważ push_back automatycznie rozszerza kontener. Jednak nie jest tak w przypadku wkładki używającej begin().

Jeśli używasz begin(), musisz się upewnić, że zakres docelowy jest wystarczająco duży, aby pomieścił wszystkie elementy. W przeciwnym razie przeniesiemy twój kod do sfery niezdefiniowanego zachowania.

Answer 3

Kompiluje się dobrze, ponieważ otrzymujesz poprawny iterator z powrotem z funkcji begin, ale jeśli wektor jest pusty, otrzymasz z powrotem iterator end, a następnie kontynuuj od tego.

To zadziała tylko jeśli cel wektor zawiera już co najmniej tak wiele elementów, jak starają się dodać, a następnie będzie ona rzeczywiście zastąpić te elementy, a nie dodawać nowe.

Dodanie elementów jest tym, co robi iterator back_inserter, zwraca iterator, który w zasadzie ma wartość push_back w wektorze.