Une manière efficace de retourner un std::vector en c++.

Question

Combien de données sont copiées, lors du retour d'un fichier std::vector dans une fonction et quelle sera l'ampleur de l'optimisation si l'on place le vecteur std::vector en free-store (sur le tas) et que l'on renvoie un pointeur à la place, c'est-à-dire si :

std::vector *f()
{
  std::vector *result = new std::vector();
  /*
    Insert elements into result
  */
  return result;
} 

plus efficace que :

std::vector f()
{
  std::vector result;
  /*
    Insert elements into result
  */
  return result;
} 

?

Answer 1

En C++11, c'est la méthode préférée :

std::vector<X> f();

C'est-à-dire le retour par valeur.

Avec C++11, std::vector a une sémantique de mouvement, ce qui signifie que le local déclaré dans votre fonction sera déplacé sur le retour et dans certains cas, même le déplacement peut être évité par le compilateur.

Answer 2

Vous devez retourner par valeur.

La norme a une caractéristique spécifique pour améliorer l'efficacité du retour par valeur. Elle s'appelle "copy elision", et plus spécifiquement dans ce cas la "named return value optimization (NRVO)".

Les compilateurs n'ont pas à l'implémenter, mais là encore, les compilateurs n'ont pas à le faire. ont pour implémenter l'inlining des fonctions (ou pour effectuer une quelconque optimisation). Mais les performances des bibliothèques standard peuvent être assez faibles si les compilateurs n'optimisent pas, et tous les compilateurs sérieux implémentent l'inlining et le NRVO (et d'autres optimisations).

Lorsque le NRVO est appliqué, il n'y aura pas de copie dans le code suivant :

std::vector<int> f() {
    std::vector<int> result;
    ... populate the vector ...
    return result;
}

std::vector<int> myvec = f();

Mais l'utilisateur peut vouloir le faire :

std::vector<int> myvec;
... some time later ...
myvec = f();

L'élision de copie n'empêche pas une copie ici car il s'agit d'une affectation plutôt que d'une initialisation. Cependant, vous devriez toujours retourner par valeur. En C++11, l'affectation est optimisée par quelque chose de différent, appelé "move semantics". En C++03, le code ci-dessus provoque une copie, et bien que en théorie un optimiseur pourrait être capable de l'éviter, mais en pratique, c'est trop difficile. Ainsi, au lieu de myvec = f() En C++03, vous devriez écrire ceci :

std::vector<int> myvec;
... some time later ...
f().swap(myvec);

Il existe une autre option, qui consiste à offrir une interface plus souple à l'utilisateur :

template <typename OutputIterator> void f(OutputIterator it) {
    ... write elements to the iterator like this ...
    *it++ = 0;
    *it++ = 1;
}

Vous pouvez alors également prendre en charge l'interface vectorielle existante :

std::vector<int> f() {
    std::vector<int> result;
    f(std::back_inserter(result));
    return result;
}

Ce site pourrait être moins efficace que votre code existant, si votre code existant utilise reserve() d'une manière plus complexe qu'un simple montant fixe à l'avance. Mais si votre code existant appelle essentiellement push_back sur le vecteur de manière répétée, alors ce code basé sur un modèle devrait être aussi bon.

Answer 3

Il est temps que je poste une réponse sur RVO moi aussi...

Si vous retournez un objet par valeur, le compilateur l'optimise souvent pour qu'il ne soit pas construit deux fois, puisqu'il est superflu de le construire dans la fonction en tant que temporaire et de le copier ensuite. C'est ce qu'on appelle l'optimisation de la valeur de retour : l'objet créé sera déplacé au lieu d'être copié.

Answer 4

Un idiome courant avant C++11 est de passer une référence à l'objet à remplir.

Il n'y a donc pas de copie du vecteur.

void f( std::vector & result )
{
  /*
    Insert elements into result
  */
}

Answer 5

Si le compilateur prend en charge l'optimisation des valeurs de retour nommées ( http://msdn.microsoft.com/en-us/library/ms364057(v=vs.80).aspx ), vous pouvez directement retourner le vecteur à condition qu'il n'y en ait pas :

1. Des chemins différents renvoient des objets nommés différents
2. Des chemins de retour multiples (même si le même objet nommé est retourné sur tous les chemins) avec les états EH introduits.
3. L'objet nommé renvoyé est référencé dans un bloc asm en ligne.

NRVO optimise les appels redondants des constructeurs et destructeurs de copie et améliore ainsi les performances globales.

Il ne devrait pas y avoir de réelle différence dans votre exemple.