2008-09-11 39 views
28

Vuelvo a C++ después de estar lejos por un tiempo y de intentar desempolvar el melón viejo.Iteradores en C++ (stl) vs Java, ¿hay alguna diferencia conceptual?

En Java Iterator es una interfaz a un contenedor que tiene métodos: hasNext(), next() y remove(). La presencia de hasNext() significa que tiene el concepto de un límite para el contenedor que se atraviesa.

//with an Iterator 
Iterator<String> iter = trees.iterator(); 
while (iter.hasNext()) 
{ 
    System.out.println(iter.next()); 
} 

En biblioteca de plantillas estándar de C++, iteradores parecen representar un tipo de datos o una clase de los soportes del operador ++ y el operador == pero tiene ningún concepto de un límite construida en lo que se requiere la comparación antes de avanzar a la siguiente ít. El límite debe ser verificado por el usuario comparando dos iteradores en el caso normal, el segundo iterador es el final del contenedor.

vector<int> vec; 
vector<int>::iterator iter; 

// Add some elements to vector 
v.push_back(1); 
v.push_back(4); 
v.push_back(8); 

for(iter= v.begin(); iter != v.end(); iter++) 
{ 
    cout << *i << " "; //Should output 1 4 8 
} 

La parte interesante aquí es que en C++ un puntero es un iterador de una matriz. El STL tomó lo que existía y construyó una convención a su alrededor.

¿Hay alguna otra sutileza en esto que me falta?

+0

Casi lo dijiste tú mismo. En Java, los conceptos de rango e iterador están bastante fusionados. En C++, un iterador no tiene concepto de qué rango de elementos forma parte, y de hecho, puede ser parte de múltiples rangos (de principio a fin, de principio a fin-1, de inicio + de 3 a final, de comienzo a comenzar + 6 y así sucesivamente.) – jalf

+0

"... tratando de desempolvar el melón viejo" - frase brillante. – kevinarpe

Respuesta

18

Sí, hay una gran diferencia conceptual. C++ utiliza diferentes "clases" de iteradores. Algunos se usan para acceso aleatorio (a diferencia de Java), otros se usan para acceso directo (como java). Mientras que otros se usan para escribir datos (para usar con, digamos, transform).

Véase el concepto de iteradores en el C++ Documentation:

  • iterador de entrada
  • iterador de salida
  • Adelante iterador
  • bidireccional iterador
  • de acceso aleatorio iterador

Estos son mucho Más interesante y potente en comparación con los iteradores insignificantes de Java/C#. Esperemos que estas convenciones se codificarán usando C++ 0x Concepts.

+0

La biblioteca Java tiene ListIterator que es de acceso aleatorio y bidireccional. –

+1

"acceso aleatorio y bidireccional" es una contradicción. Lo que quiere decir es que ListIterator es bidireccional y ofrece acceso de lectura y escritura. –

+0

NOTA: ListIterator does _not_ no incluye todos los requisitos de 'bidireccional'. No es compatible con la copia, es decir, no puede guardar su ubicación actual para volver a visitarla más tarde. Vea la respuesta separada a continuación. – Aaron

1

Los iteradores son solo equivalentes a punteros en el caso trivial de iterar sobre los contenidos de una matriz en secuencia. Un iterador podría estar suministrando objetos de cualquier cantidad de otras fuentes: de una base de datos, de un archivo, de la red, de algún otro cálculo, etc.

7

Un puntero a un elemento de matriz es de hecho un iterador en la matriz.

