Moyen efficace de renvoyer un std :: vector en c ++

108

Combien de données sont copiées, lors du retour d'un std :: vector dans une fonction et quelle sera la taille d'une optimisation pour placer le std :: vector en magasin libre (sur le tas) et renvoyer un pointeur à la place, c'est-à-dire:

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;
} 

?

Morten
la source
4
Que diriez-vous de passer le vecteur par référence, puis de le remplir à l'intérieur f?
Kiril Kirov
4
RVO est une optimisation assez basique que la plupart des compilateurs seront capables de faire à tout moment.
Remus Rusanu
Au fur et à mesure que les réponses affluent, cela peut vous aider à clarifier si vous utilisez C ++ 03 ou C ++ 11. Les meilleures pratiques entre les deux versions varient un peu.
Drew Dormann
@Kiril Kirov, puis-je le faire sans le mettre dans la liste des arguments de la fonction, c'est-à-dire. void f (std :: vecteur et résultat)?
Morten

Réponses:

141

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

std::vector<X> f();

Autrement dit, retour par valeur.

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

Nawaz
la source
13
@LeonidVolnitsky: Oui si c'est local . En fait, return std::move(v);désactivera l'élision de mouvement même si c'était possible avec juste return v;. Donc, ce dernier est préféré.
Nawaz
1
@juanchopanza: Je ne pense pas. Avant C ++ 11, vous pouviez vous y opposer car le vecteur ne sera pas déplacé; et RVO est une chose dépendante du compilateur! Parlez des choses des années 80 et 90.
Nawaz
2
Ma compréhension de la valeur de retour (par valeur) est la suivante: au lieu de `` été déplacé '', la valeur de retour dans l'appelé est créée sur la pile de l'appelant, donc toutes les opérations dans l'appelé sont en place, il n'y a rien à déplacer dans RVO . Est-ce exact?
r0ng
2
@ r0ng: Oui, c'est vrai. C'est ainsi que les compilateurs implémentent généralement RVO.
Nawaz
1
@Nawaz Ce n'est pas le cas. Il n'y a même plus de mouvement.
Courses de légèreté en orbite
71

Vous devez retourner par valeur.

La norme a une particularité pour améliorer l'efficacité du retour en valeur. C'est ce qu'on appelle "élision de copie", et plus précisément dans ce cas "l'optimisation de la valeur de retour nommée (NRVO)".

Compilateurs ne pas mettre en œuvre, mais là encore compilateurs n'ont à mettre en œuvre la fonction inline (ou effectuer une optimisation du tout). Mais les performances des bibliothèques standard peuvent être assez médiocres si les compilateurs n'optimisent pas, et tous les compilateurs sérieux implémentent l'inlining et NRVO (et d'autres optimisations).

Lorsque 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 faire ceci:

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

Copy elision n'empêche pas ici une copie car c'est une affectation plutôt qu'une initialisation. Cependant, vous devez toujours renvoyer par valeur. En C ++ 11, l'affectation est optimisée par quelque chose de différent, appelé "déplacer la sémantique". En C ++ 03, le code ci-dessus provoque une copie, et bien qu'en théorie un optimiseur puisse l'éviter, en pratique c'est trop difficile. Donc 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 flexible à l'utilisateur:

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

En plus de cela, vous pouvez également prendre en charge l'interface vectorielle existante:

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

Cela peut être moins efficace que votre code existant, si votre code existant utilise reserve()d'une manière plus complexe qu'un montant fixe à l'avance. Mais si votre code existant appelle essentiellement push_backle vecteur à plusieurs reprises, alors ce code basé sur un modèle devrait être aussi bon.

Steve Jessop
la source
A voté pour la réponse vraiment meilleure et détaillée. Cependant, dans votre variante swap () ( pour C ++ 03 sans NRVO ), vous aurez toujours une copie du constructeur de copie faite dans f (): de la variable result à un objet temporaire caché qui sera enfin échangé vers myvec .
JenyaKh
@JenyaKh: bien sûr, c'est un problème de qualité de mise en œuvre. La norme n'exigeait pas que les implémentations C ++ 03 implémentent NRVO, tout comme elle ne nécessitait pas d'incrustation de fonction. La différence avec l'inlining de fonction, c'est que l'inlining ne change pas la sémantique ou votre programme contrairement à NRVO. Le code portable doit fonctionner avec ou sans NRVO. Un code optimisé pour une implémentation particulière (et des indicateurs de compilateur particuliers) peut rechercher des garanties concernant NRVO dans la propre documentation de l'implémentation.
Steve Jessop
3

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

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


la source
1

Un idiome pré-C ++ 11 courant consiste à transmettre une référence à l'objet en cours de remplissage.

