C ++ Iterator, Dlaczego nie ma klasy bazowej Iterator, z której dziedziczą wszystkie iteratory

Uczę się do egzaminu i mam pytanie, na które staram się udzielić odpowiedzi.

Dlaczego nie istnieje żadna klasa bazowa iteratorów, z której dziedziczą wszystkie inne iteratory?

Domyślam się, że mój nauczyciel odnosi się do struktury hierarchicznej z odwołania cpp „ http://prntscr.com/mgj542 ” i musimy podać inny powód niż dlaczego?

Wiem, jakie są (iteratory) iteratory i że są używane do pracy na kontenerach. Z tego, co rozumiem ze względu na różne możliwe bazowe struktury danych, różne kontenery mają różne iteratory, ponieważ na przykład możesz losowo uzyskać dostęp do tablicy, ale nie połączona lista i różne kontenery wymagają różnych sposobów przemieszczania się po nich.

Prawdopodobnie są to specjalistyczne szablony w zależności od pojemnika, prawda?

Otrzymałeś już odpowiedzi wskazujące, dlaczego nie jest konieczne, aby wszystkie iteratory dziedziczyły z jednej klasy podstawowej Iterator. Ale poszedłem jeszcze dalej. Jednym z celów C ++ jest abstrakcja przy zerowym koszcie wykonania.

Jeśli iteratory działały przez wszystkich dziedziczących po wspólnej klasie bazowej i używały funkcji wirtualnych w klasie bazowej do definiowania interfejsu, a klasy pochodne zapewniały implementacje tych funkcji wirtualnych, które mogłyby (i często dodawałyby) znaczny czas działania koszty ogólne związane z operacjami.

Rozważmy na przykład prostą hierarchię iteratorów, która korzysta z funkcji dziedziczenia i funkcji wirtualnych:

template <class T>
class iterator_base { 
public:
    virtual T &operator*() = 0;
    virtual iterator_base &operator++() = 0;
    virtual bool operator==(iterator_base const &other) { return pos == other.pos; }
    virtual bool operator!=(iterator_base const &other) { return pos != other.pos; }
    iterator_base(T *pos) : pos(pos) {}
protected:
    T *pos;
};

template <class T>
class array_iterator : public iterator_base<T> {
public: 
    virtual T &operator*() override { return *pos; }
    virtual array_iterator &operator++() override { ++pos; return *this; }
    array_iterator(T *pos) : iterator_base(pos) {}
};

Dajmy więc szybki test:

int main() { 
    char input[] = "asdfasdfasdfasdfasdfasdfasdfadsfasdqwerqwerqwerqrwertytyuiyuoiiuoThis is a stringy to search for something";
    using namespace std::chrono;

    auto start1 = high_resolution_clock::now();
    auto pos = std::find(std::begin(input), std::end(input), 'g');
    auto stop1 = high_resolution_clock::now();

    std::cout << *++pos << "\n";

    auto start2 = high_resolution_clock::now();
    auto pos2 = std::find(array_iterator(input), array_iterator(input+sizeof(input)), 'g');
    auto stop2 = high_resolution_clock::now();

    std::cout << *++pos2 << "\n";

    std::cout << "time1: " << duration_cast<nanoseconds>(stop1 - start1).count() << "ns\n";
    std::cout << "time2: " << duration_cast<nanoseconds>(stop2 - start2).count() << "ns\n";
}

[uwaga: w zależności od kompilatora może być konieczne wykonanie nieco więcej czynności, takich jak zdefiniowanie kategorii iterator_category, typ różnicowy, odwołanie itd., aby kompilator zaakceptował iterator.]

Wyjście to:

y
y
time1: 1833ns
time2: 2933ns

[Oczywiście, jeśli uruchomisz kod, wyniki nie będą dokładnie do nich pasować.]

Nawet w tym prostym przypadku (i wykonując tylko około 80 przyrostów i porównań) dodaliśmy około 60% kosztów ogólnych do prostego wyszukiwania liniowego. Zwłaszcza, gdy iteratory zostały pierwotnie dodane do C ++, sporo osób po prostu nie zaakceptowałoby projektu z tak dużym obciążeniem. Prawdopodobnie nie zostałyby ujednolicone, a nawet gdyby tak było, praktycznie nikt by ich nie użył.

Różnica jest między Co coś jest, a jak coś zachowuje.

Wiele języków próbuje połączyć te dwa języki razem, ale są to dość różne rzeczy.

Co to jest i co to jest ...

Jeśli wszystko odziedziczy objectpo tym, pojawiają się pewne korzyści, takie jak: dowolna zmienna obiektu może posiadać dowolną wartość. Ale to też jest pocieranie, wszystko musi zachowywać się ( jak ) objecti wyglądać jak ( co ) object.

Ale:

• Co jeśli twój obiekt nie ma sensownej definicji równości?
• Co jeśli nie ma znaczącego skrótu?
• Co jeśli twój obiekt nie może być sklonowany, ale obiekty mogą być?

Albo ten objecttyp stanie się zasadniczo bezużyteczny - z powodu braku podobieństwa między obiektami we wszystkich możliwych instancjach. Albo będą istnieć obiekty, które mają złamaną / rogową w buty / absurdalną definicję jakiejś przypuszczalnej uniwersalnej własności, na objectktórej zachowuje się niemal uniwersalne zachowanie, z wyjątkiem kilku głupków.

