Itérateurs en C++ (stl) vs Java, y a-t-il une différence conceptuelle ?

StackOverflow https://stackoverflow.com/questions/56347

  •  09-06-2019
  •  | 
  •  

Question

Je reviens au C++ après avoir été absent un moment et essayé de dépoussiérer le vieux melon.

En Java, Iterator est une interface vers un conteneur ayant des méthodes :hasNext(), next() et remove().La présence de hasNext() signifie que a le concept de limite pour le conteneur traversé.

//with an Iterator
Iterator<String> iter = trees.iterator();
while (iter.hasNext()) 
{
    System.out.println(iter.next());
}

Dans la bibliothèque de modèles standard C++, les itérateurs semblent représenter un type de données ou une classe qui prend en charge l'opérateur++ et l'opérateur== mais a aucune notion de limite intégré, une comparaison est donc nécessaire avant de passer à l’élément suivant.La limite doit être vérifiée par l'utilisateur en comparant deux itérateurs. Dans le cas normal, le deuxième itérateur est la fin du conteneur.

vector<int> vec;
vector<int>::iterator iter;

// Add some elements to vector
v.push_back(1);
v.push_back(4);
v.push_back(8);

for(iter= v.begin(); iter != v.end(); iter++)
{
    cout << *i << " "; //Should output 1 4 8
}

La partie intéressante ici est qu’en C++, un pointeur est un itérateur vers un tableau.Le TSL a pris ce qui existait et a construit une convention autour de cela.

Y a-t-il une autre subtilité qui me manque ?

Était-ce utile?

La solution

Oui, il existe une grande différence conceptuelle.C++ utilise différentes « classes » d’itérateurs.Certains sont utilisés pour un accès aléatoire (contrairement à Java), d'autres sont utilisés pour un accès direct (comme Java).Alors que d'autres encore sont utilisés pour écrire des données (pour une utilisation avec, par exemple, transform).

Voir le concept des itérateurs dans le Documentation C++:

  • Itérateur d'entrée
  • Itérateur de sortie
  • Itérateur avant
  • Itérateur bidirectionnel
  • Itérateur d'accès aléatoire

Ceux-ci sont bien plus intéressants et puissants que les petits itérateurs de Java/C#.Espérons que ces conventions seront codifiées à l'aide de C++0x Concepts.

Autres conseils

Peut-être un peu plus théorique.Mathématiquement, les collections en C++ peuvent être décrites comme un intervalle semi-ouvert d'itérateurs, à savoir un itérateur pointant vers le début de la collection et un itérateur pointant vers juste derrière le dernier élément.

Cette convention ouvre une multitude de possibilités.De la même manière que les algorithmes fonctionnent en C++, ils peuvent tous être appliqués aux sous-séquences d’une collection plus grande.Pour que cela fonctionne en Java, vous devez créer un wrapper autour d'une collection existante qui renvoie un itérateur différent.

Un autre aspect important des itérateurs a déjà été mentionné par Frank.Il existe différents concepts d'itérateurs.Les itérateurs Java correspondent aux itérateurs d'entrée C++, c'est-à-direce sont des itérateurs en lecture seule qui ne peuvent être incrémentés qu'une étape à la fois et ne peuvent pas revenir en arrière.

À l’autre extrême, vous avez des pointeurs C qui correspondent exactement au concept C++ d’itérateur à accès aléatoire.

Dans l’ensemble, C++ offre un concept beaucoup plus riche et plus pur qui peut être appliqué à une bien plus grande variété de tâches que les pointeurs C ou les itérateurs Java.

Comme mentionné, les itérateurs Java et C# décrivent une position (état) et une plage (valeur) mélangées, tandis que les itérateurs C++ séparent les concepts de position et de plage.Les itérateurs C++ représentent « où suis-je maintenant » séparément de « où puis-je aller ? ».

Les itérateurs Java et C# ne peuvent pas être copiés.Vous ne pouvez pas récupérer une position précédente.Les itérateurs C++ courants le peuvent.

Considérer cet exemple:

// for each element in vec
for(iter a = vec.begin(); a != vec.end(); ++a){
  // critical step!  We will revisit 'a' later.
  iter cur = a; 
  unsigned i = 0;
  // print 3 elements
  for(; cur != vec.end() && i < 3; ++cur, ++i){
      cout << *cur << " ";
  }
  cout << "\n";
}

Cliquez sur le lien ci-dessus pour voir la sortie du programme.

