Disponible la nueva versión "donationware" 7.3 de OrganiZATOR
Descubre un nuevo concepto en el manejo de la información.
La mejor ayuda para sobrevivir en la moderna jungla de datos la tienes aquí.

Curso C++

[Home]  [Inicio]  [Índice]


5.1.2 Iteradores

§1 Sinopsis

El concepto de iterador es fundamental para entender las clases de contenedores y algoritmos asociados inclusos en la Librería Estándar de Plantillas de C++.  Hemos señalado ( 5.1) que son una generalización de los punteros, utilizados como nexo de unión entre los algoritmos y los miembros de los contenedores sobre los que operan. En realidad los algoritmos son funciones globales que aceptan iteradores como argumentos, y a través de ellos puedan operar sobre los elementos del contenedor.

Nota: el diseño de la STL permite que cualquier función genérica que acepte un iterador funcione igualmente bien aceptando un puntero ordinario.


Así pues, un iterador es una especie de puntero que es utilizado por un algoritmo para recorrer los elementos almacenados en un contenedor. Dado que los distintos algoritmos necesitan recorrer los contenedores de diversas maneras para realizar diversas operaciones, y los contenedores deben ser accedidos de formas distintas, existen diferentes tipos de iteradores. Cada contenedor de la Librería Estándar puede generar un iterador con funcionalidad adecuada a la técnica de almacenamiento que utiliza. Es precisamente el tipo de iterador requerido como argumento, lo que distingue qué algoritmos STL pueden ser utilizados con cada clase de contenedor. Por ejemplo, si un contenedor solo dispone de iteradores de acceso secuencial, no pueden utilizarse con algoritmos que exijan iteradores de acceso aleatorio. 

Nota: los iteradores no solo sirven para señalar elementos dentro de los contenedores de la STL, también se utilizan para señalar elementos dentro de otras estructuras: flujos ("Streams"  5.3.2b) y bufers de flujo ("Buffers streams"  5.3.2f) [4]. Además se han definido de modo que cuando los elementos de matriz están definidos mediante subíndices son también iteradores. La consecuencia es que ciertos algoritmos pueden aplicarse también sobre las matrices (recuerde las matrices son un tipo de estructura de datos, y que el operador elemento de matriz [] se define como la indirección de un puntero 4.9.16).


La cosa funciona más o menos según el siguiente esquema (observe su paralelismo con los punteros):

vector<int> cInt;                // contenedor tipo vector para enteros

...                              // introducimos algunos enteros en cInt

std::vector<int>::iterator iT1;  // iterador-a-vector-de-int

...

iT1 = cInt.begin();              // iT1 señala al primer miembro de cInt

...

std::cout << *iT1;               // muestra el primer miembro de cInt

...

++iT1;                           // desplaza iT1 al segundo miembro

std::cout << *iT1;               // muestra el segundo miembro de cInt

§2 La clase iterator

La sentencia anterior, donde se declara un iterador iT1 de la clase vector<int> es fundamental para entender la naturaleza de los iteradores

std::vector<int>::iterator iT1;

En efecto: esta sentencia intancia un objeto iT1 de la clase iterator que pertenece al espacio de una instanciación concreta, vector<int>, de una clase genérica vector<T>.  Esto significa que la clase iterator para vectores-de-int está definida en el ámbito de la clase genérica vector<T>.  Es decir, la definición del contenedor vector es algo como:

template <class T, ...> vector {

  public:

  class iterator;

};

A su vez esta clase iterator debe dispone de su propia definición en algún punto de la cabecera <vector>:

class vector<T>::iterator {

/* definición dependiente de la implementación */

};

Esta es la razón por la que coloquialmente se dice que un contenedor puede generar un iterador adecuado. Como puede verse, existen tantas clases iterator como contenedores distintos; todas ellas son distintas e independientes. Aunque comparten el mismo nombre y están definidas en subespacio distintos de std (recuerde que las clases constituyen ámbitos en sí mismas).

typedef implementation defined iterator;
typedef implementation defined const_iterator;
typedef implementation defined size_type;
typedef implementation defined difference_type;

typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

§2 Características

