过滤范围、lambdas和is_sorted

Question

这是我对过滤迭代器问题的一个简化版本(因此没有必要要求我以不同的方式重写它以避免过滤器)。奇怪的是，在真正的代码中，只有is_sorted才是问题所在，其他用途似乎运行良好。

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

这不能用Clang++ 3.5和G++ 4.9编译(在Mac上，目前为止)：

$ 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; });
                             ^

我知道将我的lambda存储在std::function中可以修复它，但我想避免支付它的代价。在std::is_sorted周围使用自定义包装器并不能解决这个问题。这个问题似乎与其他人(如boost transform iterator and c++11 lambda)有关，但它不是--至少他们的治疗方法不适用于这里。

谢谢!

Answer 1

在is_sorted内部复制用于迭代序列的迭代器，以便可以用来比较相邻的元素。这意味着，filtered的谓词(即lambda)也需要复制，即使它从未实际用于增量尾随迭代器。其他复制迭代器的算法也会遇到同样的问题，例如adjacent_find。

复制其迭代器的算法与不复制迭代器的算法的区别在于前者被称为“多通”算法，并要求它们的迭代器类型满足ForwardIterator，而后者是单通的，只需要InputIterator。

解决方案是给您的lambda本地作用域生存期并通过reference_wrapper传递它。

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

另一种选择是+

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

不过，这只适用于无圈套的羔羊，而且可能不清楚。