Boost logo

Boost :

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] [2]

Boost list run by bdawes at, gregod at, cpdaniel at, john at