C++
Flytta semantik

Flytta semantik

Flytta semantik är ett sätt att flytta ett objekt till ett annat i C ++. För detta tömmer vi det gamla objektet och placerar allt det hade i det nya objektet.

För detta måste vi förstå vad en värderingsreferens är. En rvalue-referens ( T&& där T är objekttypen) skiljer sig inte mycket från en normal referens ( T& , nu kallad lvalue-referenser). Men de fungerar som två olika typer, och så kan vi göra konstruktörer eller funktioner som tar den ena eller den andra typen, vilket kommer att vara nödvändigt när vi arbetar med flytta semantik.

Anledningen till att vi behöver två olika typer är att ange två olika beteenden. Lvalue referens konstruktörer är relaterade till kopiering, medan rvalue referens konstruktörer är relaterade till rörelse.

För att flytta ett objekt kommer vi att använda std::move(obj) . Denna funktion returnerar en värderingsreferens till objektet, så att vi kan stjäla data från det objektet till ett nytt. Det finns flera sätt att göra detta som diskuteras nedan.

Viktigt att notera är att användningen av std::move bara skapar en rvalue-referens. Med andra ord, uttalandet std::move(obj) ändrar inte innehållet i obj, medan auto obj2 = std::move(obj) (eventuellt) gör det.

Flytta konstruktören

Säg att vi har det här kodavsnittet.

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

För att skapa en kopieringskonstruktör, det vill säga att göra en funktion som kopierar ett objekt och skapar ett nytt, skulle vi normalt välja syntaxen som visas ovan, vi skulle ha en konstruktör för A som hänvisar till ett annat objekt av typ A, och vi skulle kopiera objektet manuellt inuti metoden.

Alternativt kunde vi ha skrivit A(const A &) = default; som automatiskt kopierar över alla medlemmar och använder sin kopieringskonstruktör.

För att skapa en rörlig konstruktör kommer vi dock att ta en rvalue-referens istället för en lvalue-referens, som här.

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

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

Observera att vi ställer in de gamla värdena till zero . Standardkonstruktören för flyttning ( Wallet(Wallet&&) = default; ) kopierar värdet på nrOfDollars , eftersom det är en POD.

Eftersom flytta semantik är utformad för att tillåta "stjäla" tillstånd från den ursprungliga instansen, är det viktigt att överväga hur den ursprungliga instansen ska se ut efter denna stjäla. I detta fall, om vi inte skulle ändra värdet till noll, skulle vi ha fördubblat mängden dollar till spel.

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

Således har vi flyttat konstruerat ett objekt från ett gammalt.

Medan ovanstående är ett enkelt exempel, visar det vad flyttkonstruktören är avsedd att göra. Det blir mer användbart i mer komplexa fall, till exempel när resurshantering är inblandad.

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

Flytta uppdraget

På samma sätt som hur vi kan tilldela ett värde till ett objekt med en lvaluerreferens och kopiera det, kan vi också flytta värdena från ett objekt till ett annat utan att konstruera ett nytt. Vi kallar detta draguppdrag. Vi flyttar värdena från ett objekt till ett annat befintligt objekt.

För detta måste vi överbelasta operator = , inte så att den tar en lvaluerreferens, som i kopieringstilldelning, men så att den tar en rvalue-referens.

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

Detta är den typiska syntaxen för att definiera flytttilldelning. Vi överbelasta operator = så att vi kan mata den en rvalue-referens och den kan tilldela den till ett annat objekt.

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

Således kan vi flytta tilldela ett objekt till ett annat.

Använda std :: flytta för att minska komplexiteten från O (n²) till O (n)

C ++ 11 introducerade kärnspråk och standardbibliotekstöd för att flytta ett objekt. Tanken är att när ett objekt o är ett tillfälligt och man vill ha en logisk kopia, så är det säkert att bara pilfer o resurser, till exempel en dynamiskt tilldelad buffert, vilket lämnar o logiskt tomt men ändå förstörbart och kopierbart.

