Capacité initiale du vecteur en C++

Question

Quel est le capacity() d'un std::vector qui est créé en utilisant le constucteur par défaut ? Je sais que le size() est égal à zéro. Peut-on affirmer qu'un vecteur construit par défaut ne fait pas appel à l'allocation de la mémoire du tas ?

De cette façon, il serait possible de créer un tableau avec une réserve arbitraire en utilisant une seule allocation, comme par exemple std::vector<int> iv; iv.reserve(2345); . Disons que, pour une raison ou une autre, je ne veux pas lancer la size() le 2345.

Par exemple, sous Linux (g++ 4.4.5, kernel 2.6.32 amd64)

#include <iostream>
#include <vector>

int main()
{
  using namespace std;
  cout << vector<int>().capacity() << "," << vector<int>(10).capacity() << endl;
  return 0;
}

imprimé 0,10 . Est-ce une règle, ou cela dépend-il du fournisseur de STL ?

Answer 1

La norme ne spécifie pas ce qu'est l'obligation initiale capacity d'un conteneur devrait être, vous vous fiez donc à l'implémentation. Une implémentation commune commencera la capacité à zéro, mais il n'y a aucune garantie. D'autre part, il n'y a aucun moyen d'améliorer votre stratégie de std::vector<int> iv; iv.reserve(2345); alors restez-en là.

Answer 2

Les implémentations de stockage de std::vector varient considérablement, mais toutes celles que j'ai rencontrées commencent à partir de 0.

Le code suivant :

#include <iostream>
#include <vector>

int main()
{
  using namespace std;

  vector<int> normal;
  cout << normal.capacity() << endl;

  for (unsigned int loop = 0; loop != 10; ++loop)
  {
      normal.push_back(1);
      cout << normal.capacity() << endl;
  }

  cin.get();
  return 0;
}

Donne le résultat suivant :

0
1
2
4
4
8
8
8
8
16
16

sous GCC 5.1, 11.2 - Clang 12.0.1 et :

0
1
2
3
4
6
6
9
9
9
13

sous MSVC 2013.

Answer 3

D'après ce que j'ai compris de la norme (bien que je ne puisse pas citer de référence), l'instanciation des conteneurs et l'allocation de mémoire ont été intentionnellement découplées pour une bonne raison. Ainsi, vous avez des appels distincts et séparés pour

• constructor pour créer le conteneur lui-même
• reserve() préallouer un bloc de mémoire suffisamment grand pour accueillir au moins ( !) un nombre donné d'objets

Et cela a beaucoup de sens. Le seul droit d'exister pour reserve() est de vous donner l'opportunité de coder autour des réallocations éventuellement coûteuses lors de la croissance du vecteur. Pour être utile, vous devez connaître le nombre d'objets à stocker ou au moins être capable de le deviner. Si cela n'est pas possible, il vaut mieux ne pas utiliser la fonction reserve() car vous ne ferez que changer la réallocation de la mémoire gaspillée.

Donc, en mettant tout ça ensemble :

• La norme fait intentionnellement no spécifier un constructeur qui vous permet de préallouer un bloc de mémoire pour un nombre spécifique d'objets (ce qui serait au moins plus souhaitable que d'allouer un "quelque chose" fixe, spécifique à l'implémentation, sous le capot).
• L'allocation ne doit pas être implicite. Donc, pour pré-allouer un bloc, vous devez faire un appel séparé à reserve() et il n'est pas nécessaire que cela se fasse au même endroit que la construction (cela pourrait/devrait bien sûr se faire plus tard, après que vous ayez pris conscience de la taille nécessaire à accueillir).
• Ainsi, si un vecteur devait toujours préallouer un bloc de mémoire d'une taille définie par l'implémentation, cela contrecarrerait l'objectif de l'implémentation. reserve() n'est-ce pas ?
• Quel serait l'avantage de préallouer un bloc si la STL ne peut naturellement pas connaître l'objectif et la taille prévue d'un vecteur ? Ce serait plutôt absurde, voire contre-productif.
• La bonne solution consiste plutôt à allouer un bloc spécifique à l'implémentation avec le premier bloc de l'application push_back() - si elle n'a pas déjà été explicitement allouée auparavant par reserve() .
• Dans le cas d'une réallocation nécessaire, l'augmentation de la taille du bloc est également spécifique à l'implémentation. Les implémentations vectorielles que je connais commencent par une augmentation exponentielle de la taille mais plafonnent le taux d'incrémentation à un certain maximum pour éviter de gaspiller d'énormes quantités de mémoire ou même de la faire sauter.

Tout ceci n'est pleinement opérationnel et avantageux que s'il n'est pas perturbé par un constructeur d'allocation. Vous avez des valeurs par défaut raisonnables pour les scénarios courants qui peuvent être remplacées à la demande par reserve() (y shrink_to_fit() ). Donc, même si la norme ne l'indique pas explicitement, je suis sûr que supposer qu'un vecteur nouvellement construit n'est pas pré-alloué est un pari assez sûr pour toutes les implémentations actuelles.

Answer 4

Pour compléter les autres réponses, j'ai découvert que lors de l'exécution dans des conditions de débogage avec Visual Studio, un vecteur construit par défaut s'alloue toujours sur le tas, même si la capacité commence à zéro.

En particulier, si _ITERATOR_DEBUG_LEVEL != 0, le vecteur allouera de l'espace pour faciliter la vérification des itérateurs.

https://docs.microsoft.com/en-gb/cpp/standard-library/iterator-debug-level

J'ai juste trouvé cela légèrement ennuyeux car j'utilisais un allocateur personnalisé à l'époque et je ne m'attendais pas à cette allocation supplémentaire.

Answer 5

Il s'agit d'une vieille question, et toutes les réponses ici ont expliqué à juste titre le point de vue de la norme et la façon dont vous pouvez obtenir une capacité initiale d'une manière portable en utilisant std::vector::reserve ;

Cependant, je vais expliquer pourquoi cela n'a pas de sens pour une implémentation STL d'allouer de la mémoire lors de la construction d'un objet de type std::vector<T> objet ;

1. std::vector<T> de types incomplets ;

   Avant C++17, il était indéfini de construire un fichier de type std::vector<T> si la définition de T est encore inconnu au moment de l'instanciation. Toutefois, cette contrainte a été assouplie en C++17. .

   Afin d'allouer efficacement de la mémoire à un objet, vous devez connaître sa taille. À partir de C++17 et au-delà, il se peut que vos clients aient des cas où l'objet std::vector<T> ne connaît pas la taille de la classe T . Est-il logique que les caractéristiques d'allocation de la mémoire dépendent de la complétude des types ?

2. Unwanted Memory allocations

   Il y a beaucoup, beaucoup, beaucoup de fois où vous aurez besoin de modéliser un graphique dans un logiciel. (Un arbre est un graphe) ; Vous allez très probablement le modéliser comme suit :

   class Node {
       ....
       std::vector<Node> children; //or std::vector< *some pointer type* > children;
       ....
    };

   Maintenant, réfléchissez un instant et imaginez que vous avez beaucoup de nœuds terminaux. Vous seriez très mécontent si votre implémentation de la STL allouait de la mémoire supplémentaire simplement en prévision de la présence d'objets dans les nœuds terminaux. children .

   Ce n'est qu'un exemple, n'hésitez pas à en trouver d'autres...