C++
Sposta semantica

Spostare la semantica

Spostare la semantica è un modo di spostare un oggetto in un altro in C ++. Per questo, svuotiamo il vecchio oggetto e posizioniamo tutto ciò che aveva nel nuovo oggetto.

Per questo, dobbiamo capire che cos'è un riferimento di valore. Un riferimento rvalue ( T&& dove T è il tipo di oggetto) non è molto diverso da un riferimento normale ( T& , ora chiamato riferimenti lvalue). Ma agiscono come 2 tipi diversi, quindi possiamo creare costruttori o funzioni che prendono un tipo o l'altro, che sarà necessario quando si ha a che fare con la semantica del movimento.

Il motivo per cui abbiamo bisogno di due tipi diversi è quello di specificare due comportamenti diversi. I costruttori di riferimento di Lvalue sono correlati alla copia, mentre i costruttori di riferimento di rvalue sono correlati allo spostamento.

Per spostare un oggetto, useremo std::move(obj) . Questa funzione restituisce un riferimento di rvalue all'oggetto, in modo che possiamo rubare i dati da quell'oggetto in uno nuovo. Ci sono diversi modi per farlo, che sono discussi di seguito.

È importante notare che l'uso di std::move crea solo un riferimento di rvalue. In altre parole, l'istruzione std::move(obj) non cambia il contenuto di obj, mentre auto obj2 = std::move(obj) (possibilmente).

Sposta costruttore

Supponiamo di avere questo frammento di codice.

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

Per creare un costruttore di copie, cioè, per creare una funzione che copi un oggetto e ne crei uno nuovo, normalmente sceglieremo la sintassi mostrata sopra, avremmo un costruttore per A che prende un riferimento a un altro oggetto di tipo A, e dovremmo copiare l'oggetto manualmente all'interno del metodo.

In alternativa, avremmo potuto scrivere A(const A &) = default; che copia automaticamente su tutti i membri, facendo uso del suo costruttore di copie.

Tuttavia, per creare un costruttore di mosse, prenderemo un riferimento di rvalue invece di un riferimento di lvalue, come qui.

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

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

Si prega di notare che abbiamo impostato i vecchi valori a zero . Il costruttore di movimento predefinito ( Wallet(Wallet&&) = default; ) copia il valore di nrOfDollars , in quanto è un POD.

Poiché la semantica del movimento è progettata per consentire lo stato di "rubare" dall'istanza originale, è importante considerare come dovrebbe apparire l'istanza originale dopo questo furto. In questo caso, se non cambiassimo il valore a zero avremmo raddoppiato la quantità di dollari in gioco.

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

Così abbiamo spostato un oggetto costruito da un vecchio.

Mentre sopra è un semplice esempio, mostra ciò che il costruttore di movimento è destinato a fare. Diventa più utile in casi più complessi, come quando è coinvolta la gestione delle risorse.

    // 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);
        }
    };

Sposta il compito

Analogamente a come possiamo assegnare un valore a un oggetto con un riferimento a lvalue, copiandolo, possiamo anche spostare i valori da un oggetto a un altro senza costruirne uno nuovo. Chiamiamo questo incarico di movimento. Spostiamo i valori da un oggetto a un altro oggetto esistente.

Per fare ciò, dovremo sovraccaricare l' operator = , non in modo che richieda un riferimento a lvalue, come nell'assegnazione delle copie, ma in modo che richieda un riferimento di rvalue.

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

Questa è la tipica sintassi per definire l'assegnazione del movimento. Noi sovraccarichiamo l' operator = modo che possiamo nutrirlo con un riferimento di rvalue e può assegnarlo a un altro oggetto.

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

Quindi, possiamo spostare assegnare un oggetto a un altro.

Utilizzo di std :: move per ridurre la complessità da O (n²) a O (n)

C ++ 11 ha introdotto il linguaggio di base e il supporto della libreria standard per lo spostamento di un oggetto. L'idea è che quando un oggetto o è un temporanea e vuole una copia logica, allora il suo sicuro per soli risorse s' antifurto o, ad esempio un buffer allocato in modo dinamico, lasciando o logicamente vuota ma ancora distruttibili e copiabile.

Il supporto linguistico di base è principalmente

