c++ - libreria - ¿Por qué los rangos del iterador estándar[comienzan, finalizan) en lugar de[comienzan, terminan]?

stl c++ español

Question

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

Answer 1

1. Si un contenedor está vacío, begin() == end() .
2. Los programadores de C ++ tienden a utilizar != vez de < (menos que) en condiciones de bucle, por lo tanto, es conveniente tener el end() apuntando a una posición que está fuera de término.

Answer 2

Con el end() apuntando hacia el final, es fácil iterar una colección con un ciclo for:

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

Con end() apuntando al último elemento, un bucle sería más complejo:

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

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

    it++;
}

Answer 3

De hecho, muchas cosas relacionadas con el iterador de repente tienen mucho más sentido si consideramos que los iteradores no apuntan a los elementos de la secuencia sino que están entre ellos , con la eliminación de referencias accediendo al siguiente elemento directamente a ella. Entonces, el iterador de "un extremo pasado" de repente tiene sentido inmediato:

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

Obviamente begin puntos al comienzo de la secuencia, y los puntos end al final de la misma secuencia. La desreferencia begin acceso al elemento A , y el desreferenciamiento no tiene sentido porque no hay ningún elemento adecuado para ello. Además, agregar un iterador i en el medio da

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

e inmediatamente verá que el rango de elementos desde el begin hasta el i contiene los elementos A y B mientras que el rango de elementos de i hasta el end contiene los elementos C y D La desreferenciación da el elemento correcto, es el primer elemento de la segunda secuencia.

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

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

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

Answer 4

El mejor argumento es el del propio Dijkstra :

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

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

Aún debe justificar por qué comienza a contar en cero en lugar de uno, pero eso no formaba parte de su pregunta.

La sabiduría detrás de la convención [inicio, finalización] se paga una y otra vez cuando se tiene algún tipo de algoritmo que maneje 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 implicaría código poco común y extremadamente desagradable y ruidoso. Por ejemplo, considere una partición [ n ₀ , n ₁ ) [ n ₁ , n ₂ ) [ n ₂ , n ₃ ). Otro ejemplo es el ciclo iterativo estándar for (it = begin; it != end; ++it) , que ejecuta las horas end - begin . El código correspondiente sería mucho menos legible si ambos extremos fueran inclusivos, e imagina cómo manejarías los rangos vacíos.

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

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

Answer 5

La expresión idiomática del iterador de intervalos semicerrados [begin(), end()) se basa originalmente en la aritmética del 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 medio cerrados [begin, end) es muy simple cuando tienes esa información:

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

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

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

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

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

Como 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 a std::find(array, array + size, some_value) que a llamar a 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 hacerlo con rangos completamente cerrados. Estás atrapado con <= .

El único tipo de iterador que admite operaciones < y > 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 todos sus iteradores totalmente comparables, y tendría menos opciones para crear iteradores menos capaces (como los iteradores bidireccionales en std::list , o los iteradores de entrada que operan en iostreams ) si C ++ usó rangos totalmente cerrados.

Answer 6

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 otro miembro llamado invalid() que devuelve un iterador no válido?
Dos iteradores ya son suficientemente dolorosos ...

Ah, y mira this publicación relacionada .

También:

Si el end fuera anterior al último elemento, ¿cómo insert() en el verdadero final?

Answer 7

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

Porque:

1. Evita un manejo especial para rangos vacíos. Para rangos vacíos, begin() es igual a end() y
2. Hace que el criterio final sea simple para los bucles que iteran sobre los elementos: los bucles simplemente continúan mientras no se llegue a end() .