Un iterator es un objeto que se mueve a través de un contenedor de otros objetos y selecciona a uno de ellos cada vez, sin porporcionar un acceso directo a la implementación del contenedor. Los iteradores proporcionan una forma estándar de acceder a los elementos, sin importar si un contenedor proporciona alguna marnera de acceder a los elementos directamente. Se verán a los iteradores usados frecuentemente en asociación con clases contenedoras, y los iteradores son un concepto fundamental en el diseño y el uso de los contenedores del Standard C++, los cuales son descritos en el Volumen 2 de este libro (que se puede bajar de www.BruceEckel.com. Un iterador es también un tipo de patrón de diseño, lo cual es materia de un capítulo del Volumen 2.

En muchos sentidos, un iterador es un «puntero elegante», y de hecho se verá que los iteradores normalmente ocultan la mayoría de las operaciones de los punteros. Sin embargo, al contrario que un puntero, el iterador es diseñado para ser seguro por lo que es mucho menos probable de hacer el equivalente de avanzar atravesando el final de un array (o si se hace, se encontrará más fácilmente).

Considere el primer ejemplo de este capítulo. Aquí está pero añadiendo un iterador sencillo:

//: C16:IterIntStack.cpp
// Simple integer stack with iterators
//{L} fibonacci
#include "fibonacci.h"
#include "../require.h"
#include <iostream>
using namespace std;

class IntStack {
  enum { ssize = 100 };
  int stack[ssize];
  int top;
public:
  IntStack() : top(0) {}
  void push(int i) {
    require(top < ssize, "Too many push()es");
    stack[top++] = i;
  }
  int pop() {
    require(top > 0, "Too many pop()s");
    return stack[--top];
  }
  friend class IntStackIter;
};

// An iterator is like a "smart" pointer:
class IntStackIter {
  IntStack& s;
  int index;
public:
  IntStackIter(IntStack& is) : s(is), index(0) {}
  int operator++() { // Prefix
    require(index < s.top, 
      "iterator moved out of range");
    return s.stack[++index];
  }
  int operator++(int) { // Postfix
    require(index < s.top, 
      "iterator moved out of range");
    return s.stack[index++];
  }
};

int main() {
  IntStack is;
  for(int i = 0; i < 20; i++)
    is.push(fibonacci(i));
  // Traverse with an iterator:
  IntStackIter it(is);
  for(int j = 0; j < 20; j++)
    cout << it++ << endl;
} ///:~

El IntStackIter ha sido creado para trabajar solo con un IntStack. Hay que resaltar que IntStackIter es un friend de IntStack, lo que lo da un acceso a todos los elementos privados de IntStack.

Como un puntero, el trabajo de IntStackIter consiste en moverse a través de un IntStack y devolver valores. En este sencillo ejemplo, el objeto IntStackIter se puede mover sólo hacia adelante (usando la forma prefija y sufija del operador++ ). Sin embargo, no hay límites de la forma en que se puede definir un iterador a parte de las restricciones impuestas por el contenedor con el que trabaje. Esto es totalmente aceptable (incluido los límites del contenedor que se encuentre por debajo) para un iterador que se mueva de cualquier forma por su contenedor asociado y para que se puedan modificar los valores del contenedor.

Es usual el que un iterador sea creado con un constructor que lo asocie a un único objeto contenedor, y que ese iterador no pueda ser asociado a otro contenedor diferente durante su ciclo de vida. (Los iteradores son normalemente pequeños y baratos, por lo que se puede crear otro fácilmente).

Con el iterador, se puede atravesar los elementos de la pila sin sacarlos de ella, como un puntero se mueve a través de los elementos del array. Sin embargo, el iterador conoce la estructura interna de la pila y como atravesar los elementos, dando la sensación de que se está moviendo a través de ellos como si fuera «incrementar un puntero», aunque sea más complejo lo que pasa por debajo. Esta es la clave del iterador: Abstrae el proceso complicado de moverse de un elemento del contenedor al siguiente y lo convierte en algo parecido a un puntero. La meta de cada iterador del programa es que tengan la misma interfaz para que cualquier código que use un iterador no se preocupe de a qué está apuntando - sólo se sabe que todos los iteradores se tratan de la misma manera, por lo que no es importante a lo que apunte el iterador. De esta forma se puede escribir código más genérico. Todos los contenedores y algoritmos en la Librería Estándar de C++ se basan en este principio de los iteradores.

Para ayudar a hacer las cosas más genéricas, sería agradable decir «todas las clases contenedoras tienen una clase asociada llamada iterator», pero esto causará normalmente problemas de nombres. La solución consite en añadir una clase anidada para cada contenedor (en este caso, «iterator» comienza con una letra minúscula para que esté conforme al estilo del C++ estándar). Aquí está el InterIntStack.cpp con un iterator anidado:

//: C16:NestedIterator.cpp
// Nesting an iterator inside the container
//{L} fibonacci
#include "fibonacci.h"
#include "../require.h"
#include <iostream>
#include <string>
using namespace std;

class IntStack {
  enum { ssize = 100 };
  int stack[ssize];
  int top;
public:
  IntStack() : top(0) {}
  void push(int i) {
    require(top < ssize, "Too many push()es");
    stack[top++] = i;
  }
  int pop() {
    require(top > 0, "Too many pop()s");
    return stack[--top];
  }
  class iterator;
  friend class iterator;
  class iterator {
    IntStack& s;
    int index;
  public:
    iterator(IntStack& is) : s(is), index(0) {}
    // To create the "end sentinel" iterator:
    iterator(IntStack& is, bool) 
      : s(is), index(s.top) {}
    int current() const { return s.stack[index]; }
    int operator++() { // Prefix
      require(index < s.top, 
        "iterator moved out of range");
      return s.stack[++index];
    }
    int operator++(int) { // Postfix
      require(index < s.top, 
        "iterator moved out of range");
      return s.stack[index++];
    }
    // Jump an iterator forward
    iterator& operator+=(int amount) {
      require(index + amount < s.top,
        "IntStack::iterator::operator+=() "
        "tried to move out of bounds");
      index += amount;
      return *this;
    }
    // To see if you're at the end:
    bool operator==(const iterator& rv) const {
      return index == rv.index;
    }
    bool operator!=(const iterator& rv) const {
      return index != rv.index;
    }
    friend ostream& 
    operator<<(ostream& os, const iterator& it) {
      return os << it.current();
    }
  };
  iterator begin() { return iterator(*this); }
  // Create the "end sentinel":
  iterator end() { return iterator(*this, true);}
};

int main() {
  IntStack is;
  for(int i = 0; i < 20; i++)
    is.push(fibonacci(i));
  cout << "Traverse the whole IntStack\n";
  IntStack::iterator it = is.begin();
  while(it != is.end())
    cout << it++ << endl;
  cout << "Traverse a portion of the IntStack\n";
  IntStack::iterator 
    start = is.begin(), end = is.begin();
  start += 5, end += 15;
  cout << "start = " << start << endl;
  cout << "end = " << end << endl;
  while(start != end)
    cout << start++ << endl;
} ///:~

Cuando se crea una clase friend anidada, hay que seguir el proceso de primero declarar el nombre de la clase, después declararla como friend, y después definir la clase. De otra forma, se confundirá el compilador.

Al iterador se le han dado algunas vueltas de tuerca más. La función miembro current() produce el elemento que el iterador está seleccionando actualmente en el contenedor. Se puede «saltar» hacia adelante un número arbitrario de elementos usando el operator+=. También, se pueden ver otros dos operadores sobrecargados: == y != que compararán un iterador con otro. Estos operadores pueden comparar dos IntStack::iterator, pero su intención primordial es comprobar si el iterador está al final de una secuencia de la misma manera que lo hacen los iteradores «reales» de la Librería Estándar de C++. La idea es que dos iteradores definan un rango, incluyendo el primer elemento apuntado por el primer iterador pero sin incluir el último elemento apuntado por el segundo iterador. Por esto, si se quiere mover a través del rango definido por los dos iteradores, se dirá algo como lo siguiente:

while (star != end)
    cout << start++ << endl;

Donde start y end son los dos iteradores en el rango. Note que el iterador end, al cual se le suele referir como el end sentinel, no es desreferenciado y nos avisa que estamos al final de la secuencia. Es decir, representa el que «otro sobrepasa el final».

La mayoría del tiempo se querrá mover a través de la secuencia entera de un contenedor, por lo que el contenedor necesitará alguna forma de producir los iteradores indicando el principio y el final de la secuencia. Aquí, como en la Standard C++ Library, estos iteradores se producen por las funciones miembro del contenedor begin() y end(). begin() usa el primer constructor de iterator que por defecto apunta al principio del contenedor (esto es el primer elemento que se introdujo en la pila). Sin embargo, un segundo constructor, usado por end(), es necesario para crear el iterador final. Estar «al final» significa apuntar a lo más alto de la pila, porque top siempre indica el siguiente espacio de la pila que esté disponible pero sin usar. Este constructor del iterator toma un segundo argumento del tipo bool, lo cual es útil para distinguir los dos constructores.

De nuevo se usan los números Fibonacci para rellenar la IntStack en el main(), y se usan iteradores para moverse completamente a través de la IntStack así como para moverse en un reducido rango de la secuencia.

El siguiente paso, por supuesto, es hacer el código general transformándolo en un template del tipo que maneje, para que en vez ser forzado a manejar enteros se pueda gestionar cualquier tipo:

//: C16:IterStackTemplate.h
// Simple stack template with nested iterator
#ifndef ITERSTACKTEMPLATE_H
#define ITERSTACKTEMPLATE_H
#include "../require.h"
#include <iostream>

template<class T, int ssize = 100>
class StackTemplate {
  T stack[ssize];
  int top;
public:
  StackTemplate() : top(0) {}
  void push(const T& i) {
    require(top < ssize, "Too many push()es");
    stack[top++] = i;
  }
  T pop() {
    require(top > 0, "Too many pop()s");
    return stack[--top];
  }
  class iterator; // Declaration required
  friend class iterator; // Make it a friend
  class iterator { // Now define it
    StackTemplate& s;
    int index;
  public:
    iterator(StackTemplate& st): s(st),index(0){}
    // To create the "end sentinel" iterator:
    iterator(StackTemplate& st, bool) 
      : s(st), index(s.top) {}
    T operator*() const { return s.stack[index];}
    T operator++() { // Prefix form
      require(index < s.top, 
        "iterator moved out of range");
      return s.stack[++index];
    }
    T operator++(int) { // Postfix form
      require(index < s.top, 
        "iterator moved out of range");
      return s.stack[index++];
    }
    // Jump an iterator forward
    iterator& operator+=(int amount) {
      require(index + amount < s.top,
        " StackTemplate::iterator::operator+=() "
        "tried to move out of bounds");
      index += amount;
      return *this;
    }
    // To see if you're at the end:
    bool operator==(const iterator& rv) const {
      return index == rv.index;
    }
    bool operator!=(const iterator& rv) const {
      return index != rv.index;
    }
    friend std::ostream& operator<<(
      std::ostream& os, const iterator& it) {
      return os << *it;
    }
  };
  iterator begin() { return iterator(*this); }
  // Create the "end sentinel":
  iterator end() { return iterator(*this, true);}
};
#endif // ITERSTACKTEMPLATE_H ///:~

Se puede ver que la transformación de una clase regular en un template es razonablemente transparente. Esta aproximación de primero crear y depurar una clase ordinaria, y después transformarla en plantilla, está generalmente considerada como más sencilla que crear el template desde la nada.

Dese cuenta que en vez de sólo decir:

friend iterator;  // Hacerlo amigo

Este código tiene:

friend class iterator;  // Hacerlo amigo

Esto es importante porque el nombre «iterator» ya existe en el ámbito de resolución, por culpa de un archivo incluido.

En vez de la función miembro current(), el iterator tiene un operator* para seleccionar el elemento actual, lo que hace que el iterator se parezca más a un puntero lo cual es una práctica común.

Aquí está el ejemplo revisado para comprobar el template.

//: C16:IterStackTemplateTest.cpp
//{L} fibonacci
#include "fibonacci.h"
#include "IterStackTemplate.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main() {
  StackTemplate<int> is;
  for(int i = 0; i < 20; i++)
    is.push(fibonacci(i));
  // Traverse with an iterator:
  cout << "Traverse the whole StackTemplate\n";
  StackTemplate<int>::iterator it = is.begin();
  while(it != is.end())
    cout << it++ << endl;
  cout << "Traverse a portion\n";
  StackTemplate<int>::iterator 
    start = is.begin(), end = is.begin();
  start += 5, end += 15;
  cout << "start = " << start << endl;
  cout << "end = " << end << endl;
  while(start != end)
    cout << start++ << endl;
  ifstream in("IterStackTemplateTest.cpp");
  assure(in, "IterStackTemplateTest.cpp");
  string line;
  StackTemplate<string> strings;
  while(getline(in, line))
    strings.push(line);
  StackTemplate<string>::iterator 
    sb = strings.begin(), se = strings.end();
  while(sb != se)
    cout << sb++ << endl;
} ///:~

