https://svn.boost.org/trac10/ticket/1993 <p> 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&lt; Function, std::deque&lt;int&gt; &gt;: 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. </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/1993 Trac 1.4.3 Wijnand Suijlen <wijnandsuijlen@…> Fri, 06 Jun 2008 08:58:27 GMT https://svn.boost.org/trac10/ticket/1993 https://svn.boost.org/trac10/ticket/1993 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">example.cpp</span> </li> </ul> <p> Smallest program suffering from bug </p> Ticket Dave Abrahams Fri, 06 Jun 2008 15:25:55 GMT https://svn.boost.org/trac10/ticket/1993#comment:1 https://svn.boost.org/trac10/ticket/1993#comment:1 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">invalid</span> </li> </ul> <p> The categories are correctly computed. An iterator cannot be called a standard forward iterator unless its operator* returns value_type&amp;, and that is not possible with a zip iterator or with a transform iterator whose function returns by value. Please see <a href="http://www.boost.org/doc/libs/1_35_0/libs/iterator/doc/new-iter-concepts.html#motivation">http://www.boost.org/doc/libs/1_35_0/libs/iterator/doc/new-iter-concepts.html#motivation</a> </p> <p> If you think you can get away with it, you can always specialize std::iterator_traits&lt;It&gt; to lie about the iterator's iterator_category. </p> Ticket