Un iterator es un objeto que se mueve a través de un contenedor de otros objetos y los selecciona de uno en uno, sin proporcionar un acceso directo a la implementación del contenedor. Los iteradores proporcionan una forma estándar de acceder a los elementos, tanto si un contenedor proporciona alguna manera de acceder a los elementos directamente como si no. Los iteradores se usan sobre todo en asociación con clases contenedoras, y son un concepto fundamental en el diseño y el uso de los contenedores del C++ Estándar, que se describen por completo 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, que es el tema de un capítulo del Volumen 2.

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

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

//: 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 sólo con un IntStack. Hay que resaltar que IntStackIter es un friend de IntStack, lo que le da 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 obtener valores. En este sencillo ejemplo, el objeto IntStackIter se puede mover sólo hacia adelante (usando las formas prefija y sufija del operator++ ). Sin embargo, no hay límites en la forma en que se puede definir un iterador aparte de las restricciones impuestas por el contenedor con el que trabaje. Es totalmente aceptable (dentro de los límites del contenedor subyacente) que un iterador se mueva de cualquier forma por su contenedor asociado y que provoque la modificación de los valores contenidos.

Es habitual que un iterador se cree con un constructor que lo asocie a un único objeto contenedor, y que ese iterador no se asocie a otro contenedor diferente durante su ciclo de vida. (Los iteradores son normalmente pequeños y baratos, por lo que se puede crear otro fácilmente).

Con el iterador, se pueden recorrer los elementos de la pila sin sacarlos de ella, igual que un puntero se mueve a través de los elementos de un array. Sin embargo, el iterador conoce la estructura interna de la pila y cómo recorrer los elementos, de modo que, aunque se avance por ellos simulando «incrementar un puntero», lo que pasa por debajo es más complejo. Ésa 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. El objetivo es que todos los iteradores del programa tengan la misma interfaz para que el código que use un iterador no se preocupe de a qué está apuntando; sólo sabe que puede reposicionar todos los iteradores de la misma manera, por lo que no importa a qué contenedor 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 poder decir «todo contenedor tiene una clase asociada llamada iterator», pero esto causará normalmente problemas de nombres. La solución consiste en añadir una clase iterator anidada a cada contenedor (fíjese en que, en este caso, «iterator» comienza con una letra minúscula para que esté conforme al estilo de la Librería Estándar de C++). Aquí está IterIntStack.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, el compilador se confundirá.

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+=. Además, se pueden ver dos operadores sobrecargados, == y !=, que comparan un iterador con otro. Estos operadores pueden comparar dos IntStack::iterator cualesquiera, 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(start != end)
  cout << start++ << endl;

Donde start y end son los dos iteradores del rango. Note que el iterador end, al que a menudo se denomina end sentinel (centinela final), no se dereferencia y sólo está ahí para indicar que se ha llegado al final de la secuencia. Es decir, representa «uno más allá del final».

La mayor parte del tiempo se querrá recorrer la secuencia entera de un contenedor, por lo que el contenedor necesitará alguna forma de producir los iteradores que indican el principio de la secuencia y el centinela final. Aquí, como en la Librería Estándar de C++, estos iteradores los producen 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 centinela 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, que es ficticio y sólo sirve para distinguir los dos constructores.

De nuevo se usan los números Fibonacci para rellenar el IntStack en el main(), y se usan iteradores para moverse completamente a través del 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 una plantilla del tipo que maneje, para que en vez de estar obligado a manejar sólo 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 normal en una plantilla 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 la plantilla desde cero.

Fíjese en que en vez de decir sólo:

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, procedente de un fichero 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 y es una práctica común.

Aquí está el ejemplo revisado para comprobar la plantilla:

//: 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 centinela final funciona correctamente). En el segundo uso, se puede ver cómo los iteradores permiten fácilmente especificar un rango de elementos (los contenedores y los iteradores de la Librería Estándar de C++ usan este concepto de rangos casi en todas partes). El operator+= sobrecargado mueve los iteradores start y end a posiciones que están en el medio del rango de elementos de is, y esos elementos se imprimen. Hay que resaltar, como se ve en la salida, que el centinela final no está incluido en el rango, por lo que puede estar uno más allá del final del rango para indicar que se ha sobrepasado el final; pero no hay que dereferenciar el centinela final, o se puede acabar dereferenciando un puntero nulo. (He puesto código de protección en StackTemplate::iterator, pero los contenedores y los iteradores de la Librería Estándar de C++ no tienen ese código, por motivos de eficiencia, así que hay que prestar atención).

Por último, para verificar que StackTemplate funciona con objetos de clases, se instancia uno para strings y se rellena con las líneas del fichero de código fuente, que después se imprimen.

//: 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;
} ///:~