C ++ Iterator, Pourquoi n'y a-t-il pas de classe de base Iterator dont tous les itérateurs héritent

J'apprends pour un examen et j'ai une question à laquelle j'ai du mal à répondre et à répondre.

Pourquoi n'existe-t-il pas de classe de base d'itérateur dont tous les autres itérateurs héritent?

Je suppose que mon professeur fait référence à la structure hiérarchique de la référence cpp " http://prntscr.com/mgj542 " et nous devons fournir une autre raison que pourquoi le devraient-ils?

Je sais ce que sont les itérateurs (en quelque sorte) et qu'ils sont utilisés pour travailler sur des conteneurs. D'après ce que je comprends en raison des différentes infrastructures de données sous-jacentes possibles, différents conteneurs ont différents itérateurs parce que vous pouvez accéder de manière aléatoire à un tableau, par exemple, mais pas à une liste liée et différents conteneurs nécessitent différentes façons de les parcourir.

Ce sont probablement des modèles spécialisés en fonction du conteneur, non?

Vous avez déjà obtenu des réponses indiquant pourquoi il n'est pas nécessaire que tous les itérateurs héritent d'une seule classe de base Iterator. J'étais cependant allé un peu plus loin. L'un des objectifs de C ++ est l'abstraction avec un coût d'exécution nul.

Si les itérateurs fonctionnaient tous en héritant d'une classe de base commune et utilisaient des fonctions virtuelles dans la classe de base pour définir l'interface, et que les classes dérivées fournissaient des implémentations de ces fonctions virtuelles, cela pourrait (et souvent ajouterait) une exécution substantielle frais généraux pour les opérations concernées.

Prenons par exemple une hiérarchie d'itérateurs simple qui utilise l'héritage et les fonctions virtuelles:

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

Alors donnons-lui un test rapide:

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

[Remarque: selon votre compilateur, vous devrez peut-être en faire un peu plus, comme définir la catégorie d'itérateur, le type de différence, la référence, etc., pour que le compilateur accepte l'itérateur.]

Et la sortie est:

y
y
time1: 1833ns
time2: 2933ns

[Bien sûr, si vous exécutez le code, vos résultats ne correspondront pas exactement à ceux-ci.]

Donc, même pour ce cas simple (et en ne faisant que 80 incréments et comparaisons), nous avons ajouté environ 60% de surcharge à une simple recherche linéaire. Surtout lorsque les itérateurs ont été initialement ajoutés au C ++, un certain nombre de personnes n'auraient tout simplement pas accepté un design avec autant de frais généraux. Ils n'auraient probablement pas été standardisés, et même s'ils l'avaient été, pratiquement personne ne les utiliserait.

La différence est entre ce qu'est quelque chose et comment se comporte quelque chose.

Beaucoup de langues essaient de confondre les deux, mais ce sont des choses bien distinctes.

Si comment est quoi et comment est-il ...

Si tout hérite objectalors certains avantages se produisent comme: n'importe quelle variable d'objet peut contenir n'importe quelle valeur. Mais c'est aussi le hic, tout doit se comporter ( le comment ) comme un object, et ressembler ( au quoi ) un object.

Mais:

• Et si votre objet n'a pas de définition significative de l'égalité?
• Et s'il n'a pas de hachage significatif?
• Et si votre objet ne peut pas être cloné, mais que des objets peuvent l'être?

Soit le objecttype devient essentiellement inutile - car l'objet ne fournit aucun point commun entre toutes les instances possibles. Ou il existera des objets qui ont une définition cassée / à cornes de chaussure / absurde d'une propriété universelle présumée trouvée sur objectlaquelle prouve un comportement presque universel à l'exception d'un certain nombre de pièges.

Si ce qui n'est pas lié à comment

Alternativement, vous pouvez séparer le Quoi et le Comment . Ensuite, plusieurs types différents (avec rien en commun du tout quoi ) peuvent tous se comporter de la même manière que vu par le collaborateur le comment . En ce sens, l'idée d'un Iteratorn'est pas un quoi spécifique , mais un comment . Plus précisément, comment interagissez-vous avec une chose lorsque vous ne savez pas encore avec quoi vous interagissez.

