Incorrect iterator_category computation in some iterator classes in Boost.Iterator

[Wijnand Suijlen <wijnandsuijlen@…>]

In contrary of the documentation of Boost.Iterator transform_iterator and zip_iterator are not random access iterators, when their bases are. I discovered this, when profiling an application. The culprit was std::lower_bound on a transform_iterator< Function, std::deque<int> >: Its complexity was not O( log n ) but more something like O( n² ). The attached program shows with help of the Boost concept check, that the iterator_category in transform_iterator and zip_iterator isn't computed correctly.

[Wijnand Suijlen <wijnandsuijlen@…>]

Smallest program suffering from bug

[Dave Abrahams]

The categories are correctly computed. An iterator cannot be called a standard forward iterator unless its operator* returns value_type&, and that is not possible with a zip iterator or with a transform iterator whose function returns by value. Please see http://www.boost.org/doc/libs/1_35_0/libs/iterator/doc/new-iter-concepts.html#motivation

If you think you can get away with it, you can always specialize std::iterator_traits<It> to lie about the iterator's iterator_category.