Iteradores entendimiento en la STL

Question

Hola así que estoy un poco confundido acerca de iteradores y lo que realmente son .... en el STL C++

En este caso im usando una lista, y yo no entiendo por qué tiene para hacer un iterador:
std::list <int>::const_iterator iElementLocator;

a Dipslay contenido de la lista por el operador derefrence:
cout << *iElementLocator;

después de asignar a tal list.begin();

Explique exactamente qué es un iterador y por qué tengo que eliminarlo/usarlo.
Gracias!

Answer 1

Hay tres bloques de construcción en el TEL:

• Contenedores
• Algoritmos
• Iteradores

A nivel conceptual recipientes contienen datos. Eso por sí solo no es muy útil, porque quiere hacer algo con los datos; desea operar en él, manipularlo, consultarlo, jugar con él. Los algoritmos hacen exactamente eso.Pero los algoritmos no contienen datos, no tienen datos - necesitan un contenedor para esta tarea. Dale un contenedor a un algoritmo y tienes una acción en marcha.

El único problema que queda por resolver es cómo un algoritmo atraviesa un contenedor, desde un punto de vista técnico. Técnicamente, un contenedor puede ser una lista vinculada, o puede ser una matriz o un árbol binario, o cualquier otra estructura de datos que pueda contener datos. Pero atravesar una matriz se hace de forma diferente a atravesar un árbol binario. Aunque conceptualmente todo lo que un algoritmo quiere es "obtener" un elemento a la vez de un contenedor, y luego trabajar en ese elemento, la operación de obteniendo el siguiente elemento de un contenedor es técnicamente muy específico del contenedor.

Parece como si tuviera que escribir el mismo algoritmo para cada contenedor, de modo que cada versión del algoritmo tenga el código correcto para atravesar el contenedor. Pero hay una mejor solución: solicite al contenedor que devuelva un objeto que pueda atravesar el contenedor. El objeto tendría una interfaz de algoritmos saber. Cuando un algoritmo le pide al objeto "obtener el siguiente elemento", el objeto cumpliría. Como el objeto proviene directamente del contenedor, sabe cómo acceder a los datos del contenedor. Y debido a que el objeto tiene una interfaz que el algoritmo conoce, no necesitamos duplicar un algoritmo para cada contenedor.

Este es el iterador.

El iterador aquí pega el algoritmo al contenedor, sin combinar los dos. Un iterador está acoplado a un contenedor, y un algoritmo está acoplado a la interfaz del iterador. La fuente de la magia aquí es realmente la programación de plantillas. Considere el algoritmo estándar copy():

template<class In, class Out> 
Out copy(In first, In last, Out res) 
{ 
    while(first != last) { 
     *res = *first; 
     ++first; 
     ++res; 
    } 
    return res; 
} 

El algoritmo copy() toma como parámetros dos iteradores con plantilla del tipo In y uno iterador de tipo Out. Copia los elementos comenzando en la posición first y termina justo antes de la posición last, en res. El algoritmo sabe que para obtener el siguiente elemento necesita decir ++first o ++res. Sabe que para leer un elemento necesita decir x = *first y para escribir un elemento necesita decir *res = x. Esa es parte de la interfaz que suponen los algoritmos y los iteradores se comprometen. Si por error un iterador no cumple con la interfaz, entonces el compilador emitiría un error para llamar a una función sobre el tipo In o Out, cuando el tipo no define la función.

Answer 2

Ya existen muchas buenas explicaciones de los iteradores. Solo busca en google.

One example.

Si hay algo específico que no entiende volver y preguntar.

Answer 3

Estoy siendo flojo. Así que no escribiría describiendo qué es un iterador y cómo se usan, especialmente cuando ya hay muchos artículos en línea que puede leer usted mismo.

Aquí son pocos los que puedo citar para un comienzo, lo que ha facilitado los enlaces a artículos completos:

MSDN dice,

iteradores son una generalización de punteros, haciendo abstracción de sus requisitos en una forma que permite que un programa C++ funcione con diferentes estructuras de datos de una manera uniforme. Los iteradores actúan como intermediarios entre los contenedores y los algoritmos genéricos . En lugar de operar en tipos de datos específicos, los algoritmos son definidos para operar en un rango especificado por un tipo de iterador. Cualquier estructura de datos que satisfaga los requisitos del iterador puede entonces ser operada por el algoritmo . Hay cinco tipos o categorías de iterador [...]

Por cierto, parece que el MSDN ha tomado el texto en negrita de C++ estándar en sí, específicamente de la sección §24.1/1, que dice

