deque selber implementieren

rean

hustbaer schrieb:

@rean:
Und dass der Speichervarbrauch dabei ständig wächst ist dir egal?
Nur mal als Tip: ne deque wird häufig als FIFO verwendet.
Da wird immer nur push_back und pop_front gemacht.

Weil es ja auch unmöglich wäre den Code so zu erweitern, dass ab einem gewissen Schwellwert die Objekte wieder an den Anfang kopiert werden.

Incocnito schrieb:

Also bei mir kackt das Program schon bei etwas mehr als 100 Elementen ab:
int main()
{
    xdeque<int> ints;
    for(int i = 0; i <= 200; i++)
        ints.push_back(d);
    for(unsigned i = 0; i < ints.size(); ++i)
        std::cout << ints[i] << " ";
}
"Programm.exe funktioniert nicht mehr [...]"

Wundert mich aber auch nicht bei den ganzen new's und delete's und den ganzen Zeigern, und noch Sachen wie memmove etc.
Da muss einfach irgendwann was schief laufen

hab iwie die falsche version hochgeladen...

hustbaer

rean schrieb:

hustbaer schrieb:

@rean:
Und dass der Speichervarbrauch dabei ständig wächst ist dir egal?
Nur mal als Tip: ne deque wird häufig als FIFO verwendet.
Da wird immer nur push_back und pop_front gemacht.

Weil es ja auch unmöglich wäre den Code so zu erweitern, dass ab einem gewissen Schwellwert die Objekte wieder an den Anfang kopiert werden.

Ja, man könnte da irgendwie rumbasteln, damit der Speicherverbrauch nicht ständig wächst.

Wenn man das macht, dann ändern sich aber die Adressen der Elemente (da ja umkopiert wird). Und dann könnte man auch gleich einen dynamischen Ringpuffer verwenden. Der muss bei ständigem push_back() + pop_front() nämlich gar nix umkopieren.

@Krauzi
Das recenter() kannst du dir sparen, wenn du die "innere deque" gleich als dynamischen Ringpuffer auslegst.
Und natürlich bietet es sich an std::vector zu verwenden.

hm durch was kann ich mir denn meine innere deque sparen?
zum thema vector: kann ich so leider nicht verwenden, da ich meine deque eigentlich in c schreiben sollte. ich hab mir zwar bereits eine vektor "klasse" in c geschrieben, allerdings sollten die structs optimales größe/performance verhältniss haben (das schließt den einsatz eines vectors eigentlich aus).

hm jetzt den code gefixt, aber irgendwie klappt etwas noch nicht wenn man alle elemente entfernt hat und wieder mit hinzufügen beginnt. das kann ich mir aber nicht erklären, da wie man bei den pop methoden erkennen kann alles wieder resetet wird.

EDIT: fehler war ziemlich einfach: beim reseten wurde die deltas falsch gesetzt.
bei einer geraden blockgröße hat alles gepasst weil da beide deltas gleich waren (und das sollten sie auch sein, es wird ja beim push_front/back --front bzw back++ gemacht).

hustbaer

Krauzi schrieb:

hm durch was kann ich mir denn meine innere deque sparen?

Na z.B. indem du einen dynamischen Ringpuffer verwendest. Wie ich schon gesagt habe, ändern sich dann aber die Adressen der Elemente wenn die Puffergrösse angepasst werden muss.

Falls du dir unter "dynamischem Ringpuffer" nix vorstellen kannst... stell dir einen normalen vector vor + start offset (wo ist das erste Element?) + länge + "wrap around" am Ende. D.h. wenn das Array 10 Elemente gross ist, Start-Offset ist 8 und Länge ist 5, dann sieht es im Speicher so aus:

pos      0 1 2 3 4 5 6 7 8 9
element  3 4 5 . . . . . 1 2

Und wenn das Ding zu klein wird, dann musst du es eben resizen - ganz normal wie man es bei einem Vektor auch machen würde.

Ich wollte aber auch gar nicht vorschlagen die innere deque ganz einzusparen. Sondern nur das recenter() zu sparen - was du eben wie beschrieben mit einem dynamischem Ringpuffer machen kannst.

Wobei: amortisiert O(1) für push/pop an beiden Enden + O(1) für Lookup bekommst du mit einem dynamischem Ringpuffer ohne innere Deque auch. Die innere Deque bringt nur was, wenn entweder die Elemente teuer zu kopieren sind, oder es notwendig ist dass die Adressen der Elemente stabil bleiben.

