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  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 .
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk