C++
Semantik verschieben

Semantik verschieben

Verschiebesemantik ist eine Möglichkeit, ein Objekt in C ++ zu einem anderen zu verschieben. Dazu leeren wir das alte Objekt und legen alles in das neue Objekt.

Dazu müssen wir verstehen, was ein Referenzwert ist. Eine rvalue-Referenz ( T&& wobei T der Objekttyp ist) unterscheidet sich nicht wesentlich von einer normalen Referenz ( T& , jetzt lvalue-referenzen genannt). Sie fungieren jedoch als zwei verschiedene Typen, und so können Konstruktoren oder Funktionen erstellt werden, die den einen oder den anderen Typ annehmen, was bei der Umzugssemantik erforderlich ist.

Der Grund, warum wir zwei unterschiedliche Typen benötigen, besteht darin, zwei unterschiedliche Verhaltensweisen anzugeben. Lvalue-Referenzkonstruktoren beziehen sich auf das Kopieren, während sich rvalue-Referenzkonstruktoren auf das Verschieben beziehen.

Um ein Objekt zu verschieben, verwenden wir std::move(obj) . Diese Funktion gibt eine rvalue-Referenz auf das Objekt zurück, sodass wir die Daten von diesem Objekt in ein neues stehlen können. Dazu gibt es mehrere Möglichkeiten, die im Folgenden beschrieben werden.

Es ist wichtig zu beachten, dass durch die Verwendung von std::move nur eine rvalue-Referenz erstellt wird. Mit anderen Worten ändert die Anweisung std::move(obj) den Inhalt von obj nicht, während auto obj2 = std::move(obj) (möglicherweise) dies tut.

Konstruktor verschieben

Angenommen, wir haben diesen Code-Ausschnitt.

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

Um einen Kopierkonstruktor zu erstellen, dh um eine Funktion zu erstellen, die ein Objekt kopiert und ein neues erstellt, wählen wir normalerweise die oben gezeigte Syntax. Wir haben einen Konstruktor für A, der einen Verweis auf ein anderes Objekt vom Typ A verwendet und wir würden das Objekt manuell in die Methode kopieren.

Alternativ hätten wir A(const A &) = default; schreiben können A(const A &) = default; die automatisch über alle Elemente kopiert wird, wobei der Copy-Konstruktor verwendet wird.

Um einen Bewegungskonstruktor zu erstellen, verwenden wir jedoch anstelle des Werts eine Referenz, wie hier.

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

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

Bitte beachten Sie, dass wir die alten Werte auf zero . Der Standardkonstruktor für Verschiebungen ( Wallet(Wallet&&) = default; ) kopiert den Wert von nrOfDollars , da es sich um einen POD handelt.

Da die Umzugs-Semantik so gestaltet ist, dass ein Zustand "Diebstahl" von der ursprünglichen Instanz ermöglicht wird, muss berücksichtigt werden, wie die ursprüngliche Instanz nach diesem Diebstahl aussehen sollte. In diesem Fall hätten wir, wenn wir den Wert nicht auf null ändern würden, den Betrag des Dollars verdoppelt.

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

So haben wir aus einem alten Objekt ein Objekt konstruiert.

Während das obige Beispiel ein einfaches Beispiel ist, zeigt es, was der Bewegungskonstruktor tun soll. In komplexeren Fällen, beispielsweise beim Ressourcenmanagement, ist dies sinnvoller.

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

Zuordnung verschieben

Ähnlich wie wir einem Objekt einen Wert mit einer lvalue-Referenz zuweisen und kopieren können, können wir die Werte auch von einem Objekt zu einem anderen verschieben, ohne einen neuen zu erstellen. Wir nennen diese Umzugszuordnung. Wir verschieben die Werte von einem Objekt zu einem anderen vorhandenen Objekt.

Dazu müssen wir operator = überladen, nicht so, dass eine lvalue-Referenz wie bei der Zuweisung von Kopien erforderlich ist, sondern eine rvalue-Referenz.

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

Dies ist die typische Syntax zum Definieren der Bewegungszuweisung. Wir überladen operator = damit wir ihm eine rvalue-Referenz geben können, die er einem anderen Objekt zuweisen kann.

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

Daher können wir verschieben, ein Objekt einem anderen Objekt zuweisen.

Verwenden von std :: move, um die Komplexität von O (n²) nach O (n) zu reduzieren

Mit C ++ 11 wurde die Unterstützung für Kernsprachen und Standardbibliotheken zum Verschieben eines Objekts eingeführt. Die Idee ist , dass , wenn ein Objekt o eine temporäres ist und man eine logische Kopie will, dann sicher seiner nur pilfer o ‚s Ressourcen, wie zum Beispiel eines dynamisch zugewiesenen Puffer, so dass o logisch leer , aber immer noch zerstörbar und kopierbar.

Die Hauptsprachenunterstützung ist hauptsächlich

