iterators - libreria stack c++

¿Qué tan portátil es la disminución del iterador final?

Question

Acabo de encontrar el decremento del end() iterator en los códigos fuente de mi compañía y me parece extraño. Por lo que recuerdo, esto estaba funcionando en algunas plataformas, pero no para las demás. Tal vez estoy equivocado, sin embargo no pude encontrar nada útil en el estándar sobre eso. El estándar solo dice que end() devuelve un iterador que es el valor pasado al final, pero ¿se garantiza que sea decrementable? ¿Cómo funciona el código que coincide con el estándar?

std::list<int>::iterator it = --l.end();

Gracias por adelantado.

Answer 1

Creo que esta es la cláusula relevante:

ISO / IEC 14882: 2003 C ++ Standard 23.1.1 / 12 - Secuencias

La Tabla 68 enumera las operaciones de secuencia que se proporcionan para algunos tipos de contenedores secuenciales pero no para otros. Una implementación deberá proporcionar estas operaciones para todos los tipos de contenedores que se muestran en la columna "contenedor", y los implementará para tomar el tiempo constante amortizado.

+----------------------------------------------------------------------------+ | Table 68 | +--------------+-----------------+---------------------+---------------------+ | expression | return type | operational | container | | | | semantics | | +--------------+-----------------+---------------------+---------------------+ | a.front() | reference; | *a.begin() | vector, list, deque | | | const_reference | | | | | for constant a | | | +--------------+-----------------+---------------------+---------------------+ | a.back() | reference; | *--a.end() | vector, list, deque | | | const_reference | | | | | for constant a | | | .............................................................................. . . . . . . . . . . .............................................................................. | a.pop_back() | void | a.erase(--a.end()) | vector, list, deque | .............................................................................. . . . . . . . . . .

Por lo tanto, para los contenedores enumerados, no solo se puede decretar el iterador devuelto desde end() , sino que el iterador decrementado también debe ser desreferenciable. (A menos que el contenedor esté vacío, por supuesto. Eso invoca un comportamiento indefinido).

De hecho, las implementaciones vector , list y deque que vienen con el compilador de Visual C ++ lo hacen exactamente como la tabla. Por supuesto, eso no implica que todos los compiladores lo hagan así:

// From VC++''s <list> implementation

reference back()
    {    // return last element of mutable sequence
    return (*(--end()));
    }

const_reference back() const
    {    // return last element of nonmutable sequence
    return (*(--end()));
    }

Nota sobre el código en la tabla:

Norma ISO / IEC 14882: 2003 C ++ 17.3.1.2/6 - Requisitos

En algunos casos, los requisitos semánticos se presentan como código C + +. Tal código pretende ser una especificación de equivalencia de una construcción a otra construcción , no necesariamente como la forma en que la construcción debe ser implementada.

Entonces, si bien es cierto que una implementación puede no implementar esas expresiones en términos de begin() y end() , el estándar C ++ especifica que las dos expresiones son equivalentes. En otras palabras, a.back() y *--a.end() son construcciones equivalentes de acuerdo con la cláusula anterior. Me parece que significa que debe poder reemplazar cada instancia de a.back() con *--a.end() y viceversa y hacer que el código siga funcionando.

Según Bo Persson, la revisión del estándar de C ++ que tengo a mano tiene un defecto con respecto a la Tabla 68.

Propuesta de resolución:

Cambie la especificación en la tabla 68 "Operaciones de secuencia opcionales" en 23.1.1 / 12 para "a.back ()" de

*--a.end()

a

{ iterator tmp = a.end(); --tmp; return *tmp; }

y la especificación para "a.pop_back ()" de

a.erase(--a.end())

a

{ iterator tmp = a.end(); --tmp; a.erase(tmp); }

Parece que todavía puede disminuir el iterador devuelto desde end() y eliminar la referencia del iterador decrementado, siempre que no sea temporal.

Answer 2

Este código no está bien, en caso de que la lista esté vacía, tiene problemas.

Así que verifique que, si la lista no está vacía, el código es muy bueno.