Un vecteur déplacé est-il toujours vide?

Je sais qu’en général la norme impose peu d’exigences aux valeurs qui ont été déplacées:

N3485 17.6.5.15 [lib.types.movedfrom] / 1:

Les objects des types définis dans la bibliothèque standard C ++ peuvent être déplacés de (12.8). Les opérations de déplacement peuvent être explicitement spécifiées ou implicitement générées. Sauf indication contraire, ces objects déplacés doivent être placés dans un état valide mais non spécifié.

Je ne trouve rien dans le vector qui l’exclue explicitement de ce paragraphe. Cependant, je ne peux pas proposer une implémentation saine qui aurait pour résultat que le vecteur ne soit pas vide.

Existe-t-il un élément standard qui implique ce que je manque ou est-ce similaire au traitement de basic_ssortingng tant que tampon contigu en C ++ 03 ?

J’arrive en retard à cette soirée et j’apporte une réponse supplémentaire car je ne crois pas qu’aucune autre réponse soit tout à fait correcte.

Question:

Un vecteur déplacé est-il toujours vide?

Réponse:

Habituellement, mais non, pas toujours.

Les détails sanglants:

vector n’a pas d’état déplacé d’origine défini comme le font certains types (par exemple, unique_ptr est spécifié égal à nullptr après avoir été déplacé de). Cependant, les exigences pour le vector sont telles qu’il n’y a pas trop d’options.

La réponse dépend du constructeur du déplacement ou de l’opérateur d’affectation du déplacement. Dans ce dernier cas, la réponse dépend également de l’allocateur du vector .


 vector::vector(vector&& v) 

Cette opération doit avoir une complexité constante. Cela signifie qu’il n’y a pas d’autre option que de voler les ressources de v pour construire *this , en laissant v dans un état vide. Ceci est vrai quels que soient l’allocateur A et le type T

Donc, pour le constructeur de déplacement, oui, le vector déplacé sera toujours vide. Ceci n’est pas directement spécifié, mais découle de l’exigence de complexité et du fait qu’il n’y a pas d’autre moyen de la mettre en œuvre.


 vector& vector::operator=(vector&& v) 

C’est considérablement plus compliqué. Il y a 3 cas majeurs:

Un:

 allocator_traits::propagate_on_container_move_assignment::value == true 

( propagate_on_container_move_assignment évalué à true_type )

Dans ce cas, l’opérateur d’atsortingbution de mouvement va détruire tous les éléments de *this , libérer de la capacité en utilisant l’allocateur à partir de *this , déplacer affecter les allocateurs, puis transférer la propriété du tampon de mémoire de v à *this . À l’exception de la destruction d’éléments dans *this , il s’agit d’une opération de complexité O (1). Et typiquement (par exemple dans la plupart des std :: algorithmes mais pas tous), les lhs d’une affectation de déplacement ont la valeur empty() == true avant l’atsortingbution de déplacement.

Remarque: En C ++ 11, propagate_on_container_move_assignment pour std::allocator false_type est false_type , mais a été remplacé par true_type pour C ++ 1y (y == 4 nous espérons).

Dans le cas Un, le vector déplacé sera toujours vide.

Deux:

 allocator_traits::propagate_on_container_move_assignment::value == false && get_allocator() == v.get_allocator() 

( propagate_on_container_move_assignment évalué à false_type , et les deux allocateurs se comparent égaux)

Dans ce cas, l’opérateur d’affectation de déplacement se comporte exactement comme le cas 1, avec les exceptions suivantes:

  1. Les allocateurs ne sont pas déplacés.
  2. La décision entre ce cas et le cas Trois se produit au moment de l’exécution, et le cas Trois nécessite plus de T , et donc le cas Deux, même si le cas Deux n’exécute pas réellement ces exigences supplémentaires sur T

Dans le cas deux, le vector déplacé sera toujours vide.

Trois:

 allocator_traits::propagate_on_container_move_assignment::value == false && get_allocator() != v.get_allocator() 

( propagate_on_container_move_assignment évalué à false_type , et les deux allocateurs ne se comparent pas égaux)

Dans ce cas, l’implémentation ne peut pas déplacer, assigner les allocateurs, ni transférer de ressources de v à *this (les ressources étant la mémoire tampon). Dans ce cas, le seul moyen d’implémenter l’opérateur d’affectation de déplacement consiste à:

 typedef move_iterator Ip; assign(Ip(v.begin()), Ip(v.end())); 

Autrement dit, déplacez chaque individu T de v vers *this . L’ assign peut réutiliser à la fois la capacity et la size dans *this si disponible. Par exemple, si *this a la même size que v l’implémentation peut se déplacer et assigner chaque T de v à *this . Cela nécessite que T soit MoveAssignable . Notez que MoveAssignable n’exige pas que T ait un opérateur d’affectation de déplacement. Un opérateur d’assignation de copie suffira également. MoveAssignable signifie simplement que T doit être assignable à partir d’une valeur T

