C++
Déplacer la sémantique

Déplacer la sémantique

La sémantique de déplacement est un moyen de déplacer un objet vers un autre en C ++. Pour cela, nous viderons l'ancien objet et placerons tout ce qu'il contenait dans le nouvel objet.

Pour cela, nous devons comprendre ce qu'est une référence de valeur. Une référence de valeur ( T&& où T est le type d'objet) n'est pas très différente d'une référence normale ( T& , maintenant appelée références lvalue). Mais ils agissent comme 2 types différents, et nous pouvons donc créer des constructeurs ou des fonctions qui prennent un type ou un autre, ce qui sera nécessaire pour traiter la sémantique du mouvement.

La raison pour laquelle nous avons besoin de deux types différents est de spécifier deux comportements différents. Les constructeurs de référence Lvalue sont liés à la copie, tandis que les constructeurs de référence Rvalue sont liés au déplacement.

Pour déplacer un objet, nous utiliserons std::move(obj) . Cette fonction renvoie une référence de valeur à l'objet, afin que nous puissions voler les données de cet objet dans une nouvelle. Il y a plusieurs façons de faire cela, qui sont discutées ci-dessous.

Il est important de noter que l'utilisation de std::move crée uniquement une référence de valeur. En d'autres termes, l'instruction std::move(obj) ne modifie pas le contenu de obj, alors que auto obj2 = std::move(obj) (éventuellement) le fait.

Déplacer constructeur

Disons que nous avons cet extrait de code.

class A {
public:
    int a;
    int b;
       
    A(const A &other) {
        this->a = other.a;
        this->b = other.b;
    }
};

Pour créer un constructeur de copie, c'est-à-dire créer une fonction qui copie un objet et en créer un nouveau, nous choisirions normalement la syntaxe ci-dessus, nous aurions un constructeur pour A qui prend une référence à un autre objet de type A, et nous copierions l'objet manuellement dans la méthode.

Alternativement, nous aurions pu écrire A(const A &) = default; qui copie automatiquement tous les membres, en utilisant son constructeur de copie.

Pour créer un constructeur de déplacement, nous allons prendre une référence de valeur plutôt qu'une référence de lvalue, comme ici.

class Wallet {
public:
    int nrOfDollars;
    
    Wallet() = default; //default ctor

    Wallet(Wallet &&other) {
        this->nrOfDollars = other.nrOfDollars;
        other.nrOfDollars = 0;
    }
};

Veuillez noter que nous avons mis les anciennes valeurs à zero . Le constructeur de déplacement par défaut ( Wallet(Wallet&&) = default; ) copie la valeur de nrOfDollars , car il s'agit d'un POD.

Comme la sémantique de mouvement est conçue pour permettre un état de «vol» à partir de l'instance d'origine, il est important de considérer comment l'instance d'origine devrait ressembler après ce vol. Dans ce cas, si nous ne modifions pas la valeur à zéro, nous aurions doublé le montant en dollars.

Wallet a;
a.nrOfDollars = 1;
Wallet b (std::move(a)); //calling B(B&& other);
std::cout << a.nrOfDollars << std::endl; //0
std::cout << b.nrOfDollars << std::endl; //1

Nous avons donc construit un objet à partir d'un ancien.

Bien que ce qui précède soit un exemple simple, il montre ce que le constructeur de déplacement est censé faire. Cela devient plus utile dans les cas plus complexes, par exemple lorsque la gestion des ressources est impliquée.

    // Manages operations involving a specified type.
    // Owns a helper on the heap, and one in its memory (presumably on the stack).
    // Both helpers are DefaultConstructible, CopyConstructible, and MoveConstructible.
    template<typename T,
             template<typename> typename HeapHelper,
             template<typename> typename StackHelper>
    class OperationsManager {
        using MyType = OperationsManager<T, HeapHelper, StackHelper>;

        HeapHelper<T>* h_helper;
        StackHelper<T> s_helper;
        // ...

      public:
        // Default constructor & Rule of Five.
        OperationsManager() : h_helper(new HeapHelper<T>) {}
        OperationsManager(const MyType& other)
          : h_helper(new HeapHelper<T>(*other.h_helper)), s_helper(other.s_helper) {}
        MyType& operator=(MyType copy) {
            swap(*this, copy);
            return *this;
        }
        ~OperationsManager() {
            if (h_helper) { delete h_helper; }
        }

        // Move constructor (without swap()).
        // Takes other's HeapHelper<T>*.
        // Takes other's StackHelper<T>, by forcing the use of StackHelper<T>'s move constructor.
        // Replaces other's HeapHelper<T>* with nullptr, to keep other from deleting our shiny
        //  new helper when it's destroyed.
        OperationsManager(MyType&& other) noexcept
          : h_helper(other.h_helper),
            s_helper(std::move(other.s_helper)) {
            other.h_helper = nullptr;
        }

        // Move constructor (with swap()).
        // Places our members in the condition we want other's to be in, then switches members
        //  with other.
        // OperationsManager(MyType&& other) noexcept : h_helper(nullptr) {
        //     swap(*this, other);
        // }

        // Copy/move helper.
        friend void swap(MyType& left, MyType& right) noexcept {
            std::swap(left.h_helper, right.h_helper);
            std::swap(left.s_helper, right.s_helper);
        }
    };

