生成器在C++20视图管道中调用了两次

2022-05-16 00:00:00 c++ c++20 std-ranges range-v3

views适配器的简单管道中,有gen函数被调用以生成值序列(使用内部状态),然后对其进行筛选。

令人惊讶和违反直觉(至少对我来说)的是,生成器函数在每次迭代中被调用两次,因此对同一筛选器的下一次检查失败(筛选的值不会在管道中重复使用)。

您知道这是否是正确的预期行为(以及为什么)?

在GCC 10.3、11.1和干线(code)中使用libstdc++测试,和range-v3与GCC和乒乓(code)一起测试。

int main() {
  int n = 0;
  auto gen = [&n]() {
    auto result = ++n;
    std::cout << "Generate [" << result << "]
";
    return result;
  };

  auto tmp =
      ranges::views::iota(0)
      | ranges::views::transform([gen](auto &&) { return gen(); })
      | ranges::views::filter([](auto &&i) {
          std::cout << "#1 " << i << " " << (i % 2) << "
";
          return (i % 2) == 1;
        });

  for (auto &&i : tmp | ranges::views::take(1)) {
    std::cout << "#2 " << i << " " << ((i % 2) == 1) << "
";
    assert(((i % 2) == 1));
  }
}

注意:如果gen函数被编写为具有内部状态的可变函数,则它不会编译:

  auto gen = [n=0]() mutable {
    auto result = ++n;
    std::cout << "Generate [" << result << "]
";
    return result;
  };

(我知道纯函数更好)


解决方案

您知道这是否是正确的预期行为(以及为什么)?

是:这是预期行为。这是迭代模型的固有属性,在迭代模型中,operator*operator++作为单独的操作。

filteroperator++必须寻找满足谓词的下一个底层迭代器。这涉及到对transform的迭代器进行操作,这涉及调用函数。但是,一旦我们找到下一个迭代器,当我们再次读取它时,它将再次调用转换。在代码片段中:

decltype(auto) transform_view<V, F>::iterator::operator*() const {
    return invoke(f_, *it_);
}

decltype(auto) filter_view<V, P>::iterator::operator*() const {
    // reading through the filter iterator just reads
    // through the underlying iterator, which in this
    // case means invoking the function
    return *it_;
}

auto filter_view<V, P>::iterator::operator++() -> iterator& {
    for (++it_; it_ != ranges::end(parent_->base_); ++it_) {
        // when we eventually find an iterator that satisfies this
        // predicate, we will have needed to read it (which calls
        // the functions) and then the next operator* will do
        // that same thing again
        if (invoke(parent_->pred_, *it_))) {
            break;
        }
    }
    return *this;
}

结果是我们对每个满足该谓词的元素调用该函数两次。


解决办法是要么不关心(让转换足够便宜以至于调用两次不重要,或者让筛选器足够少以至于重复转换的数量不重要,或者同时考虑两者),或者向管道中添加缓存层。

C++20 Ranges中没有缓存视图,但Range-v3中有一个名为views::cache1

ranges::views::iota(0)
    | ranges::views::transform(f)
    | ranges::views::cache1
    | ranges::views::filter(g)

这确保每个元素最多只调用f一次,代价是必须处理元素缓存并将您的范围降级为仅为输入范围(以前是双向的)。

相关文章