iteradores son una generalización de punteros que permiten una C + + programa para trabajo con estructuras diferentes de datos (recipientes) de una manera uniforme. Para poder construir la plantilla algoritmos que funcionan correctamente y de manera eficiente en diferentes tipos de datos estructuras, la biblioteca no formaliza sólo las interfaces sino también los supuestos semántica y complejidad de iteradores.Todos los iteradores admiten la expresión * i, lo que da como resultado un valor de alguna clase, enumeración o tipo incorporado T, denominado tipo de valor del iterador. Todos los iteradores i para cuya expresión (* i) .m es bien definida, admite la expresión i-> m con la misma semántica que (* i) .m. Para cada tipo de iterador X para la que la igualdad se define, hay un tipo integral correspondiente firmado llama el tipo de diferencia de la iterador.

cplusplus dice,

En C++, un iterador es cualquier objeto que, apuntando a algún elemento en una gama de elementos (como una matriz o un recipiente) , tiene la capacidad a iterar a través de los elementos de ese rango utilizando un conjunto de operadores (en menos, el incremento (++) y los operadores dereference (*)).

La forma más obvia de iterador es un puntero [...]

Y también se puede leer estos:

• What Is an Iterator?
• Iterators in the Standard C++ Library
• Iterator (en el wiki entrada)

Ten paciencia y lee todo esto. Con suerte, tendrá una idea de lo que es un iterador, en C++. Aprender C++ requiere paciencia y tiempo.

Answer 4

Sugiero leer acerca de la sobrecarga del operador en C++. Esto dirá por qué * y -> pueden significar esencialmente cualquier cosa. Solo entonces deberías leer sobre los iteradores. De lo contrario, puede parecer muy confuso.

Answer 5

Un iterador es un contenedor STL lo que un puntero está a una matriz. Puede pensar en ellos como objetos de puntero a contenedores STL. Como punteros, podrá usarlos con la notación del puntero (por ejemplo, *iElementLocator, iElementLocator++). Como objetos, tendrán sus propios atributos y métodos (http://www.cplusplus.com/reference/std/iterator).

Answer 6

Un iterador no es el mismo que el propio recipiente. El iterador se refiere a un solo elemento en el contenedor, y también proporciona formas de llegar a otros elementos.

considerar el diseño de su propio contenedor sin iteradores. Podría tener una función size para obtener el número de elementos que contiene, y podría sobrecargar el operador [] para permitirle obtener o establecer un elemento por su posición.

Pero "acceso aleatorio" de este tipo no es fácil de implementar de manera eficiente en algunos tipos de envase. Si obtiene el elemento número mil millones: c[1000000] y el contenedor utiliza internamente una lista vinculada, deberá escanear un millón de elementos para encontrar el que desea.

En su lugar, puede decidir permitir que la colección recuerde un elemento "actual". Podría tener funciones como start y more y next que le permiten colocar a través de los contenidos:

c.start(); 
while (c.more()) 
{ 
    item_t item = c.next(); 

    // use the item somehow 
} 

Pero esto pone el "iteración estado" dentro del contenedor. Esta es una seria limitación. ¿Qué pasa si quiere comparar cada artículo en el contenedor con cada otro artículo? Eso requiere dos bucles anidados, ambos iterando a través de todos los elementos. Si el contenedor almacena la posición de la iteración, no tiene forma de anidar dos de esas iteraciones: el bucle interno destruirá el funcionamiento del bucle externo.

Por lo tanto, los iteradores son una copia independiente de un estado de iteración. Usted puede comenzar una iteración:

container_t::iterator i = c.begin(); 

Eso iterador, i, es un objeto independiente que representa una posición dentro del contenedor. Se puede recuperar todo lo que se almacena en esa posición:

item_t item = *i; 

se puede pasar al siguiente tema:

i++; 

Con algunos iteradores puede saltar hacia adelante varios artículos:

i += 1000; 

O obtener un artículo en alguna posición relativa a la posición identificada por el iterador:

item_t item = i[1000]; 

Y con algunos iteradores puede retroceder.

Y se puede descubrir si ha llegado más allá de los contenidos del contenedor mediante la comparación del iterador a end:

while (i != c.end()) 

que se pueda imaginar end como devolver un iterador que representa una posición que es uno más allá la última posición en el contenedor.

Un punto importante a tener en cuenta con los iteradores (y en C++ en general) es que pueden dejar de ser válidos. Esto generalmente ocurre, por ejemplo, si vacía un contenedor: los iteradores que apuntan a las posiciones en ese contenedor ahora se han vuelto inválidos. En ese estado, la mayoría de las operaciones en ellos no están definidas, ¡podría pasar cualquier cosa!