Itérateur

Le terme itérateur vient du domaine du développement logiciel et décrit un pointeur avec lequel les éléments d'un ensemble peuvent être itérés (par exemple une liste). Le terme est dérivé de la méthode mathématique d' itération . L'itérateur est généralement appelé le curseur , en particulier dans le champ de la base de données .

la description

Un itérateur est un pointeur spécial qui peut être utilisé dans un programme par le développeur du logiciel pour accéder aux éléments d'un ensemble, en d'autres termes à une liste. Les itérateurs fonctionnent sur le principe de base "S'il y a un autre élément dans la liste, alors rendez-le disponible."

En termes simplifiés, cela revient à lire un texte qui est une liste de mots: «S'il y a un mot suivant, lisez-le. Lorsqu'il n'y a plus de mot, le texte est terminé. »À chaque étape d'accès appelée itération, exactement un mot du texte est disponible pour le traitement.

De nombreux itérateurs utilisés dans la pratique de la programmation fournissent des mécanismes au-delà de l'accès en lecture qui suppriment un élément actuellement lu de la liste ou ajoutent un nouvel élément à la liste, tout comme des mots peuvent être insérés ou supprimés lors de l'édition d'un texte.

Itérateurs externes et modèle de conception d'itérateur

Un itérateur externe peut être vu comme une sorte de pointeur qui a deux fonctions principales: référencer un certain élément dans un ensemble d'objets (appelé accès aux éléments ) et pointer vers l'élément suivant de l'ensemble par auto-modification (appelé parcours d'élément ). En fonction du langage de programmation utilisé et de l'application, les itérateurs peuvent avoir des fonctionnalités supplémentaires et un comportement différent.

Le but principal de l'itérateur est de permettre à l'utilisateur d'accéder à n'importe quel élément d'un ensemble tout en l'isolant de la structure de données de l'ensemble. Cela permet à la foule de gérer les éléments de toutes les manières possibles, tout en agissant pour l'utilisateur comme s'il s'agissait d'une simple séquence ou liste. Une classe d'itérateur est conçue en étroite coordination avec sa classe de conteneur, c'est-à-dire son ensemble. Habituellement, la classe conteneur fournit les fonctions utilisées pour créer des itérateurs. Un compteur dans une boucle (également appelé compteur de boucle) est parfois appelé un itérateur de boucle. Il convient de noter qu'un tel compteur ne mappe que la fonctionnalité de traversée d'élément et non la fonctionnalité d' accès aux éléments .

Itérateurs implicites

Plusieurs langages orientés objet tels que Perl , Python , C # , Ruby ainsi que les versions plus récentes de Java et Delphi fournissent un moyen intrinsèque d'itérer des éléments sans utiliser d' objet itérateur explicite. Cependant, cela peut également être présent, mais n'est pas disponible dans le code du langage de programmation respectif si cela devait être le cas.

Les itérateurs implicites se manifestent souvent via la commande foreach ou ses équivalents, comme indiqué dans l'exemple Python ci-dessous:

for value in iterable:
    print(value)

L'ensemble / liste iterableest parcouru en utilisant la forboucle; à chaque passage de boucle, la variable valuecontient l'élément courant iterable.

Parfois, les itérateurs sont également générés directement à partir de l'objet de collecte de données, comme le montre l'exemple Ruby ci-dessous:

iterable.each do |value|
    puts value
end

L'appel de la méthode de eachl'ensemble / de la liste iterablefournit un itérateur, que la doboucle parcourt élément par élément. Le corps de la boucle est puts valueexécuté pour chaque élément , la variable valuecontenant l'élément courant.

Ce style d'itération est également appelé itération interne car son code est complètement exécuté dans le contexte de l'objet à itérer. Cela contrôle tous les aspects de l'itération, l'utilisateur ou le programmeur respectif ne fournit l'opération que pour les étapes d'itération individuelles en utilisant un sous-programme anonyme .

Les langages qui prennent en charge les extensions de liste ou les constructions similaires, analogues à Python, utilisent également les itérateurs implicites lors de la création de la liste de résultats:

names = [person.name for person in roster if person.male]

for ... in ...voici la "boucle" au-dessus de la quantité / liste rosteravec "variable élément courant" person. Pour chaque élément, on vérifie si une condition s'applique (pour l'élément), c'est if person.male-à- dire que la quantité est filtrée. Les éléments restants sont copiés person.namedans la namesliste de résultats - une liste de noms.