Ensuite, il n'y a pas de copie du vecteur.

void f( std::vector & result )
{
  /*
    Insert elements into result
  */
} 
Drew Dormann
la source
3
Ce n'est plus un idiome en C ++ 11.
Nawaz
1
@Nawaz je suis d'accord. Je ne sais pas quelle est la meilleure pratique actuellement en matière de SO concernant les questions sur C ++ mais pas spécifiquement C ++ 11. Je soupçonne que je devrais être enclin à donner des réponses C ++ 11 à un étudiant, des réponses C ++ 03 à quelqu'un à la taille en code de production. Avez-vous une opinion?
Drew Dormann
7
En fait, après la sortie de C ++ 11 (qui a 19 mois), je considère chaque question comme une question C ++ 11, à moins qu'il ne soit explicitement indiqué comme une question C ++ 03.
Nawaz
1

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

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

NRVO optimise les appels de constructeur et de destructeur de copie redondants et améliore ainsi les performances globales.

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

taocp
la source
0
vector<string> getseq(char * db_file)

Et si vous voulez l'imprimer sur main (), vous devez le faire en boucle.

int main() {
     vector<string> str_vec = getseq(argv[1]);
     for(vector<string>::iterator it = str_vec.begin(); it != str_vec.end(); it++) {
         cout << *it << endl;
     }
}
Akash Kandpal
la source
-2

Aussi agréable que puisse être le "retour par valeur", c'est le genre de code qui peut conduire à une erreur. Considérez le programme suivant:

    #include <string>
    #include <vector>
    #include <iostream>
    using namespace std;
    static std::vector<std::string> strings;
    std::vector<std::string> vecFunc(void) { return strings; };
    int main(int argc, char * argv[]){
      // set up the vector of strings to hold however
      // many strings the user provides on the command line
      for(int idx=1; (idx<argc); ++idx){
         strings.push_back(argv[idx]);
      }

      // now, iterate the strings and print them using the vector function
      // as accessor
      for(std::vector<std::string>::interator idx=vecFunc().begin(); (idx!=vecFunc().end()); ++idx){
         cout << "Addr: " << idx->c_str() << std::endl;
         cout << "Val:  " << *idx << std::endl;
      }
    return 0;
    };
  • Q: Que se passera-t-il lorsque ce qui précède sera exécuté? R: Un coredump.
  • Q: Pourquoi le compilateur n'a-t-il pas détecté l'erreur? R: Parce que le programme est syntaxiquement, mais pas sémantiquement, correct.
  • Q: Que se passe-t-il si vous modifiez vecFunc () pour renvoyer une référence? R: Le programme s'exécute jusqu'à la fin et produit le résultat attendu.
  • Q: Quelle est la différence? R: Le compilateur n'a pas besoin de créer et de gérer des objets anonymes. Le programmeur a demandé au compilateur d'utiliser exactement un objet pour l'itérateur et pour la détermination du point de terminaison, plutôt que deux objets différents comme le fait l'exemple cassé.

Le programme erroné ci-dessus n'indiquera aucune erreur même si l'on utilise les options de rapport GNU g ++ -Wall -Wextra -Weffc ++

Si vous devez produire une valeur, alors ce qui suit fonctionnerait au lieu d'appeler deux fois vecFunc ():

   std::vector<std::string> lclvec(vecFunc());
   for(std::vector<std::string>::iterator idx=lclvec.begin(); (idx!=lclvec.end()); ++idx)...

Ce qui précède ne produit pas non plus d'objets anonymes pendant l'itération de la boucle, mais nécessite une opération de copie possible (qui, comme certains le notent, peut être optimisée dans certaines circonstances. Mais la méthode de référence garantit qu'aucune copie ne sera produite. Croire que le compilateur sera perform RVO n'est pas un substitut pour essayer de construire le code le plus efficace possible. Si vous pouvez évoquer la nécessité pour le compilateur de faire RVO, vous êtes en avance sur le jeu.

dragon onclesmrgol
la source
3
Ceci est plus un exemple de ce qui peut mal tourner si un utilisateur n'est pas familiarisé avec C ++ en général. Quelqu'un qui est familier avec les langages basés sur des objets comme .net ou javascript supposerait probablement que le vecteur de chaîne est toujours passé en tant que pointeur et donc dans votre exemple pointerait toujours vers le même objet. vecfunc (). begin () et vecfunc (). end () ne correspondront pas nécessairement dans votre exemple car ils devraient être des copies du vecteur de chaîne.
Medran
-2
   vector<string> func1() const
   {
      vector<string> parts;
      return vector<string>(parts.begin(),parts.end()) ;
   } 
Amruth A
la source