Vecteur : initialisation ou réserve ?

Question

Je connais la taille d'un vecteur, quelle est la meilleure façon de l'initialiser ?

Option 1 :

vector<int> vec(3); //in .h
vec.at(0)=var1;     //in .cpp
vec.at(1)=var2;     //in .cpp
vec.at(2)=var3;     //in .cpp

Option 2 :

vector<int> vec;     //in .h
vec.reserve(3);      //in .cpp
vec.push_back(var1); //in .cpp
vec.push_back(var2); //in .cpp
vec.push_back(var3); //in .cpp

Je suppose que l'option 2 est meilleure que l'option 1. C'est le cas ? D'autres options ?

Answer 1

D'une manière ou d'une autre, une réponse sans réponse qui est complètement fausse est restée acceptée et la plupart des votes positifs pendant ~7 ans. Ce n'est pas une question de pommes et d'oranges. Il ne s'agit pas d'une question à laquelle il faut répondre par de vagues clichés.

Pour une règle simple à suivre :

L'option 1 est plus rapide...

...mais cela ne devrait pas être votre plus grande préoccupation.

Tout d'abord, la différence est assez mineure. Deuxièmement, lorsque nous augmentons l'optimisation du compilateur, la différence devient encore plus petite. Par exemple, sur mon gcc-5.4.0, la différence est sans doute triviale lorsque l'optimisation du compilateur est de niveau 3 ( -O3 ) :

Donc, en général, je recommande d'utiliser la méthode n° 1 chaque fois que vous rencontrez cette situation. Cependant, si vous ne pouvez pas vous rappeler laquelle est optimale, cela ne vaut probablement pas la peine de chercher à la découvrir. Choisissez simplement l'une ou l'autre et passez à autre chose, car il est peu probable que cela entraîne un ralentissement notable de votre programme dans son ensemble.

---

Ces tests ont été effectués en échantillonnant des tailles de vecteurs aléatoires à partir d'une distribution normale, puis en chronométrant l'initialisation des vecteurs de ces tailles à l'aide des deux méthodes. Nous conservons une variable somme fictive pour nous assurer que l'initialisation du vecteur n'est pas optimisée, et nous rendons aléatoires les tailles et les valeurs des vecteurs pour tenter d'éviter toute erreur due à la prédiction des branches, à la mise en cache et à d'autres astuces de ce type.

main.cpp :

/* 
 * Test constructing and filling a vector in two ways: construction with size
 * then assignment versus construction of empty vector followed by push_back
 * We collect dummy sums to prevent the compiler from optimizing out computation
 */

#include <iostream>
#include <vector>

#include "rng.hpp"
#include "timer.hpp"

const size_t kMinSize = 1000;
const size_t kMaxSize = 100000;
const double kSizeIncrementFactor = 1.2;
const int kNumVecs = 10000;

int main() {
  for (size_t mean_size = kMinSize; mean_size <= kMaxSize;
       mean_size = static_cast<size_t>(mean_size * kSizeIncrementFactor)) {
    // Generate sizes from normal distribution
    std::vector<size_t> sizes_vec;
    NormalIntRng<size_t> sizes_rng(mean_size, mean_size / 10.0); 
    for (int i = 0; i < kNumVecs; ++i) {
      sizes_vec.push_back(sizes_rng.GenerateValue());
    }
    Timer timer;
    UniformIntRng<int> values_rng(0, 5);
    // Method 1: construct with size, then assign
    timer.Reset();
    int method_1_sum = 0;
    for (size_t num_els : sizes_vec) {
      std::vector<int> vec(num_els);
      for (size_t i = 0; i < num_els; ++i) {
        vec[i] = values_rng.GenerateValue();
      }
      // Compute sum - this part identical for two methods
      for (size_t i = 0; i < num_els; ++i) {
        method_1_sum += vec[i];
      }
    }
    double method_1_seconds = timer.GetSeconds();
    // Method 2: reserve then push_back
    timer.Reset();
    int method_2_sum = 0;
    for (size_t num_els : sizes_vec) {
      std::vector<int> vec;
      vec.reserve(num_els);
      for (size_t i = 0; i < num_els; ++i) {
        vec.push_back(values_rng.GenerateValue());
      }
      // Compute sum - this part identical for two methods
      for (size_t i = 0; i < num_els; ++i) {
        method_2_sum += vec[i];
      }
    }
    double method_2_seconds = timer.GetSeconds();
    // Report results as mean_size, method_1_seconds, method_2_seconds
    std::cout << mean_size << ", " << method_1_seconds << ", " << method_2_seconds;
    // Do something with the dummy sums that cannot be optimized out
    std::cout << ((method_1_sum > method_2_sum) ? "" : " ") << std::endl;
  }

  return 0;
}