Cette boucle plutôt idiote parcourt une séquence (en utilisant uniquement la sémantique de l'itérateur direct), imprimant chaque sous-séquence contiguë de 3 éléments exactement une fois (et quelques sous-séquences plus courtes à la fin).Mais en supposant N éléments et M éléments par ligne au lieu de 3, cet algorithme serait toujours constitué d'incréments d'itérateur O(N*M) et d'espace O(1).

Les itérateurs de style Java n'ont pas la capacité de stocker la position de manière indépendante.Vous le ferez soit

  • perdre de l'espace O(1), en utilisant (par exemple) un tableau de taille M pour stocker l'historique au fur et à mesure de votre itération
  • devra parcourir la liste N fois, ce qui fait un temps O(N^2+N*M)
  • ou utilisez un type Array concret avec la fonction membre GetAt, perdant le généricité et la possibilité d'utiliser des types de conteneurs de liste chaînée.

Étant donné que seuls les mécanismes d'itération avant ont été utilisés dans cet exemple, j'ai pu échanger une liste avec pas de problème.Ceci est essentiel à la création d’algorithmes génériques, tels que la recherche, l’initialisation et l’évaluation retardées, le tri, etc.

L’incapacité à conserver l’état correspond le plus à l’itérateur d’entrée C++ STL, sur lequel très peu d’algorithmes sont construits.

Un pointeur vers un élément du tableau est en effet un itérateur dans le tableau.

Comme vous le dites, en Java, un itérateur a plus de connaissances sur le conteneur sous-jacent qu'en C++.Les itérateurs C++ sont généraux et un paire des itérateurs peuvent désigner n’importe quelle plage :cela peut être une sous-plage d'un conteneur, une plage sur plusieurs conteneurs (voir http://www.justsoftwaresolutions.co.uk/articles/pair_iterators.pdf ou http://www.boost.org/doc/libs/1_36_0/libs/iterator/doc/zip_iterator.html) ou même une plage de nombres (voir http://www.boost.org/doc/libs/1_36_0/libs/iterator/doc/counting_iterator.html)

Les catégories d'itérateur identifient ce que vous pouvez et ne pouvez pas faire avec un itérateur donné.

Pour moi, la différence fondamentale est que les itérateurs Java pointent entre les éléments, tandis que les itérateurs C++ STL pointent vers les éléments.

Les itérateurs C++ sont une généralisation du concept de pointeur ;ils le rendent applicable à un plus large éventail de situations.Cela signifie qu’ils peuvent être utilisés pour définir des plages arbitraires, par exemple.

Les itérateurs Java sont des énumérateurs relativement stupides (mais pas aussi mauvais que ceux de C# ;au moins Java a ListIterator et peut être utilisé pour muter la collection).

Les itérateurs ne sont équivalents aux pointeurs que dans le cas trivial d’une itération séquentielle sur le contenu d’un tableau.Un itérateur peut fournir des objets à partir de nombreuses autres sources :à partir d'une base de données, d'un fichier, du réseau, d'un autre calcul, etc.

Les itérateurs de la bibliothèque C++ (anciennement connue sous le nom de STL) sont conçus pour être compatibles avec les pointeurs.Java, sans arithmétique de pointeur, avait la liberté d'être plus convivial pour les programmeurs.

En C++, vous devez utiliser une paire d'itérateurs.En Java, vous utilisez soit un itérateur, soit une collection.Les itérateurs sont censés être le lien entre l’algorithme et la structure des données.Le code écrit pour 1.5+ a rarement besoin de mentionner les itérateurs, à moins qu'il n'implémente un algorithme ou une structure de données particulière (ce que la grande majorité des programmeurs n'ont pas besoin de faire).Comme Java opte pour les sous-ensembles de polymorphisme dynamique et autres, ils sont beaucoup plus faciles à gérer.

Il existe de nombreuses bonnes réponses sur les différences, mais j'ai senti que la chose qui m'énervait le plus avec les itérateurs Java n'était pas soulignée : vous ne pouvez pas lire la valeur actuelle plusieurs fois.Ceci est vraiment utile dans de nombreux scénarios, notamment lorsque vous fusionnez des itérateurs.

En C++, vous disposez d'une méthode pour faire avancer l'itérateur et lire la valeur actuelle.La lecture de sa valeur ne fait pas avancer l'itération ;vous pouvez donc le lire plusieurs fois.Ce n'est pas possible avec les itérateurs Java, et je finis par créer des wrappers qui font cela.

Une remarque complémentaire :un moyen simple de créer un wrapper consiste à en utiliser un existant :PeekingItérateur de Goyave.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top