Comment les conteneurs STL copient-ils les objets ?

Question

Je connais les conteneurs STL comme vector copie l'objet lorsqu'il est ajouté. push_back ressemble à une méthode :

void push_back ( const T& x );

Je suis surpris de voir qu'il prend l'élément comme référence . J'ai écrit un programme d'exemple pour voir comment cela fonctionne.

struct Foo
{
    Foo()
    {
        std::cout << "Inside Foo constructor" << std::endl;
    }

    Foo(const Foo& f)
    {
        std::cout << "inside copy constructor" << std::endl;
    }
};

Foo f;
std::vector<Foo> foos;
foos.push_back(f);

Cela copie l'objet et je peux voir qu'il appelle copieur-constructeur .

Ma question est, quand le push_back prend l'élément comme référence, comment appelle-t-il le constructeur de copie ? Ou est-ce que quelque chose m'échappe ici ?

Des idées ?

Answer 1

Il utilise probablement le "placement new "pour construire l'objet sur place dans son tableau interne. Placement new n'alloue pas de mémoire ; il place simplement l'objet à l'endroit spécifié et appelle le constructeur. La syntaxe est la suivante new (address) Class(constructor_arguments) .

Le constructeur de copie T::T(T const &) est appelé pour créer la copie sur place. Quelque chose comme ceci (simplifié) :

template<T>
void vector<T>::push_back(T const &item) {
    // resize if necessary
    new (&d_array[d_size++]) T(item);
}

Notez que T doit avoir un constructeur de copie pour que cela fonctionne. Par défaut (si vous ne faites rien), il en obtient un gratuitement. Si vous le définissez explicitement, il doit être public pour vector<T> pour travailler.

Voici comment la libstdc++ de GNU le fait mais je doute que ce soit très instructif. Il y a un allocateur (le deuxième argument de template à vector ) qui rend la chose moins évidente.

Answer 2

Le SDK C++ prend toujours const T & comme paramètre de fonction pour l'efficacité.

Dans votre cas, s'il faut T comme paramètre, l'action de copie sera effectuée deux fois, l'une pour la passer à la fonction push_back(f) un pour l'ajout interne dans le conteneur. Et en prenant const T& comme paramètre, une seule copie est nécessaire !

Answer 3

Il utilise l'opérateur de placement new et le copie dans une mémoire unitialisée ;

Le placement new crée un nouvel élément à une adresse spécifiée en mémoire, dans le cas du vecteur, le end() actuel ;

void push_back(const T& val){
::new (&*end()) T(val);
[increase end]
}

regardez http://spotep.com/dev/devector.h dont le code est assez clair (contrairement à la plupart des implémentations STL).