Si la size de *this n’est pas suffisante, alors le nouveau T devra être construit dans *this . Cela nécessite que T soit MoveInsertable . Pour tout allocateur sain auquel je peux penser, MoveInsertable revient à la même chose que MoveConstructible , ce qui signifie constructible à partir d’une rvalue T (n’implique pas l’existence d’un constructeur de déplacement pour T ).

Dans le cas trois, le vector déplacé ne sera généralement pas vide. Il pourrait être plein d’éléments déplacés. Si les éléments n’ont pas de constructeur de mouvement, cela pourrait être équivalent à une affectation de copie. Cependant, rien ne l’exige. L’implémenteur est libre de faire un travail supplémentaire et d’exécuter v.clear() s’il le souhaite, en laissant v vide. Je ne suis au courant d’aucune implémentation ni d’aucune motivation pour une implémentation de le faire. Mais je ne vois rien l’interdire.

David Rodríguez rapporte que GCC 4.8.1 appelle v.clear() dans ce cas, laissant v vide. libc ++ ne le fait pas, laissant v non vide. Les deux implémentations sont conformes.

Bien que cela puisse ne pas être une implémentation saine dans le cas général, une implémentation valide du constructeur / affectation du déplacement consiste simplement à copier les données de la source, en laissant la source intacte. De plus, dans le cas d’une affectation, move peut être implémenté en tant que swap et le conteneur transféré depuis peut contenir l’ancienne valeur du conteneur transféré .

L’implémentation de déplacement en tant que copie peut en réalité se produire si vous utilisez des allocateurs polymorphes, comme nous le faisons, et que l’allocateur n’est pas réputé faire partie de la valeur de l’object (et donc, l’affectation ne modifie jamais l’allocateur réel utilisé). Dans ce contexte, une opération de déplacement peut détecter si la source et la destination utilisent le même allocateur. S’ils utilisent le même allocateur, l’opération de déplacement peut simplement déplacer les données de la source. S’ils utilisent des allocateurs différents, la destination doit copier le conteneur source.

Dans de nombreuses situations, la construction et l’affectation de déplacements peuvent être implémentées en déléguant à l’ swap – en particulier si aucun allocateur n’est impliqué. Il y a plusieurs raisons à cela:

  • swap doit être mis en œuvre de toute façon
  • efficacité des développeurs car moins de code doit être écrit
  • efficacité d’exécution car moins d’opérations sont exécutées au total

Voici un exemple d’affectation de déménagement. Dans ce cas, le vecteur de transfert ne sera pas vide si le vecteur transféré n’était pas vide.

 auto operator=(vector&& rhs) -> vector& { if (/* allocator is neither move- nor swap-aware */) { swap(rhs); } else { ... } return *this; } 

J’ai laissé des commentaires à cet effet sur d’autres réponses, mais je me suis précipité avant de donner des explications complètes. Le résultat d’un vecteur déplacé doit toujours être vide ou, dans le cas d’une affectation de déplacement, doit être vide ou être le même état de l’object précédent (c.-à-d. Un échange), car sinon les règles d’invalidation de l’iterator ne peuvent pas être respectées, à savoir qu’un déplacement ne les invalide pas. Considérer:

 std::vector move; std::vector::iterator it; { std::vector x(some_size); it = x.begin(); move = std::move(x); } std::cout << *it; 

Ici, vous pouvez voir que l'invalidation des iterators expose la mise en œuvre du déplacement. L'exigence selon laquelle ce code doit être légal, en particulier que l'iterator rest valide, empêche l'implémentation de réaliser une copie, un stockage de petits objects ou toute autre chose similaire. Si une copie était faite, it serait invalidée lors de la suppression de l'option, et il en va de même si le vector utilise un type de stockage SSO. Pour l’essentiel, la seule mise en œuvre raisonnable possible consiste à échanger des pointeurs, ou simplement à les déplacer.

Veuillez consulter les devis standard sur les exigences pour tous les conteneurs:

 X u(rv) X u = rv 

poste: u doit être égal à la valeur qu'avaient les véhicules récréatifs avant cette construction

 a = rv 

a doit être égal à la valeur qu'avait avant cette affectation

La validité de l'iterator fait partie de la valeur d'un conteneur. Bien que la norme ne l’énonce pas clairement et sans ambiguïté, nous pouvons voir, par exemple,

begin () renvoie un iterator faisant référence au premier élément du conteneur. end () retourne un iterator qui est la valeur passée-fin-pour le conteneur. Si le conteneur est vide, alors begin () == end ();

Toute implémentation déplacée des éléments de la source au lieu de permuter la mémoire serait défectueuse. Je suggère donc que toute formulation de la norme indiquant le contraire est un défaut, notamment parce que la norme n'est pas très claire sur ce point . Ces citations proviennent de N3691.