c++ - geeksforgeeks - ¿Por qué es legal la comparación con el iterador "end()"?

next iterator c++

Question

De acuerdo con el estándar C ++ (3.7.3.2/4) que usa (no solo la desreferenciación, sino también la copia, el lanzamiento, lo que sea) un puntero no válido es un comportamiento indefinido (en caso de duda, consulte esta pregunta ). Ahora el código típico para atravesar un contenedor STL se ve así:

std::vector<int> toTraverse;
//populate the vector
for( std::vector<int>::iterator it = toTraverse.begin(); it != toTraverse.end(); ++it ) {
//process( *it );
}

std::vector::end() es un iterador sobre el elemento hipotético más allá del último elemento del contenedor. No hay ningún elemento allí, por lo tanto, usar un puntero a través de ese iterador es un comportamiento indefinido.

Ahora, ¿cómo funciona el != end() entonces? Quiero decir, para hacer la comparación, se debe construir un iterador envolviendo una dirección no válida y luego esa dirección no válida tendrá que usarse en una comparación que, de nuevo, es un comportamiento indefinido. ¿Es legal tal comparación y por qué?

Answer 1

Además de lo que ya se dijo (los iteradores no necesitan ser punteros), me gustaría señalar la regla que usted cita

De acuerdo con el estándar C ++ (3.7.3.2/4) que usa (no solo la desreferenciación, sino también la copia, el lanzamiento, lo que sea) un puntero no válido es un comportamiento indefinido

No se aplicaría al end() iterador de todos modos. Básicamente, cuando tiene una matriz, todos los punteros a sus elementos, más un puntero más allá del final, más un puntero antes del inicio de la matriz, son válidos. Eso significa:

int arr[5];
int *p=0;
p==arr+4; // OK
p==arr+5; // past-the-end, but OK
p==arr-1; // also OK
p==arr+123456; // not OK, according to your rule

Answer 2

Eh No hay una regla que diga que los iteradores deben implementarse usando nada más que un puntero.

Podría tener una bandera booleana allí, que se establece cuando la operación de incremento ve que pasa el final de los datos válidos, por ejemplo.

Answer 3

El único requisito para end() es que ++(--end()) == end() . El end() podría ser simplemente un estado especial en el que se encuentra el iterador. No hay ninguna razón para que el iterador end() tenga que corresponder a un puntero de ningún tipo.

Además, incluso si fuera un puntero, comparar dos punteros no requiere ningún tipo de desreferencia de todos modos. Considera lo siguiente:

char[5] a = {''a'', ''b'', ''c'', ''d'', ''e''};
char* end = a+5;
for (char* it = a; it != a+5; ++it);

Ese código funcionará bien y reflejará su código vectorial.

Answer 4

La implementación del iterador end() del contenedor de una biblioteca estándar está bien definida por la implementación, por lo que la implementación puede jugar trucos que sabe la plataforma para admitir.
Si implementó sus propios iteradores, puede hacer lo que quiera, siempre que sea conforme a la norma. Por ejemplo, su iterador, si almacena un puntero, podría almacenar un puntero NULL para indicar un iterador final. O podría contener una bandera booleana o lo que sea.

Answer 5

Respondo aquí ya que otras respuestas están ahora desactualizadas; Sin embargo, no estaban del todo en lo cierto.

Primero, C ++ 14 ha cambiado las reglas mencionadas en la pregunta. La indirección a través de un valor de puntero no válido o pasar un valor de puntero no válido a una función de desasignación aún no está definida, pero otras operaciones ahora están definidas por implementación, consulte la Documentación de conversión de "valor de puntero no válido" en implementaciones de C ++ .

