5.1.2a Iteradores de entrada
§1 Sinopsis
Los iteradores de entrada (InputIterator) sirven a operaciones de lectura de datos. La fuente de datos puede ser un contenedor STL (lo más frecuente); un contenedor preconstruido en el lenguaje (matriz); un contenedor construido por el usuario (que satisfaga las condiciones requeridas), o un flujo de datos ("Stream").
Nota: observe que en esta sección y en la siguiente
(
5.1.2b) la cuestión entrada/salida es considerada
desde el punto de vista del programa. En consecuencia, iterador
de entrada se refiere a entrada de datos en el programa desde el contenedor (lectura); iterador de salida
significa salida de datos desde el programa al contenedor (escritura).
Los iteradores de entrada son de solo lectura y movimiento hacia delante, lo que significa que solo
pueden usarse con algoritmos que no alteren los miembros del contenedor (son
iteradores constantes), y solo está permitido con ellos el operador de desplazamiento
hacia adelante ++. El operador de indirección
*, y los relacionales igualdad ==
y desigualdad != siempre están disponibles entre iteradores de un mismo contenedor.
Se exige que los algoritmos que utilicen este tipo de iteradores sean de pasada simple. Esto significa que solo realizarán una pasada en cada elemento del contenedor sobre el que operan (no realizarán operaciones sobre ellos más que en una ocasión).
§2 Condiciones
Se considera que cualquier tipoX simple o compuesto satisface las condiciones de un iterador de entrada para un
tipo-valor T (
5.1.2) si satisface las condiciones señaladas a continuación.
Nota: en la descripción que sigue suponemos que tipoX es una clase que puede considerarse una estructura de datos cuyos miembros son tipo T. Por ejemplo, en una matriz de enteros definida como int M[10];, tipoX está representada por la matriz M, y el tipo-valor T es int.
Además suponemos que:
- a y b son objetos tipoX
- n es el valor de una diferencia (distancia entre dos miembros del contenedor).
- u, tmp, y m son identificadores (nombres).
- r es un objeto tipo tipoX&.
- t es un valor de tipo T.
Operación | Tipo de objeto resultante de la operación | Comentario |
tipoX(a); | tipoX | Construye una copia de a. Se supone que existe un destructor visible |
tipoX u(a); | tipoX | Utiliza el contructor-copia; como resultado u == a |
tipoX u = a; | tipoX | Es una asignación; como resultado u es una copia de a; u == a |
a == b | bool | Un valor bool o convertible a bool |
a != b | bool | Un valor bool o convertible a bool |
*a | T |
Un tipo T o convertible a T. Si a == b, implica que *a == *b. |
a->m | miembro de T |
Supone que T es un tipo compuesto, y que m es un miembro de T. Supone también que está definida la operación (¨*a).m y que a->m == (*a).m |
++r | tipoX& |
Se exigen las condiciones siguientes: Que r sea deferenciable (se le pueda aplicar el operador *) Que el resultado de la operación sea deferenciable o un valor past-the-end. |
*r++ | T |
La expresión debe ser equivalente a la siguiente secuencia: { T temp = *r; ++r; return temp} |
Nota: la clase tipoX puede estar construida de forma que el operador relacional a == b entre dosmiembros a y b, no implica necesariamente que ++a == ++b.
Como consecuencia de lo anterior, para que r pueda ser utilizado como iterador de entrada, deben estar definidas en él las siguientes operaciones como mínimo:
*r = valor Asignar valor al elemento del contenedor señalado por r.
++r Alterar r de forma que señale al próximo elemento de la secuencia.
§3 Descripción
Describiremos los iteradores de entrada analizando un trozo de código que utiliza el algoritmo no modificativo find()
( 5.1.3).
template <class InputIterator, class T>
InputIterator find (InputIterator first,
InputIterator last,
const T& value) {
while (first != last && *first != value) ++first;
return first;
}
Podemos ver que este algoritmo genérico es en realidad una función genérica (una plantilla
4.12.1). La función acepta tres
argumentos; los dos primeros first y last, son iteradores de entrada (InputIterator) que delimitan el rango
de la búsqueda (
5.1.2). El tercer argumento value es una referencia a un valor
constante del tipo T de los miembros del contenedor.
El bucle de la función se limita a incrementar el valor del primer iterador mientras no sea igual al segundo y el valor señalado sea distinto del buscado. Si se alcanza la concordancia el valor devuelto es el iterador en que se cumple la condición. Observe que si el valor buscado no se encuentra en el contenedor, el iterador devuelto es el límite superior del rango, de forma que si returned es el valor devuelto, la condición returned == last es señal de que no se ha encontrado el valor buscado. Si el rango de búsqueda se hubiera extendido a la totalidad del contenedor el iterador devuelto sería el valor past-the-end.
El algoritmo anterior pone de manifiesto tres características de los iteradores de entrada:
-
Los operadores relacionales igualdad == y desigualdad != (
4.9.12) puede ser utilizado con dos iteradores de entrada. Lo mismo que ocurre con los punteros ordinarios (
4.2.2), estos operadores solo puede utilizarse con iteradores correspondientes al mismo contenedor; la igualdad significa que ambos iteradores señalan al mismo elemento; la desigualdad es el caso contrario.
-
Un iterador de entrada puede ser deferenciado mediante el operador de indirección * (
4.9.11); el valor obtenido es el miembro del contenedor señalado por el iterador.
-
Un iterador de entrada puede ser incrementado con el operador unario ++ para señalar al siguiente miembro de la secuencia.
Es interesante observar que el significado de los operadores desigualdad
(!=),
deferencia (*)
y suma unaria (++) depende de
como estén definidos en la clase operador de entrada (InputIterator) utilizada como primer argumento de la plantilla. Como
es posible redefinir estas funciones-operador, la sobrecarga de iteradores también es
posible, y como consecuencia final, el comportamiento de los algoritmos como el presente para ciertos tipos específicos.
§4 Tipos de iteradores de entrada
Existen tres tipos principales de iteradores de entrada (InputIterator): punteros ordinarios; iteradores estándar de contenedor, e iteradores de flujo de entrada (Input stream iterator).
§4.1 Punteros ordinarios
Hemos señalado ( 4.3)
que las matrices ordinarias son un tipo de estructura de datos, y es fácil
comprobar que los punteros a estas matrices satisfacen los criterios
señalados (§2
)
para que puedan ser considerados como iteradores de entrada., y en consecuencia pueden aplicárseles los algoritmos de la
STL. Por ejemplo, el siguiente código busca el valor 7 en una matriz de enteros de 100 elementos:
int data[100];
...
int* where = find(data, data+100, 7);
Nota: una de las características de los iteradores de entrada es que no permiten
operaciones de escritura sobre los datos del contenedor (decimos que son constantes
5.1.2). En el caso de
punteros a matrices regulares esto puede ser simulado fácilmente definiendo
punteros-a-constantes. Por ejemplo, en el caso anterior la
representación sería más exacta con las siguientes sentencias:
const int * first = data;
const int * last = data + 100;
...
const int * where = find(first, last, 7);
Ejemplo
Como aclaración de lo anteriormente expuesto, proponemos una demostración de que pueden definirse iteradores de entrada sobre las matrices regulares, de forma que pueden aplicarse sobre ellas algunos algoritmos de la STL, como la mencionada función find().
#include <iostream>
#include <algorithm>
using namespace std;
int main(void) { //
===============
int A[10] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
int* apt1 = A;
int* apt2 = apt1+10; // M3:
int v = 7;
// M5:
int* apt3 = find(apt1, apt2, v);
if (apt1 == apt2)
cout << "Valor " << v << " no encontrado" << endl;
else {
cout << "Valor " << v << " encontrado en
elemento A[";
for (int i=0; i<10; i++)
if (apt1+i == apt3) cout << i << "]" << endl;
}
}
Salida:
Valor 7 encontrado en elemento A[3]
Comentario:
Los punteros apt1 y apt2 gozan de las propiedades de los iteradores, de forma que pueden ser utilizados como argumentos de la función find() para buscar miembros del contenedor representado por la matriz A (una estructura de datos para albergar enteros).
Tal como se ha utilizado, la función find() busca el valor 7 entre los miembros A[0]-A[9] de la matriz. Recordemos
que el iterador apt2 representa el elemento past-the-end del rango [apt1, apt2), y que este
valor es excluido de la búsqueda (
5.1.2). Esto puede ser comprobado fácilmente sustituyendo la expresión M3 por:
int* apt2 = apt1+3; // M3b:
Aunque ahora apt2 señala justamente al valor 7, el resultado es
Valor 7 no encontrado.
Puede demostrarse, que en realidad, los punteros a matrices regulares son iteradores
de acceso aleatorio (RandomAccessIterator
5.1.2e) por lo que pueden ser considerados también iteradores de
entrada.
La consecuencia
destacable es que pueden aplicarse a las matrices la mayoría de los algoritmos de la STL.
§4.2 Iteradores de contenedor estándar
La totalidad de los iteradores que pueden definirse para los
contenedores de la STL pueden considerarse, al menos, como contenedores de
entrada (recuerde que los iteradores constituyen una jerarquía y que los de
orden superior pueden también efectuar las funciones de los de orden
inferior
5.1.2).
Todos los contenedores de la STL (clases genéricas) que soportan iteradores, disponen de dos funciones-miembro begin() y
end() que devuelven sendos iteradores al elemento inicial y después del último (past-the-end). Por ejemplo,
suponiendo que tenemos un contenedor tipo list (
5.1.1) denominado aList
previsto para manejar enteros, la forma de buscar un miembro de valor 7 sería:
list<int>::iterator where = find(aList.begin(), aList.end(), 7);
Esta expresión declara que where es un iterador a aList, y lo inicia con el
valor devuelto por la función. La explicación de la declaración
(Lvalue de la expresión) es que cada contenedor de la STL que soporta
iteradores incluye en su declaración un tipo que es un iterador a la
clase. Este tipo (que es en realidad una subclase genérica -plantilla-
dentro del contenedor) tiene el nombre iterator (o cons_iterator si es constante [1]).
Esto permite que puedan declararse iteradores a estos contenedores utilizando
una sintaxis uniforme como la utilizada en la sentencia anterior.
§4.3 Iteradores de flujo de entrada
La STL también proporciona iteradores que pueden ser utilizados con los flujos de entrada. Son los denominados istream_iterator, que pueden ser utilizados con contenedores de la clase basic_istream.
[1] El iterador también puede ser constante si la propia estructura (contenedor) goza de esta característica.