Reverse iterator returns garbage during optimization

Question

I have an AsIterator template class that takes a numeric type, in this example it is just int , and converts it to an iterator ( ++ and -- ) and reduces the number, and operator* just returns a reference to it).

This works fine if it was not wrapped in std::reverse_iterator and compiled with any optimization ( -O ). When I optimize the binary, the compiler removes the dereference call reverse_iterator and replaces it with some weird value. It should be noted that it still does the correct number of iterations . This is just the value obtained by the reverse iterator, which is garbage.

Consider the following code:

 #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; } 

This should apparently loop from the highest inserted number to the lowest and print it, for example, in this run (compiled with -O0 ):

 Insert two integers: 1 4 3 2 1 

What I get with -O , instead:

 Insert two integers: 1 4 1 0 0 

You can try it online here ; digits may vary, but they are always “wrong” when optimizing a binary file.

---

What I tried:

• hard coding of input integers is enough to get the same result;
• the problem persists with gcc 5.4.0 and clang 3.8.0, also when using lib ++;
• creating all const objects (i.e. returning const int & and declaring all variables as such) does not fix it;
• using reverse_iterator in the same way, for example, some std::vector<int> work fine;
• If I just use AsIterator<int> for a normal forward or reverse loop, it works fine.
• in my tests, the constant 0 that is printed is actually hard-coded by the compiler, the printf calls look like once they are compiled with -S -O :

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

Given the sequence of behavior of clang and gcc, I am sure that they are doing it right, and I misunderstood, but I really don't see it.

Answer 1

Looking at std::reverse_iterator the libstdC ++ implementation shows something interesting:

  /** * @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, @cx, a reference obtained by * @c *x remains valid after @cx has been modified or * destroyed. This is a bug: http://gcc.gnu.org/PR51823 */ _GLIBCXX17_CONSTEXPR reference operator*() const { _Iterator __tmp = current; return *--__tmp; } 

The @warning section states that the requirement for the base type of the iterator is that *x must remain valid even after the base iterator has been modified / destroyed.

Looking at the mentioned error link , you will find more interesting information:

at some point between C ++ 03 and C ++ 11, the definition of reverse_iterator :: operator * was changed to clarify what makes the libstdC ++ implementation incorrect. The standard now says:

[Note. This operation should use an auxiliary member variable, not a temporary variable, to avoid returning a link that is stored outside the life of the associated iterator. (See 24.2.) -End note]

Comment by Jonathan Wackley (2012)

So this seems like an error ... but at the end of the topic:

The definition of reverse_iterator has been reverted to C ++ 03, which does not use an additional element, so stop iterators cannot be used with reverse_iterator.

Commentary by Jonathan Wackley (2014)

So it seems that using std::reverse_iterator with "stashing iterators" really leads to UB.

---

Looking at DR 2204: " reverse_iterator , a second copy of the base iterator is not required , further clarifies the problem:

This is a note in 24.5.1.3.4 [reverse.iter.op.star] / 2:

[Note. This operation should use an auxiliary member variable, not a temporary variable, to avoid returning a link that is stored outside the life of the associated iterator. (See 24.2.) -End note]

[my note: I think the above note will fix your problem with UB]

incorrect, since such iterator implementations are excluded 24.2.5 [forward.iterators] / 6, which states:

If a and b are dereferenced, then a == b if and only if * a and * b are associated with the same object.