deque selber implementieren

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