W jaki sposób realizowane są iteratory z dostępem swobodnym dla nieciągłych kontenerów (takich jak std :: deque)?

Question

Rozumiem, jak iteratory dostępu bezpośredniego działają dla sąsiadujących kontenerów, takich jak std :: vector: iterator po prostu utrzymuje wskaźnik do bieżącego elementu, a wszelkie dodatki/odejmowania są stosowane do wskaźnika. Jednak jestem zaskoczony, w jaki sposób można zastosować podobną funkcjonalność dla nieciągłego kontenera. Moim pierwszym przypuszczeniem, w jaki sposób działa std :: deque: iterator jest to, że zachowuje wskaźnik do jakiejś tabeli grup ciągłych pamięci, które zawiera, ale nie jestem pewien.

W jaki sposób typowa biblioteka standardowa to wdroży?

Answer 1

Możesz z grubsza spełnić wymagania dotyczące std::deque z std::vector<std::unique_ptr<std::array<T,N>>>. plus znak niskiej/wysokiej wody informujący o miejscu pierwszego/ostatniego elementu. (dla implementacji zdefiniowanej N, która może się różnić w przypadku T, a std::array s są w rzeczywistości blokami prawidłowo wyrównanej niezainicjowanej pamięci, a nie std::array s, ale masz pomysł).

Używaj zwykłego wzrostu wykładniczego, ale z przodu iz tyłu.

Wyszukiwanie po prostu powoduje, że (index+first)/N i znajdują blok i element podrzędny.

Jest to droższe niż odnośnik std::vector, ale jest O (1).

Answer 2

Można zaimplementować iterator przechyłki, przechowując zarówno wskaźnik do przywoływanej wartości, jak i podwójny wskaźnik do sąsiedniego bloku pamięci, w którym znajduje się ta wartość. Podwójny wskaźnik wskazuje na ciągły szereg wskaźników do bloków zarządzanych przez deque.

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

Ponieważ zarówno value i block punktu w pamięci ciągłej, można zaimplementować operacje takie ustalenie odległości między iteratorów w stałym czasie (przykład adaptacja libC++).

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); 
} 

zauważyć, że podczas gdy value nie zostaną unieważnione przez operacje, takie jak push_front i push_back, block może być, dlatego deque_iterator podważa takich operacji.