Existen diversas características principales que distinguen unos iteradores de otros. Podemos resumirlas como sigue:

  • Capacidad de modificar los datos subyacentes. En este sentido pueden ser de solo lectura; solo escritura, o lectura/escritura.
  • Tipo de desplazamiento que puede realizarse con ellos para recorrer el contenedor. Puede ser de avance secuencial; avance y retroceso secuencial, o acceso aleatorio.
  • Otras características adicionales. Por ejemplo, la posibilidad de ser utilizados por algoritmos que permiten insertar o borrar elementos del contenedor asociado.
§3 Categorías

El Estándar distingue cinco variedades de iteradores (denominadas categorías) en función de algunas de las características antes enunciadas:

Categoría Nombre genérico Resumen de propiedades
Acceso aleatorio RandomAccessIterator Lectura/escritura. Acceso aleatorio
Bidireccional BidirectionalIterator Lectura/escritura, movimiento adelante y atrás
Adelante ForwardIterator Lectura/escritura, movimiento hacia delante.
Entrada InputIterator Solo lectura, movimiento hacia delante
Salida OutputIterator Solo escritura, movimiento hacia delante

 

Jerarquía de iteradores

Lo que hemos denominado nombre genérico en la tabla anterior, es en cierta forma un especificador de tipo, de forma que podríamos considerar que existen cinco tipos de iteradores. De hecho, para poder efectuar la resolución de sobrecarga ( 4.4.1a) basándose en diferencias de categoría con funciones que utilizan iteradores como argumento, la STL proporciona cinco clases que representan cada una de estas categorías. Corresponden al esquema de la figura adjunta y responden las definiciones siguientes [3]:

struct InputIterator { ... };

struct OutputIterator { ... };

struct FordwarIterator : public InpuptIterator { ... };

struct BidirectionalIterator : public FordwardIterator { ... };

struct RandomAccessIterator : public BidirectionalIterator { ... };


Tenga en cuenta que la lista anterior representa una jerarquía, en el sentido de que cualquier iterador de la lista puede ser sustituido por el anterior. Por ejemplo, los iteradores adelante pueden ser usados donde se requieran iteradores de entrada o salida; los bidireccionales pueden utilizarse en lugar de los iteradores adelante y los de acceso aleatorio pueden usarse en situaciones en que se requieran los bidireccionales.  Por ejemplo, un algoritmo que utilice un InputIterator puede ser utilizado con cualquier contenedor que acepte iteradores de entrada o cualquiera de los que le preceden en la tabla anterior (FordwarIterator, BidirectionalIterator o RandomAccessIterator).

Nota: un iterador de entrada solo garantiza lectura (en el programa). Es decir, puede ser deferenciado para obtener el valor que señala, pero no puede ser utilizado para alterar este valor en el contenedor. Análogamente, un iterador de salida (del programa) solo garantiza que puede ser utilizado para escribir un miembro en el contenedor, pero no que pueda utilizarse para acceder al mismo.


La tabla siguiente muestra los modos en que son generadas las diversas categorías de iteradores por los contenedores STL.

Categoría Generado por
Iterador de entrada istream_iterator
Iterador de salida

ostream_iterator

insert_iterator

front_insert_iterator

back_insert_iterator

Iterador bidireccional

list

set y multiset

map y multimap

Iterador de acceso aleatorio

Punteros ordinarios

vector

deque


§3.1 Es importante entender que cada una de estas categorías de iteradores tiene ciertas propiedades. Por ejemplo, cuando un algoritmo señala que uno de sus argumentos es un InputIterator,  debe proporcionársele un puntero o iterador a una estructura de datos que satisfaga estas propiedades. En este sentido los nombres genéricos anteriores son auténticos calificadores de tipo. Por ejemplo el prototipo del algoritmo find():

template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& value);

indica que los dos primeros argumentos (y el valor devuelto) son iteradores de tipo entrada.

También es importante recordar que la forma de desplazamiento de los iteradores por los miembros del contenedor asociado, no es igual en todos los casos. Por esta razón suele afirmarse que un iterador impone un orden determinado en el contenedor señalado. En unos contenedores puede suponer un desplazamiento por sus miembros en el orden "natural" -como están colocados físicamente-. Es el caso de un contenedor list, en el que el recorrido de un iterador se corresponde con el orden en que fueron introducidos los datos. En otros casos el recorrido sigue un orden lógico -un criterio definido por un índice-. Por ejemplo, en un contenedor vector o map los iteradores están definidos de forma que el orden de recorrido corresponde a un índice (numérico en el primer caso y de cualquier otro tipo en el segundo).

