On 06-06-2013 10:22, John Reid wrote:

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.

[snip]

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)>

A defect.

Code to demonstrate the transform then slice problem:

I'm puzzled too. I can understand that filter_iterators needs to be bidirectional. sliced should not compile if it is not given random access. So it must be something else. -Thorsten

On Thu, Jun 6, 2013 at 1:22 AM, John Reid <j.reid@mail.cryst.bbk.ac.uk>wrote:

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; } };

I'm guessing the result of your transform will be classified very "badly", i.e., as a SinglePassRange or something like that. Your reference type isn't a "real" reference, so the iterator_category of the iterators of your transformed range will be Input (I think) rather than Random Access :( This is required by the standard, is a defect (IMHO), and has been discussed at length on this list in the past. E.g., try changing the result_type of identity to int & or int const & (with a corresponding change to the parameter type). 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; }

HTH, - Jeff