Est-il possible de repousser un élément du même vecteur ?

Question

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. Ce n'est donc 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 ?

Answer 1

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

1) Les paramètres pris par la référence const peuvent être modifiés pendant 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 que ce n'était pas un défaut :

vector::insert(iter, value) est obligé de fonctionner parce que la norme ne donne pas la permission de ne pas fonctionner.

Answer 2

Oui, c'est sûr, et les implémentations de la bibliothèque standard font des pieds et des mains pour qu'il en soit ainsi.

Je crois que les responsables de la mise en œuvre font remonter cette exigence à la norme 23.2/11 d'une manière ou d'une autre, mais je n'arrive pas à savoir comment, et je n'arrive pas non plus à trouver quelque chose de plus concret. 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.

Answer 3

La norme garantit que même votre premier exemple est sûr. Citation de C++11

[séquence.reqmts]

3 Dans les tableaux 100 et 101 ... X désigne une classe de conteneur de séquence, a désigne une valeur de X contenant des éléments de type T , ... t désigne une valeur lval ou une valeur r const de X::value_type

16 Tableau 101 ...

Expression a.push_back(t) Type de retour void Sémantique opérationnelle Ajoute une copie de t. Exige : T est CopyInsertable en X . Container basic_string , deque , list , vector

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

Answer 4

Il n'est pas évident que le premier exemple soit sûr, car la mise en œuvre la plus simple de l'option push_back serait 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_back fait une gestion spéciale du cas où 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
                    ...
        }
    }

Answer 5

Il ne s'agit pas d'une garantie de la norme, mais d'un autre point de données, v.push_back(v[0]) est sans danger pour libc++ de LLVM .

de libc++ std::vector::push_back appelle __push_back_slow_path lorsqu'il doit 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.
}