Déplacer la cession

De la même façon que nous pouvons assigner une valeur à un objet avec une référence lvalue, en la copiant, nous pouvons également déplacer les valeurs d'un objet vers un autre sans en construire un nouveau. Nous appelons cette affectation de déplacement. Nous déplaçons les valeurs d'un objet vers un autre objet existant.

Pour cela, nous devrons surcharger operator = , pas pour qu'il prenne une référence lvalue, comme dans une affectation de copie, mais pour qu'il prenne une référence de valeur.

class A {
    int a;
    A& operator= (A&& other) {
        this->a = other.a;
        other.a = 0;
        return *this;
    }
};

C'est la syntaxe typique pour définir l'affectation de déplacement. Nous surchargons l' operator = afin que nous puissions lui fournir une référence de valeur et qu'il puisse l'assigner à un autre objet.

A a;
a.a = 1;
A b;
b = std::move(a); //calling A& operator= (A&& other)
std::cout << a.a << std::endl; //0
std::cout << b.a << std::endl; //1

Ainsi, nous pouvons déplacer affecter un objet à un autre.

Utiliser std :: move pour réduire la complexité de O (n²) à O (n)

C ++ 11 a introduit le support du langage de base et de la bibliothèque standard pour déplacer un objet. L'idée est que lorsqu'un objet o est temporaire et veut une copie logique, sa sécurité à seulement chaparder o ressources de, comme un tampon alloué dynamiquement, laissant o logiquement vide mais toujours destructible et copiable.

Le support linguistique de base est principalement

• le type de référence rvalue builder && , par exemple std::string&& est une référence rvalue à un std::string , indiquant que l'objet référencé est un temporaire dont les ressources peuvent simplement être volées (c'est-à-dire déplacées)

• support spécial pour un constructeur de déplacement T( T&& ) , qui est supposé déplacer efficacement les ressources de l'objet spécifié, au lieu de copier réellement ces ressources, et

• support spécial pour un opérateur d' auto operator=(T&&) -> T& attribution de mouvement auto operator=(T&&) -> T& , qui est également supposé se déplacer de la source.

Le support standard de la bibliothèque est principalement le modèle de fonction std::move de l’en-tête <utility> . Cette fonction produit une référence de valeur à l'objet spécifié, indiquant qu'elle peut être déplacée, comme s'il s'agissait d'un objet temporaire.

Pour un conteneur, la copie réelle est généralement de complexité O ( n ), où n est le nombre d'éléments dans le conteneur, tandis que le déplacement est O (1), temps constant. Et pour un algorithme qui logiquement copies contenant n fois, cela peut réduire la complexité de l'O habituellement peu pratique (n ²) à seulement O linéaire (n).

Dans son article «Containers That Never Change» du Dr. Dobbs Journal du 19 septembre 2013 , Andrew Koenig a présenté un exemple intéressant d'inefficacité algorithmique lors de l'utilisation d'un style de programmation où les variables sont immuables après l'initialisation. Avec ce style, les boucles sont généralement exprimées en utilisant la récursivité. Et pour certains algorithmes tels que la génération d'une séquence Collatz, la récursivité nécessite de copier logiquement un conteneur:

// Based on an example by Andrew Koenig in his Dr. Dobbs Journal article
// “Containers That Never Change” September 19, 2013, available at
// <url: http://www.drdobbs.com/cpp/containters-that-never-change/240161543>

// Includes here, e.g. <vector>

namespace my {
    template< class Item >
    using Vector_ = /* E.g. std::vector<Item> */;

    auto concat( Vector_<int> const& v, int const x )
        -> Vector_<int>
    {
        auto result{ v };
        result.push_back( x );
        return result;
    }

    auto collatz_aux( int const n, Vector_<int> const& result )
        -> Vector_<int>
    {
        if( n == 1 )
        {
            return result;
        }
        auto const new_result = concat( result, n );
        if( n % 2 == 0 )
        {
            return collatz_aux( n/2, new_result );
        }
        else
        {
            return collatz_aux( 3*n + 1, new_result );
        }
    }

    auto collatz( int const n )
        -> Vector_<int>
    {
        assert( n != 0 );
        return collatz_aux( n, Vector_<int>() );
    }
}  // namespace my

#include <iostream>
using namespace std;
auto main() -> int
{
    for( int const x : my::collatz( 42 ) )
    {
        cout << x << ' ';
    }
    cout << '\n';
}

Sortie:

42 21 64 32 16 8 4 2

Le nombre d'opérations de copie d'éléments dues à la copie des vecteurs est ici approximativement O ( n² ), puisque c'est la somme 1 + 2 + 3 + ... n .

En chiffres concrets, avec les compilateurs g ++ et Visual C ++, l'invocation de collatz(42) ci-dessus a entraîné une séquence Collatz de 8 éléments et 36 opérations de copie d'éléments (8 * collatz(42) = 28, plus quelques).

