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.
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
andb
denote values of typeX
orconst X
,difference_type
andreference
refer to the typesiterator_traits<X>::difference_type
anditerator_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 toT
; ifX
is a const iterator,reference
is a reference toconst T
,