Une affectation vectorielle invalide-t-elle la "réserve" ?

Question

Supposons que j'écrive

std::vector<T> littleVector(1);
std::vector<T> bigVector;

bigVector.reserve(100);
bigVector = littleVector;

La norme dit-elle que bigVector aura encore 100 éléments réservés ? Ou est-ce que je subirais une réallocation de la mémoire si je devais push_back 99 éléments ? Peut-être même que cela varie entre les implémentations de la STL.

Ceci a été discuté précédemment aquí mais aucune référence standard n'a été donnée.

Answer 1

Malheureusement, la norme ne spécifie pas le comportement de l'assignation des conteneurs de séquences en fonction de l'allocateur, et est en fait strictement inconsistante.

Nous savons (à partir du tableau 28 et de 23.2.1p7) que si allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value es true alors l'allocateur est remplacé lors de l'affectation des copies. De plus, d'après les tableaux 96 et 99, nous constatons que la complexité de l'affectation des copies est linéaire et le post-condition sur le fonctionnement a = t c'est que a == t c'est-à-dire (Tableau 96) que distance(a.begin(), a.end()) == distance(t.begin(), t.end()) && equal(a.begin(), a.end(), t.begin()) . D'après 23.2.1p7, après l'affectation de la copie, si l'allocateur propage, alors a.get_allocator() == t.get_allocator() .

En ce qui concerne la capacité vectorielle, 23.3.6.3 [capacité.vecteur] a :

5 - Remarques : La réaffectation invalide toutes les références, pointeurs et itérateurs se référant aux éléments de la séquence. Il est garanti qu'aucune réallocation n'a lieu pendant les insertions qui se produisent après un appel à reserve() jusqu'au moment où une insertion rendrait la taille du vecteur supérieure à la valeur de capacity() .

Si nous prenons bibliothèque DR341 comme guide de lecture de la norme :

Cependant, la formulation de 23.3.6.3 [vector.capacity]paragraphe 5 empêche la réduction de la capacité d'un vecteur, suite à un appel à reserve(). Cela invalide l'idiome, car swap() est ainsi empêché de réduire la capacité. [...]

Le DR341 a été résolu en ajoutant des paragraphes dans le paragraphe 23.3.6.3 :

void swap(vector<T,Allocator>& x);
7 - Effets : Échange le contenu et capacity() de *this avec celle de x .
8 - La complexité : Temps constant.

La conclusion est que, du point de vue du comité de la Bibliothèque, les opérations ne modifient que capacity() si elle est mentionnée au point 23.3.6.3. L'attribution de la copie n'est pas mentionnée dans l'article 23.3.6.3, et ne modifie donc pas l'article 23.3.6.3. capacity() . (L'affectation de Move a le même problème, surtout si l'on tient compte de la résolution proposée de Bibliothèque DR2321 .)

Il s'agit clairement d'un défaut de la norme, car l'affectation par copie propage des allocateurs inégaux. debe entraîner une réaffectation, ce qui contredit l'article 23.3.6.3p5.

Nous pouvons nous attendre et espérer que ce défaut sera résolu en faveur de :

• non réduit capacity() sur l'affectation de copie non modifiable par l'allocateur ;
• non spécifié capacity() sur l'affectation des copies modifiant l'allocateur ;
• non réduit capacity() sur l'affectation des déplacements sans propagation de l'allocateur ;
• conteneur-source capacity() sur l'affectation des déplacements par propagation de l'allocateur.

Cependant, dans la situation actuelle et jusqu'à ce que cela soit clarifié, vous feriez bien de ne pas dépendre d'un comportement particulier. Heureusement, il existe une solution de contournement simple qui garantit de ne pas réduire le nombre d'utilisateurs. capacity() :

bigVector.assign(littleVector.begin(), littleVector.end());

Answer 2

La seule exigence sur operator= pour les conteneurs standard est que par la suite, src == dst comme spécifié dans le tableau 96 (dans 23.2, Prescriptions générales relatives aux conteneurs). En outre, le même tableau précise la signification de operator == :

distance(lhs.begin(), lhs.end()) == distance(rhs.begin(), rhs.end()) // same size
  && equal(lhs.begin(), lhs.end(), rhs.begin()) // element-wise equivalent

Notez que cela n'inclut en aucun cas la capacité. Aucune autre partie de la norme ne mentionne non plus la capacité au-delà de l'invariant général selon lequel capacity() >= size() . La valeur de la capacité après l'affectation n'est donc pas spécifiée, et le conteneur est libre de mettre en œuvre l'affectation comme il le souhaite, tant que les exigences de l'allocateur sont respectées.

---

En général, vous constaterez que les implémentations se comportent de telle sorte que

• si les allocateurs sont égaux et que le dst a une capacité suffisante, il conservera son ancien stockage,
• sinon il allouera juste assez de stockage pour les nouveaux éléments, et
• en aucun cas ne se souciera de la capacité de la src.

Bien sûr, l'affectation des déménagements est une autre histoire. Comme elle est généralement mise en œuvre en volant le stockage source, la capacité sera également prise.

Answer 3

Cela dépend de l'allocateur de traits.

Voici un extrait de http://en.cppreference.com/w/cpp/container/vector/operator%3D:

Si std::allocator_traits::propagate_on_container_copy_assignment() est vrai, la cible de l'allocateur est remplacé par une copie de la source de l'allocateur. Si la cible et la source d'allocateurs de ne pas comparer l'égalité, la cible (*this) allocateur est utilisé pour désallouer la mémoire, puis de l'autre de l'allocateur est utilisée pour répartir les avant de copier les éléments.(depuis C++11)

Fondamentalement, la mémoire est réaffecté à la nouvelle allocation, si les allocateurs sont incompatibles (si ils ne peuvent pas libérer les uns les autres en mémoire.

Il ne devrait pas entre le vecteur des implémentations, mais entre l'allocateur implémentations (ce qui est logique).