Toutes ces opérations de copie d'éléments peuvent être supprimées en déplaçant simplement des vecteurs dont les valeurs ne sont plus nécessaires. Pour ce faire, il est nécessaire de supprimer const et reference pour les arguments de type vectoriel, en passant les vecteurs par valeur . Les retours de fonctions sont déjà automatiquement optimisés. Pour les appels où les vecteurs sont passés et ne sont plus utilisés dans la fonction, appliquez simplement std::move pour déplacer ces tampons plutôt que de les copier:

using std::move;

auto concat( Vector_<int> v, int const x )
    -> Vector_<int>
{
    v.push_back( x );
    // warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
    // See https://stackoverflow.com/documentation/c%2b%2b/2489/copy-elision
    // return move( v );
    return v;
}

auto collatz_aux( int const n, Vector_<int> result )
    -> Vector_<int>
{
    if( n == 1 )
    {
        return result;
    }
    auto new_result = concat( move( result ), n );
    struct result;      // Make absolutely sure no use of `result` after this.
    if( n % 2 == 0 )
    {
        return collatz_aux( n/2, move( new_result ) );
    }
    else
    {
        return collatz_aux( 3*n + 1, move( new_result ) );
    }
}

auto collatz( int const n )
    -> Vector_<int>
{
    assert( n != 0 );
    return collatz_aux( n, Vector_<int>() );
}

Ici, avec les compilateurs g ++ et Visual C ++, le nombre d'opérations de copie d'éléments dues aux invocations du constructeur de la copie vectorielle était exactement 0.

L'algorithme est nécessairement encore O (n) de la longueur de la séquence Collatz produit, mais cela est une amélioration tout à fait spectaculaire: O (n ²) → O (n).

Avec certains langages, on peut peut-être utiliser le mouvement et exprimer et imposer l'immuabilité d'une variable entre son initialisation et son déplacement final , après quoi toute utilisation de cette variable devrait être une erreur. Hélas, à partir de C ++ 14 C ++ ne le supporte pas. Pour le code sans boucle, la non utilisation après le déplacement peut être imposée via une nouvelle déclaration du nom correspondant en tant que struct incomplète, comme avec le struct result; ci-dessus, mais c'est moche et peu susceptible d'être compris par d'autres programmeurs; les diagnostics peuvent aussi être trompeurs.

En résumé, le support du langage C ++ et de la bibliothèque pour le déplacement permet des améliorations drastiques de la complexité des algorithmes, mais en raison de l'incomplétude du support, au détriment des garanties d'exactitude du code et de clarté que const peut fournir.

template< class Item >
class Copy_tracking_vector
{
private:
    static auto n_copy_ops()
        -> int&
    {
        static int value;
        return value;
    }
    
    vector<Item>    items_;
    
public:
    static auto n() -> int { return n_copy_ops(); }

    void push_back( Item const& o ) { items_.push_back( o ); }
    auto begin() const { return items_.begin(); }
    auto end() const { return items_.end(); }

    Copy_tracking_vector(){}
    
    Copy_tracking_vector( Copy_tracking_vector const& other )
        : items_( other.items_ )
    { n_copy_ops() += items_.size(); }

    Copy_tracking_vector( Copy_tracking_vector&& other )
        : items_( move( other.items_ ) )
    {}
};

Utilisation de la sémantique de déplacement sur les conteneurs

Vous pouvez déplacer un conteneur au lieu de le copier:

void print(const std::vector<int>& vec) {
    for (auto&& val : vec) {
        std::cout << val << ", ";
    }
    std::cout << std::endl;
}

int main() {
    // initialize vec1 with 1, 2, 3, 4 and vec2 as an empty vector
    std::vector<int> vec1{1, 2, 3, 4};
    std::vector<int> vec2;

    // The following line will print 1, 2, 3, 4
    print(vec1);

    // The following line will print a new line
    print(vec2);

    // The vector vec2 is assigned with move assingment.
    // This will "steal" the value of vec1 without copying it.
    vec2 = std::move(vec1);

    // Here the vec1 object is in an indeterminate state, but still valid.
    // The object vec1 is not destroyed,
    // but there's is no guarantees about what it contains.

    // The following line will print 1, 2, 3, 4
    print(vec2);
}

Réutiliser un objet déplacé

Vous pouvez réutiliser un objet déplacé:

void consumingFunction(std::vector<int> vec) {
    // Some operations
}

int main() {
    // initialize vec with 1, 2, 3, 4
    std::vector<int> vec{1, 2, 3, 4};

    // Send the vector by move
    consumingFunction(std::move(vec));

    // Here the vec object is in an indeterminate state.
    // Since the object is not destroyed, we can assign it a new content.
    // We will, in this case, assign an empty value to the vector,
    // making it effectively empty
    vec = {};

    // Since the vector as gained a determinate value, we can use it normally.
    vec.push_back(42);

    // Send the vector by move again.
    consumingFunction(std::move(vec));
}