¿Por qué los rangos de iterador estándar [comenzar, finalizar] en lugar de [comenzar, finalizar]?

204

¿Por qué define el estándar? end() como uno pasado el final, en lugar de en el final real?

Perrito
fuente
19
Supongo que "porque eso es lo que dice el estándar" no es suficiente, ¿verdad? :)
Luchian Grigore
39
@LuchianGrigore: Por supuesto que no. Eso erosionaría nuestro respeto por la (gente detrás) del estándar. Deberíamos esperar que haya una razón para las elecciones hechas por el estándar.
Kerrek SB
44
En resumen, las computadoras no cuentan como las personas. Pero si tiene curiosidad acerca de por qué las personas no cuentan como las computadoras, le recomiendo The Nothing that Is: A Natural History of Zero para una mirada en profundidad a los problemas que los humanos tuvieron al descubrir que hay un número que es uno menos de una.
John McFarlane
8
Debido a que solo hay una forma de generar el "último", a menudo no es barato porque tiene que ser real. Generar "te caíste del final del acantilado" siempre es barato, muchas representaciones posibles servirán. (nulo *) "ahhhhhhh" estará bien.
Hans Passant
66
Miré la fecha de la pregunta y por un segundo pensé que estabas bromeando.
Asaf

Respuestas:

286

El mejor argumento fácilmente es el que hizo el propio Dijkstra :

  • Desea que el tamaño del rango sea un simple final de diferencia  :  comience ;

  • incluir el límite inferior es más "natural" cuando las secuencias degeneran en vacías, y también porque la alternativa ( excluyendo el límite inferior) requeriría la existencia de un valor centinela "uno antes del comienzo".

Todavía necesita justificar por qué comienza a contar en cero en lugar de uno, pero eso no era parte de su pregunta.

La sabiduría detrás de la convención [comenzar, finalizar] vale la pena una y otra vez cuando tiene algún tipo de algoritmo que trata con múltiples llamadas anidadas o iteradas a construcciones basadas en rangos, que se encadenan naturalmente. Por el contrario, el uso de un rango doblemente cerrado incurriría en códigos extraños y extremadamente desagradables y ruidosos. Por ejemplo, considere una partición [ n 0 , n 1 ) [ n 1 , n 2 ) [ n 2 , n 3 ). Otro ejemplo es el ciclo de iteración estándar for (it = begin; it != end; ++it), que se ejecutaend - begin tiempos. El código correspondiente sería mucho menos legible si ambos extremos fueran inclusivos, e imagine cómo manejaría los rangos vacíos.

Finalmente, también podemos hacer un buen argumento de por qué el conteo debe comenzar en cero: con la convención medio abierta para rangos que acabamos de establecer, si se le da un rango de N elementos (por ejemplo, enumerar los miembros de una matriz), entonces 0 es el "comienzo" natural para que pueda escribir el rango como [0, N ), sin correcciones ni compensaciones incómodas.

En pocas palabras: el hecho de que no veamos el número 1en todas partes en los algoritmos basados ​​en rango es una consecuencia directa de la convención [comienzo, fin] y motivación.

Kerrek SB
fuente
2
La típica C para iteración de bucle sobre una matriz de tamaño N es "for (i = 0; i <N; i ++) a [i] = 0;". Ahora, no puede expresar eso directamente con iteradores: muchas personas perdieron el tiempo tratando de hacer que <sea significativo. Pero es casi igualmente obvio decir "para (i = 0; i! = N; i ++) ..." Por lo tanto, es conveniente asignar 0 para comenzar y N para terminar.
Krazy Glew
3
@KrazyGlew: No puse tipos en mi ejemplo de bucle deliberadamente. Si piensa en beginy endcomo ints con valores 0y N, respectivamente, encaja perfectamente. Podría decirse que es la !=condición más natural que la tradicional <, pero nunca lo descubrimos hasta que empezamos a pensar en colecciones más generales.
Kerrek SB
44
@KerrekSB: Estoy de acuerdo en que "nunca descubrimos que [! = Es mejor] hasta que empezamos a pensar en colecciones más generales". En mi humilde opinión, esa es una de las cosas por las que Stepanov merece crédito: hablar como alguien que intentó escribir tales bibliotecas de plantillas antes del STL. Sin embargo, discutiré acerca de que "! =" Es más natural, o, más bien, ¡argumentaré que! = Probablemente ha introducido errores, eso <atraparía. Piensa en (i = 0; i! = 100; i + = 3) ...
Krazy Glew
@KrazyGlew: Su último punto está algo fuera de tema, ya que la secuencia {0, 3, 6, ..., 99} no tiene la forma sobre la que preguntó el OP. Si desea que sea así, debe escribir una ++plantilla de iterador incremental step_by<3>, que luego tendría la semántica anunciada originalmente.
Kerrek SB
@KrazyGlew Incluso si <alguna vez ocultara un error, de todos modos es un error . Si alguien usa !=cuando debería usar <, entonces es un error. Por cierto, ese rey del error es fácil de encontrar con pruebas unitarias o afirmaciones.
Phil1970
80