En este sentido se definen iteradores inversos ("Reverse iterator"), cuya forma de recorrido es justamente inversa de los iteradores normales. Por ejemplo, en un contenedor vector o list, un iterador inverso recorre la estructura en sentido inverso que un iterador normal (del final al principio). En un sentido estricto los iteradores inversos no representan ninguna nueva categoría sobre los normales; son simplemente una adaptación de los iteradores bidireccionales y de acceso aleatorio. Por evidente, parece innecesario indicar que estas clases -que permiten acceso aleatorio- son las únicas que disponen de iteradores inversos.

§4 Tipos de iteradores

Los iteradores pueden ser clasificados de varias formas según la característica que se considere. A continuación se relacionan algunos de ellos.

§4.1 Iteradores reversibles y no-reversibles

Para distinguirlos de los que sirven para recorrer la secuencia en una sola dirección, no-reversibles, los que permiten recorrerla secuencialmente en ambas direcciones, o mediante acceso aleatorio, se denominan reversibles.

§4.2 Iteradores constantes y mutables

Otra característica distintiva de los iteradores es si pueden o no utilizarse para modificar los valores de los miembros del contenedor asociado. En este sentido, un iterador constante (const_iterator) es aquel que solo sirve para acceso y no puede usarse para modificaciones; en caso contrario el iterador es mutable.

Según se desprende del cuadro anterior, evidentemente los iteradores salida (OutputIterator) nunca son constantes, y los de entrada (InputIterator) lo son siempre. Otros iteradores pueden ser constantes o no, dependiendo de cómo sean creados. Existen iteradores bidireccionales (BidirectionalIterator) constantes y no-constantes; lo mismo para los de acceso aleatorio (RandomAccessIterator).

Nota: en ocasiones los algoritmos alteran el valor de los iteradores pasados como argumento (esto ocurre también con las funciones ordinarias). En tal caso, se exige naturalmente que los iteradores utilizados tengan la propiedad mutable.

§4.3 Iteradores de flujo

En C++ las entradas/salidas pueden ser realizadas al estilo clásico C, aunque el lenguaje proporciona un nuevo método mediante clases denominadas de forma genérica iostreams ( 5.3.1) que encapsulan las funcionalidad de las Librerías tradicionales C de E/S, es decir, permiten leer y escribir desde/en los flujos de E/S.

La STL proporciona dos iteradores diseñados especialmente para ser utilizados con los flujos de entrada/salida (en este sentido los flujos actúan a modo de contenedores), lo que permite que los algoritmos de la STL puedan ser utilizados directamente con los flujos de E/S.

  • istream_iterator para leer datos de un flujo de entrada.
  • ostream_iterator para escribir en un flujo de salida.

Ejemplo: Podemos crear un contenedor vInt para contener enteros de la clase vector y llenarlo con datos numéricos introducidos desde el flujo estándar de entrada (normalmente será el teclado):

vector<int> vInt;
istream_iterator<int> in(cin);
istream_iterator<int> eos;
copy (in, eos, back_inserter(vInt));

Posteriormente podemos escribir el contenido del vector vInt en el flujo de salida estándar (normalmente será la pantalla):

ostream_iterator<int> out(cout, ", ");
copy (vInt.begin(), vInt.end(), out);

§5 Operatoria y álgebra de iteradores

Lo mismo que los punteros ( 4.2.2), los iteradores disponen también de un álgebra rudimentaria, de forma que pueden realizarse ciertas operaciones con ellos.  El diseño de la STL garantiza que cada iterador que acepta una operación, lo hace siempre mediante la misma interfaz. Por ejemplo, los operadores que aceptan la suma y resta unaria ++ y -- mueven respectivamente un iterador de cualquier tipo hasta el elemento siguiente o anterior, dentro del contenedor asociado. Del mismo modo, la aplicación del operador de indirección * sobre cualquier iterador permite acceder al miembro correspondiente.

Dependiendo del tipo de miembros contenidos en el contenedor, la deferenciación de un iterador *i produce siempre una entidad T que es:

a.-  Un objeto (instancia de clase)

b.-  Una enumeración ( 4.8)

c.-  Un tipo fundamental preconstruido en el lenguaje ( 2.2).

El tipo de T se dice que es el tipo-valor del iterador.

