spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hmm, wie kann das sein, wenn Elemente nie kopiert werden müssen und der Speicher nicht linear zusammenhängen ist? Je nach Größe der Deque werden es doch mehr und mehr Teilstücke.

Soweit ich mich erinnere: Der Speicher einer deque ist stückweise linear, nicht insgesamt linear. Die Zugriffszeiten sind daher O(1) in dem Sinne, dass es zuerst anhand des Index irgendwo in ein Array aus Segmenten reingreift und dann den Index innerhalb dieses Blockes auflöst. Quasi eine Indirektionsstufe mehr als beim std::vector, und wegen der separaten Allokation eines neuen Segments aller x Hinzufügungen auch nicht so gut für die Cache-Kohärenz, aber dafür halt amortisiert O(1) bei Front-Hinzufügungen. Und es bedeutet halt auch, dass ein einmal abgelegtes Element auch eine feste Speicheradresse hat, solange niemand was in der Mitte einfügt oder rauslöscht.

Der Content wird in mehreren Arrays gespeichert, wies auf cppref steht. Der §\mathcal{O}\left(1\right)§-"Trick" ist nun, ein dynamisches Array zu haben, welches Zeiger auf jedem dieser Arrays speichert.
EDIT: Habs sogar auf Wikipedia gefunden!

MfG
Check