c++ - guia - El iterador inverso devuelve basura cuando está optimizado

qgis manual

Question

Tengo una clase de plantilla AsIterator que toma un tipo numérico, en este ejemplo solo un int , y lo convierte en un iterador ( ++ e -- incrementa y disminuye el número, y el operator* simplemente le devuelve una referencia).

Esto funciona bien a menos que esté std::reverse_iterator en un std::reverse_iterator y compilado con cualquier optimización ( -O es suficiente). Cuando optimizo el binario, el compilador elimina la llamada de desreferencia al reverse_iterator y la reemplaza con un valor extraño. Debe notarse que todavía hace la cantidad correcta de iteraciones . Es solo el valor obtenido por el iterador inverso que es basura.

Considera el siguiente código:

#include <iterator>
#include <cstdio>

template<typename T>
class AsIterator : public std::iterator<std::bidirectional_iterator_tag, T> {
    T v;
public:
    AsIterator(const T & init) : v(init) {}

    T &operator*() { return v; }

    AsIterator &operator++() { ++v; return *this; }
    AsIterator operator++(int) { AsIterator copy(*this); ++(*this); return copy; }
    AsIterator &operator--() { --v; return *this; }
    AsIterator operator--(int) { AsIterator copy(*this); --(*this); return copy; }

    bool operator!=(const AsIterator &other) const {return v != other.v;}
    bool operator==(const AsIterator &other) const {return v == other.v;}
};

typedef std::reverse_iterator<AsIterator<int>> ReverseIt;

int main() {
    int a = 0, b = 0;
    printf("Insert two integers: ");
    scanf("%d %d", &a, &b);
    if (b < a) std::swap(a, b);

    AsIterator<int> real_begin(a);
    AsIterator<int> real_end(b);
    for (ReverseIt rev_it(real_end); rev_it != ReverseIt(real_begin); ++rev_it) {
        printf("%d/n", *rev_it);
    }
    return 0;
}

Esto debería, -O0 desde el número insertado más alto al más bajo e imprimirlos, como en esta ejecución (compilada con -O0 ):

Insert two integers: 1 4 
3
2
1

Lo que obtengo con -O es en cambio:

Insert two integers: 1 4 
1
0
0

Puedes probarlo en línea aquí ; los números pueden variar pero siempre están "equivocados" al optimizar el binario.

Lo que he intentado:

• codificar los enteros de entrada es suficiente para producir el mismo resultado;
• el problema persiste con gcc 5.4.0 y clang 3.8.0 , también cuando se usa libc ++ ;
• hacer todos los objetos const (es decir, devolver const int & y declarar todas las variables como tales) no lo soluciona;
• usando el reverse_iterator de la misma manera, por ejemplo, std::vector<int> funciona bien;
• si solo uso AsIterator<int> para un ciclo normal hacia adelante o hacia atrás, funciona bien.
• en mis pruebas, la constante 0 que se imprime está realmente codificada por el compilador, las llamadas a printf ven así cuando se compilan con -S -O :

    movl    $.L.str.2, %edi  # .L.str.2 is "%d/n"
    xorl    %eax, %eax
    callq   printf

Dada la consistencia del clang y el comportamiento de gcc aquí, estoy bastante seguro de que lo están haciendo bien y lo he entendido mal, pero realmente no puedo verlo.

Answer 1

Viendo la implementación libstdc ++ de std::reverse_iterator , se revela algo interesante:

  /**
   *  @return  A reference to the value at @c --current
   *
   *  This requires that @c --current is dereferenceable.
   *
   *  @warning This implementation requires that for an iterator of the
   *           underlying iterator type, @c x, a reference obtained by
   *           @c *x remains valid after @c x has been modified or
   *           destroyed. This is a bug: http://gcc.gnu.org/PR51823
  */
  _GLIBCXX17_CONSTEXPR reference
  operator*() const
  {
    _Iterator __tmp = current;
     return *--__tmp;
  }

La sección @warning nos dice que un requisito del tipo de iterador subyacente es que *x debe seguir siendo válido incluso después de que el iterador subyacente se modifique / destruya.

Mirando el enlace de error mencionado revela información más interesante:

en algún punto entre C ++ 03 y C ++ 11 la definición de reverse_iterator :: operator * se cambió para aclarar esto, haciendo que la implementación de libstdc ++ sea incorrecta. El estándar ahora dice:

[Nota: esta operación debe usar una variable de miembro auxiliar en lugar de una variable temporal para evitar devolver una referencia que persista más allá de la duración de su iterador asociado. (Ver 24.2.) -finalización]

comentario de Jonathan Wakely (2012)

Entonces parece un error ... pero al final del tema:

La definición de reverse_iterator ha sido revertida a la versión C ++ 03, que no usa un miembro adicional, por lo que "iteradores de almacenamiento" no se pueden usar con reverse_iterator.

comentario de Jonathan Wakely (2014)

Por lo tanto, parece que usar std::reverse_iterator con "iteradores de almacenamiento" conduce a UB.

Mirando el DR 2204: " reverse_iterator no debería requerir una segunda copia del iterador base" aclara aún más el problema:

Esta nota en 24.5.1.3.4 [reverse.iter.op.star] / 2:

[Nota: esta operación debe usar una variable de miembro auxiliar en lugar de una variable temporal para evitar devolver una referencia que persista más allá de la duración de su iterador asociado. (Ver 24.2.) -finalización]

[mi nota: creo que la nota anterior solucionaría su problema de UB]

es incorrecto porque tales implementaciones de iterador están descartadas por 24.2.5 [forward.iterators] / 6, donde dice:

Si a y b son ambos referenciables, entonces a == b si y solo si * a y * b están vinculados al mismo objeto.