Capacité initiale du vecteur en C ++

Quel est le capacity()d'un std::vectorqui est créé en utilisant le constuctor par défaut? Je sais que le size()est nul. Pouvons-nous déclarer qu'un vecteur construit par défaut n'appelle pas l'allocation de mémoire de tas?

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

Par exemple, sous Linux (g ++ 4.4.5, noyau 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. S'agit-il d'une règle ou dépend-il du fournisseur STL?

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

Les implémentations de stockage de std :: vector varient considérablement, mais toutes celles que j'ai rencontrées commencent à 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 la sortie suivante:

0
1
2
4
4
8
8
8
8
16
16

sous GCC 5.1 et:

0
1
2
3
4
6
6
9
9
9
13

sous MSVC 2013.

Pour autant que j'ai compris la norme (bien que je ne puisse en fait pas nommer de référence), l'instanciation de conteneur et l'allocation de mémoire ont été intentionnellement découplées pour une bonne raison. Par conséquent, vous avez des appels distincts et séparés pour

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

Et cela a beaucoup de sens. Le seul droit d'exister reserve()est de vous donner la possibilité de coder autour de 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 faire une estimation éclairée. Si cela ne vous est pas donné, vous feriez mieux de rester à l'écart reserve()car vous changerez simplement la réaffectation pour la mémoire gaspillée.

Donc, mettre tout cela ensemble:

• La norme ne spécifie pas intentionnellement 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 une implémentation spécifique, fixe "quelque chose" sous le capot).
• L'allocation ne doit pas être implicite. Donc, pour préallouer un bloc, vous devez passer un appel séparé reserve()et cela ne doit pas être au même lieu de construction (pourrait / devrait bien sûr être plus tard, après avoir pris connaissance de la taille requise pour accueillir)
• Ainsi, si un vecteur préallouait toujours un bloc de mémoire de taille définie par l'implémentation, cela déjouerait le travail prévu reserve(), n'est-ce pas?
• Quel serait l'avantage de préallouer un bloc si la STL ne peut naturellement pas connaître le but recherché et la taille attendue d'un vecteur? Ce sera plutôt insensé, voire contre-productif.
• La solution appropriée consiste plutôt à allouer et à implémenter un bloc spécifique avec le premier push_back()- sinon déjà explicitement alloué avant par reserve().
• En cas de réaffectation nécessaire, l'augmentation de la taille des blocs est également spécifique à l'implémentation. Les implémentations vectorielles que je connais commencent par une augmentation exponentielle de la taille, mais plafonneront le taux d'incrément à un certain maximum pour éviter de gaspiller d'énormes quantités de mémoire ou même de la faire exploser.

Tout cela n'est pleinement opérationnel et avantageux que s'il n'est pas perturbé par un constructeur allouant. Vous avez des valeurs par défaut raisonnables pour les scénarios courants qui peuvent être remplacées à la demande par reserve()(et shrink_to_fit()). Donc, même si la norme ne le dit pas explicitement, je suis tout à fait sûr de supposer qu'un vecteur nouvellement construit ne préalloue pas est une valeur sûre pour toutes les implémentations actuelles.

Comme un léger ajout aux autres réponses, j'ai trouvé que lors de l'exécution dans des conditions de débogage avec Visual Studio, un vecteur construit par défaut sera toujours alloué sur le tas même si la capacité commence à zéro.

Plus précisément, si _ITERATOR_DEBUG_LEVEL! = 0, alors vector allouera de l'espace pour aider à la vérification de l'itérateur.

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

Je viens de trouver cela un peu ennuyeux car j'utilisais un allocateur personnalisé à l'époque et ne m'attendais pas à l'allocation supplémentaire.

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

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

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

   Avant C ++ 17, il était un comportement indéfini de construire un std::vector<T>si la définition de Test encore inconnue au point d'instanciation. Cependant, cette contrainte a été assouplie dans C ++ 17 .

   Afin d'allouer efficacement de la mémoire pour un objet, vous devez connaître sa taille. À partir de C ++ 17 et au-delà, vos clients peuvent avoir des cas où votre std::vector<T>classe ne connaît pas la taille de T. Est-il judicieux que les caractéristiques d'allocation de mémoire dépendent de l'exhaustivité du type?

2. Unwanted Memory allocations

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

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

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

   Ce n'est qu'un exemple, n'hésitez pas à penser à plus ...

Standard ne spécifie pas la valeur initiale de la capacité, mais le conteneur STL se développe automatiquement pour accueillir autant de données que vous en mettez, à condition que vous ne dépassiez pas la taille maximale (utilisez la fonction membre max_size pour savoir). Pour les vecteurs et les chaînes, la croissance est gérée par réallocation chaque fois que plus d'espace est nécessaire. Supposons que vous souhaitiez créer un vecteur contenant la valeur 1-1000. Sans utiliser de réserve, le code entraînera généralement entre 2 et 18 réallocations au cours de la boucle suivante:

vector<int> v;
for ( int i = 1; i <= 1000; i++) v.push_back(i);

La modification du code pour utiliser reserve peut entraîner 0 allocations pendant la boucle:

vector<int> v;
v.reserve(1000);

for ( int i = 1; i <= 1000; i++) v.push_back(i);

En gros, les capacités des vecteurs et des chaînes augmentent d'un facteur compris entre 1,5 et 2 à chaque fois.