Pourquoi std:: vector reserve ne" double " pas sa capacité, alors que resize le fait?

je viens de découvrir que std::vector<T>::resize "double" sa capacité même en redimensionnant à un élément au-dessus de la taille actuelle: 

std::vector<int> v(50);
v.resize(51);
std::cout << v.capacity() << std::endl;

ce programme produit 100 avec GCC et Clang, et 75 avec Visual C++. Cependant, lorsque je passe de resize à reserve : 

std::vector<int> v(50);
v.reserve(51);
std::cout << v.capacity() << std::endl;

la sortie est 51 avec les trois compilateurs.

je me demande pourquoi les implémentations utilisent une stratégie d'expansion différente pour resize et reserve . Cela semble incohérent, et je m'attendrais au même comportement ici.

Je ne fais qu'ajouter un lien à une motivation pour ma question, Où l'impact sur la performance est rapporté: pourquoi les vecteurs C++ STL 1000x sont-ils plus lents quand ils font beaucoup de réserves?

ajout d'une citation de la norme C++11 pour clarifier les exigences reserve ; §23.3.6.3(2):

après reserve() , capacity() est plus grand ou égal à l'argument de reserve si la réallocation se produit...

Quelques réflexions supplémentaires: à Partir de C++11 Standard:

complexité: la complexité est linéaire dans le nombre d'éléments insérés plus la distance jusqu'à l'extrémité du vecteur.

qui, en fait, implique une complexité constante (amortie) pour l'insertion d'un seul élément à la fin. Toutefois , cela ne s'applique qu'aux modificateurs de vecteurs , tels que push_back ou insert (§23.3.6.5).

resize ne figure pas parmi les modificateurs. Elle est listée au § 23.3.6.3 vector section capacité. Et il n'y a pas d'exigences de complexité pour resize .

cependant, dans la section vector aperçu général (§23.3.6.1), il est écrit:

it ( vector ) prend en charge (amorti) temps constant insérer et effacer les opérations à la fin

la question Est de savoir si resize(size()+1) est considéré comme " insertion à la fin " .

24
demandé sur Daniel Langr 2018-01-31 11:38:45

5 réponses

pour autant que je puisse dire, ni resize ni reserve n'est nécessaire pour avoir le comportement démontré. Tous deux sont toutefois autorisés à adopter un tel comportement, bien qu'ils puissent soit attribuer le montant exact, soit multiplier l'allocation précédente en ce qui concerne la norme.

chaque stratégie d'allocation a ses avantages. L'avantage de l'allocation de quantité exacte est qu'il n'a pas de mémoire aérienne lorsque l'allocation maximale est connue préalablement. L'avantage de la multiplication est qu'elle maintient la propriété amortie constante lorsqu'elle est mélangée avec les opérations d'insertion finale.

l'approche choisie par les implémentations testées présente l'avantage de permettre les deux stratégies lors du redimensionnement. Pour utiliser une stratégie, on peut réserver puis redimensionner. Pour utiliser l'autre, il suffit de redimensionner. Bien sûr, il faut être conscient du comportement non spécifié pour en profiter. Cet avantage peut être ou non le raisonnement derrière le choix de ces implémentations.

on pourrait considérer comme une défaillance de l'API vectorielle, comme spécifié dans la norme, qu'exprimer le comportement de réattribution prévu n'est pas possible (d'une manière qui est garantie par la norme).

15
répondu user2079303 2018-05-23 20:14:46

quand vous resize plus qu'il n'y a de capacité, vous "démontrez" déjà que vous ne voulez pas réserver juste la bonne capacité. Par contre, si vous utilisez reserve , vous demandez explicitement la bonne capacité. Si reserve utilisait la même stratégie que resize , il n'y aurait aucun moyen de réserver juste le bon montant.

Dans ce sens resize sans reserve est pour les paresseux ou dans le cas où vous ne connaissez pas le montant exact réserver. Vous appelez reserve si vous savez de quelle capacité vous avez besoin. C'est deux scénarios différents.

