Cosa succede se uso vector :: begin() invece di std :: back_inserter (vector) per l'output di set_intersection?

Question

Sono stato con la sintassi altamente concisa ed intuitivo C++ per trovare l'intersezione di due filtrate vector s e ponendo il risultato in una terza vector:

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

Questo dovrebbe impostare c all'intersezione (a, b), supponendo che a e b siano ordinati.

Ma cosa succede se mi basta usare c.begin() (ho pensato che ho visto un esempio da qualche parte di questo, che è il motivo per cui ho fatto io):

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

set_intersection aspetta un OutputIterator a quel parametro. Lo standard credo che richiede solo che c.begin() restituisca un forward iterator, che suppongo potrebbe o non potrebbe essere un OutputIterator.

In ogni caso, il codice con c.begin() è compilato in clang.

Che cosa è garantito per lo standard? Se questo viene compilato, è probabile che ciò accada, ovvero quando l'iteratore restituito da c.begin() viene infine incrementato oltre la fine del vettore e viene effettuato un tentativo di accesso all'elemento puntato su, che cosa deve/può accadere? Può un'implementazione conforme estendere in modo silenzioso il vettore in questo caso, quindi OutputIterator come OutputIterator è ?

Lo chiedo principalmente per capire come funziona lo standard con gli iteratori: cosa sta succedendo davvero, quindi posso andare oltre il copia-e-incolla nell'utilizzo dell'STL.

Answer 1

Il requisito importante per un iteratore uscita è che sia valido e scrivere-in grado per la gamma
[out, out+dimensione di uscita).

Passando c.begin() porterà ai valori che sono sovrascritti che funziona soltanto se il recipiente c tiene elementi sufficienti per sovrascrivere. Immagina che c.begin() restituisca un puntatore a una matrice di dimensione 0, quindi vedrai il problema quando scrivi *out++ = 7;.

back_inserteraggiunge ogni valore assegnato ad una vector (via push_back) e fornisce un modo conciso di messa STL algoritmi estendere una gamma - sovraccarica gli operatori che vengono utilizzati per iteratori appropriato.

Così

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

invoca comportamento indefinito volta set_intersection scrive qualcosa al suo iteratore uscita, cioè quando l'intersezione di set di a e b non è vuoto.

Può un conforme attuazione estendere silenziosamente il vettore in questo caso, in modo che iniziano() è in realtà un aggiungendo OutputIterator come back_inserter è?

Naturalmente. È un comportamento indefinito. (Questo è un approccio umoristico per dirti che non dovresti nemmeno prendere in considerazione l'uso di questo, indipendentemente dagli effetti su qualsiasi implementazione.)

Answer 2

back_inserter inserisce l'elemento nella gamma chiamando push_back (è per questo che non è possibile utilizzare back_inserter con la gamma che non prevede push_back funzionamento).

Quindi, non ti interessa il oltre la fine dell'intervallo come push_back espande automaticamente il contenitore. Tuttavia, questo non è il caso con insert utilizzando begin().

Se si utilizza begin(), è necessario assicurarsi che l'intervallo di destinazione sia sufficientemente grande da contenere tutti gli elementi.. Non riuscendo a farlo, trasferirebbe istantaneamente il tuo codice nel regno di un comportamento indefinito.

Answer 3

Compilano bene perché si ottiene un iteratore valido dalla funzione begin, ma se il vettore è vuoto, si ripristinerà l'iteratore end, quindi si continuerà da lì.

Funzionerà solo se il vettore di destinazione contiene già almeno altrettanti elementi come si tenta di aggiungere, quindi sarà effettivamente sovrascrivere questi elementi e non aggiungere nuovi.

E l'aggiunta di elementi è proprio ciò che fa l'iteratore back_inserter, restituisce un iteratore che sostanzialmente fa push_back sul vettore.