Est-il sûr de repousser un élément du même vecteur?

vector<int> v;
v.push_back(1);
v.push_back(v[0]);

Si le second push_back provoque une réallocation, la référence au premier entier du vecteur ne sera plus valide. Donc ce n'est pas sûr?

vector<int> v;
v.push_back(1);
v.reserve(v.size() + 1);
v.push_back(v[0]);

Cela le rend sûr?

Il semble que http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#526 a abordé ce problème (ou quelque chose de très similaire) comme un défaut potentiel de la norme:

1) Les paramètres pris par référence const peuvent être modifiés lors de l'exécution de la fonction

Exemples:

Étant donné std :: vector v:

v.insert (v.begin (), v [2]);

v [2] peut être modifié en déplaçant les éléments du vecteur

La résolution proposée était qu'il ne s'agissait pas d'un défaut:

vector :: insert (iter, value) est requis pour fonctionner car le standard ne donne pas la permission pour qu'il ne fonctionne pas.

Oui, c'est sûr, et les implémentations de bibliothèques standard sautent à travers les obstacles pour y parvenir.

Je pense que les développeurs font remonter cette exigence à 23.2 / 11 d'une manière ou d'une autre, mais je ne peux pas comprendre comment, et je ne peux pas trouver quelque chose de plus concret non plus. Le mieux que je puisse trouver est cet article:

http://www.drdobbs.com/cpp/copying-container-elements-from-the-c-li/240155771

L'inspection des implémentations de libc ++ et libstdc ++ montre qu'elles sont également sûres.

La norme garantit même votre premier exemple d'être en sécurité. Citant C ++ 11

[sequence.reqmts]

3 Dans les tableaux 100 et 101 ... Xdésigne une classe de conteneur de séquence, adésigne une valeur d' Xéléments contenant de type T, ... tdésigne une lvalue ou une const rvalue deX::value_type

16 Tableau 101 ...

Expression a.push_back(t) Type de retour void Sémantique opérationnelle Ajoute une copie de t. Requiert: T doit être CopyInsertabledans X. Conteneur basic_string , deque, list,vector

Ainsi, même si ce n'est pas vraiment trivial, l'implémentation doit garantir qu'elle n'invalidera pas la référence lors de l'exécution du push_back.

Il n'est pas évident que le premier exemple soit sûr, car l'implémentation la plus simple de push_backserait d'abord de réallouer le vecteur, si nécessaire, puis de copier la référence.

Mais au moins, cela semble être sûr avec Visual Studio 2010. Son implémentation de push_backfait une gestion spéciale du cas lorsque vous repoussez un élément dans le vecteur. Le code est structuré comme suit:

void push_back(const _Ty& _Val)
    {   // insert element at end
    if (_Inside(_STD addressof(_Val)))
        {   // push back an element
                    ...
        }
    else
        {   // push back a non-element
                    ...
        }
    }

Ce n'est pas une garantie de la norme, mais comme un autre point de données, il v.push_back(v[0])est sans danger pour la libc ++ de LLVM .

std::vector::push_backAppels de libc ++__push_back_slow_path quand il a besoin de réallouer de la mémoire:

void __push_back_slow_path(_Up& __x) {
  allocator_type& __a = this->__alloc();
  __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), 
                                                  size(), 
                                                  __a);
  // Note that we construct a copy of __x before deallocating
  // the existing storage or moving existing elements.
  __alloc_traits::construct(__a, 
                            _VSTD::__to_raw_pointer(__v.__end_), 
                            _VSTD::forward<_Up>(__x));
  __v.__end_++;
  // Moving existing elements happens here:
  __swap_out_circular_buffer(__v);
  // When __v goes out of scope, __x will be invalid.
}

La première version n'est certainement PAS sûre:

Les opérations sur les itérateurs obtenues en appelant un conteneur de bibliothèque standard ou une fonction membre de chaîne peuvent accéder au conteneur sous-jacent, mais ne doivent pas le modifier. [Remarque: en particulier, les opérations de conteneur qui invalident les itérateurs sont en conflit avec les opérations sur les itérateurs associés à ce conteneur. - note de fin]

de la section 17.6.5.9

Notez qu'il s'agit de la section sur les courses de données, à laquelle les gens pensent normalement en conjonction avec le threading ... mais la définition réelle implique des relations «se produit avant», et je ne vois aucune relation d'ordre entre les multiples effets secondaires de push_backin play ici, à savoir que l'invalidation de référence ne semble pas être définie comme ordonnée par rapport à la construction par copie du nouvel élément de queue.

C'est complètement sûr.

Dans votre deuxième exemple, vous avez

v.reserve(v.size() + 1);

ce qui n'est pas nécessaire car si le vecteur sort de sa taille, cela impliquera l'extension reserve.

Vector est responsable de ce truc, pas vous.

Les deux sont sûrs car push_back copiera la valeur, pas la référence. Si vous stockez des pointeurs, c'est toujours sûr en ce qui concerne le vecteur, mais sachez simplement que vous aurez deux éléments de votre vecteur pointant vers les mêmes données.

Section 23.2.1 Exigences générales relatives aux conteneurs

16

• a.push_back (t) Ajoute une copie de t. Requiert: T doit être CopyInsertable into X.
• a.push_back (rv) Ajoute une copie de rv. Requiert: T doit être MoveInsertable dans X.

Les implémentations de push_back doivent donc garantir qu'une copie de v[0] est insérée. Par contre-exemple, en supposant une implémentation qui se réallouerait avant la copie, elle n'ajouterait pas assurément une copie de v[0]et, en tant que telle, violerait les spécifications.

À partir du 23.3.6.5/1: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid.

Comme nous l'insérons à la fin, aucune référence ne sera invalidée si le vecteur n'est pas redimensionné. Donc, si le vecteur est capacity() > size()alors il est garanti de fonctionner, sinon il est garanti qu'il s'agit d'un comportement indéfini.