Benutzt eigentlich irgendwer std::list?
-
Wegen Cache-Locality: Teilweise ist es cool sich einen kleinen Pool-Allocator zu basteln und den zu verwenden. Zb ist std::set eine astreine priority queue wenn man die Nodes aus einem Pool zieht und viel, viel schneller als std::priority_queue.
Hatte das mal gemessen.Bei std::list macht es bestimmt auch gewaltig etwas aus.
-
Ethon schrieb:
Wegen Cache-Locality: Teilweise ist es cool sich einen kleinen Pool-Allocator zu basteln und den zu verwenden. Zb ist std::set eine astreine priority queue wenn man die Nodes aus einem Pool zieht und viel, viel schneller als std::priority_queue.
Hatte das mal gemessen.Würde ich als schnellen Hack bezeichnen. Müßte bei längerem Betrieb und ein wenig Füllstand die Lokalität gänzlich verlieren. Heaps kann man auch aus (4k-)Blöcken bauen, die dürften dann astrein sein.
-
Wieso sollte man std::list nicht verwendet, wenn std::list besser als std::vector passt?
-
Weil std::list langsamer als vector<Object> und vector<unique_ptr<Object>> ist und es genug andere container Alternativen gibt in denen man etwas stored.
E.g. Map, Set, unordered Map/Set etc.
Wenn einem die Reihenfolge innerhalb einer Liste egal ist kann man sowieso einen Vector nehmen, denn du kannst auch in einem vector innerhalb der Liste loeschen ohne eine Reallokierung zu verursachen.
(swap found element with last element und dann popback benutzen).
Der Witz an der Sache ist, dass selbst wenn du eine sortierte Liste brauchst, ab einer gewissen Anzahl von Elementen ein swap + sort schneller ist als die std::list zu benutzen.
Der Erfinder von C++ Bjarne Stroustrup hat sich zu std::list auch mal in einem Talk geäußert.
siehe:
Minute: 44min 41sec
http://channel9.msdn.com/Events/GoingNative/GoingNative-2012/Keynote-Bjarne-Stroustrup-Cpp11-Style
-
Nein, wenn eine List besser als ein Vector passt, nimmt man die List!
-
... z.B. zur Verwaltung von indizes in einem LRU Cache. Hier ist es am preiswertesten, das MRU Element an das Ende der Liste zu verschieben (so dass am Anfang immer das LRU Element steht)
Wenn da jemand eine performantere Struktur fuer hat: Immer her damit. Ich lerne gerne hinzu!
-
Manchmal hat man aber nicht die Möglichkeit, externe Bibliotheken mit spezialisierten Containerklassen zu verwenden oder sich ganze Implementierungen selbst zu schreiben. std::list ist dann alleine schon die beste Wahl für einen sequentiellen Container, wenn die Iteratoren immer gültig bleiben müssen.
splice() ist auch ein nettes Feature, auch wenn es mit C++11 leider performance-degradiert wurde...
-
wannichlistbenutze schrieb:
... z.B. zur Verwaltung von indizes in einem LRU Cache. Hier ist es am preiswertesten, das MRU Element an das Ende der Liste zu verschieben (so dass am Anfang immer das LRU Element steht)
Wenn da jemand eine performantere Struktur fuer hat: Immer her damit. Ich lerne gerne hinzu!
Vielleicht
http://en.wikipedia.org/wiki/Unrolled_linked_list
-
volkard schrieb:
Vielleicht
http://en.wikipedia.org/wiki/Unrolled_linked_listAlso eine
std::list<std::array<data, 4>>bzw.std::list<static_vector<int, 4>>?
-
Arcoth schrieb:
std::list<static_vector<int, 4>>?Ja, das wäre das Speicherlayout. Vielleicht 30 statt 4 als erste Schätzung.
-
volkard schrieb:
Vielleicht
http://en.wikipedia.org/wiki/Unrolled_linked_listGrundseatzlich ginge das, ja - und entspricht vom Prinzip her dem was deque intern macht.
Aber:
Der Spitzel schrieb:
std::list ist dann alleine schon die beste Wahl für einen sequentiellen Container, wenn die Iteratoren immer gültig bleiben müssen.
splice() ist auch ein nettes Feature, auch wenn es mit C++11 leider performance-degradiert wurde...
Gerade die Tatsache, dass die Iteratoren auch beim Loeschen und Verschieben gueltig bleiben ist ein entscheidender Vorteil, weil dadurch die "Buchhaltung" drastisch reduziert wird.
