3. Empfehlt mir einen Container

Empfehlt mir einen Container

  • X

    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

    0

  • 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.

    0
  • L

    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..

    0

  • 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 😉

    0
  • L

    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 ;).

    0
  • ?

    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?

    0

  • @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

    0

  • @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.

    0
  • ?

    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.

    0

  • 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.

    0
  • ?

    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...

    0

  • @Scorcher24:
    Wenn du das willst was C-Style Listen machen, dann sind die Boost.Intrusive Listen optimal für dich.

    Dann musst du aber wirklich die Objekte selbst in die intrusive List stecken, und nicht eine Hilfsklasse mit nur einem Zeiger.

    0
Anmelden zum Antworten