Un iterador es una estructura de datos que permite recorrer cada uno de los elementos que formen parte de una colección de datos, de forma ordenada.
Las colecciones de datos podrán ser las primitivas que suele haber en el lenguaje de programación. Por ejemplo, un array, una lista, un mapa, un diccionario o un árbol pueden ser consideradas estructuras que representan colecciones. En este caso, un iterador nos puede permitir ir recorriendo cada uno de los elementos que formen parte de la misma.
Un iterador nos permitiría examinar cada uno de los elementos de un array de forma ordenada, o cada uno de los elementos de una lista. Los iteradores nos permitirían examinar los distintos pares clave-valor que formen parte de un mapa, o recorrer en inorden, preorden o postorden los elementos de un árbol.
Sin embargo, los iteradores son estructuras que están diseñadas también para poder definirlos de forma personalizada, en base a una función generadora, de tal manera que se pueda fabricar una colección de elementos usando puramente código, sin que tenga que existir necesariamente una estructura en memoria detrás.
La función next: recorrer el iterador
Cualquier iterador debería tener una función de avanzar al siguiente elemento de la colección. Vamos a esta función next() (aunque cada lenguaje de programación puede tener luego su propia forma de llamarlo en la biblioteca estandar). Esta función devuelve el siguiente elemento de la colección sobre la que estamos iterando. Cada vez que llames a next() te entregará un nodo que no hayas visto previamente.
Por ejemplo, si fabricas un iterador para recorrer una colección con los elementos [1, 2, 3, 4], la primera vez que llames a next(), esta función debería devolverte el 1. La siguiente vez que la llames, esta función debería devolverte 2. La siguiente vez que la llames, un 3, y finalmente un 4.
Esto también nos dice que el iterador internamente necesitará algo de memoria para almacenar el estado del iterador, sobre todo qué elementos ya hemos visto, o cuál sería el siguiente elemento a devolver. Un iterador alimentado por un array, por ejemplo, podría devolver el siguiente índice del array a devolver.
Toma el siguiente código de ejemplo en Java,
class IteradorArray<T> {
private T[] array;
private int pos = 0;
public IteradorArray(T[] array) {
this.array = array;
}
public T next() {
T next = this.array[this.pos];
this.pos += 1;
return next;
}
}
public static void main(String[] args) {
Integer[] datos = { 1, 2, 3, 4 };
var arr = new IteradorArray(datos);
for (int i = 0; i < 4; i++) {
System.out.println(arr.next());
}
}
O el siguiente código de TypeScript,
class IteratorArray<T> {
private pos: number = 0;
constructor(private readonly arr: T[]) { }
next(): T {
const nextItem = this.arr[this.pos];
this.pos += 1;
return nextItem;
}
}
const data = [ 1, 2, 3, 4 ];
const iter = new IteratorArray(data);
for (let i = 0; i < 4; i++) {
console.log(iter.next());
}
O el siguiente código de Python,
class IteratorArray:
def __init__(self, arr):
self.arr = arr
self.pos = 0
def next(self):
val = self.arr[self.pos]
self.pos += 1
return val
data = [ 1, 2, 3, 4]
it = IteratorArray(data)
for i in range(4):
print(it.next())
Como podemos deducir, la función next tendrá a menudo efectos colaterales para recordar qué ha devuelto hasta ahora. En este ejemplo tengo una variable llamada pos que representa el índice del siguiente elemento. Sin embargo, para otras estructuras, podría ser cualquier otra forma de obtener el siguiente valor. De una lista enlazada podríamos guardar el siguiente nodo.
Incluso, algunos iteradores podrían computar sobre la marcha el propio valor a devolver en la función next. Echa un vistazo a este ejemplo en el que la función next no saca las cosas de un array o estructura, sino que las calcula directamente:
class FibonacciIterator {
private prev1: number;
private prev2: number;
private count: number;
constructor() {
this.prev1 = 1;
this.prev2 = 1;
this.count = 0;
}
next(): number {
const count = this.count;
this.count++;
if (count == 0) {
return this.prev1;
} else if (count == 1) {
return this.prev2;
} else {
const next = this.prev1 + this.prev2;
this.prev1 = this.prev2;
this.prev2 = next;
return next;
}
}
}
La función hasNext: hay que saber cuándo parar
La otra función que cualquier iterador debería tener se llama hasNext, stop, done o similares. Esta función es la que se usa para saber si hay más elementos que sacar del iterador o si ya hemos terminado de recorrerlo.
Esta función parece una tontería pero en realidad es bastante importante que esté, porque si la función next() siempre devuelve el siguiente elemento, hay que saber cuándo deja de ser seguro llamar a next() por haber alcanzado el final del iterador.
Te propongo retomar el ejemplo del iterador que recorre el array. En todos los códigos que he escrito, hay un bucle que hace 4 iteraciones. Imagina que no lo pongo y siempre llamo a next(). Eventualmente, el índice que guardo en pos apuntaría a una posición que se sale de los límites del array, y el programa fallaría por un acceso de memoria ilegal:
public static void main(String[] args) {
Integer[] datos = { 1, 2, 3, 4 };
var arr = new IteradorArray(datos);
while (true)
System.out.println(arr.next());
}
}
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 4 out of bounds for length 4
at Main$IteradorArray.next(Main.java:20)
at Main.main(Main.java:30)
*/
La función hasNext siempre indica si quedan más elementos. Por lo tanto, indica si es seguro llamar a la función next() o si deberíamos evitarlo. Por lo general, deberíamos consultar la salida de esta función antes de meternos en otra llamada a next(), y considerar que hemos terminado de recorrer el iterador cuando la función de fin devuelve que ya no hay más elementos por primera vez.
public boolean hasNext() {
return this.pos < this.array.length;
}
public static void main(String[] args) {
var datos = new Integer[] { 1, 2, 3, 4 };
var arr = new IteradorArray(datos);
while (arr.hasNext()) {
System.out.println(arr.next());
}
}
El ejemplo en otros lenguajes de programación es fácil de deducir.
Consideraciones sobre los iteradores
Un iterador puede funcionar en orden o no. Por ejemplo, un iterador que se alimente por una lista enlazada o por un array podría optar por ordenar los elementos antes de empezar a devolverlos.
Algunas colecciones, por la forma en la que funcionan, podrían ni siquiera ser ordenables. El iterador que permita interactuar con los elementos que forman parte de un conjunto es dificil que pueda ordenarlo porque los conjuntos por su propia definición no tienen noción de orden en muchos lenguajes de programación.
Por otra parte, estos son los dos métodos más importantes que debe tener cualquier iterador: el método que permite recuperar el siguiente elemento, y el método que indica si existen más elementos en primer lugar. Pero eso no quita que un iterador pueda tener más métodos, como puede ser un método que vuelva al inicio de un iterador, o un método que se salte elementos de un iterador.