• Der Builder für den rvalue-Referenztyp && , z. B. std::string&& ist ein rvalue-Verweis auf einen std::string , der darauf hinweist, dass das referenzierte Objekt ein temporäres Objekt ist, dessen Ressourcen nur gestohlen (dh verschoben) werden können.

• spezielle Unterstützung für einen Bewegungskonstruktor T( T&& ) , der Ressourcen effizient aus dem angegebenen anderen Objekt verschieben soll, anstatt diese Ressourcen tatsächlich zu kopieren, und

• spezielle Unterstützung für einen Verschiebungszuweisungsoperator auto operator=(T&&) -> T& , der auch von der Quelle auto operator=(T&&) -> T& soll.

Die Standard-Bibliotheksunterstützung ist hauptsächlich die Funktionsvorlage std::move aus dem Header <utility> . Diese Funktion erzeugt eine rvalue-Referenz auf das angegebene Objekt, um anzuzeigen, dass es aus diesem Objekt verschoben werden kann, als wäre es ein temporärer.

Für einen Container ist das tatsächliche Kopieren typischerweise eine O ( n ) -Komplexität, wobei n die Anzahl der Elemente im Container ist, während das Verschieben eine konstante Zeit von O (1) ist. Und für einen Algorithmus, der logisch Kopien , die Container n - mal, dies die Komplexität des in der Regel unpraktisch O reduzieren können (n ²) nur lineare O (n).

In seinem Artikel „Container, die sich nie ändern“ im Dr. Dobbs Journal vom 19. September 2013 präsentierte Andrew Koenig ein interessantes Beispiel für algorithmische Ineffizienz, wenn ein Programmierstil verwendet wird, bei dem Variablen nach der Initialisierung unveränderlich sind. Bei diesem Stil werden Schleifen im Allgemeinen mit Rekursion ausgedrückt. Bei einigen Algorithmen, z. B. beim Generieren einer Collatz-Sequenz, erfordert die Rekursion das logische Kopieren eines Containers:

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

Ausgabe:

42 21 64 32 16 8 4 2

Die Anzahl der Elementkopiervorgänge aufgrund des Kopierens der Vektoren beträgt hier ungefähr 0 ( n² ), da es sich um die Summe 1 + 2 + 3 + ... n handelt .

In konkreten Zahlen führte bei g ++ - und Visual C ++ - Compilern der obige Aufruf von collatz(42) zu einer Collatz-Sequenz von 8 Elementen und 36 collatz(42) 8 * collatz(42) = 28, plus einige) in Vektorkopiekonstruktoraufrufen.

Alle diese Elementkopiervorgänge können entfernt werden, indem Sie einfach Vektoren verschieben, deren Werte nicht mehr benötigt werden. Dazu müssen Sie const und reference für die Vektortypargumente entfernen und die Vektoren nach Wert übergeben . Die Funktionsrückgaben werden bereits automatisch optimiert. Für die Aufrufe, bei denen Vektoren übergeben und nicht weiter verwendet werden, wenden Sie einfach std::move an, um diese Puffer zu verschieben , anstatt sie tatsächlich zu kopieren:

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

Bei g ++ - und Visual C ++ - Compilern betrug die Anzahl der Elementkopiervorgänge aufgrund von Vektorkopiekonstruktoraufrufen genau 0.

Der Algorithmus ist notwendigerweise immer noch O (n) in der Länge der Collatz - Sequenz erzeugt, aber das ist eine ziemlich dramatische Verbesserung: O (n ²) → O (n).

Mit etwas Sprachunterstützung könnte man vielleicht Moving verwenden und dennoch die Unveränderlichkeit einer Variablen zwischen ihrer Initialisierung und ihrer endgültigen Verschiebung ausdrücken und durchsetzen, wonach jede Verwendung dieser Variablen ein Fehler sein sollte. Leider unterstützt C ++ ab C ++ 14 das nicht. Bei schleifenfreiem Code kann die Nichtbenutzung nach dem Verschieben durch eine erneute Deklaration des betreffenden Namens als unvollständige struct erzwungen werden, wie bei struct result; oben, aber das ist hässlich und wird von anderen Programmierern wahrscheinlich nicht verstanden; Auch die Diagnose kann irreführend sein.

Zusammenfassend lässt sich sagen, dass die Unterstützung für das Verschieben von C ++ - Sprache und -Bibliothek drastische Verbesserungen der Algorithmuskomplexität ermöglicht, jedoch aufgrund der Unvollständigkeit der Unterstützung auf Kosten der Verzicht auf die Garantien für die Korrektheit des Codes und die Klarheit, die const sich bringt.

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

Verwenden der Verschiebesemantik für Container

Sie können einen Container verschieben, anstatt ihn zu kopieren:

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

Verwenden Sie ein verschobenes Objekt erneut

Sie können ein verschobenes Objekt wiederverwenden:

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