Vermeidung unnötiger Kopien: LinkedList::append<T>(T)

Dante3085

Ich hoffe ihr habt alle heute viel Spaß beim programmieren

Mich beschäftigt folgendes Problem:

Ich bin gerade dabei aus Testzwecken eine LinkedList Klasse in C++ zu schreiben und möchte beim Aufruf von Funktionen, die neue Elemente in die Liste stecken vermeiden, dass unnötige Kopien entstehen. Mir sind 2 Konzepte bekannt, die mir bei dieser Sache vielleicht helfen könnten. Move-Semantics und Perfect-Forwarding. Allerdings ist mein Verständnis für diese 2 Konzepte etwas wackelig, weshalb ich eure Hilfe benötige.

Ich habe eine rudimentäre MyString Klasse geschrieben, mit der ich feststelle, wann ein Objekt konstruiert, kopiert, gemoved oder zerstört wurde. Die konkrete Implementierung ist denke ich unwichtig, weshalb ich hier nur zeige, dass für jeden Fall eine Ausgabe gemacht wird.

MyString(char const *string)
{
     std::cout << "Constructed!" << std::endl;
     // ...
}

MyString(MyString const &other)
{
     std::cout << "Copied!" << std::endl;
     // ...
}

MyString(MyString &&other) noexcept
{
     std::cout << "Moved" << std::endl;
     // ...
}

~MyString()
{
     std::cout << "Deleted!" << std::endl;
     // ...
}

Perfect-Forwarding
So wie ich das Perfect-Forwarding verstehe, ist es das Ziel Argumente über eine Funktion anzunehmen und diese so an eine andere Funktion weiterzugeben, so dass die lvalue/rvalue Eigenschaften unverändert bleiben. Was ich dann also machen könnte, ist es die Argumente für den Konstruktor eines neuen Elements einfach von außen anzunehmen und nach innen weiterzugeben, damit das neue Element direkt im Speicher der LinkedList erstellt wird, anstatt ein temporäres Objekt von außen reinzukopieren. Folgendes müsste bei meiner Implementation dann ungefähr passieren...

Aufruf der append() Funktion mit den Argumenten für den MyString Konstruktor...

LinkedList<MyString> ll;
ll.append("Hallo Welt");

In append() werden die MyString Konstruktor Argumente an ein neues Link Objekt gegeben. Ich weiß nicht genau wie die Signatur von append() aussehen müsste(Variadic-Templates ?). Deswegen schreibe ich einfach args.

void append(args)
{
     new Link{args, nullptr};
}

Der Link Konstruktor gibt die MyString Konstruktor Argumente schließlich an den MyString Konstruktor...

Link(args, Link<T>* next)
     : 
     data{args},
     next{next}
{
     
}

Move-Semantics
Im Fall der Move-Semantics würde glaube ich vieles ähnlich passieren wie im Fall des Perfect-Forwarding. Der Unterschied ist, dass ein existierendes Objekt von außen in die LinkedList reingemoved wird.

Könnt ihr mir vielleicht helfen diese Ansätze zu konkretisieren bzw. Fehler zu beseitigen.

Grüße
Dante

DocShoe

Link( T&& obj, Link* nxt ) :
   data( std::move( obj ) ),
   next( nxt )
{
}

void LinkedList::append( T&& obj )
{
   new Link( std::forward<T>( obj ), nullptr );
}

In deinem Beispiel erzeugst du mit ll.append( "Hallo Welt" ) ein temporäres Objekt. Das kannst du bei entsprechender Überladung der append-Methode fangen und per std::forward an den Konstruktor deines Knotens weiterreichen (Perfect Forwarding). Du brauchst dann noch einen Konstruktor, der einen rvalue als Argument akzeptiert und ihn in die Zielvariable movt. Moved. Wie immer man das auch schreibt.

Edit:
(Fast alles) Quatsch. Wenn append templatisiert ist wird kein temporäres Objekt erzeugt, sondern eine neue Methode mit const char* als Parameter. Die append Methode könnte dann so aussehen:

template<typename ...Args>
Link( Link* nxt, Args&&... args ) :
   next( nxt ),
  data( std::forward<Args>( args )... )
{
}

class LinkedList
{
   template<typename ...Args>
   void append( Args&&... args )
   {
      new Link( nullptr, std::forward<Args>( args )... );
   } 
}

Dante3085

@DocShoe Perfekt. Nur noch ein Konstruktoraufruf und keine 2 Kopien mehr. Danke !

Mechanics

Wenn du dir schon Gedanken über Kopien und perfect forwarding machst, warum dann eine Linked List?

hustbaer

Dieser Beitrag wurde gelöscht!

It0101

@Mechanics sagte in Vermeidung unnötiger Kopien: LinkedList::append<T>(T):

Wenn du dir schon Gedanken über Kopien und perfect forwarding machst, warum dann eine Linked List?

Vermutlich weil es eine häufige und dankbare Übungsaufgabe für diverse Techniken ist.

Dante3085

@Mechanics Ich habe vor kurzem ein paar Videos zu Move-Semantics und Perfect-Forwarding gesehen. In dem Kontext kommt eben auch die Sache auf, dass man seine Objekte als Anfänger oft unnötig kopiert und nicht da erstellt, wo man sie eigentlich haben will. Also beispielsweise wenn ich meine Objekte eigentlich nur in einem Container (std::vector oder ähnliches) haben will, kann ich sie auch gleich in dem Speicher des Containers erstellen. Oder wenn mein std::vector seine Kapazität erreicht hat und neuen Speicher allokieren muss, will ich das Kopieren all meiner Objekte meistens vermeiden. Um ein besseres und praktisches Verständnis von diesen Optimierungstechniken zu bekommen, habe ich einfach irgendeine mir bekannte Datenstruktur implementiert. Mein Anspruch war hier nicht etwas produktionsreifes zu erstellen.

Du spielst vermutlich darauf an, dass eine LinkedList in den meisten Fällen sowieso beispielsweise dem std::vector unterlegen ist. Das stimmt zwar, war mir in diesem Übungsfall aber nicht wichtig.
Ich kann deinen Gedankengang aber nachvollziehen.