El primer uso del iterador simplemente lo recorre de principio a fin (y muestra que el límite final funciona correctamente). En el segundo uso, se puede ver como los iteradores permite fácilmente especificar un rango de elementos (los contenedores y los iteradores del Standard C++ Library usan este concepto de rangos casi en cualquier parte). El sobrecargado operator+= mueve los iteradores start y end a posiciones que están en el medio del rango de elementos de is, y estos elementos son imprimidos. Hay que resaltar, como se ve en la salida, que el elemento final no está incluido en el rango, o sea que una vez llegado al elemento final (end sentinel) se sabe que se ha pasado el final del rango - pero no hay que desreferenciar el elemento final o si no se puede acabar desreferenciando un puntero nulo. (Yo he puesto un guardian en el StackTemplate::iterator, pero en la Librería Estándar de C++ los contenedores y los iteradores no tienen ese código - por motivos de eficiencia - por lo que hay que prestar atención).

Por último para verificar que el StackTemplate funciona con objetos clase, se instancia uno para strings y se rellena con líneas del código fuente, las cuales son posteriormente imprimidas en pantalla.

//: C16:TStack2.h
// Templatized Stack with nested iterator
#ifndef TSTACK2_H
#define TSTACK2_H

template<class T> class Stack {
  struct Link {
    T* data;
    Link* next;
    Link(T* dat, Link* nxt)
      : data(dat), next(nxt) {}
  }* head;
public:
  Stack() : head(0) {}
  ~Stack();
  void push(T* dat) {
    head = new Link(dat, head);
  }
  T* peek() const { 
    return head ? head->data : 0;
  }
  T* pop();
  // Nested iterator class:
  class iterator; // Declaration required
  friend class iterator; // Make it a friend
  class iterator { // Now define it
    Stack::Link* p;
  public:
    iterator(const Stack<T>& tl) : p(tl.head) {}
    // Copy-constructor:
    iterator(const iterator& tl) : p(tl.p) {}
    // The end sentinel iterator:
    iterator() : p(0) {}
    // operator++ returns boolean indicating end:
    bool operator++() {
      if(p->next)
        p = p->next;
      else p = 0; // Indicates end of list
      return bool(p);
    }
    bool operator++(int) { return operator++(); }
    T* current() const {
      if(!p) return 0;
      return p->data;
    }
    // Pointer dereference operator:
    T* operator->() const { 
      require(p != 0, 
        "PStack::iterator::operator->returns 0");
      return current(); 
    }
    T* operator*() const { return current(); }
    // bool conversion for conditional test:
    operator bool() const { return bool(p); }
    // Comparison to test for end:
    bool operator==(const iterator&) const {
      return p == 0;
    }
    bool operator!=(const iterator&) const {
      return p != 0;
    }
  };
  iterator begin() const { 
    return iterator(*this); 
  }
  iterator end() const { return iterator(); }
};

template<class T> Stack<T>::~Stack() {
  while(head)
    delete pop();
}

template<class T> T* Stack<T>::pop() {
  if(head == 0) return 0;
  T* result = head->data;
  Link* oldHead = head;
  head = head->next;
  delete oldHead;
  return result;
}
#endif // TSTACK2_H ///:~

//: C16:TStack2Test.cpp
#include "TStack2.h"
#include "../require.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main() {
  ifstream file("TStack2Test.cpp");
  assure(file, "TStack2Test.cpp");
  Stack<string> textlines;
  // Read file and store lines in the Stack:
  string line;
  while(getline(file, line))
    textlines.push(new string(line));
  int i = 0;
  // Use iterator to print lines from the list:
  Stack<string>::iterator it = textlines.begin();
  Stack<string>::iterator* it2 = 0;
  while(it != textlines.end()) {
    cout << it->c_str() << endl;
    it++;
    if(++i == 10) // Remember 10th line
      it2 = new Stack<string>::iterator(it);
  }
  cout << (*it2)->c_str() << endl;
  delete it2;
} ///:~