En el primer caso (cuando los miembros del contenedor son instancias de clases), para cada iterador i en el que esté definida la expresión (*i).m para acceder a un miembro m del objeto, puede utilizarse también la sintaxis i->m con el mismo significado que si se trata de punteros-a-clases ( 4.9.16).


Del mismo modo que en los punteros regulares, además de la suma y resta unarias, en los iteradores también pueden estar definidas las operaciones suma y resta con un entero y diferencia (distancia) de dos iteradores. Sean It1 e It2 dos iteradores relativos al mismo contenedor, y n un entero. Las operaciones aritméticas y relacionales ( 4.9.12) que pueden estar permitidas, y los resultados obtenidos con ellas son:

Operación Resultado Comentario
It1 ++ Iterador Desplazamiento ascendente (1 elemento). Definido para todos los iteradores
It1 -- Iterador Desplazamiento descendente (1 elemento). No aplicable a los iteradores de entrada y salida
It1 + n Iterador Desplazamiento ascendente (n elementos).  
It1 - n Iterador Desplazamiento descendente (n elementos). No aplicable a los iteradores de entrada y salida
It1 - It2 entero Distancia entre elementos. Para los ForwardIterator, la diferencia debe ser positiva. Para los iteradores bidireccionales y aleatorios, puede ser positiva o negativa.
It1 == It2 bool Igualdad entre iteradores. Puede ser aplicada a iteradores de cualquier tipo
It1 != It2 bool Desigualdad de iteradores. Puede ser aplicada a iteradores de cualquier tipo

Otros operadores:

<,  >, <=, >=

bool Estos operadores solo pueden ser aplicados entre iteradores de acceso aleatorio.

Nota: la STL proporciona dos funciones que pueden utilizarse para desplazar iteradores y calcular su distancia ( 5.1.2h)

§5.1 Ejemplo

Creamos un contenedor tipo vector para contener enteros:

vector<int> vInt;


for (int i=0; i < 100; i++) vInt.push_back(i);

El contenedor vInt así definido puede ser recorrido mediante un iterador iter que inicialmente señala al primer miembro del contenedor. A continuación va desplazándose por los diversos miembros hasta alcanzar el último mediante la operación iter++:

vector<int>::iterator iter;


for (iter = vInt.begin(); iter != vInt.end(); iter++) {
  cout << *iter << endl;
}

§6 Valores posibles

Los iteradores de cualquier tipo siempre pueden adoptar un valor que señale a una posición después del último elemento de su estructura de datos (algo que puede ocurrir también con los subíndices de matrices); este valor se conoce como valor después del final ("past-the-end"). Estos iteradores no son deferenciables.  Por contra, los que señalan a posiciones dentro de la estructura si lo son.

Nota: recordemos aquí que los contenedores disponen de dos métodos begin() y end(), que devuelven iteradores a la posiciones del principio y después del final del contenedor ( 5.1.2a).


A veces los punteros pueden ser nulos ( 4.2.1), significando entonces que no señalan nada. También los iteradores pueden no asignar ningún valor específico. En ciertas circunstancias, cuando los iteradores no señalan a ninguna estructura de datos (contenedor), se dice que tienen un valor singular (podemos suponer que es una generalización del concepto de puntero nulo). Los valores deferenciables y los past-the-end no son nunca valor singular. Del mismo modo que es un error deferenciar un puntero nulo, también es un error deferenciar un iterador que no está denotando ningún valor.

§7 Accesibilidad y Rango

Muchos de los algoritmos de la STL operan sobre un subconjunto de los miembros de un contenedor definido entre dos iteradores a y b; en tal caso, se dice que el par a, b constituyen un rango, y se designa [1] mediante [a, b). El rango [a, a) es el rango nulo.

Un iterador b se dice que es accesible desde otro iterador a, si y solo si, existe una secuencia finita de operaciones ++a que hagan que a == b; en este instante ambos iteradores referencian al mismo contenedor.

La utilización de rangos en los algoritmos se ajusta a las siguientes reglas:

  • Si un algoritmo utiliza un rango [a, b) el rango debe ser válido.  Esto significa que b debe ser accesible desde a [2].
  • La operación asociada al algoritmo se realiza en los elementos comprendidos dentro del rango, empezando por el elemento señalado por a hasta el señalado por b (excluyendo este último).

