std::list sort range?

Columbo

Ups, lol. So natürlich nicht. Vergesse jedes mal das sort RandomAccessIterators erwartet.

Dann trenne doch den Teil der Liste den du sortieren möchtest in eine neue Liste, sortiere diese mittels der Memberfunktion und füge sie wieder in die ursprüngliche Liste ein.

Ja, das dachte ich mir auch schon.
Wollte es nur einfacher haben, aber wenn das nicht geht..

hustbaer

Selbst wenn es mit std::sort ginge wäre splice + list::sort besser, und zwar wegen...

http://www.cplusplus.com/reference/list/list/sort/ schrieb:

The entire operation does not involve the construction, destruction or copy of any element object. Elements are moved within the container.

Wobei "move" hier nicht bedeutet dass irgendwas move-assigned oder gar move-constructed würde.
"Moved" heisst einfach nur dass die list -internen next- und previous-Zeiger umgesetzt werden um die Reihenfolge der Elemente zu verändern.

Die Elemente selbst werden dabei nur "gelesen" (bzw. was auch immer operator < bzw. comp macht).

std::sort dagegen weiss nichts über list -Interna und muss daher wirklich swap pen.

SeppJ

hustbaer schrieb:

Selbst wenn es mit std::sort ginge wäre splice + list::sort besser, und zwar wegen...

http://www.cplusplus.com/reference/list/list/sort/ schrieb:

The entire operation does not involve the construction, destruction or copy of any element object. Elements are moved within the container.

Bloß hat die std::list dummerweise keinen random access, weswegen weniger schnelle Algorithmen benutzt werden müssen (Gegenüber dem, was mit std::sort möglich ist). Daher ist es dann in der Praxis doch wieder deutlich langsamer als andere Container; wie so oft bei verketteten Listen, die eben nur in der Theorie ganz toll klingen.

(Eine gut designte Klasse mit großen Datenfeldern hat auch eine Indirektion für diese Datenfelder, so dass Vertauschungsaktionen zweier Instanzen ähnliche Kosten haben wie das Vertauschen von zwei list-Elementen. Und wenn die Klasse es aus irgendeinem Grund nicht so handhabt, kann man immer noch selber nur Verweise im Container speichern)

PS: Laut diesem Benchmark aus dem Jahr 2012 ist der crossover, ab dem die list beim Sortieren besser wird als vector/deque irgendwo zwischen 128 und 1024 Byte pro Datenelement. Das ist schon eine ganze Menge und sicherlich ein Punkt, an dem man so langsam anfängt, den Datenbereich eines Objekts dynamisch zu verwalten.

volkard

SeppJ schrieb:

PS: Laut diesem Benchmark aus dem Jahr 2012 ist der crossover, ab dem die list beim Sortieren besser wird als vector/deque irgendwo zwischen 128 und 1024 Byte pro Datenelement. Das ist schon eine ganze Menge und sicherlich ein Punkt, an dem man so langsam anfängt, den Datenbereich eines Objekts dynamisch zu verwalten.

Jo, die mit move-Semantik wird auch ungeheuer aufräumen.

Unabhängig davon ist es bei fetten (und langsamen) Objekten eine feine Idee, sich vor dem Sortieren einen Index als vectorquellcontainer::iterator zu ziehen und jenen erst zu sortieren und dann den quellcontainer mit der minimalen Anzahl von moves anhand des Idex zu ordnen.
Ups, fühlt sich an, als würde das viel schneller werden als die Messungen und den Unterschied zwischen vector/deque/list auch wegmachen.

TGGC

volkard schrieb:

Unabhängig davon ist es bei fetten (und langsamen) Objekten eine feine Idee, sich vor dem Sortieren einen Index als vectorquellcontainer::iterator zu ziehen und jenen erst zu sortieren und dann den quellcontainer mit der minimalen Anzahl von moves anhand des Idex zu ordnen.

Meistens kann man auf das abschliessende Ordnen dann auch komplett verzichten, da man schon eine Menge Zugriffe auf den geordneten Vector machen muss, bevor sich das amortisiert.

SeppJ

volkard schrieb:

Unabhängig davon ist es bei fetten (und langsamen) Objekten eine feine Idee, sich vor dem Sortieren einen Index als vectorquellcontainer::iterator zu ziehen und jenen erst zu sortieren und dann den quellcontainer mit der minimalen Anzahl von moves anhand des Idex zu ordnen.

Ich habe das Gefühl, das multiset da fast immer besser sein sollte. Aber das ist so ein Fall, wo man messen sollte. Wahrscheinlich mag ich einfach set zu sehr.

splice() kannte ich gar nicht.
Super, danke an alle

hustbaer

@SeppJ
list::sort ist besser für list .
Ob list der passende Container ist, ist dann wieder ne andere Frage. Der Punkt war nicht gefragt, daher bin ich davon ausgegangen dass list schon Sinn macht.

TGGC

SeppJ schrieb:

Ich habe das Gefühl, das multiset da fast immer besser sein sollte. Aber das ist so ein Fall, wo man messen sollte. Wahrscheinlich mag ich einfach set zu sehr.

Mach doch ein Benchmark. (SCNR)