for_each on a reverse_iterator of a custom bidirectional iterator requires OutputIterator

Question

I created a simple immutable bidirectional iterator:

#include <iostream>
#include <memory>
#include <iterator>
#include <vector>
#include <algorithm>

class my_iterator : public std::iterator<std::bidirectional_iterator_tag, int
//, std::ptrdiff_t, int*, int
> {
  int d_val;
public:
  my_iterator() : d_val(0) {}
  my_iterator(int val) : d_val(val) {}

  my_iterator  operator--(int) { d_val--; return my_iterator(d_val + 1); }
  my_iterator &operator--()    { d_val--; return *this; }
  my_iterator  operator++(int) { d_val++; return my_iterator(d_val - 1); }
  my_iterator &operator++()    { d_val++; return *this; }

  int operator*() const { return d_val; }

  bool operator==(my_iterator const  &o) { return d_val == o.d_val; }
  bool operator!=(my_iterator const  &o) { return d_val != o.d_val ; }
};


int main() {
  std::reverse_iterator<my_iterator> reverse_it_begin(25);
  std::reverse_iterator<my_iterator> reverse_it_end(12);
  std::for_each(reverse_it_begin, reverse_it_end, [](int e){ std::cout << e << ' '; });
  std::cout << '\n';
}

The iterator is immutable, since operator*() returns an int instead of a int reference. To the best of my understanding this is possible, since whether an iterator meets the BidirectionalIterator concept or the OutputIterator concept is orthogonal (all 4 combinations are possible).

However, the code below results in an compile time error, namely:

/usr/include/c++/4.9/bits/stl_iterator.h:164:9: error: invalid initialization of non-const reference of type 'std::reverse_iterator<my_iterator>::reference {aka int&}' from an rvalue of type 'int'

Full context:

In file included from /usr/include/c++/4.9/bits/stl_algobase.h:67:0,
                from /usr/include/c++/4.9/bits/char_traits.h:39,
                from /usr/include/c++/4.9/ios:40,
                from /usr/include/c++/4.9/ostream:38,
                from /usr/include/c++/4.9/iostream:39,
                from prog.cpp:1:
/usr/include/c++/4.9/bits/stl_iterator.h: In instantiation of 'std::reverse_iterator<_Iterator>::reference std::reverse_iterator<_Iterator>::operator*() const [with _Iterator = my_iterator; std::reverse_iterator<_Iterator>::reference = int&]':
/usr/include/c++/4.9/bits/stl_algo.h:3755:6:   required from '_Funct std::for_each(_IIter, _IIter, _Funct) [with _IIter = std::reverse_iterator<my_iterator>; _Funct = main()::<lambda(int)>]'
prog.cpp:30:86:   required from here
/usr/include/c++/4.9/bits/stl_iterator.h:164:9: error: invalid initialization of non-const reference of type 'std::reverse_iterator<my_iterator>::reference {aka int&}' from an rvalue of type 'int'
  return *--__tmp;
        ^

Success time: 0 mem

The pages on cppreference about the reverse_iterator and for_each state that both need a BidirectionalIterator and an InputIterator respectively. I think both requirements are met, however the stl still assigns a dereferenced value to a reference.

Why does stl's for_each/reverse_iterator expect a T &operator*() on an iterator that needs not to be an OutputIterator?

PS: The commented line can fix the problem by stating that references should be stored by value, very hacky of course.

Answer 1

It doesn't require an OutputIterator. The problem is that your code violates a basic requirement for all input iterators^*: *r must return reference^**. Your code defines my_iterator::reference as int & (due to std::iterator's default template argument), but operator* returns an int.

It is valid for reference to not actually be a reference type (istreambuf_iterator<charT>::reference, for example, is charT), but operator* must return reference. reverse_iterator relies on this, as it defines its reference member, and hence the return type of its operator*, as its wrapped iterator's reference.

According to the standard, for forward iterators or stronger, reference must be a reference type. But the standard itself lies when it calls vector<bool>::iterator a random access iterator (its operator* must return a proxy), and the committee is apparently planning to lie some more with the array_view proposal. So while making my_iterator::reference int would mean that it is technically no longer a bidirectional iterator, in practice it's likely to work. Hopefully with Concepts we can get better and finer-grained requirements than what we currently have.

---

_{^* There's a contradiction in the standard with respect to output iterators. See LWG issue 2437.}

_{^** Technically, std::iterator_traits<It>::reference. For class types, iterator_traits by default defers to the member typedef It::reference.}

Answer 2

The iterator requirements for all iterators are listed in [iterator.iterators]:

reference refers to the typedef of iterator_traits<my_iterator<..>>:

In the following sections, a and b denote values of type X or const X, difference_type and reference refer to the types iterator_traits<X>::difference_type and iterator_traits<X>::reference, respectively, [..]

Since the primary template of iterator_traits just defaults the typedefs to the types defined in the template argument itself, we're talking about the reference typedef of my_iterator - and that one is inherited from the base std::iterator<...>, which defaults it to T&.
Your operator* returns an int though, which is certainly not int&.

Uncommenting your line is fine for InputIterators since int is convertible to int:

It fails for ForwardIterators though - [forward.iterators]/1:

A class or pointer type X satisfies the requirements of a forward iterator if

— if X is a mutable iterator, reference is a reference to T; if X is a const iterator, reference is a reference to const T,