Les fichiers d'en-tête que j'ai utilisés sont situés ici :

• rng.hpp
• timer.hpp

Answer 2

La "meilleure" façon serait :

vector<int> vec = {var1, var2, var3};

disponible avec un compilateur compatible C++11.

Je ne sais pas exactement ce que vous voulez dire par faire des choses dans un en-tête ou des fichiers d'implémentation. Un global mutable est un non-non pour moi. Si c'est un membre de classe, alors il peut être initialisé dans la liste d'initialisation du constructeur.

Sinon, l'option 1 est généralement utilisée si vous savez combien d'éléments vous allez utiliser et que les valeurs par défaut (0 pour int) sont utiles.
Utilisation de at signifie ici que vous ne pouvez pas garantir que l'index est valide. Une telle situation est en soi alarmante. Même si vous serez en mesure de détecter les problèmes de manière fiable, il est définitivement plus simple d'utiliser push_back et arrêter de s'inquiéter de l'exactitude des index.

Dans le cas de l'option 2, la différence de performance est généralement nulle, que vous réserviez de la mémoire ou non, il est donc plus simple de ne pas réserver*. Sauf peut-être si le vecteur contient des types qui sont très coûteux à copier (et ne fournissent pas de déplacement rapide en C++11), ou si la taille du vecteur va être énorme.

---

* De Stroustrups FAQ sur le style et la technique C++ :

Les gens s'inquiètent parfois du coût de la croissance de std::vector de façon incrémentale. J'avais l'habitude de m'inquiéter de cela et j'utilisais reserve() pour optimiser la croissance. Après avoir mesuré mon code et avoir à plusieurs reprises des difficultés à trouver les avantages de reserve() en termes de performances programmes réels, j'ai cessé de l'utiliser sauf lorsqu'il était nécessaire d'éviter l'invalidation des itérateurs (un cas rare dans mon code). Encore une fois : mesurez avant vous optimisez.

Answer 3

Les deux variantes ont une sémantique différente, c'est-à-dire que vous comparez des pommes et des oranges.

La première vous donne un vecteur de n valeurs initialisées par défaut, la seconde variante réserve la mémoire, mais ne les initialise pas.

Choisissez ce qui correspond le mieux à vos besoins, c'est-à-dire ce qui est "mieux" dans une certaine situation.

Answer 4

Bien que vos exemples soient essentiellement les mêmes, il se peut que lorsque le type utilisé n'est pas un int le choix vous est retiré. Si votre type n'a pas de constructeur par défaut, ou si vous devez reconstruire chaque élément plus tard de toute façon, j'utiliserais reserve . Mais ne tombez pas dans le piège que j'ai fait et utilisez reserve et ensuite le operator[] pour l'initialisation !

---

Constructeur

std::vector<MyType> myVec(numberOfElementsToStart);
int size = myVec.size();
int capacity = myVec.capacity();

Dans ce premier cas, en utilisant le constructeur, size et numberOfElementsToStart seront égales et capacity seront supérieures ou égales à celles-ci.

Considérez monVec comme un vecteur contenant un certain nombre d'éléments de type MyType qui peut être consulté et modifié, push_back(anotherInstanceOfMyType) l'ajoutera à la fin du vecteur.

---

Réserve

std::vector<MyType> myVec;
myVec.reserve(numberOfElementsToStart);
int size = myVec.size();
int capacity = myVec.capacity();

Lorsque vous utilisez le reserve fonction, size sera 0 jusqu'à ce que vous ajoutiez un élément au tableau et capacity sera égal ou supérieur à numberOfElementsToStart .

Pensez à monVec comme à un vide auquel de nouveaux éléments peuvent être ajoutés à l'aide de la fonction push_back sans allocation de mémoire pour au moins la première numberOfElementsToStart éléments.

Notez que push_back() nécessite toujours une vérification interne pour s'assurer que taille < capacité et à incrémenter la taille Vous pouvez donc mettre en balance cet aspect avec le coût de la construction par défaut.

---

Initialisation de la liste

std::vector<MyType> myVec{ var1, var2, var3 };

Il s'agit d'une option supplémentaire pour initialiser votre vecteur, et bien qu'elle ne soit réalisable que pour de très petits vecteurs, c'est une façon claire d'initialiser un petit vecteur avec des valeurs connues. size sera égal au nombre d'éléments avec lesquels vous l'avez initialisé, et capacity sera égale ou supérieure à la taille. Les compilateurs modernes peuvent optimiser la création d'objets temporaires et éviter les copies inutiles.

Answer 5

L'option 2 est meilleure, car elle ne nécessite que de réserver de la mémoire (3 * sizeof(T)), tandis que la première option appelle le constructeur du type de base pour chaque cellule à l'intérieur du conteneur.

Pour les types C, ce sera probablement la même chose.