Jeśli co nie jest związane z How

Alternatywnie możesz zachować Co i jak osobno. Potem kilka różnych typów (z nic wspólnego w ogóle what ) wszystko może zachowywać się w taki sam sposób, jak wynika z współpracownik How . W tym sensie idea an Iteratornie jest konkretnym co , ale jak . W szczególności Jak wchodzisz w interakcję z rzeczą, gdy jeszcze nie wiesz, z czym masz do czynienia.

Java (i podobne) umożliwiają podejście do tego przy użyciu interfejsów. Interfejs w tym względzie opisuje środki komunikacji i pośrednio protokół komunikacji i działania, które należy stosować. Wszelkie Co który deklaruje się być danego Jak stwierdza, że obsługuje on odpowiednią komunikację i działania przedstawionego przez protokół. Pozwala to każdy współpracownik polegać na how i nie ugrzęznąć określając dokładnie, które What „s mogą być użyte.

C ++ (i podobne) umożliwiają podejście do tego poprzez pisanie kaczych znaków. Szablon nie dba o to, czy typ współpracujący zadeklaruje, że zachowuje się, tak jak w danym kontekście kompilacji, z którym obiekt może wchodzić w interakcję w określony sposób. Pozwala to na używanie wskaźników tego samego kodu i wskaźników C ++ oraz obiektów przekraczających określone operatory. Ponieważ spełniają listę kontrolną, którą należy uznać za równoważną.

• obsługuje iterator * a, a->, ++ a i ++ -> input / forward
• obsługuje * a, a->, ++ a, a ++, --a i a - -> iterator dwukierunkowy

Typ bazowy nawet nie muszą być iteracji pojemnik, może to być dowolna co . Dodatkowo pozwala niektórym współpracownikom być jeszcze bardziej ogólnym, wyobraź sobie, że funkcja potrzebuje tylko a++, iterator może to zaspokoić, podobnie jak wskaźnik, liczba całkowita, aby każdy obiekt mógł się zaimplementować operator++.

Niedostateczna i nadmierna specyfikacja

Problem z obydwoma podejściami jest niezgodny ze specyfikacją.

Korzystanie z interfejsu wymaga, aby obiekt zadeklarował, że obsługuje dane zachowanie, co oznacza również, że twórca musi go nasycić od samego początku. Powoduje to, że niektóre Co „s, aby nie dokonać cięcia, gdyż nie ogłoszono go. Oznacza to również, że zawsze Co ma wspólnego przodka, interfejs reprezentujący How . To przywraca pierwotny problem object. Powoduje to, że współpracownicy nadmiernie określają swoje wymagania, jednocześnie powodując, że niektóre obiekty są niezdatne do użytku z powodu braku deklaracji lub są ukrytymi problemami, ponieważ oczekiwane zachowanie jest źle zdefiniowane.

Korzystanie z szablonu wymaga współpracy współpracownika z całkowicie nieznanym What , a poprzez interakcje definiuje How . W pewnym stopniu utrudnia to pisanie współpracowników, ponieważ musi analizować Co za prymitywy komunikacyjne (funkcje / pola / itp.), Unikając błędów kompilacji, lub przynajmniej wskazywać, w jaki sposób dane Czego nie spełniają jego wymagania dotyczące Jak . Pozwala to na współpracownika żądać absolutnego minimum z danym Co , pozwalając najszerszy zakres co „s ma być używany. Niestety ma to tę wadę, że pozwala na bezsensowne wykorzystanie obiektów, które technicznie zapewniają prymityw komunikacyjny dla danegoJak , ale nie postępuj zgodnie z domniemanym protokołem pozwalającym na występowanie różnego rodzaju złych rzeczy.

Iteratory

W tym przypadku Iteratorjest Jak to jest skrótem opisu interakcji. Wszystko, co pasuje do tego opisu, jest z definicji an Iterator. Knowing How pozwala nam pisać ogólne algorytmy i mieć krótką listę „ Jak podano konkretne Co ”, które należy podać, aby algorytm działał. Że lista jest funkcja / Właściwości / etc, ich realizacja uwzględnia specyficznych Co to jest rozpatrywana przez algorytm.

Ponieważ C ++ nie musi mieć (abstrakcyjnych) klas bazowych do polimorfizmu. Ma podsieci strukturalne, a także podsieci nominalne .

Myląco w szczególnym przypadku iteratorów poprzednie normy zdefiniowane std::iteratorjako (w przybliżeniu)

template <class Category, class T, class Distance = std::ptrdiff_t, class Pointer = T*, class Reference = T&>
struct iterator {
    using iterator_category = Category;
    using value_type = T;
    using difference_type = Distance;
    using pointer = Pointer;
    using reference = Reference;
}

To znaczy, że jest jedynie dostawcą wymaganych typów członków. Nie zachowywał się w środowisku uruchomieniowym i był przestarzały w C ++ 17

Zauważ, że nawet to nie może być wspólną podstawą, ponieważ szablon klasy nie jest klasą, każda instancja jest niezależna od innych.

Jednym z powodów jest to, że iteratory nie muszą być instancjami klasy. Wskaźniki są na przykład bardzo dobrymi iteratorami w wielu przypadkach, a ponieważ są prymitywami, nie mogą dziedziczyć po niczym.