Filtered ranges, lambdas, and is_sorted

Question

This is a stripped-down version of a problem I have with filtered iterators (so there's no point in asking me to rewrite it differently to avoid the filters). Weirdly enough, in the real code only is_sorted seems to the problem, other uses appear to work fine.

#include <vector>
#include <boost/range/adaptor/filtered.hpp>
#include <boost/range/algorithm_ext/is_sorted.hpp>

int main(int argc, const char* argv[])
{
  using namespace boost::adaptors;
  std::vector<int> all = {1,2,3,4,5,6,7,8,9};
  auto some = all | filtered([] (int i) { return i % 2; });
  return boost::is_sorted(some);
}

This fails to compile with both Clang++ 3.5 and G++ 4.9 (on Mac OS X, up to date):

$ clang++-mp-3.5 -std=c++11 -isystem /opt/local/include/ foo.cc
In file included from foo.cc:3:
In file included from /opt/local/include/boost/range/algorithm_ext/is_sorted.hpp:18:
/opt/local/include/boost/detail/is_sorted.hpp:25:28: error: object of type
      'boost::filter_iterator<(lambda at foo.cc:9:30), std::__1::__wrap_iter<int
      *> >' cannot be assigned because its copy assignment operator is
      implicitly deleted
  for (; it != last; first = it, ++it)
                           ^
...

/opt/local/include/boost/iterator/filter_iterator.hpp:106:17: note: copy
      assignment operator of 'filter_iterator<(lambda at foo.cc:9:30),
      std::__1::__wrap_iter<int *> >' is implicitly deleted because field
      'm_predicate' has a deleted copy assignment operator
      Predicate m_predicate;
                ^
foo.cc:9:30: note: lambda expression begins here
  auto some = all | filtered([] (int i) { return i % 2; });
                             ^

I know storing my lambda in a std::function fixes it, but I want to avoid paying its price. Using a custom wrapper around std::is_sorted does not fix the issue. This problem seems related to others (e.g., boost transform iterator and c++11 lambda), but it's not – at least their cure does not apply here.

Thanks!

Answer 1

Inside is_sorted the iterator used for iterating over the sequence is copied, so that it can be used to compare adjacent elements. This means that the predicate of filtered (i.e. your lambda) needs to be copied as well, even though it is never actually used to increment the trailing iterator. Other algorithms that copy the iterator would have the same problem, e.g. adjacent_find.

The difference between algorithms that copy their iterators and those that do not is that the former are termed "multipass" algorithms, and require their iterator type to satisfy ForwardIterator, while the latter are single-pass and only require InputIterator.

The solution is to give your lambda local scope lifetime and pass it by reference_wrapper:

auto odd = [] (int i) { return i % 2; };
auto some = all | filtered(std::ref(odd));

An alternative is to coerce your lambda to a function pointer using +:

auto some = all | filtered(+[] (int i) { return i % 2; });

This works only with captureless lambdas, though, and is potentially unclear.