Parfois, la nature implicite et cachée n'est que partiellement présente. Le langage de programmation C ++ fournit la fonctionnalité for_each via des modèles de fonctions , ce qui permet une itération implicite.

Le contraire de l'indexation

L'itérateur est en contraste avec un index ou une clé :

L'élément associé est accessible directement via un itérateur sans connaître la structure de données elle-même. Avec un index, vous avez toujours besoin d'un index et d'une structure de données.
Un itérateur n'est valide que pour exactement une structure de données. Un index peut être transféré vers d'autres structures de données.
Les itérateurs ne peuvent pas être sérialisés . Pour ce faire, ils doivent d'abord être convertis en index.

La capacité d'un conteneur à se modifier tout en itérant à travers ses éléments s'est avérée importante dans les langages de programmation modernes orientés objet. Les relations entre les objets individuels et les effets de leurs opérations ne sont plus claires dans ces langages. Les itérateurs sont utilisés pour résoudre ce problème.

Générateurs

Un générateur est une forme spéciale d'une coroutine qui renvoie un (ou plusieurs) élément (s) d'une séquence à chaque fois qu'elle est appelée. Cette séquence peut être une liste donnée, auquel cas le générateur correspond largement à un itérateur. Un générateur ne peut également générer les éléments (suivants) que lorsqu'ils sont appelés - alors il n'a pas besoin d'une liste existante, comme cela est nécessaire pour l'itérateur.

La plupart des itérateurs peuvent être implémentés naturellement et intuitivement par des générateurs. Étant donné que les générateurs conservent leur état local entre les appels de fonction, ils sont idéaux pour implémenter des itérateurs avec état complexes tels que des traverseurs d'arbres binaires .

Exemple de générateur qui crée des éléments au lieu de les lire à partir d'une liste:

( Séquence de Fibonacci ; "retour" de la valeur respective à l'aide de la commande Python yield)

# Ein Generator für die Fibonacci-Folge
def fibonacci(limit_anzahl_elemente):
    a, b = 0, 1

    for _ in range(limit_anzahl_elemente):
        a, b = b, a + b
        yield a

# Die ersten Zahlen der Folge werden berechnet und ausgegeben
for number in fibonacci(100):
    print(number)

Itérateurs dans différents langages de programmation

C # et autres langages .NET

Les itérateurs dans le framework .NET sont appelés énumérateurs et sont représentés par l'interface IEnumerator. IEnumeratorfournit une fonction appelée MoveNext()qui va à l'élément suivant de l'ensemble et montre quand la fin a été atteinte, ainsi qu'une propriété appelée Currentpour obtenir la valeur de l'élément courant. De plus, une Reset()fonction optionnelle est proposée pour revenir au début. L'énumérateur renvoie une valeur spéciale comme valeur d'initialisation, qui marque le début. Pour cette raison, il est nécessaire d' MoveNext()exécuter après l'initialisation .

Les énumérateurs sont généralement renvoyés par une GetEnumerator()fonction associée à un objet qui IEnumerableimplémente l' interface. La commande foreach en C # fonctionne sur une telle fonction, même si elle ne provient pas d'un objet qui IEnumerableimplémente l' interface. L'exemple suivant montre une utilisation simple des itérateurs en C # 2.0:

// explizite Version
IEnumerator<MyType> iter = list.GetEnumerator();
while (iter.MoveNext())
    Console.WriteLine(iter.Current);

// implizite Version
foreach (MyType item in list)
    Console.WriteLine(item);

C # 2.0 prend également en charge les générateurs: une fonction qui renvoie comme IEnumerable(ou aussi IEnumerator) mais yield returnutilise la commande est automatiquement convertie par le compilateur en une nouvelle classe qui implémente l'interface appropriée.

C ++

Le langage de programmation C ++ utilise des itérateurs à grande échelle et fournit des itérateurs de différents types tels que des itérateurs avant , des itérateurs bidirectionnels et des itérateurs à accès aléatoire via la bibliothèque standard C ++ . Chacune des classes de conteneur standard a des types d'itérateur. La syntaxe des itérateurs standard était basée sur l' arithmétique des pointeurs de C. Les opérateurs et sont utilisés pour référencer les éléments. D'autres opérateurs tels que sont utilisés pour naviguer dans les éléments. *->++

Les itérateurs sont généralement utilisés par paires. Un itérateur représente l'itération actuelle, tandis que l'autre représente la fin de l'itération. Les itérateurs sont générés par la classe de conteneur correspondante à l'aide des fonctions standard begin()et end(). L'itérateur begin()retourné par pointe vers le premier élément, tandis que l'itérateur end()retourné par pointe vers une valeur spéciale qui ne fait référence à aucun élément. Si un itérateur est placé après le dernier élément, il renvoie la valeur spéciale de end(). L'exemple suivant montre l'utilisation typique d'un itérateur en C ++:

ContainerType c; // Ein beliebiger Standard-Containertyp, wie std::list<sometype>

for (ContainerType::const_iterator constIt = c.begin(); constIt != c.end(); ++constIt) {
    std::cout << *constIt << '\n';
}

Il existe de nombreux types d'itérateurs avec un comportement légèrement différent. Tous les types d'itérateur ne prennent pas en charge tous les types de conteneurs. Cependant, il est possible pour les programmeurs de définir leurs propres types d'itérateur en dérivant une classe du modèle std::iterator. La sécurité de l'itérateur est définie séparément pour les différents types. L'itération implicite est partiellement disponible en C ++ et est assurée par les fonctions std::for_each(), std::copy()et std::accumulate(). Cependant, les itérateurs ont toujours besoin d'un objet explicite pour les initialiser, généralement ceux qui sont retournés par begin()et end(). Une fois cela fait, l'itération se fait implicitement sans utiliser l'objet iterator. L'exemple ci-dessous montre l'utilisation de for_each:

// Ein beliebiger Standard-Containertyp jedes ItemType Elements
ContainerType<ItemType> c;

// Funktion, die Zugriff auf jedes Element besitzt
void processItem(const ItemType& i) {
    std::cout << i << '\n';
}

// Eine for-each-Iterationsschleife
std::for_each(c.begin(), c.end(), processItem);

La même chose peut être obtenue en utilisant std::copyet std::ostream_iterator:

std::copy(C.begin(), C.end(), std::ostream_iterator<ItemType>(std::cout, "\n"));

Une limitation de cette technique est qu'elle ne permet pas de déclarer la coque en ligne. De plus, cela nécessite un pointeur de fonction, qui doit être déclaré ailleurs et passé en paramètre. Cela peut être partiellement compensé par l'utilisation de bibliothèques telles que Boost et l'utilisation de Lambda, qui sont utilisées pour générer des objets de fonction avec une syntaxe d'infixe associée. Étant donné que cette fonctionnalité n'est disponible que via des bibliothèques externes, diverses solutions de contournement , également appelées solutions de contournement , doivent être utilisées.

Java

L'interface java.util.Iterator, qui a été introduite dans Java JDK 1.2, permet d'itérer les classes de conteneurs. Chacun Iteratorfournit des fonctions appelées next(), hasNext()ainsi qu'une fonction facultative appelée remove(). Les itérateurs sont généralement iterator()générés par une fonction appelée , qui est mise à disposition par la classe de conteneur correspondante. Un itérateur renvoie une valeur spéciale comme valeur d'initialisation, qui marque le début. Pour cette raison, il est nécessaire d' next()exécuter après l'initialisation , ce qui retournera le premier élément. La fonction hasNext()permet de savoir si le dernier élément a déjà été renvoyé. L'exemple suivant montre une utilisation simple des itérateurs en Java:

Iterator iter = list.iterator();

while (iter.hasNext())
    System.out.println(iter.next());

Pour les collections qui le prennent en charge, la fonctionnalité facultative supprime remove()le dernier élément auquel vous avez accédé. La plupart des autres modifications de ce type ne sont pas sûres. En outre, java.util. Listun itérateur appelé itérateur ListIterator, qui fournit une interface similaire qui permet une itération avant et arrière ainsi que renvoie l'index de l'élément courant et peut insérer l'élément à une position donnée.

Avec J2SE 5.0, l'interface a été Iterableintroduite, qui représente une boucle for étendue au sens de foreach. Iterabledéfinit la fonction iterator()qui Iteratorvous renvoie. En utilisant la boucle for étendue, l'exemple précédent peut être écrit de la manière suivante:

for (MyType obj: list)
    System.out.print(obj);

MATLAB

MATLAB prend en charge les itérateurs externes et internes. Dans le cas d'une itération externe, dans laquelle l'utilisateur est obligé de fournir l'élément suivant, plusieurs éléments peuvent être définis puis exécutés avec une boucle for, comme le montre l'exemple suivant:

% Definition eines an integer arrays
myArray = [1, 3, 5, 7, 11, 13];

for n = myArray
   % ... etwas mit n machen...
   disp(n) %Integerausgabe zur Kommandozeile
end

Dans le cas d'une itération interne, l'utilisateur peut passer une opération à l'itérateur pour accéder à chaque élément d'un tableau. De nombreux opérateurs natifs et fonctions MATLAB sont surchargés pour obtenir un tableau de sortie correspondant en tant que valeur de retour implicite. En outre, les fonctions arrayfunet peuvent être utilisées cellfunpour des opérations définies par l'utilisateur via des tableaux natifs et ce que l'on appelle des tableaux de cellules .

function simpleFun
% Definition eines an integer arrays
myArray = [1, 3, 5, 7, 11, 13];

% Benutzerdefinierte Operation für jedes Element durchführen
myNewArray = arrayfun(@(a)myCustomFun(a), myArray);

% Arrayausgabe zur Kommandozeile
myNewArray

function outScalar = myCustomFun(inScalar)
% Mit 2 multiplizieren
outScalar = 2 * inScalar;

En variante, il peut être souhaitable d'abstraire les mécanismes de stockage de la matrice de la programmation en fournissant une implémentation personnalisée, orientée objet du modèle de conception d'itérateur. Une telle implémentation, qui prend en charge l'itération externe, est proposée dans l'élément MATLAB Central File Exchange. Ce modèle de conception est écrit selon la nouvelle syntaxe de définition de classe qui a été introduite avec MATLAB version 7.6 (R2008a). En outre, une implémentation de matrice de cellules unidimensionnelle du type de données abstrait de liste est incluse afin de stocker chaque type de données de manière hétérogène. Il fournit la fonctionnalité de traiter une liste hasNext(), next()et reset()dans un tout boucle.

PHP

Avec PHP4, une foreachconstruction a été introduite qui a été structurée de manière similaire à Perl et à de nombreux autres langages de programmation. Cette construction permet un moyen simple d'itérer sur des tableaux. La foreachcommande ne fonctionne qu'avec des tableaux en PHP4 et générera une erreur si vous essayez de l'utiliser sur un type de données différent ou une variable non initialisée. En PHP5, la foreachcommande d'itérer sur tous les membres publics est autorisée. L'exemple suivant montre deux notations différentes, la seconde est une extension utile de la première notation:

Exemple A.

foreach (array_expression as $value)
    echo "$value\n"

Exemple B.

foreach (array_expression as $key => $value)
    echo "($key)$value\n";

Dans l'exemple A, un tableau représenté par array_expression est itéré. À chaque passage de boucle, la valeur de l'élément du tableau est $valueaffectée et le pointeur interne du tableau est poussé en avant de un. Cela signifie que l'élément de tableau suivant est renvoyé lors de la prochaine passe de boucle. L'exemple B a la même fonctionnalité que l'exemple A. De plus, l'index de l'élément est affecté à la variable à chaque fois qu'elle est bouclée $key.

En PHP5, l'interface de l'itérateur est prédéfinie, les objets peuvent être modifiés pour gérer l'itération.

class MyIterator implements Iterator {
    private $var = array();

    public function __construct($array) {
        if (is_array($array)) {
            $this->var = $array;
        }
    }

    public function rewind() {
        echo "rewinding\n";
        reset($this->var);
    }

    public function current() {
        $var = current($this->var);
        echo "current: $var\n";
        return $var;
    }

    public function key() {
        $var = key($this->var);
        echo "key: $var\n";
        return $var;
    }

    public function next() {
        $var = next($this->var);
        echo "next: $var\n";
        return $var;
    }

    public function valid() {
        $var = $this->current() !== false;
        echo "valid: {$var}\n";
        return $var;
    }
}

Ces fonctions sont toutes utilisées dans une foreach($obj as $key=>$value)séquence complète . Les méthodes d'itération s'exécutent dans l'ordre suivant:

  1. rewind()
  2. while valid()
     {
          2.1 current() in $value
          2.3 key() in $key
          2.4 next()
     }

python

Les itérateurs en Python représentent une partie fondamentale du langage, mais ils sont souvent utilisés implicitement et donc invisiblement cachés dans les commandes du langage. Ces commandes sont par exemple B. for(foreach) dans les compréhensions dites de liste et dans les expressions génératrices. Tous les types de base séquentiels ainsi que de nombreuses classes de la bibliothèque standard en Python prennent en charge les itérations. L'exemple suivant montre une itération typique sur une séquence:

for value in sequence:
    print(value)

Les dictionnaires Python , une forme de tableau associatif, lui permettent d'itérer directement sur lui-même lorsque les soi-disant clés de dictionnaire sont renvoyées. Il peut également être itéré sur la fonction items d'un dictionnaire, où il renvoie les valeurs de la clé et de la valeur selon l'exemple suivant:

for key in dictionary:
    value = dictionary[key]
    print(key, value)

for key, value in dictionary.items():
    print(key, value)

Les itérateurs en Python peuvent également être explicitement définis et utilisés. Pour chaque type de séquence itérable ou chaque classe itérable, la iter()fonction intégrée est disponible pour générer un objet itérateur. L'objet iterator peut être utilisé pour naviguer vers l'élément suivant avec les fonctions next(), ou __next__(). Si la fin de l'ensemble est atteinte, une StopIterationerreur est générée. L'exemple suivant montre une implémentation équivalente d'itérateurs explicites:

it = iter(sequence)

while True:
    try:
        value = it.next()
    except StopIteration:
        break

    print(value)

Chaque classe définie par l'utilisateur peut prendre en charge l'itération standard si une _iter__()fonction a été définie qui génère un objet itérateur, l'itérateur doit alors __next__()définir une fonction qui renvoie l'élément suivant. Les générateurs Python implémentent ce protocole d'itération.

Rubis

L'implémentation des itérateurs dans Ruby diffère de la plupart des autres langages de programmation: toutes les itérations suivent l'idée de passer par des fermetures de rappel aux méthodes de conteneur. De cette façon, Ruby implémente non seulement une fonctionnalité de base des itérateurs, mais mappe également de nombreux modèles de conception d'itérateurs tels que: B. ce que l'on appelle la cartographie des fonctions , les filtres et ce qu'on appelle la réduction .

Ruby prend également en charge une syntaxe alternative pour chaque fonction de base pour l'itération:

(0...42).each do |n|
    puts n
end

… et …

for n in 0...42
    puts n
end

ou même plus court

42.times do |n|
    puts n
end

Voir également

Modèle de conception d'itérateur

liens web

Joshua Gatcomb: Comprendre et utiliser les itérateurs . (Anglais)
Une technique d'itération générique et son optimisation . (PDF; anglais; 216 kB)
Itérateurs STL . (Anglais)
Que sont les itérateurs? - Description de référence. (Anglais)
Interface IteratorAPI Java
Interface .NET dans MSDN
Boost C ++ Iterator Library (anglais)
PHP: itération d'objets (anglais)

Preuve individuelle

↑ std::for_each()
↑ std::copy()
↑ std::accumulate()
↑ std::ostream_iterator
↑ java.util.Iterator Spécification de l'API Java
↑ next() Spécification de l'API Java
↑ hasNext() Spécification de l'API Java
↑ remove() Spécification de l'API Java
↑ java.util.List Spécification de l'API Java
↑ java.util.ListIterator Spécification de l'API Java
↑ Iterable Spécification de l'API Java
↑ iterator() Spécification de l'API Java
↑ Design Pattern: Itérateur (Comportement)

[1] std::for_each()

[2] std::copy()

[3] std::accumulate()

[4] std::ostream_iterator

[5] java.util.Iterator Spécification de l'API Java

[6] next() Spécification de l'API Java

[7] hasNext() Spécification de l'API Java

[8] remove() Spécification de l'API Java

[9] java.util.List Spécification de l'API Java

[10] java.util.ListIterator Spécification de l'API Java

[11] Iterable Spécification de l'API Java

[12] iterator() Spécification de l'API Java

[13] Design Pattern: Itérateur (Comportement)

Languages