Como dices, en Java, un iterador tiene más conocimiento del contenedor subyacente que en C++. C iteradores ++ son generales, y una par de iteradores pueden denotar cualquier rango: esto puede ser un sub-intervalo de un recipiente, una gama sobre múltiples recipientes (ver http://www.justsoftwaresolutions.co.uk/articles/pair_iterators.pdf o http://www.boost.org/doc/libs/1_36_0/libs/iterator/doc/zip_iterator.html) o incluso un intervalo de números (véase http://www.boost.org/doc/libs/1_36_0/libs/iterator/doc/counting_iterator.html)

Las categorías de iterador identifican lo que puede y no puede hacer con un iterador determinado.

19

Quizás un poco más teórico.Matemáticamente, las colecciones en C++ se pueden describir como un intervalo de iteradores medio abierto, es decir, un iterador que apunta al inicio de la colección y un iterador que apunta a justo detrás de el último elemento.

Esta convención abre una gran cantidad de posibilidades. La forma en que los algoritmos funcionan en C++, todos se pueden aplicar a las subsecuencias de una colección más grande. Para hacer que algo funcione en Java, debe crear un contenedor alrededor de una colección existente que devuelva un iterador diferente.

Frank ha mencionado otro aspecto importante de los iteradores. Hay diferentes conceptos de iteradores. Los iteradores de Java corresponden a los iteradores de entrada de C++, es decir, son iteradores de solo lectura que solo pueden incrementarse paso por paso y no pueden retroceder.

En el otro extremo, tiene punteros C que corresponden exactamente al concepto de C++ de un iterador de acceso aleatorio.

Con todo, C++ ofrece un concepto mucho más rico y más puro que se puede aplicar a una variedad mucho más amplia de tareas que los punteros C o los iteradores de Java.

+0

Java tiene un ListIterator, que puede ir en ambas direcciones. – akuhn

+0

Sé que esta es una respuesta anterior, pero ... 1.Bi-direccional significa que se mueve hacia adelante y hacia atrás. 2.El acceso aleatorio significa que puede acceder a los elementos en un orden arbitrario, no secuencial, ** aleatorio ** (como el acceso indexado, por ejemplo). 3. el acceso de lectura/escritura es un concepto diferente llamado enteramente mutabilidad. Los iteradores de solo lectura solo pueden reenviarse o rebobinarse. Son dos variables independientes. De más interés para mí es la cuestión de mover un iterador o restablecerlo y reutilizar el iterador. Sun claramente tiene un uso en mente que involucra interfaces, pero parece poco desarrollado. –

+1

@SinthiaV Hmm. No estoy seguro de qué hacer con este comentario. Por supuesto, estoy al tanto de estas distinciones, y nada en mi respuesta contradice eso (aparte del hecho de que estoy usando el concepto C++ cuando hablo de "iterador de entrada", este concepto está modelado en solo lectura * hacia adelante * iterador). –

1

Los iteradores de la biblioteca C++ (la parte antes conocida como STL) están diseñados para ser compatibles con punteros. Java, sin aritmética de puntero, tenía la libertad de ser más amigable con los programadores.

En C++, termina teniendo que usar un par de iteradores. En Java, puede usar un iterador o una colección. Se supone que los iteradores son el pegamento entre el algoritmo y la estructura de datos. El código escrito para 1.5+ rara vez necesita iteradores de mención, a menos que esté implementando un algoritmo particular o una estructura de datos (que la mayoría de los programadores no tienen que hacer). Como Java va para subconjuntos de polimorfismo dinámico y similares son mucho más fáciles de manejar.

3

Para mí, la diferencia fundamental es que los Iteradores de Java apuntan entre los elementos, mientras que los iteradores de C++ STL apuntan a los elementos.

2

Los iteradores de C++ son una generalización del concepto de puntero; lo hacen aplicable a una gama más amplia de situaciones. Significa que se pueden usar para hacer cosas tales como definir rangos arbitrarios.

Los iteradores de Java son enumeradores relativamente tontos (aunque no tan malos como los de C#; al menos Java tiene ListIterator y se pueden usar para mutar la colección).

11

Como se mencionó, los iteradores Java y C# describen una posición entremezclada (estado) y rango (valor), mientras que los iteradores C++ separan los conceptos de posición y rango. Los iteradores de C++ representan '¿dónde estoy ahora? Separadamente de' ¿a dónde puedo ir? '.

Los iteradores de Java y C# no se pueden copiar. No puedes recuperar una posición anterior. Los iteradores comunes de C++ pueden.

Considere this example:

// for each element in vec 
for(iter a = vec.begin(); a != vec.end(); ++a){ 
    // critical step! We will revisit 'a' later. 
    iter cur = a; 
    unsigned i = 0; 
    // print 3 elements 
    for(; cur != vec.end() && i < 3; ++cur, ++i){ 
     cout << *cur << " "; 
    } 
    cout << "\n"; 
} 

Haga clic en el enlace de arriba para ver la salida del programa.

Este bucle bastante tonto pasa por una secuencia (utilizando solo la semántica del iterador directo), imprime cada subsecuencia contigua de 3 elementos exactamente una vez (y un par de subsecuencias más cortas al final). Pero suponiendo N elementos y M elementos por línea en lugar de 3, este algoritmo seguiría siendo O (N * M) incrementos de iterador y O (1) espacio.

Los iteradores de estilo Java carecen de la capacidad de almacenar la posición de forma independiente.Que o bien

  • perder O (1) el espacio, utilizando (por ejemplo) una matriz de tamaño M para almacenar la historia como iterar
  • tengan que atravesar los tiempos lista de N, por lo que O (n^2 + N * M) time
  • o utilice un tipo concreto de matriz con función de miembro de GetAt, perdiendo el genérico y la capacidad de utilizar tipos de contenedor de lista enlazada.

Como en este ejemplo solo se utilizaron mecanismos de iteración directa, pude intercambiar una lista con no problems. Esto es crítico para la creación de algoritmos genéricos, como búsqueda, inicialización y evaluación diferidas, clasificación, etc.

La incapacidad para retener el estado corresponde más estrechamente al iterador de entrada C++ STL, en el que se crean muy pocos algoritmos.

+0

Sí, pero ¡qué algoritmos útiles! std :: find (_if), std :: count y std :: copy son la base de muchos códigos importantes. –

+0

Este ejemplo es poco sincero. Se basa en que '= operator' funciona de manera diferente en Java y C++. En C++, realiza una copia del objeto en un nuevo objeto (instantánea superficial), mientras que en Java (y C#) copia la referencia, por lo que ambas variables operan en el mismo objeto. El comportamiento de copia de C++ significa que 'cur' se puede avanzar sin afectar' a' usando la sintaxis anterior, mientras que en Java o C# el iterador subyacente se modificará.Usando 'clone()' podrías tener el mismo comportamiento en Java. – BeeOnRope

1

Hay muchas buenas respuestas sobre las diferencias, pero sentí que lo que más me molesta con los iteradores de Java no se enfatizó: no se puede leer el valor actual varias veces. Esto es realmente útil en muchos escenarios, especialmente cuando se combinan iteradores.

En C++, tiene un método para avanzar el iterador y leer el valor actual. Leer su valor no hace avanzar la iteración; para que puedas leerlo muchas veces Esto no es posible con los iteradores de Java, y termino creando wrappers que hacen esto.

Una nota al margen: una manera fácil de crear un contenedor es utilizar uno existente - PeekingIterator de Guava.

+0

Tan cierto. Los iteradores de Java componen las operaciones de la posición en movimiento, recuperando el valor actual y las pruebas si están fuera de rango, cuando idealmente deberían mantenerse separadas y distintas. – beldaz

Cuestiones relacionadas