For it to be a `std::random_access_iterator_tag` it must a reference. That is, `iterator_traits<X>::reference` must be an actual reference.
Can you point me at a reference (pun not intended) for this requirement? The sites I've looked at don't mention this [1-3]. Is it a requirement for, say, bidirectional iterators too? Your message makes it sound like this is specific to random access iterators.
It is a requirement for forward iterators and higher. The authoritative source for the requirement is the C++ standard. In the 2003 standard, section 24.1.3 has a table listing requirements for forward iterators. One of them is that if 'a' if a forward iterator, '*a' is a valid expression and has type 'T&', where T is the iterator's value type. In the 2011 standard, it's even more clear: section 24.2.5 states that one of the requirements for X to be a forward iterator is that "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'". Regarding the sites you linked to, the completeness and accuracy of their information is to be taken with a grain of salt, but I do see [1] list as a requirement for forward, bidirectional, and random access iterators that they "can be deferenced as an lvalue", which effectively requires that 'reference' be a reference type.
And in any case, isn't this a flaw? my_iterator can be advanced etc. in constant time - why should the STL be forced to use a possibly-suboptimal overload of some algorithm on account of the reference type?
Yes, it's a flaw. The STL unnecessarily conflates iterator traversal and iterator value access in its iterator categories. This is why Boost has developed, and uses, its own iterator concepts. See [2]. You can take advantage of Boost's iterator concepts by modifying 'func' from your original post to dispatch on boost::iterator_traversal<TITerator>::type() instead of std::iterator_traits<TIterator>::iterator_category(), since traversal is the relevant aspect in that case.
If the iterator's reference must be a real reference type, then why does iterator_facade not check this at compile time?
It "must" be a real reference type only from the point of view of the STL's broken iterator concepts. Boost.Iterator is perfectly happy to let you write an iterator whose traversal is random-access but whose 'reference' is not a reference type, which will then be considered an 'input iterator' by the STL. Hope that helps. Regards, Nate [1] http://www.cplusplus.com/reference/iterator/ForwardIterator/ http://www.cplusplus.com/reference/iterator/BidirectionalIterator/ http://www.cplusplus.com/reference/iterator/RandomAccessIterator/ [2] http://www.boost.org/doc/libs/1_53_0/libs/iterator/doc/new-iter-concepts.htm...