Java (et similaire) permet des approches à cela en utilisant des interfaces. Une interface à cet égard décrit les moyens de communication, et implicitement un protocole de communication et d'action qui est suivi. Tout Quoi qui se déclare être d'un Comment donné , déclare qu'il soutient la communication et l'action pertinentes décrites par le protocole. Cela permet à tout collaborateur de compter sur la Comment et non s'enliser en précisant exactement quels Quelles « s peuvent être utilisés.

C ++ (et similaire) permet des approches à cela en tapant du canard. Un modèle ne se soucie pas si le type collaborateur déclare qu'il suit un comportement, juste que dans un contexte de compilation donné, avec lequel l'objet peut interagir d'une manière particulière. Cela permet aux pointeurs C ++ et aux opérateurs spécifiques dépassant les objets d'être utilisés par le même code. Parce qu'ils répondent à la liste de contrôle pour être considérés comme équivalents.

• prend en charge * a, a->, ++ a et a ++ -> itérateur d'entrée / transfert
• prend en charge * a, a->, ++ a, a ++, --a et a-- -> itérateur bidirectionnel

Le type sous-jacent n'a même pas besoin d'itérer un conteneur, il peut être n'importe quoi . De plus, cela permet à certains collaborateurs d'être encore plus génériques, imaginez qu'une fonction n'a besoin que a++, un itérateur peut le satisfaire, tout comme un pointeur, un entier, tout comme n'importe quel objet à implémenter operator++.

Spécifications inférieures et supérieures

Le problème avec les deux approches est sous et sur-spécifié.

L'utilisation d'une interface nécessite que l'objet déclare qu'il prend en charge un comportement donné, ce qui signifie également que le créateur doit l'imprégner dès le début. Cela fait que certains What 's ne font pas la coupe, car ils ne l'ont pas déclaré. Cela signifie également que toujours ce qui a un ancêtre commun, l'interface représentant le comment . Cela revient au problème initial de object. Cela oblige les collaborateurs à sur-spécifier leurs besoins, tout en rendant simultanément certains objets inutilisables en raison d'un manque de déclaration, ou des accrochages cachés car un comportement attendu est mal défini.

L'utilisation d'un modèle nécessite que le collaborateur travaille avec un Quoi complètement inconnu , et à travers ses interactions il définit un Comment . Dans une certaine mesure, cela rend la rédaction des collaborateurs plus difficile, car elle doit analyser le Quoi pour ses primitives de communication (fonctions / champs / etc.) tout en évitant les erreurs de compilation, ou au moins indiquer comment un Quoi donné ne correspond pas à ses exigences pour le Comment . Cela permet au collaborateur d'exiger le minimum absolu de tout ce qui est donné, ce qui permet d'utiliser la plus large gamme de ce qui est utilisé. Malheureusement, cela a l'inconvénient de permettre des utilisations insensées d'objets qui fournissent techniquement les primitives de communication pour unComment , mais ne suivez pas le protocole implicite permettant à toutes sortes de mauvaises choses de se produire.

Itérateurs

Dans ce cas , un Iteratorest un Comment est un raccourci pour une description de l' interaction. Tout ce qui correspond à cette description est par définition un Iterator. Savoir comment nous permet d'écrire des algorithmes généraux et d'avoir une courte liste de « comment » est donné un quoi spécifique qui doit être fourni afin de faire fonctionner l'algorithme. Cette liste est la fonction / propriétés / etc, leur implémentation prend en compte ce que spécifique est traité par l'algorithme.

Parce que C ++ n'a pas besoin d'avoir des classes de base (abstraites) pour faire du polymorphisme. Il a un sous-typage structurel ainsi qu'un sous-typage nominatif .

Confusément dans le cas particulier des itérateurs, les normes précédentes définies std::iteratorcomme (approximativement)

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

C'est-à-dire en tant que simple fournisseur des types de membres requis. Il n'avait aucun comportement d'exécution et était obsolète en C ++ 17

Notez que même cela ne peut pas être une base commune, car un modèle de classe n'est pas une classe, chaque instanciation est indépendante des autres.

L'une des raisons est que les itérateurs ne doivent pas nécessairement être des instances d'une classe. Les pointeurs sont de très bons itérateurs dans de nombreux cas, par exemple, et comme ce sont des primitifs, ils ne peuvent hériter de rien.