Iteradores (Programación)

Iteradores (Programación) Concepto: Es un puntero que es utilizado por un algoritmo para recorrer los elementos almacenados en un contenedor

Iteradores (Programación). Un iterador es un 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.

Los iteradores 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) y bufers de flujo (Buffers streams). 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 (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).

Ejemplo

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 

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 iteradotes

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

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>. 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; 

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.

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

Nombre genérico es un especificador de tipo, de forma que existen cinco tipos de iteradores. Para poder efectuar la resolución de sobrecarga 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:

struct InputIterator { ... };
struct OutputIterator { ... };
struct FordwarIterator : public InpuptIterator { ... };
struct BidirectionalIterator : public FordwardIterator { ... };
struct RandomAccessIterator : public BidirectionalIterator { ... }; 

Tipos de iteradotes

Los iteradores pueden ser clasificados de varias formas según la característica que se considere.

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.

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.

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).

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 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.

Operatoria y álgebra de iteradotes

Lo mismo que los punteros, 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. 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 diferenciación de un iterador *i produce siempre una entidad T que es:

a.-  Un objeto (instancia de clase)
b.-  Una enumeración 
c.-  Un tipo fundamental preconstruido en el lenguaje  

El tipo de T 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. 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.

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 diferenciables. Por contra, los que señalan a posiciones dentro de la estructura si lo son. Los punteros pueden ser nulos, 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. Los valores deferenciables y los past-the-end no son nunca valor singular. Del mismo modo que es un error diferenciar un puntero nulo, también es un error diferenciar un iterador que no está denotando ningún valor.

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).

Los rangos pueden 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.

Precauciones con los iteradotes

Los iteradores son un tipo de punteros a ciertas estructuras de datos (contenedores). Ciertos contenedores ofrecen la capacidad de crecer a medida que se van insertando nuevos elementos. Para 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. 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.

Puede Consultar

• Función (programación)
• Operadores
• Sentencias (Programación)
• Iteradores de entrada (Programación)
• Iteradores de salida (Programación)

Fuente

• Iteradores