Pisanie własnej implementacji podobnego do Iteratora w C++

Question

Obecnie próbuję zrozumieć istotę iteratorów w różnych językach, tj. Sposób ich implementacji.

Na przykład istnieje poniższa klasa, która eksponuje interfejs listy.

template<class T> 
class List 
{ 

    public: 

    virtual void Insert(int beforeIndex, const T item) throw(ListException) =0 ; 
    virtual void Append(const T item) =0; 

    virtual T Get(int position) const throw(ListException) =0; 
    virtual int GetLength() const =0; 

    virtual void Remove(int position) throw(ListException) =0; 


    virtual ~List() =0 {}; 
}; 

Według GoF, najlepszym sposobem wdrożenia iterator, który może obsługiwać różne rodzaje przechodzenie jest utworzenie klasy bazowej Iterator (przyjaciel) z listy chronionych metod, które mogą uzyskać dostęp do członków listy jest. Konkretne implementacje Iteratora obsłużą zadanie na różne sposoby i uzyskają dostęp do prywatnych i chronionych danych List za pośrednictwem interfejsu podstawowego.

Stąd rzeczy stają się coraz bardziej zagmatwane. Powiedzmy, mam klasy LinkedList i ArrayList, obie pochodzą z List, a tam są też odpowiednie iteratory, każda z klas zwraca. Jak mogę wdrożyć LinkedListIterator? Nie mam pomysłów. I jakie dane może pobrać klasa iteratora z listy (która jest zwykłym interfejsem, podczas gdy implementacje wszystkich klas pochodnych różnią się znacząco)?

Answer 1

STL tak naprawdę nie używa abstrakcyjnych klas podstawowych i funkcji wirtualnych. Zamiast tego jest świadomie zaprojektowany, aby nie był OO (w sensie GoF) i zbudowany w całości na szablonach, dążąc do "polimorfizmu w czasie kompilacji". Szablony nie dbają o abstrakcyjne interfejsy. Rzeczy działają tak długo, jak długo mają dostatecznie podobny interfejs (np. Jeśli miałbyś nazwać Appendpush_back zamiast tego, więcej kodu spodziewa się, że kontenery zgodne z STL będą działać dla ciebie, takie jak std::back_insert_iterator).

STL iterator zgodny musiałby przeciążać wiele operatorów zachowywać się jak wskaźnik (o ile to możliwe, biorąc pod uwagę ograniczenia pojemnika), w tym *, ->, ++, -- (jeśli dwukierunkowy - podwójnie związany), == i !=.

Answer 2

Biblioteka standardowa C++ nie wykorzystuje polimorfizmu i dziedziczenia w implementacji iteratorów; zamiast tego używa metaprogramowania szablonów C++ i pojęcia (ale nie formalnej składni *) "pojęć".

Zasadniczo będzie działać, jeśli interfejs dla klasy iteratora spełnia pewne wymagania. Ten zestaw wymagań nazywany jest "pojęciem". Istnieje kilka różnych koncepcji iteratora (patrz this page for a list of all of them) i są one hierarchiczne. Podstawy tworzenia zgodnego iteratora C++ to dostosowanie interfejsu do koncepcji. Dla prostego iteracyjnej, że idzie tylko w kierunku do przodu, wymagałoby to:

• typedef value_type do wartości wynikającej z dereferencing swój iterator.
• Typedef reference_type, który jest typem odniesienia dla odpowiedniego typu wartości.
• Typedef pointer, który jest typem wskaźnika dla odpowiedniego typu wartości.
• Typedef iterator_category, który musi być jednym z parametrów input_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag lub random_access_iterator_tag, w zależności od mechanizmu traversal.
• Typedef difference_type wskazujący wynik odejmowania dwóch różnych iteratorów.
• A const value_type& operator*()const Funkcja do dereferencji iteratora.
• A value_type& operator*() funkcja, jeśli można użyć iteratora do manipulowania wartością.
• Przyrost (funkcje operator++() i operator++(int)) do wyszukiwania w przód.
• Funkcja różnica: difference_type operator-(const type_of_iterator&)

Jeśli wybierzesz jedną z bardziej zaawansowanych kategoriach iterator, może być konieczne, aby określić ubytek i plusa operatora, aby móc dążyć do tyłu lub do poszukiwania dowolną odległość .

* Standardowa biblioteka C++ używa pojęć tak często w nieformalny sposób, że komitet standardów C++ starał się wprowadzić formalny mechanizm deklarowania ich w C++ (obecnie istnieją one tylko w dokumentacji standardowej biblioteki, a nie w żadnej z nich; wyraźny kod). Jednak trwałe nieporozumienia w sprawie wniosku doprowadziły do ​​tego, że został on złomowany pod kątem C++ 0x, chociaż najprawdopodobniej zostanie ponownie rozpatrzony dla standardu po tym.