zum thema vector: kann ich so leider nicht verwenden, da ich meine deque eigentlich in c schreiben sollte. ich hab mir zwar bereits eine vektor "klasse" in c geschrieben, allerdings sollten die structs optimales größe/performance verhältniss haben (das schließt den einsatz eines vectors eigentlich aus).

OK. Nur wieso postest du dann im C++ Forum?

danke für die antwort.

hustbaer schrieb:

Krauzi schrieb:

hm durch was kann ich mir denn meine innere deque sparen?

Na z.B. indem du einen dynamischen Ringpuffer verwendest. Wie ich schon gesagt habe, ändern sich dann aber die Adressen der Elemente wenn die Puffergrösse angepasst werden muss.

das wäre an und für sich net gute idee, allerdings wollte ich zumindest ein bisschen code wiederverwenden. da bietet sich die innere deque gut an, da ich die selber als deque implementierung zur verfügung stellen kann.
Ich habe dazu mal ein paar performance tests gemacht (100*10^6 char durchjagen), da ist das deque array höllisch schnell (fast genauso schnell wie ein vector), die (nicht array) deque ungefähr 3 mal langsamer. die msvc std::deque hat so lange gebraucht dass ich keine ergebnisse hab

hustbaer schrieb:

zum thema vector: kann ich so leider nicht verwenden, da ich meine deque eigentlich in c schreiben sollte. ich hab mir zwar bereits eine vektor "klasse" in c geschrieben, allerdings sollten die structs optimales größe/performance verhältniss haben (das schließt den einsatz eines vectors eigentlich aus).

OK. Nur wieso postest du dann im C++ Forum?

die deque in c (mit der wurden die teste durchgeführt) ist typlos, deshalb muss beim constructor die element größe (sizeof) übergeben werden, push und pop vorgänge laufen dann über memcpy und zeiger auf die elemente, in die dann sizeof(typ) bytes gelesen oder eben geschrieben wird.

EDIT: der grund dass ich hier poste ist, dass die c deque wirklich keiner mehr versteht. c++ ist einfach wesentlich übersichtlicher als c (ordentlich geplant vorausgesetzt natürlich).

DocShoe

Das mit dem Ringpuffer finde ich eine schicke Idee, aber warum nur einen? Wenn die deque z.B. aus std::vector<std::unique_ptr<circular_buffer>> bestünde kann man beim push_front/push_back einfach einen neuen circular_buffer vorn/hinten einfügen, ohne dass man die Größe ändern müsste oder Objekte kopiert werden. Ist natürlich die Frage, was teurer zu kopieren ist, wenn der vector realloziert. Ein recenter() ist auch nicht mehr notwending, da man leere Ringpuffer am Anfang/Ende einfach löschen könnte. (gut, das könnte man jetzt auch recenter nennen...)

pumuckl

DocShoe schrieb:

Ist natürlich die Frage, was teurer zu kopieren ist, wenn der vector realloziert.

Reallikation des vector = move der unique_ptr = N Pointer-Kopien.

hustbaer

DocShoe schrieb:

Das mit dem Ringpuffer finde ich eine schicke Idee, aber warum nur einen? Wenn die deque z.B. aus std::vector<std::unique_ptr<circular_buffer>> bestünde kann man beim push_front/push_back einfach einen neuen circular_buffer vorn/hinten einfügen, ohne dass man die Größe ändern müsste oder Objekte kopiert werden. Ist natürlich die Frage, was teurer zu kopieren ist, wenn der vector realloziert. Ein recenter() ist auch nicht mehr notwending, da man leere Ringpuffer am Anfang/Ende einfach löschen könnte. (gut, das könnte man jetzt auch recenter nennen...)

Naja, das ist ja fast das selbe was die typischen std::deque Implementierungen machen.
Wobei es allerdings Sinn macht, den äusseren Vektor auch durch einen Ringpuffer zu ersetzen. Dann muss man nämlich nicht dauernd Zeiger umkopieren wenn die deque als FIFO verwendet wird.

@Krauzi

da ist das deque array höllisch schnell (fast genauso schnell wie ein vector), die (nicht array) deque ungefähr 3 mal langsamer

Ich weiss ehrlich gesagt jetzt nicht was du mit "deque array" und "(nicht array) deque" meinst.