PS: comme StoryTeller l'a souligné, aussi reserve n'est pas nécessaire de réserver le montant exact qui est demandé selon la norme. Néanmoins je pense que mon argument principal tient toujours: resize (sans reserve ) et reserve sont destinés à différents scénarios, où vous donnez une indication de combien vous voulez réserver ou ne se soucient pas de la capacité réelle et je veux juste avoir le conteneur dimensionné à ce que vous demandez.

9
répondu user463035818 2018-01-31 12:39:04

pourquoi s'attendriez-vous à ce qu'ils se comportent de la même façon? reserve est utilisé pour préallouer l'espace que vous utiliserez plus tard, avec l'attente que l'Utilisateur a une poignée décente sur la taille finale attendue du conteneur. resize est simplement une allocation normale, et donc il suit l'approche normale, Vitesse efficace, d'augmenter géométriquement l'espace alloué du conteneur.

augmentation de la taille des conteneurs par étapes multiplicatives pour réduire le nombre de les attributions sont nécessaires pour maintenir la vitesse et réduire la fragmentation de la mémoire. Le doublement est le plus courant, mais certaines mises en œuvre utilisent des étapes de 1,5 (par exemple MSVC) qui permettent d'augmenter les allocations pour réduire le gaspillage d'espace dans chaque conteneur.

mais, si l'Utilisateur a déjà dit à la bibliothèque comment grand ils pensent que le conteneur va obtenir - en provoquant reserve - il n'y a pas besoin d'allouer l'espace excédentaire, ils peuvent au lieu de faire confiance à l'utilisateur d'avoir appelé avec le bon nombre. Il est reserve qui a le comportement inhabituel, pas resize .

6
répondu Jack Aidley 2018-01-31 14:58:51

resize est nécessaire pour suivre une stratégie de réallocation exponentielle afin de remplir sa garantie de complexité (linéaire dans le nombre d'éléments inséré ). On peut le voir en considérant que resize(size() + 1) est nécessaire pour avoir amorti la complexité constante, donc doit suivre la croissance exponentielle pour la même raison que push_back (la complexité constante amortie) doit croître exponentiellement.

Une mise en œuvre de reserve est autorisé à suivre la stratégie de répartition qu'il aime, car sa seule exigence de complexité est qu'il soit linéaire dans le nombre d'éléments présent . Cependant, si une implémentation devait par exemple arrondir à la puissance suivante de deux, cela serait inefficace en termes d'espace (et surprenant) dans le cas où l'utilisateur sait exactement combien de mémoire est nécessaire, et pourrait compliquer le portage si l'utilisateur vient à se fier à ce comportement. La latitude dans la norme est mieux exercée dans les cas où il n'y a pas d'inefficacité de l'espace, par exemple en arrondissant les allocations à la taille du mot, si l'allocateur fonctionne à cette granularité.

6
répondu ecatmur 2018-01-31 16:47:59

reserve change la capacité, tandis que resize change le size .

capacity est le nombre d'éléments pour lesquels le conteneur dispose actuellement d'une place.

size est le nombre d'éléments dans le conteneur.

quand vous attribuez un vecteur vide vous obtenez un défaut capacity (alias espace). La taille est toujours 0, et quand vous ajoutez des éléments dans le vecteur, son incrément de taille. Lorsque la taille est égale à la capacité et vous ajoutez plus d'article la capacité doit croître (généralement le double lui-même).

le problème avec vector est qu'il assure la mémoire séquentielle, ce qui signifie que chaque nouvelle augmentation d'allocation aura également besoin d'une copie de l'allocation précédente à la nouvelle, au cas où il n'y avait pas d'espace pour la nouvelle taille d'allocation dans l'ancienne zone de mémoire allouée.

ici le reserve peut aider, si vous connaissez les éléments max dans le vecteur. Lorsque vous utilisez reserve , il n'y aura qu'une seule allocation et aucune copie mémoire, à moins que vous ne passiez les items réservés.

quand vous dites le nombre exact réservé, vous obtenez la mémoire exacte que vous avez demandé. Quand vous ajoutez juste des éléments (même avec redimensionner, vous ne dites pas que vous n'ajouteriez pas plus d'éléments.

1
répondu SHR 2018-01-31 12:42:07