algorithme de copie avec back_inserter

Question

Je ne comprends pas pourquoi ce code est exact

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

coll.end() représente la fin du vecteur. Après avoir push_back quoi que ce soit (comme le fait back_insert_iterator) ce que coll.end() renvoie est le même qu'avant ou quelque chose de différent? Y a-t-il plus d'un itérateur de terminaison? Pourquoi end() peut-il être utilisé comme fin de conteneur même lorsque de nouveaux contenus sont ajoutés?

En outre, vous ne pouvez pas appliquer le code à la liste conteneur - il reste bloqué. Ceci est important car dans le cas d'un vecteur, push_back rend les itérateurs peu fiables après réallocation des données (lorsque size()==capacity() et push_back() sont appelés) alors que dans le cas d'une liste, ce n'est pas le cas. Alors pourquoi le code se bloque pour la liste?

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

Les begin() et end() les pointeurs/itérateurs utilisés pour déterminer ce qui doit être copié sont évalués une fois lorsque la fonction est appelée. Donc, essentiellement, std::copy() va incrémenter son itérateur du curseur qui atteindra finalement end(), car vector<T>::const_iterator est juste un pointeur fantaisie T* sur un tableau old school.

Comme vous le mentionnais correctement, si un push_back fait la vector réallouer et déplacer les données quelque part ailleurs dans la mémoire, puis l'élément suivant copié aura une mauvaise adresse pour la source, ce qui est susceptible de se retrouver avec une faute de segmentaion.

Pour une liste, il ne peut jamais se terminer car end() est un pointeur sentinelle/garde, et vous pouvez seulement atteindre end() en incrémentant l'itérateur sur le dernier élément de la liste. Donc, l'adresse de end() ne change jamais elle-même, mais comme vous ajoutez constamment un élément à la fin de la liste, vous n'atteindrez jamais le dernier élément, donc std::copy() ne peut jamais obtenir un pointeur vers end(). Un peu comme un chien qui poursuit sa queue.

Il est plus facile à comprendre avec des illustrations et des diagrammes, des lectures sur des listes doublement chaînées et des nœuds sentinelles, tout cela aura du sens.

Answer 2

coll.end() est appelé avant l'insertion de la copie et le dos commence, donc essentiellement le code est le même que

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

sens, copy ne re -évaluer coll.end(), donc il ne remarquera pas/ne dérange pas qu'il insère dans le même vecteur, et que ce qui était autrefois la fin du vecteur n'est pas la fin après les premières insertions.

Le même algorithme ne compilera pas pour les listes, car std::list n'a pas de méthode reserve. Cependant, sans reserve il devrait fonctionner pour list s, puisque std::list::push_back n'invalide pas les itérateurs. Vous avez raison: std::vector::push_back invalide les itérateurs lorsque la réallocation se produit, il est donc très important de faire l'appel reserve, car il s'assure qu'aucune réaffectation n'est nécessaire.