Re: [boost] [iterator] Silent-but-deadly bug in iterator_facade category

Subject: Re: [boost] [iterator] Silent-but-deadly bug in iterator_facade category
From: Nathan Ridge (zeratul976_at_[hidden])
Date: 2013-05-07 00:04:28

> > 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.html