algoritmo di copia con back_inserter

Question

non capisco il motivo per cui questo codice è preciso

vector<int> coll; 
coll.reserve(2*coll.size()); 
copy (
    coll.begin(), coll.end(), // zrodlo 
    back_inserter(coll)   // przeznaczenie 
); 

coll.end() rappresenta la fine del vettore. Dopo aver premuto push_back (come fa back_insert_iterator) cosa restituisce coll.end() è lo stesso cosa era prima o qualcosa di diverso? Esistono più di un iteratore di terminazione? Perché end() può essere utilizzato come fine del contenitore anche quando vengono aggiunti nuovi contenuti?

Inoltre, non è possibile applicare il codice all'elenco contenitore: si blocca. Questo è importante perché in caso di vettore push_back rende inattendibili gli iteratori dopo la riallocazione dei dati (quando sono chiamati size()==capacity() e push_back()) mentre in caso di elenco non è il caso. Del perché il codice si blocca per la lista?

Edit: (sscce)

#include <iostream> 
#include <list> 
#include <algorithm> 
using namespace std; 

template <class T> 
inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="") 
{ 
    typename T::const_iterator pos; 

    std::cout << optcstr; 
    for (pos=coll.begin(); pos!=coll.end(); ++pos) { 
     std::cout << *pos << ' '; 
    } 
    std::cout << std::endl; 
} 

int main(){ 
    list<int> coll; 

    list<int>::iterator end = coll.end(); 
    copy (
    coll.begin(), coll.end(), // zrodlo 
    back_inserter(coll)   // przeznaczenie 
    ); 
    cout << *end << endl; 
    PRINT_ELEMENTS(coll); 
} 

Answer 1

il begin() e end() puntatori/iteratori utilizzati per determinare ciò che deve essere copiato vengono valutati una volta quando viene chiamata la funzione. Quindi essenzialmente std::copy() incrementerà il suo iteratore del cursore che alla fine raggiungerà end(), perché vector<T>::const_iterator è solo un puntatore elegante T* su un array di vecchia scuola.

Come correttamente menzionate, se un push_back rende il vector RIALLOCAZIONE e spostare i dati da qualche altra parte nella memoria, quindi l'elemento successivo copiato avrà un indirizzo sbagliato per la fonte, che rischia di finire con un guasto segmentaion.

Per un elenco, non può mai terminare perché end() è un puntatore sentinella/guardia e si può raggiungere solo end() incrementando l'iteratore sull'ultimo elemento dell'elenco. Quindi l'indirizzo di end() non cambia mai, ma poiché si aggiunge costantemente un elemento alla fine dell'elenco, non si raggiungerà mai l'ultimo elemento, pertanto std::copy() non potrà mai ottenere un puntatore a end(). Un po 'come un cane che insegue la coda.

È più facile capire con illustrazioni e diagrammi, la lettura di elenchi doppiamente collegati e nodi sentinella, tutto avrà senso.

Answer 2

coll.end() è chiamato prima dell'inserimento copia e indietro comincia, così essenzialmente il codice è lo stesso

coll.reserve(2*coll.size()); 
auto oldEnd = coll.end(); 
copy (coll.begin(), oldEnd, back_inserter(coll)); 

significato, copy non sarà ri - valutare coll.end(), in modo che non si accorga/si preoccupi di inserirsi nello stesso vettore e che ciò che una volta era la fine del vettore non è la fine dei primi inserimenti.

Lo stesso algoritmo non compilerà per gli elenchi, perché non ha un metodo std::listreserve. Tuttavia, senza reserve dovrebbe funzionare per list s, poiché std::list::push_back non invalida gli iteratori. Hai ragione che std::vector::push_back invalida gli iteratori quando si verifica la riallocazione, quindi è molto importante effettuare la chiamata reserve, perché si assicura che non sia necessaria alcuna riallocazione.