[Boost-bugs] [Boost C++ Libraries] #1993: Incorrect iterator_category computation in some iterator classes in Boost.Iterator

Subject: [Boost-bugs] [Boost C++ Libraries] #1993: Incorrect iterator_category computation in some iterator classes in Boost.Iterator
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2008-06-06 08:57:32

#1993: Incorrect iterator_category computation in some iterator classes in
Boost.Iterator
--------------------------------------------------------+-------------------
 Reporter:  Wijnand Suijlen <wijnandsuijlen_at_[hidden]>  |       Owner:  dave    
     Type:  Bugs                                        |      Status:  new     
Milestone:  Boost 1.36.0                                |   Component:  iterator
  Version:  Boost 1.35.0                                |    Severity:  Problem 
 Keywords:                                              |  
--------------------------------------------------------+-------------------
 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^2^ ). 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.

-- 
Ticket URL: <http://svn.boost.org/trac/boost/ticket/1993>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.