Empfehlt mir einen Container

Die Reihenfolge wäre in dem Fall nicht wichtig.
Wie schaut deque vs vector aus was Jodocus ansprach?
Das mit nach hinten schieben wird schwierig weil pro Durchlauf auch mehrere Elemente ungültig werden können. Klar, der reihe nach aber wie gut eignet sich da swap?

SeppJ

Jodocus schrieb:

Könnte mit SeppJs Methode eine std::deque nicht sogar besser sein (besonders was das Löschen angeht)?

deque würde ich nicht nehmen, wenn es auf Geschwindigkeit ankommt. Für deque spricht nur, dass Einfügen und Löschen am Anfang eine bessere Komplexitätsklasse hat als beim vector. Aber sonst sind die Konstanten viel größer als bei vector, außer eventuell beim Anhängen am Ende, was ähnlich schnell geht. Aber dafür wird der Elementzugriff lahm, was oftmals nicht gewünscht wird.

Das relativiert sich natürlich, falls es die Operationen auf den Elementen sind, die die Zeit verbrauchen, aber das wird hier wohl nicht der Fall sein, sonst würde ja nicht ausdrücklich nach einem schnellen Container gefragt. Und da ist vector allen anderen Containern deutlich überlegen.

(Das ist natürlich alles nicht Standard, da der Standard nur Komplexitätsklassen vorschreibt. Die Schnelligkeit von vector ergibt sich dann aber in der Praxis aus der einfacheren Implementierung von vector, der einfach nicht so viele Anforderungen erfüllen braucht).

SeppJ

Scorcher24 schrieb:

Die Reihenfolge wäre in dem Fall nicht wichtig.
Wie schaut deque vs vector aus was Jodocus ansprach?
Das mit nach hinten schieben wird schwierig weil pro Durchlauf auch mehrere Elemente ungültig werden können. Klar, der reihe nach aber wie gut eignet sich da swap?

Nimm das mit dem Verschieben nicht so wörtlich. Das ist eher so gemeint:

loesche element N aus liste. Dazu:
 1. liste[N]=letztes element aus liste
 2. letztes element loeschen

Also einfach Zuweisung und resize(size-1). Eine ganz ganz billige Operation. Danach geh'ste bei Element N weiter.

hustbaer

Also ich würde da schon swap() empfehlen, da swap() oft schneller ist als operator =.

Wenn es um Zeiger geht sollte das natürlich egal sein. Es sei denn es wären Smart-Pointer, dann ist swap() wieder der klare Sieger.
Mit std::unique_ptr geht nur swap(), und mit std::shared_ptr wird swap() ein gutes Stück schneller sein als operator =.

Und: ganz klar vector wenn einfügen/löschen am Anfang nicht benötigt wird.

rean

Eine deque ist ja typischerweise als Array von Arrays implementiert.
Das Iterieren dürfte auch nur auf ein ++offset hinauslaufen.
Was eindeutig länger braucht ist das Dereferenzieren eines Iterators weil ungefähr folgendes passiert:

#define deque_size 16; //power of 2
T map[x][deque_size];
size_t offset;
//...
T operator*()
{
 size_type block = offset / deque_size;     //könnte vom Compiler zu nem shift optimiert werden
 size_type off = offset & (deque_size - 1); //entspricht modulo

 return map[ block ][ off ];
}

Also doch ein paar Befehle mehr als bei einem vector.

Im Endeffekt läufts auf folgendes hinaus:
Hinzufügen eines Elements wenn noch Speicher im Container frei ist:
vector: O(1)
deqeue: O(1)
Hinzufügen eines Elements in einen vollen Container:
vector: Kopieren aller Elemente in neuen Speicherbereich: O(n)
deque: Kopieren aller Map-Elemente in neuen Speicherbereich: O(m) (m = n / deque_size)
Wenn die Anzahl deiner Elemente relativ konstant ist fällt das aber nicht wirklich ins Gewicht.

Wie wärs mit dem Container?
http://de.academic.ru/dic.nsf/dewiki/1359077

SeppJ

achsek schrieb:

Wie wärs mit dem Container?
http://de.academic.ru/dic.nsf/dewiki/1359077

Hmm, gefüllt mit Festplatten eine extrem gute Datenrate, selbst bei Lieferung ans andere Ende der Welt. Aber die Latenz lässt zu wünschen übrig und das ist bei Spielen wichtiger.

achsek schrieb:

Wie wärs mit dem Container?
http://de.academic.ru/dic.nsf/dewiki/1359077

Beim dem Funktionsumfang dauert die Allokierung zu lange :p.
Danke an alle

HighLigerBiMBam

Vielleicht noch das hier als Alternative: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html

XSpille

Also die Abschätzung, ob deque oder vector die bessere Wahr ist, wird
wohl nur schwer einer machen können ohne das komplette Problem genau zu kennen...

Vereinfacht:
deque: konstant langsamere Zugriffszeit per Index - bei Verwendung von Iterator (denke ich) wenig spürbar
vector: komplettes Umkopieren, falls Speicher nicht ausreichend (kann insbesondere bei großen Vektoren zu ruckeln führen)