En realidad, muchas cosas relacionadas con iteradores de repente tienen mucho más sentido si consideras que los iteradores no apuntan a los elementos de la secuencia, sino en el medio , con la eliminación de la referencia para acceder al siguiente elemento directamente. Entonces el iterador de "un extremo pasado" de repente tiene sentido inmediato:

   +---+---+---+---+
   | A | B | C | D |
   +---+---+---+---+
   ^               ^
   |               |
 begin            end

Obviamente beginapunta al comienzo de la secuencia y endapunta al final de la misma secuencia. La desreferenciación beginaccede al elemento A, y la desreferenciación endno tiene sentido porque no tiene ningún elemento correcto. Además, agregar un iterador ien el medio da

   +---+---+---+---+
   | A | B | C | D |
   +---+---+---+---+
   ^       ^       ^
   |       |       |
 begin     i      end

e inmediatamente ve que el rango de elementos de begina icontiene los elementos Ay Bmientras que el rango de elementos de ia endcontiene los elementos Cy D. Desreferenciari le da al elemento el derecho, es el primer elemento de la segunda secuencia.

Incluso el "off-by-one" para iteradores inversos de repente se vuelve obvio de esa manera: invertir esa secuencia da:

   +---+---+---+---+
   | D | C | B | A |
   +---+---+---+---+
   ^       ^       ^
   |       |       |
rbegin     ri     rend
 (end)    (i)   (begin)

He escrito los correspondientes iteradores no inversos (base) entre paréntesis a continuación. Verá, el iterador inverso que pertenece a i(que he nombrado ri) todavía apunta entre elementos By C. Sin embargo, debido a la inversión de la secuencia, ahora el elemento Bestá a la derecha.

celtschk
fuente
2
Esta es, en mi humilde opinión, la mejor respuesta, aunque creo que podría ilustrarse mejor si los iteradores apuntaran a los números, y los elementos estaban entre los números (la sintaxis foo[i]) es una abreviatura del elemento inmediatamente después de la posición i). Pensando en ello, me pregunto si podría ser útil para un lenguaje tener operadores separados para "elemento inmediatamente después de la posición i" y "elemento inmediatamente antes de la posición i", ya que muchos algoritmos funcionan con pares de elementos adyacentes y dicen " Los elementos a cada lado de la posición i "pueden estar más limpios que" Los elementos en las posiciones i e i + 1 ".
supercat
@supercat: se suponía que los números no indicaban las posiciones / índices del iterador, sino que indicaban los elementos mismos. Reemplazaré los números con letras para aclararlo. De hecho, con los números dados, begin[0](suponiendo un iterador de acceso aleatorio) accedería al elemento 1, ya que no hay ningún elemento 0en mi secuencia de ejemplo.
celtschk
¿Por qué se usa la palabra "comenzar" en lugar de "comenzar"? Después de todo, "comenzar" es un verbo.
user1741137
@ user1741137 Creo que "comenzar" está destinado a ser la abreviatura de "principio" (que ahora tiene sentido). "comenzar" es demasiado largo, "comenzar" suena como un buen ajuste. "inicio" entraría en conflicto con el verbo "inicio" (por ejemplo, cuando tiene que definir una función start()en su clase para iniciar un proceso específico o lo que sea, sería molesto si entra en conflicto con una ya existente).
Fareanor
74

