Ich habe gelesen, dass der Zugriff auf Elemente über den Positionsindex in einer STL-Deque in konstanter Zeit erfolgen kann. Soweit ich weiß, können Elemente in einer Deque an mehreren nicht zusammenhängenden Orten gespeichert werden, wodurch ein sicherer Zugriff durch Zeigerarithmetik entfällt. Zum Beispiel:

abc-> defghi-> jkl-> mnop

Die Elemente der obigen Deque bestehen aus einem einzelnen Zeichen. Der Zeichensatz in einer Gruppe zeigt an, dass er im zusammenhängenden Speicher zugeordnet ist (z. B. abc befindet sich in einem einzelnen Speicherblock, defhi befindet sich in einem anderen Speicherblock usw.). Kann jemand erklären, wie der Zugriff über den Positionsindex in konstanter Zeit erfolgen kann, insbesondere wenn sich das Element, auf das zugegriffen werden soll, im zweiten Block befindet? Oder hat eine Deque einen Zeiger auf die Blockgruppe?

Update: Oder gibt es eine andere gängige Implementierung für eine Deque?