Kärnspråkstödet är främst

• rvalue reference type builder && , t.ex. std::string&& är en rvalue-referens till en std::string , vilket indikerar att det refererade objektet är ett tillfälligt vars resurser bara kan flyttas (dvs. flyttas)

• speciellt stöd för en dragkonstruktör T( T&& ) , som är tänkt att effektivt flytta resurser från det angivna andra objektet, istället för att faktiskt kopiera dessa resurser, och

• specialstöd för en flyttilldelningsoperatör auto operator=(T&&) -> T& , som också är tänkt att flytta från källan.

Standardbibliotekstödet är huvudsakligen std::move funktionsmallen från <utility> -huvudet. Denna funktion producerar en rvalue-referens till det angivna objektet, som indikerar att det kan flyttas från, precis som om det var ett tillfälligt.

För en behållare är faktisk kopiering vanligtvis av O ( n ) komplexitet, där n är antalet objekt i behållaren, medan rörelse är O (1), konstant tid. Och för en algoritm som logiskt kopierar den behållaren n gånger, kan detta minska komplexiteten från den vanligtvis opraktiska O ( n ²) till bara linjär O ( n ).

I sin artikel “Containers That Never Change” i Dr Dobbs Journal i september 19 2013 presenterade Andrew Koenig ett intressant exempel på algoritmisk ineffektivitet när han använde en programmeringsstil där variabler är oföränderliga efter initialisering. Med denna stil uttrycks slingor generellt med rekursion. Och för vissa algoritmer som att generera en Collatz-sekvens kräver rekursionen logiskt en kopia av en behållare:

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

Produktion:

42 21 64 32 16 8 4 2

Antalet objektkopieringsoperationer på grund av kopiering av vektorerna är här ungefär O ( n² ), eftersom det är summan 1 + 2 + 3 + ... n .

I konkreta siffror, med g ++ och Visual C ++ -kompilatorer, resulterade ovannämnandet av collatz(42) i en Collatz-sekvens av 8 objekt och 36 objektskopieringsoperationer (8 * 7/2 = 28, plus några) i samtal med vektorkopier.

Alla dessa objektkopiering kan tas bort genom att helt enkelt flytta vektorer vars värden inte behövs längre. För att göra detta är det nödvändigt att ta bort const och referens för const och passera vektorerna efter värde . Funktionen återgår är redan automatiskt optimerad. För samtal där vektorer överförs och inte används längre i funktionen, använd bara std::move att flytta buffertarna istället för att faktiskt kopiera dem:

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

Här, med g ++ och Visual C ++ - kompilatorer, var antalet exemplaroperationer på grund av konstruktionskonstruktörer för vektorkopier exakt 0.

Algoritmen är nödvändigtvis fortfarande O ( n ) i längden på den producerade Collatz-sekvensen, men detta är en ganska dramatisk förbättring: O ( n ²) → O ( n ).

Med ett visst språkstöd kan man kanske använda rörelse och fortfarande uttrycka och upprätthålla en variabels immutabilitet mellan dess initialisering och slutliga drag , varefter varje användning av den variabeln bör vara ett fel. Tyvärr, från och med C ++ 14 C ++ stöder inte det. För slingfri kod kan ingen användning efter flyttning verkställas via en omdeklaration av det aktuella namnet som en ofullständig struct , som med struct result; ovan, men detta är fult och troligtvis inte förstått av andra programmerare; diagnostiken kan också vara ganska vilseledande.

Sammanfattningsvis möjliggör C ++ språk- och biblioteksstöd för flyttning drastiska förbättringar i algoritmens komplexitet, men på grund av supportens ofullständighet, till bekostnad av att man lämnar koden korrekthetsgarantier och kodklarhet som const kan ge.

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

Använda flytta semantik på containrar

Du kan flytta en behållare istället för att kopiera den:

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

Återanvänd ett rörligt objekt

Du kan använda ett flyttat objekt på nytt:

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