deque ohne realloc bei push_back



  • hallo, ich habe gerade in der c++ reference gelesen,
    das bei einer std::deque ein
    "push_back" alle iterator ungültig macht.

    Ich dachte eigentlich, das dies nicht so ist, und wollte mal nachfragen

    (ich dachte eine deque ist in chunks organisiert, deshalb kapiere ich nicht
    warum ein push_back, oder ein pop_front, ein realloc aller chunks herbeirufen
    sollte ...)

    weil sonst werde ich mir wohl eine eigene deque schreiben müssen ...



  • so steht es im standard:

    An insert in the middle of the deque invalidates all the iterators and references to elements of the deque. An insert at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque.

    also nicht reallok.



  • das ist ja mal eine gute nachricht, warum iteratoren auf die queue dann nichtmehr gültig sind, kapier ich trotzdem nicht

    heisst das, das ich die iteratoren nichtmehr "bewegen" darf,
    oder darf ich sie nichmal mehr dereferenzieren?


  • Mod

    heisst das, das ich die iteratoren nichtmehr "bewegen" darf,
    oder darf ich sie nichmal mehr dereferenzieren?

    ja und ja, du darfst sie überhaupt nicht mehr anfassen (etwa sie einem anderen iterator zuweisen).

    Treb schrieb:

    das ist ja mal eine gute nachricht, warum iteratoren auf die queue dann nichtmehr gültig sind, kapier ich trotzdem nicht

    deque ist im Vergleich zu den anderen Standardkontainern ein bisschen ungewöhnlich, indem er kein Grunddatenstruktur implementiert. Es gibt mehrere wesentlich verschiedene aber (prinzipiell) gleichermaßen effiziente Varianten deque zu implementieren (Im Vergleich dazu ist vector einfach ein array mit ein paar Zusaätzen, list eine doppelt verkette Liste und die assoziativen Container werden am Besten mittels RB-Bäumen realisiert). deque hat wie vector random-access-Iteratoren, wird aber offensichtlich nicht durch ein einzelnes Array implementiert; mithin entspricht das iterieren über die Elemente nicht einer einfachen Zeigeraddition. Das Einfügen oder Löschen von Elementen am Anfang oder am Ende verschiebt zwar keine Elemente, aber es ist plausibel anzunehmen, dass sich interne Datenstrukturen signifikant ändern, was durch den einzelnen Iterator (ohne erheblichen Overhead) nicht nachvollzogen werden kann.
    Auf der Plusseite bleibt stehen, dass zwar solche Iteratoren ungültig werden, nicht aber Referenzen oder Zeiger auf einzelne Elemente.



  • Zur C++-Implementierung der Deque sei noch zu sagen, dass sie einen *enorm* angenehmen Speicher-Footprint hat. Durch die Organisation des Speichers in Chunks eignet sich die Datenstruktur bei großen Datenmengen eigentlich immer als Ersatz für den 'vector'. Das einzige potentielle Problem könnte man durch Cache-Misses erhalten. Eine kluge Implementierung müsste es aber eigentlich schaffen, dieses Problem ebenfalls zu eleminieren (bzw. zumindest ein gleiches Verhalten wie ein Vektor zu erreichen).


Log in to reply