Tradicionalmente se admite que cuando en un programa C++ se utilizan dos punteros para describir una región de memoria. El puntero final describe la frontera superior externa de dicha región, o dicho en otras palabras: el puntero final no es parte de la región descrita. Por ejemplo: una matriz x de longitud 10 es descrita a veces como comprendida entre x y x+10, a pesar que el elemento x+10 no forme parte de la matriz; al contrario, el puntero x+10 esta después del final del ámbito descrito. Por ejemplo, las sentencias:

int A[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
list<int> Av(A, A+10);

definen una matriz de enteros de diez elementos en las que están definidos los miembros A[0] - A[9], y un contenedor Av de tipo list ( 5.1.1), cuyos miembros son iniciados utilizando los elementos de la matriz A en el rango A, A+9 (inclusive); el límite superior A+10 no se considera (además no pertenece a la matriz).

Cuando describen un rango, los iteradores se utilizan de forma similar, el segundo valor no es considerado parte de la región señalada; antes bien, el segundo valor es un elemento después del final, que describe el elemento de la colección después del último del rango. Lo mismo que con los punteros, a veces este elemento puede ser un valor realmente existente en el contenedor, mientras que otras puede ser un valor especial construido específicamente para este propósito. Pero en ningún caso está permitido deferenciar el valor utilizado para definir el límite superior de un rango.


Los rangos puede utilizarse para describir todo el contenido de un contenedor construyendo un iterador para el elemento inicial y otro especial, después del último, para el final (estos iteradores serían proporcionados por los métodos begin y end ). Los iteradores también pueden ser utilizados para describir sub-secuencias dentro de un contenedor utilizando dos iteradores a los miembros que definen los límites inferior y superior de la secuencia.

§8 Precauciones con los iteradores

Hemos indicado que los iteradores son un tipo de punteros a ciertas estructuras de datos (contenedores). Ocurre que ciertos contenedores ofrecen la capacidad de crecer a medida que se van insertando nuevos elementos. Con objeto de minimizar la fragmentación, suelen utilizar un mecanismo que asigna inicialmente espacio para un cierto número de elementos. Cuando este espacio se ha agotado, se asigna un nuevo espacio para doble número de elementos que la primera vez, y un mecanismo automático copia los elementos del espacio original en el nuevo. A continuación el espacio original es desechado (devuelto al montón 1.3.2). Esta maniobra es conocida como recolocación del contenedor ("Reallocation"), y tiene el inconveniente que los punteros (iteradores) a los elementos del contenedor apuntan a direcciones erróneas después de una recolocación. El programador debe ser consciente de ello y no guardar iteradores sino índices.

Nota: un recurso para prevenir la recolocación es asignar al contenedor espacio inicial suficiente para el máximo de elementos previstos.


Si trasladamos este concepto a las matrices, sería como decir que no debemos almacenar un índice al tercer elemento de una matriz M de elementos tipo X, sino el número 3. De forma que si la matriz puede sufrir una "reallocation" no es seguro utilizar algo como

tipoX* ptr = &M[3];

para luego intentar

X x = *ptr;

En su lugar siempre es mejor hacer:

X x = M[3];


  Inicio.


[1] No se trata de un error tipográfico, es un corchete de inicio y un paréntesis como cierre [ ).  La notación es análoga a la utilizada en matemáticas para señalar intervalos medio abiertos: siendo a y b números reales [a, b) señala el intervalo de valores a =< x < b.

[2] Siempre que se utilicen dos iteradores para describir un rango, la STL asume que el segundo iterador es accesible desde el primero, aunque este supuesto no se comprueba, de forma que si no es cierto, obtiene un error.

[3]  Observe que, en contra de lo que podría parecer, la clase ForwardIterator deriva solo de InputIterator, y no de InputIterator y OutputIterator como podría suponerse.  Parece que el inventor del lenguaje no está muy satisfecho con esta decisión del Comité de Estandarización, de forma que él mismo indica: "The reasons that it is not (derivada de ambos) are obscure and probably not valid. However, I have yet so see an example in which that derivation would have simplified real code". Stroustrup TC++PL §19.2.3.

[4] Los streams y buffer streams son estructuras pertenecientes a la Librería Estándar que formalmente no pertenecen a la STL (a la librería de plantillas), aunque en realidad estas cuestiones méramente formales no tienen demasiada importancia.