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

  Inicio.


[1]  El iterador también puede ser constante si la propia estructura (contenedor) goza de esta característica.