librerias - map c++

¿Por qué se usa "!=" Con iteradores en lugar de "<"?

Question

Estoy acostumbrado a escribir bucles como este:

for (std::size_t index = 0; index < foo.size(); index++)
{
    // Do stuff with foo[index].
}

Pero cuando veo bucles de iteradores en el código de otros, se ven así:

for (Foo::Iterator iterator = foo.begin(); iterator != foo.end(); iterator++)
{
    // Do stuff with *Iterator.
}

Encuentro que el iterator != foo.end() está en desacuerdo. También puede ser peligroso si el iterator se incrementa en más de uno.

Parece más "correcto" usar iterator < foo.end() , pero nunca lo veo en código real. Por qué no?

Answer 1

Respuesta corta: como Iterator no es un número, es un objeto.

Respuesta más larga: hay más colecciones que matrices lineales. Los árboles y los hashes, por ejemplo, no se prestan realmente a "este índice está antes de este otro índice". Para un árbol, dos índices que viven en ramas separadas, por ejemplo. O, cualquiera de los dos índices en un hash: no tienen ningún orden, por lo que cualquier orden que les imponga es arbitrario.

Usted no tiene que preocuparse por "falta" End() . Tampoco es un número, es un objeto que representa el final de la colección. No tiene sentido tener un iterador que lo supere, y de hecho no puede.

Answer 2

Todos los iteradores son de igualdad comparable. Sólo los iteradores de acceso aleatorio son comparativamente relacionales. Los iteradores de entrada, los iteradores hacia adelante y los iteradores bidireccionales no son comparables relacionalmente.

Por lo tanto, la comparación con != Es más genérica y flexible que la comparación con < .

Existen diferentes categorías de iteradores porque no todos los rangos de elementos tienen las mismas propiedades de acceso. Por ejemplo,

• Si tiene un iterador en una matriz (una secuencia contigua de elementos), es trivial compararlos; solo tienes que comparar los índices de los elementos apuntados a (o los punteros a ellos, ya que los iteradores probablemente solo contienen punteros a los elementos);

• Si tiene iteradores en una lista vinculada y desea probar si un iterador es "menor que" otro iterador, debe recorrer los nodos de la lista vinculada desde un iterador hasta que llegue al otro iterador o llegue al final. de la lista.

La regla es que todas las operaciones en un iterador deben tener una complejidad de tiempo constante (o, como mínimo, una complejidad de tiempo sublineal). Siempre puede realizar una comparación de igualdad en tiempo constante, ya que solo tiene que comparar si los iteradores apuntan al mismo objeto. Por lo tanto, todos los iteradores son de igualdad comparable.

Además, no se le permite incrementar un iterador más allá del final del rango al que apunta. Entonces, si terminas en un escenario en el it != foo.end() no hace lo mismo it < foo.end() , ya tienes un comportamiento indefinido porque has pasado la iteración hasta el final del rango.

Lo mismo es cierto para los punteros en una matriz: no se le permite incrementar un puntero más allá de uno más allá del final de la matriz; Un programa que lo hace exhibe un comportamiento indefinido. (Obviamente, no ocurre lo mismo con los índices, ya que los índices son solo enteros).

Algunas implementaciones de la Biblioteca estándar (como la implementación de la Biblioteca estándar de Visual C ++) tienen un código de depuración útil que planteará una afirmación cuando haga algo ilegal con un iterador como este.