算法能否与表达式模板兼容？

Question

假设我有一些基于数组的代码可以被表达式模板使用。例如，我为这些数组重载了 operator[]，并且还重载了算术运算符 + 等。

现在我想让STL算法any_of运行在这样的数组上。简单的方法是做

ExprArray<double, N> b, c; // init etc. 
auto a = b + c;            // for (auto i = 0; i < N; ++i) { a[i] = b[i] + c[i]; }
auto res = std::any_of(begin(a), end(a), SomePred{});

当然，我希望能够缩短计算并修改（基于范围的）lib::any_of

// only compute b[i] + c[i] until SomePred is satisified
auto res = lib::any_of(b + c, SomePred{}); // write as explicit loop over b[i] + c[i]

在其输入中根据 operator[] 编写 lib::any_of 就可以完成这项工作，就像对重载 operator+ 所做的一样。但是，这将需要对所有 STL 算法进行类似的重新实现，我可能会在此类数组上运行。

问题：所以假设我想重新使用现有的基于范围的算法（Boost.Range，range-v3）只需修改ExprArray iterators。是否可以以对基于范围的算法透明的方式修改 ExprArray 迭代器 operator* 和 operator++？

// only compute b[i] + c[i] until SomePred is satisified
// needs to eventually dispatch to 
// for (auto i = 0; i < N; ++i)
//     if (SomePred(b[i] + c[i])) return true;
// return false;
auto res = ranges::any_of(b + c, SomePred{});

因此，如果算法版本实际上是根据迭代器实现的，则循环 for (auto it = first; it != last; ++it) 需要 *it 意识到它需要计算 b[i] + c[i] 的事实，并且 ++it 必须知道它需要做 ++i.

Answer 1

这里的问题是什么b+creturns。如果它 returns 是一个真正的 ExprArray，你就不能真正进行惰性求值。数组需要填充。您不能存储对 b 和 c 的引用，因为您不知道它们的生命周期。

但是，如果 returns 一个 LazyAddition 的转换到 ExprArray 执行加法，那么看到 LazyAddition::iterator 也可以实现惰性加法。这里的风险是 auto a = b+c - 这将创建一个带有挂起引用的 LazyAddition 对象，而不是 ExprArray 对象。

如果您尝试将 ExprArray 实现为幕后的智能指针，事情就会变得非常糟糕。当然，您可以实现写入时复制，以便 b+c 是一个 ExprArray，它保留指向两个原始数组的指针。但是一旦你调用 T& ExprArray<T>::operator[] COW 就会启动，并在单个元素 read 上复制 whole 数组！（const 上的 C++ 运算符重载规则不适用于 operator[]，当参数本身为 const 时选择 const 版本，而不是用于读取访问时）

Answer 2

这个问题似乎简化为 "Can I implement iterators for my expression templates?"，我认为这很简单。假设 "expression templates" 知道它们的 size 并且重载了 operator[] 迭代器只需要保存对表达式对象的引用和它表示的范围内的偏移量：

template <class Expr>
class iterator {
public:
  using iterator_category = ranges::random_access_iterator_tag;
  using difference_type = std::ptrdiff_t;
  using value_type = typename Expr::value_type;

  iterator() = default;
  constexpr iterator(Expr& e, difference_type i) :
    expr_{&e}, i_{i} {}

  constexpr bool operator==(const iterator& that) const {
    return assert(expr_ == that.expr_), i_ == that.i_;
  }
  constexpr bool operator!=(const iterator& that) const {
    return !(*this == that);
  }
  // Similarly for operators <, >, <=, >=

  value_type operator*() const {
    return (*expr_)[i_];
  }
  value_type operator[](difference_type n) const {
    return (*expr_)[i_ + n];

  iterator& operator++() & { ++i_; }
  iterator operator++(int) & { auto tmp = *this; ++*this; return tmp; }
  // Similarly for operator--

  iterator operator+(difference_type n) const {
    return iterator{expr_, i_ + n};
  }
  // Similarly for operators -, +=, and -=

  friend iterator operator+(difference_type n, const iterator& i) {
    return i + n;
  }

private:
    Expr* expr_;
    difference_type i_;
};

现在您只需安排 "Expression templates" 有 begin 和 end 成员，return iterator{*this, 0} 和 iterator{*this, size()}。

算法能否与表达式模板兼容？

Can algorithms be made compatible with expression templates?

c++

expression-templates

range-v3