¿Por qué el Estándar defineend() como uno pasado el final, en lugar de en el final real?

Porque:

  1. Evita manipulaciones especiales para rangos vacíos. Para rangos vacíos, begin()es igual a end()&
  2. Simplifica el criterio de finalización para los bucles que iteran sobre los elementos: los bucles simplemente continúan mientras end()no se alcanza.
Alok Save
fuente
64

Porque entonces

size() == end() - begin()   // For iterators for whom subtraction is valid

y no tendrás que hacer cosas incómodas como

// Never mind that this is INVALID for input iterators...
bool empty() { return begin() == end() + 1; }

y no escribirás accidentalmente código erróneo como

bool empty() { return begin() == end() - 1; }    // a typo from the first version
                                                 // of this post
                                                 // (see, it really is confusing)

bool empty() { return end() - begin() == -1; }   // Signed/unsigned mismatch
// Plus the fact that subtracting is also invalid for many iterators

Además: ¿Qué find()devolvería si end()apuntara a un elemento válido?
¿ Realmente quieres que se llame a otro miembro invalid()que devuelva un iterador no válido?
Dos iteradores ya son lo suficientemente dolorosos ...

Ah, y mira esta publicación relacionada .


También:

Si el end fue antes del último elemento, ¿cómo llegarías insert()al verdadero final?

usuario541686
fuente
2
Esta es una respuesta altamente subestimada. Los ejemplos son concisos y directos al grano, y los "También" no fueron dichos por nadie más y son el tipo de cosas que parecen muy obvias en retrospectiva, pero me parecen revelaciones.
underscore_d
@underscore_d: ¡Gracias! :)
user541686
por cierto, en caso de que parezca un hipócrita por no votar, ¡eso es porque ya lo hice en julio de 2016!
underscore_d
@underscore_d: jajaja, ni siquiera me di cuenta, ¡pero gracias! :)
user541686
22

El idioma de iterador de rangos semicerrados [begin(), end())se basa originalmente en la aritmética de puntero para matrices simples. En ese modo de operación, tendría funciones a las que se les pasó una matriz y un tamaño.

void func(int* array, size_t size)

La conversión a rangos semicerrados [begin, end)es muy simple cuando tiene esa información:

int* begin;
int* end = array + size;

for (int* it = begin; it < end; ++it) { ... }

Para trabajar con rangos completamente cerrados, es más difícil:

int* begin;
int* end = array + size - 1;

for (int* it = begin; it <= end; ++it) { ... }

Dado que los punteros a las matrices son iteradores en C ++ (y la sintaxis fue diseñada para permitir esto), es mucho más fácil llamar std::find(array, array + size, some_value)que llamar std::find(array, array + size - 1, some_value).


Además, si trabaja con rangos semicerrados, puede usar el !=operador para verificar la condición final, porque (si sus operadores están definidos correctamente) <implica !=.

for (int* it = begin; it != end; ++ it) { ... }

Sin embargo, no hay una manera fácil de hacer esto con rangos completamente cerrados. Estás atrapado con <=.

El único tipo de iterador que admite <y >opera en C ++ son los iteradores de acceso aleatorio. Si tuviera que escribir un <=operador para cada clase de iterador en C ++, tendría que hacer que todos sus iteradores fueran totalmente comparables, y tendría menos opciones para crear iteradores menos capaces (como los iteradores bidireccionales activados std::listo los iteradores de entrada) que funcionan iostreams) si C ++ usa rangos completamente cerrados.

Ken Bloom
fuente
8

Con el end()señalador más allá del final, es fácil iterar una colección con un bucle for:

for (iterator it = collection.begin(); it != collection.end(); it++)
{
    DoStuff(*it);
}

Al end()señalar el último elemento, un bucle sería más complejo:

iterator it = collection.begin();
while (!collection.empty())
{
    DoStuff(*it);

    if (it == collection.end())
        break;

    it++;
}
Anders Abel
fuente
0
  1. Si un recipiente está vacío, begin() == end().
  2. Los programadores de C ++ tienden a usar en !=lugar de <(menos de) en condiciones de bucle, por lo tanto, end()es conveniente apuntar a una posición fuera del extremo.
Andreas DM
fuente