Wie werden Direktzugriffs-Iteratoren für nicht zusammenhängende Container (z. B. std :: deque) implementiert?

Question

Ich verstehe, wie Random-Access-Iteratoren für zusammenhängende Container wie Std :: Vector arbeiten: der Iterator verwaltet einfach einen Zeiger auf das aktuelle Element und alle Additionen/Subtraktionen werden auf den Zeiger angewendet. Ich bin jedoch verblüfft darüber, wie ähnliche Funktionalität für einen nicht zusammenhängenden Container implementiert werden könnte. Meine erste Vermutung für, wie std :: deque: Iterator funktioniert ist, dass es einen Zeiger auf eine Tabelle der Gruppen von zusammenhängenden Speicher verwaltet, die es enthält, aber ich bin mir nicht sicher.

Wie würde eine typische Standardbibliothek dies implementieren?

Answer 1

Sie können die Anforderungen einer std::deque mit einer std::vector<std::unique_ptr<std::array<T,N>>> grob erfüllen. plus eine untere/obere Wassermarke, die anzeigt, wo sich die ersten/letzten Elemente befinden. (für eine Implementierung definiert N, die mit T variieren könnte, und die s sind tatsächlich Blöcke von ordnungsgemäß ausgerichtet nicht initialisierten Speicher und nicht s, aber Sie bekommen die Idee).

Verwenden Sie das übliche exponentielle Wachstum, aber sowohl auf der Vorder- als auch auf der Rückseite.

Suche einfach (index+first)/N und %N, um das Block- und Unterelement zu finden.

Dies ist teurer als ein std::vector Lookup, aber ist O (1).

Answer 2

Ein Deque-Iterator kann implementiert werden, indem sowohl ein Zeiger auf den referenzierten Wert als auch ein Doppelzeiger auf den zusammenhängenden Speicherblock gespeichert wird, in dem sich dieser Wert befindet. Der Doppelzeiger zeigt auf ein zusammenhängendes Array von Zeigern auf Blöcke, die von der Deque verwaltet werden.

class deque_iterator 
{ 
    T* value; 
    T** block; 
    … 
} 

sowohl Da value und block Punkt in zusammenhängenden Speicher, können Sie Operationen wie das Finden der Abstand zwischen Iteratoren in konstanter Zeit (zB angepasst von libC++) implementieren.

difference_type operator-(deque_iterator const& x, deque_iterator const& y) 
{ 
    return (x.block - y.block) * block_size 
     + (x.value - *x.block) 
     - (y.value - *y.block); 
} 

Beachten Sie, dass, während value nicht durch Operationen wie push_front und push_back, für ungültig erklärt werden block sein könnte, weshalb deque_iterator durch solche Operationen für ungültig erklärt wird.