Re: [boost] boost.range bug in transformed or sliced

Subject: Re: [boost] boost.range bug in transformed or sliced
From: Jeffrey Lee Hellrung, Jr. (jeffrey.hellrung_at_[hidden])
Date: 2013-06-06 12:09:53

On Thu, Jun 6, 2013 at 1:22 AM, John Reid <j.reid_at_[hidden]>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