• il costruttore del valore di riferimento rval && , ad esempio, std::string&& è un riferimento di rvalue a std::string , che indica che quello riferito all'oggetto è un temporaneo le cui risorse possono essere semplicemente rubate (ovvero spostate)

• supporto speciale per un costruttore di movimenti T( T&& ) , che dovrebbe spostare efficientemente le risorse dall'oggetto specificato, invece di copiarle effettivamente, e

• supporto speciale per un operatore di assegnazione del movimento operatore auto operator=(T&&) -> T& , che dovrebbe anche spostarsi dalla sorgente.

Il supporto della libreria standard è principalmente il modello di funzione std::move dall'intestazione <utility> . Questa funzione produce un riferimento di rvalue all'oggetto specificato, indicando che può essere spostato da, proprio come se fosse un temporaneo.

Per un contenitore la copia effettiva è tipicamente di complessità O ( n ), dove n è il numero di elementi nel contenitore, mentre lo spostamento è O (1), tempo costante. E per un algoritmo che copia logicamente quel contenitore n volte, ciò può ridurre la complessità dal solito O poco pratico ( n ²) al solo O ( n ) lineare.

Nel suo articolo "Containers That Never Change" del Dr. Dobbs Journal del 19 settembre 2013 , Andrew Koenig ha presentato un interessante esempio di inefficienza algoritmica quando utilizza uno stile di programmazione in cui le variabili sono immutabili dopo l'inizializzazione. Con questo stile i loop sono generalmente espressi usando la ricorsione. E per alcuni algoritmi come la generazione di una sequenza di Collatz, la ricorsione richiede la copia logica di un contenitore:

// 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';
}

Produzione:

42 21 64 32 16 8 4 2

Il numero di operazioni di copia degli elementi a causa della copia dei vettori è qui approssimativamente O ( n² ), poiché è la somma 1 + 2 + 3 + ... n .

In numeri concreti, con i compilatori g ++ e Visual C ++ la precedente invocazione di collatz(42) prodotto una sequenza Collatz di 8 voci e 36 operazioni di copia degli elementi (8 * collatz(42) = 28, più alcune) nelle chiamate del costruttore di copie vettoriali.

Tutte queste operazioni di copia degli elementi possono essere rimosse semplicemente spostando i vettori i cui valori non sono più necessari. Per fare ciò è necessario rimuovere const e reference per gli argomenti del tipo vettoriale, passando i vettori per valore . I ritorni di funzione sono già ottimizzati automaticamente. Per le chiamate in cui i vettori vengono passati e non utilizzati di nuovo nella funzione, basta applicare std::move per spostare quei buffer anziché copiarli effettivamente:

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>() );
}

Qui, con i compilatori g ++ e Visual C ++, il numero di operazioni di copia degli elementi dovute alle invocazioni del costruttore della copia vettoriale era esattamente 0.

L'algoritmo è necessariamente ancora O ( n ) nella lunghezza della sequenza di Collatz prodotta, ma questo è un miglioramento piuttosto drammatico: O ( n ²) → O ( n ).

Con un supporto linguistico si potrebbe forse usare lo spostamento e ancora esprimere e applicare l'immutabilità di una variabile tra la sua inizializzazione e la mossa finale , dopo di che qualsiasi utilizzo di tale variabile dovrebbe essere un errore. Purtroppo, come in C ++ 14 C ++ non supporta questo. Per il codice senza loop, il non utilizzo dopo lo spostamento può essere applicato tramite una nuova dichiarazione del nome pertinente come una struct incompleta, come nel caso di struct result; sopra, ma questo è brutto e difficilmente comprensibile da altri programmatori; anche la diagnostica può essere abbastanza fuorviante.

Riassumendo, il linguaggio C ++ e il supporto della libreria per lo spostamento consentono drastici miglioramenti nella complessità dell'algoritmo, ma a causa dell'incompletezza del supporto, al costo di abbandonare le garanzie di correttezza del codice e la chiarezza del codice che const può fornire.

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_ ) )
    {}
};

Utilizzare la semantica di movimento sui contenitori

Puoi spostare un contenitore invece di copiarlo:

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);
}

Riutilizzare un oggetto spostato

Puoi riutilizzare un oggetto spostato:

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));
}