New und Delete

cooky451 schrieb:

wtf, ne, so war das jetzt nicht gemeint. Eine node sollte aus T + unique_ptr<node> bestehen, die liste sollte nur nen unique_ptr<node> halten. Damit werden alle Einfüge/Löschoperationen auch nur noch zu Zuweisungen zwischen unique_ptr. Ist die Frage, ob das langsamer ist, denke aber nicht.

Versuchs doch mal und zeig es mir.

Mit meiner Implementation geht es nicht, die ist dafür zu trickreich. Die Liste ist als Zyklus implementiert, um die ganzen if-Abfragen zu sparen, die man hätte, wenn das letzte Element auf NULL zeigen würde. Bevor man den Destruktor von unique_ptr ans Werk lassen könnte, müsste man zuerst den Zyklus aufbrechen. Das kostet. Alternativ könnte man was mit speziellen Deletern machen. Aber auch das kostet und wäre umständlicher.

camper

cooky451 schrieb:

wtf, ne, so war das jetzt nicht gemeint. Eine node sollte aus T + unique_ptr<node> bestehen, die liste sollte nur nen unique_ptr<node> halten. Damit werden alle Einfüge/Löschoperationen auch nur noch zu Zuweisungen zwischen unique_ptr. Ist die Frage, ob das langsamer ist, denke aber nicht.

Das halte ich für eine schlechte Idee.
Abgesehen davon, dass es Abstraktionsebenen durcheinander bringt, wäre ich nicht überrascht, wenn das Löschen einer großen Liste zum Stacküberlauf führen würde.

node* pointer_to_first;

  // das geht gut, solange nie auf data()->data zugegriffen wird.
  node* data() { return reinterpret_cast<node*>(&pointer_to_first); }

Das ist leider (im Allgemeinen) undefiniert (es ist zum Glück nicht schwierig, das standardkonform aufzuschreiben).

camper schrieb:

node* pointer_to_first;
 
  // das geht gut, solange nie auf data()->data zugegriffen wird.
  node* data() { return reinterpret_cast<node*>(&pointer_to_first); }
Das ist leider (im Allgemeinen) undefiniert (es ist zum Glück nicht schwierig, das standardkonform aufzuschreiben).

Im darauf folgenden Post hatte ich das geändert. Allerdings war noch ein Fehler drin.

Meine List hoffentlich ohne UB

camper schrieb:

wäre ich nicht überrascht, wenn das Löschen einer großen Liste zum Stacküberlauf führen würde.

Ich war überrascht, dem GCC hätte ich Tail Rekursion zugetraut.

cooky451

So, ist nur schnell zusammen-gefrickelt um die Idee zu zeigen, fehlt sicher einiges: https://ideone.com/hQgd90
Scheint auch tatsächlich etwas langsamer zu sein, interessant. Vielleicht gucke ich mir später mal an, was genau der jetzt anders macht. (Edit: Jetzt ist es fast genau so schnell. Sollte man vielleicht doch eher lokal messen. )

camper schrieb:

Abgesehen davon, dass es Abstraktionsebenen durcheinander bringt,

Wie genau meinst du das?

camper schrieb:

wäre ich nicht überrascht, wenn das Löschen einer großen Liste zum Stacküberlauf führen würde.

Das ist eben die Frage. Man sollte sich natürlich schon darauf verlassen können, dass der da nicht ernsthaft rekursiv durchgeht. Muss man gucken denke ich, wie weit die üblichen Compiler das raffen.

volkard

camper schrieb:

cooky451 schrieb:

wtf, ne, so war das jetzt nicht gemeint. Eine node sollte aus T + unique_ptr<node> bestehen, die liste sollte nur nen unique_ptr<node> halten. Damit werden alle Einfüge/Löschoperationen auch nur noch zu Zuweisungen zwischen unique_ptr. Ist die Frage, ob das langsamer ist, denke aber nicht.

Das halte ich für eine schlechte Idee.
Abgesehen davon, dass es Abstraktionsebenen durcheinander bringt,

Sehe ich auch so. Es spart zwar ein wenig Code, macht die Liste aber nur komplizierter.

Werner Salomon

Werner Salomon schrieb:

.. die std::list<> ist richtig schneller - und die Ursache liegt in der besseren Speicherverwaltung!

Ich muss das relativieren. Die Info ist ziemlich alt, und stammt wahrscheinlich noch aus Zeiten von MS VS6 plus Windows NT.

Der Vorteil der std::list<> lag darin, bei Konstruktor- oder assign-Aufrufen, wo mehr als ein Element an die Liste übergeben wurde, gleich für alle Elemente einen einzigen Speicherbereich zu reservieren. Die std::list machte damals einen eigenen kleinen Memorypool - inklusive Verwaltung auf.
So weit ich das einschätzen kann, ist aber das Bereitstellen von Speicher seitdem signifikant besser geworden, so dass sich dieser Aufwand wohl nicht mehr lohnt. Dies gilt insbesondere für viele Alloc's von kleinen Speicherbereichen.

Das war irgendwann durchaus ein Flaschenhals, und wohl auch die Motivation für Andrei Alexandrescus 'small object allocator' - siehe Modern C++ Design | ISBN: 9780201704310.
Dem ist aber heute nicht mehr so (ich rede jetzt nur von Windows und MS VS). Ich hatte den 'small object allocator' in einem Projekt verwenden wollen, aber dann festgestellt, dass der erreichte Geschwindigkeitsvorteil den Aufwand nicht lohnt.

Die aktuellen Implementierungen der std::list (VS8-VS10) reservieren für jedes Element einen eigenen Speicher. Aktuelle Messungen zeigen einen leichten Geschwindigkeitsvorteil für eine eigene SList gegenüber std::list und gegen eine std::forward_list ist kein Unterschied messbar.

Aber um zum Thema zurück zu kommen: Die Behauptung ein eigenes new/delete hätte gegenüber den Containern des C++-Standard Vorteile bei der Geschwindigkeit ist sicher falsch. Abgesehen davon handelt man sich so viele Nachteile ein, dass das in keiner Weise zu rechtfertigen ist. Bei 'großen' Projekten schon gar nicht.

Gruß
Werner