Qu’est-ce qu’un itérateur en général?

Question

Ce problème arrive lorsque j'ai essayé d'écrire une classe C++ template avec ctor qui acceptent général "itérateur". Je ne sais pas si il est approprié d'utiliser le mot général , mais ce que je veux dire c'est qu'il peut accepter itérateur comme conteneur STL.

En d'autres mots, je suis confus au sujet de itérateur. Il semble que tous les conteneur STL a le même type d'itérateur, alors c'est quoi ce type? Est-il juste de pointeur? Ou quelque chose de plus compliqué? Mais conteneur STL faire accepter une forme normale.

(Je tiens à le comparer à l' Iterator<T> en Java, ce qui est assez simple et il est juste une classe)

Answer 1

En C++ un Itérateur est un concept, pas un de béton (ou abstrait), mais tout type qui obéit à certaines itérateur comme des règles.

Par exemple itérateurs peuvent généralement être incrémenté ++i. Ils peuvent être consultés (déréférencé) *i pour obtenir la valeur qu'ils pointent actuellement à. Ils sont essentiellement des abstractions d'un pointeur.

Dans la Bibliothèque Standard de conteneurs et algorithmes il existe différents types d'itérateurs avec des propriétés différentes. Leurs propriétés sont répertoriées ici:

https://en.cppreference.com/w/cpp/iterator

Donc, lors de l'écriture d'algorithmes en C++ qui acceptent les itérateurs, généralement juste accepter générique paramètres du modèle et utilisent l'itérateur de propriétés dans la fonction. Le compilateur va se plaindre si l'utilisateur passe quelque chose à votre fonction qui n'obéissent pas à l'itérateur règles:

template<typename Iterator>
void my_algorithm(Iterator begin, Iterator end)
{
    for(; begin != end; ++begin)
        std::cout << *begin << '\n';
}

Vous pouvez ajouter tout un tas de contrôles spécifiques assurez-vous que l'utilisateur est passé quelque chose de sensé, mais c'est trop large pour cette question.

Note:

Tandis que actuellement concepts, tels que l' Itérateur, sont un ensemble d'accord sur les propriétés sémantiques dans la Norme que les programmeurs doivent suivre, une solution plus complète qui permettra de formaliser ces concepts (en code) est prévu pour la prochaine version de la Norme, C++20.

Answer 2

Les itérateurs comme " un concept qui viennent avant le C++ standard.

C++ a commencé comme C avec des classes. Plus de fonctionnalités ont été ajoutées, et l'accroissement exponentiel du nombre de gens se sont intéressés à la langue.

Un point très important, peu de travail a été appelée la STL -- la Bibliothèque de modèles Standard -- écrit à l'origine par Stepanov et Lee. en 1994 chez Hewlett-Packard, plus tard maintenu par SGI.

Cette bibliothèque a utilisé le modèle de la métaprogrammation partie de C++ dans bien des méthodes révolutionnaires. Il a été écrit pour permettre à proximité de nu-metal performance avec des types abstraits, avec des implémentations d'algorithmes divorcé d'implémentations de conteneur, pour près de types arbitraires.

Les itérateurs sont un Concept -- un genre plus élevé, de type

En elle, l'itérateur est un concept. Un concept en C++ est une catégorie de types (type de types que vous pourriez dire). Notions en C++ sont pas appliquées par le compilateur (à cette époque).

Un type qui satisfait à l'un concept si il a les opérations requises, et les opérations de respecter les règles de la notion.

Il y a une hiérarchie de concepts autour des itérateurs dans la STL et plus tard dans la norme C++. Ils vont de la mesure la moins restrictive (un itérateur) pour la plupart (lecture-écriture à accès aléatoire contiguë itérateur), et la forme d'un arbre.

Modèle de fonctions de fonctions d'écriture

Lorsqu'un algorithme modèle demande un Itérateur, ils demandent un type qui satisfait le concept d'Itérateur (comme décrit dans la norme C++). Quand ils demandent un RandomAccessIterator, ils demandent pour un type qui satisifies la RandomAccessIterator concept (qui comprend également le concept d'Itérateur, le ForwardIterator concept, et quelques autres).

Donc, template<class ForwardIterator> void std::sort( ForwardIterator, ForwardIterator ) est un modèle de fonction qui prend deux instances d'un même type qui remplissent les ForwardIterator concept.

ForwardIterators à l'appui un certain nombre d'opérations (*it, ++it, bool b = it != it, bool b = it == it, etc), suport certains traits (iterator_traits<it>::iterator_category, iterator_traits<it>::reference, iterator_traits<it>::value_type, etc), et ces opérations doivent suivre certaines règles.

Si vous nourrissez un type qui satisfait RandomAccessIterator, std::sort garantit de meilleures performances que si passé un ForwardIterator.

Un pointeur brut répond à la fois à l'avenir RandomAccess itérateur sans que vous fassiez quoi que ce soit. std::vector<?>::iterator également satisifes à la fois, mais souvent, ce n'est pas un pointeur brut (std bibliothèque fait un peu de travail).

Les deux types -- le pointeur brut et std::vector<?>::iterator - sont généralement sans rapport avec les types. C++de modèle et les traits d'un système de permis sans rapport avec les types à être entendu par le même algorithme modèle avec zéro gestion d'exécution.

En c++2a il est prévu d'introduire dans la langue des Concepts réellement vérifier certaines des exigences pour des choses comme RandomAccessIterator, et document en langue des autres conditions qu'il est pratiquement impossible d'être vérifié.

C++ n'est pas un OO-langue

Vous êtes peut-être confondu par être utilisé pour les langages orientés objets. C++ prend en charge la programmation orientée objet, mais n'est pas un langage orienté objet. Il prend en charge le polymorphisme -- le traitement de plusieurs types de la même, - sans objet à base d'héritage dans un certain nombre de façons.

Dans un langage orienté objet, chaque itérateur allait hériter d'un résumé itérateur de type. Les algorithmes peuvent interagir avec l'itérateur par l'intermédiaire de cette interface abstraite, souvent dispatching des appels via une fonction virtuelle tableau d'une certaine sorte. Les valeurs de type ne serait pas possible, comme le code de l'algorithme serait compilé sans savoir combien d'octets sont les itérateurs de prendre, de manière supplémentaire d'indirection allait se produire.

En C++, l'algorithme n'est pas une fonction jusqu'à ce que vous passiez le type de l'itérateur. À ce stade, la fonction est écrit sur mesure pour que l'itérateur. Le C++ standard stipule que si l'itérateur certaines choses (qui obéit à la Notion requis), que la fonction écrite par le modèle aura un certain comportement.

Ce modèle écrite à la fonction sait comment grand l'itérateur est, ce que les opérations ne peuvent inline les opérations et stocker les instances de l'itérateur dans les tampons ou sur la pile comme une valeur. À moins que l'itérateur forces, il n'est pas virtuel expédition, et si les opérations sont visibles, ils peuvent être incorporé dans les écrits de la fonction.

Boucles serrées peuvent être examinés par le compilateur et la vectorisation peut se produire, comme si on écrit la fonction main.

Le même modèle peut trier les entrées de base de données ou de chaînes de caractères ou des nombres entiers; chaque fois, une nouvelle fonction est écrite, et le compilateur est dit d'essayer de le faire aller plus vite.

TL;DR

Les itérateurs sont pas un type; ils sont un genre de type. Complètement sans rapport avec les types peuvent être tous les deux itérateurs. Il n'y a pas de classe de base pour les itérateurs; il y a juste certaines façons de garantir qu'ils se comportent.

C++ algorithmes génère un code personnalisé pour chaque type d'itérateur vous passez std::sort; si vous trier un vecteur de type int et un vecteur de chaînes, pas de code binaire est partagée entre les deux (à l'exception de la possibilité de pliage de comdat).

Les concepts (le genre de type) Itérateur/ForwardIterator/RandomAccessIterator sont documentées exigences sur les types passé au C++ algorithmes. Aucune application n'est fait, d'autres que le compilateur est libre de faire littéralement rien si vous ne respectez pas les exigences.

Answer 3

Iterator est un modèle de conception comportementale décrit dans le cadre de "Gang of four design patterns". Il résout un problème avec itérer sur des objets dans un objet agrégé sans connaître la structure interne de cet objet.

Se référer ci-dessous pour plus de détails sur le modèle itérateur: http://www.blackwasp.co.uk/Iterator.aspx