生成器在C++20视图管道中调用了两次 [英] Generator called twice in C++20 views pipeline

问题描述

在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++作为单独的操作。

的filter的operator++必须寻找满足谓词的下一个底层迭代器。这涉及到对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一次，代价是必须处理元素缓存并将您的范围降级为仅为输入范围(以前是双向的)。

这篇关于生成器在C++20视图管道中调用了两次的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！