[Boost-bugs] [Boost C++ Libraries] #8676: Order of transformed and sliced makes difference

Subject: [Boost-bugs] [Boost C++ Libraries] #8676: Order of transformed and sliced makes difference
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2013-06-09 08:37:52

#8676: Order of transformed and sliced makes difference
------------------------------+------------------------
 Reporter:  j.reid@…          |      Owner:  neilgroves
     Type:  Bugs              |     Status:  new
Milestone:  To Be Determined  |  Component:  range
  Version:  Boost 1.53.0      |   Severity:  Problem
 Keywords:                    |
------------------------------+------------------------
 See issue reported here:
 [http://comments.gmane.org/gmane.comp.lib.boost.devel/242170]

 Suppose you wish to transform and slice a random access range.
 Surprisingly the order in which you apply the operations makes a big
 difference to performance. I'm guessing this is not desired behaviour,
 correct me if I'm wrong. AFAICT when transforming happens before slicing
 the iterators involved in the internals of boost.range are being treated
 as forward iterators not random access iterators. An advance() operation
 is made on one of the iterators with a negative number and this advance
 is O(n) for forward iterators but O(1) for random access. The code below
 demonstrates (adapted from sliced example code).

 On an unrelated note the documentation for transformed does not mention
 that the function is part of the range return type. It is given as:
 boost::transformed_range<typeof(rng)>


 Code to demonstrate the transform then slice problem:


 {{{
 #include <boost/range/adaptor/transformed.hpp>
 #include <boost/range/adaptor/sliced.hpp>
 #include <boost/range/algorithm/copy.hpp>
 #include <boost/assign.hpp>
 #include <iterator>
 #include <iostream>
 #include <vector>
 #include <functional>

 struct identity {
         typedef int result_type;
         result_type operator()( int i ) const { return i; }
 };

 int main(int argc, const char* argv[])
 {
     using namespace boost::adaptors;
     using namespace boost::assign;

     std::vector< int > input;
     input += 1,2,3,4,5,6,7,8,9;

         // slicing then transforming my iterator range
     std::cout << "Sliced then transformed: ";
         boost::copy(
                 input | sliced( 2, 8 ) | transformed( identity() ),
                 std::ostream_iterator< int >( std::cout, ",") );
         std::cout << "\n";

         // transforming then slicing my iterator range - takes a very long
 time....
     std::cout << "Transformed then sliced: ";
         boost::copy(
                 input | transformed( identity() ) | sliced( 2, 8 ),
                 std::ostream_iterator< int >(std::cout, ","));
         std::cout << "\n";

     return 0;
 }


 }}}

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