Segundo, las palabras cuentan. No puedes pasar por alto las definiciones mientras aplicas las reglas. El punto clave aquí es la definición de "inválido". Para los iteradores, esto se define en [iterator.requirements] . De hecho, incluso es cierto que los punteros son iteradores , los significados de "no válido" para ellos son sutilmente diferentes. Las reglas para los punteros muestran "no válido" como "no indirecto a través de un valor no válido", que es un caso especial de "no dereferenceable " para los iteradores; sin embargo, "no diferible" no implica "no válido" para los iteradores. "No válido" se define explícitamente como " puede ser singular ", mientras que el valor "singular" se define como "no asociado con ninguna secuencia" (en el mismo párrafo de la definición de "no referenciable"). Ese párrafo incluso definió explícitamente los "valores pasados ​​al final".

Del texto del estándar en [iterator.requirements], está claro que:

• No se supone que los valores anteriores al final sean excluibles (al menos por la biblioteca estándar), como indica el estándar.
• Los valores no referenciables no son singulares, ya que están asociados con la secuencia.
• Los valores anteriores al final no son singulares, ya que están asociados con la secuencia.
• Un iterador no es inválido si definitivamente no es singular (por negación en la definición de "iterador inválido"). En otras palabras, si un iterador está asociado a una secuencia, no es válido.

El valor de end() es un valor pasado el final, que se asocia con una secuencia antes de que se invalide. Así que en realidad es válido por definición. Incluso con la idea errónea de "inválido" literalmente, las reglas de los punteros no son aplicables aquí.

Las reglas que permiten la comparación == en dichos valores se encuentran en los requisitos del iterador de entrada , que es heredado por alguna otra categoría de iteradores (directo, bidireccional, etc.). Más específicamente, se requiere que los iteradores válidos sean comparables en el dominio del iterador de tal manera ( == ). Además, los requisitos de iterador hacia adelante especifican que el dominio está sobre la secuencia subyacente . Y los requisitos de contenedor especifican que los tipos de iterator y const_iterator en cualquier categoría de iterador cumplen con los requisitos de iterador hacia adelante . Por lo tanto, == en end() y el iterador sobre el mismo contenedor deben estar bien definidos. Como contenedor estándar, vector<int> también cumple con los requisitos. Esa es toda la historia.

En tercer lugar, incluso cuando end() es un valor de puntero (es probable que esto ocurra con la implementación optimizada del iterador de vector instancia vector ), las reglas de la pregunta aún no son aplicables. La razón se menciona arriba (y en algunas otras respuestas): "inválido" se refiere a * (indirecto), no a la comparación. El valor de un extremo pasado se permite de manera explícita para ser comparado en formas especificadas por el estándar. Además, tenga en cuenta que ISO C ++ no es ISO C, sino que también tiene una discrepancia sutil (p. Ej., Para < en valores de puntero que no están en la misma matriz, sin especificar ni indefinido), aunque tienen reglas similares aquí.

Answer 6

Sencillo. Los iteradores no son (necesariamente) punteros.

Tienen algunas similitudes (es decir, puedes desreferenciarlas), pero eso es todo.

Answer 7

Tiene razón en que no se puede usar un puntero no válido, pero se equivoca al decir que un puntero a un elemento pasado el último elemento de una matriz es un puntero no válido, es válido.

El estándar C, sección 6.5.6.8 dice que está bien definido y es válido:

... si la expresión P apunta al último elemento de un objeto de matriz, la expresión (P) +1 apunta a uno más allá del último elemento del objeto de matriz ...

pero no puede ser desreferenciado

... si el resultado apunta uno más allá del último elemento del objeto de matriz, no se utilizará como el operando de un operador * unario que se evalúa ...

Answer 8

Una vez pasado, el final no es un valor no válido (ni con matrices regulares o iteradores). No se puede desreferenciarlo, pero se puede usar para comparaciones.

std::vector<X>::iterator it;

Este es un iterador singular. Sólo puedes asignarle un iterador válido.

std::vector<X>::iterator it = vec.end();

Este es un iterador perfectamente válido. No puede desreferenciarlo, pero puede usarlo para comparaciones y disminuirlo (suponiendo que el contenedor tenga un tamaño suficiente).