Aber mach dir keinen so großen Kopf drum.
Definier dir doch einfach ein typedef und probier es aus.
Wenn es nicht paßt, dann ändere den Typen.

Gruß,
XSpille

hustbaer

XSpille schrieb:

deque: konstant langsamere Zugriffszeit per Index - bei Verwendung von Iterator (denke ich) wenig spürbar

Da denkst du falsch, auch Iterator-Operationen werden langsamer.

life

hustbaer schrieb:

XSpille schrieb:

deque: konstant langsamere Zugriffszeit per Index - bei Verwendung von Iterator (denke ich) wenig spürbar

Da denkst du falsch, auch Iterator-Operationen werden langsamer.

Außerdem ist bei deque imho kein O(1) Index-Zugriff garantiert.

Komplexitätstheoretisch sollte eine deque äquivalent zu einer list sein, sofern die block size konstant ist..

hustbaer

Nachdem eine deque Random-Access Iteratoren hat, müsste der Zugriff amortisiert O(1) sein. Bloss wird er linear langsamer sein als bei vector.

Und deque ist von der Komplexität her sicher nicht mit list vergleichbar, sonst wäre die Klasse wohl ziemlich sinnlos

life

hustbaer schrieb:

Nachdem eine deque Random-Access Iteratoren hat, müsste der Zugriff amortisiert O(1) sein. Bloss wird er linear langsamer sein als bei vector.

Kannst Du mir die Stelle im Standard nennen? Ich habe gestern nämlich danach gesucht, aber nichts gefunden. Allerdings habe ich auch nichts zu O(1) Zugriff bei vector gefunden Dementsprechend werde ich den entsprechenden Abschnitt wohl irgendwie übersehen haben ;).

Edit: Habs gefunden: 23.1.1 Tabelle 71 in meinem Draft hier:
"Table 71 lists sequence operations that are provided for some types of sequential containers but not others. An implementation shall provide these operations for all container types shown in the “container” column, and shall implement them so as to take amortized constant time."
Demnach muss deque amortisiert O(1) für push_back , push_front und operator[] implementieren.

Also schon anders als eine list . Da hatte ich was falsches im Kopf ;).

Was haltet ihr hiervon:
http://www.boost.org/doc/libs/1_36_0/doc/html/intrusive/slist.html

Und was genau meinen die mit intrusive?

hustbaer

@Scorcher24:
Intrusive heisst dass du die Elemente anpassen musst, wenn du sie in einen solchen Container einfügen willst.
D.h. du musst z.B. von einer bestimmten Klasse ableiten oder ein Member einer bestimmten Klasse einfügen, um die Objekte in einem intrusive Container verwalten zu können.

Auch werden dabei die Elemente direkt eingefügt und keine Kopien gemacht.

http://www.boost.org/doc/libs/1_36_0/doc/html/intrusive/intrusive_vs_nontrusive.html#intrusive.intrusive_vs_nontrusive.differences_intrusive_vs_nontrusive

hustbaer

@life:
Es steht auch nochmal bei den Iterator-Categories für die Iteratoren selbst. Alle vom Standard für eine bestimmte Iterator-Category vorgeschriebenen Operationen sind mit amortisiert O(1) vorgeschrieben.

Danke für den Link, aber das eignet sich doch dann eigentlich die Spieleprogrammeriung mehr als normale Container. Es gibt kein hin- und herkopieren und nur was ich allokiere wird auch benötigt.
Ich denke ich versuchs mal mit boost::slist und schau mir dann die Performance an. Weil die meiste Zeit gehe ich meine Listen sowieso nur in eine Richtung durch.

hustbaer

Die doppelt verkettete intrusive List ist auch nicht viel langsamer.

BTW: willst du Zeiger auf die Objekte in die intrusive list stecken, oder dann die Objekte selbst? Die ganzen intrusive Container funktionieren ja auch mit abgeleiteten Klassen.

Wenn du die Objekte selbst in die intrusive list stecken kannst, dann bringt das vermutlich ein bisschen was.

hustbaer schrieb:

Die doppelt verkettete intrusive List ist auch nicht viel langsamer.

BTW: willst du Zeiger auf die Objekte in die intrusive list stecken, oder dann die Objekte selbst? Die ganzen intrusive Container funktionieren ja auch mit abgeleiteten Klassen.

Wenn du die Objekte selbst in die intrusive list stecken kannst, dann bringt das vermutlich ein bisschen was.

Hmm, naja ich erzeuge meine Objekte auf dem Heap. Hat den Grund, dass ich genau definieren muss wann diese zerstört werden damit keine Memory Leaks entstehen. Sprich, bevor der OpenGL Context zerstört wird.
Im prinzip steke ich da ja nur nen Zeiger darauf "rein". Aber bei "C"-Style verketteten Listen biegt man ja auch nur Zeiger hin und her.
Das Problem bei STL-Containern ist halt, dass diese nochmal kopieren.
Ich geb zu, ich habe so meine Probleme mit Containern...