5

假设我有一些基于数组的代码可供表达式模板使用。例如,我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]

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

问题:所以假设我想通过仅修改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

4

2 回答 2

4

这个问题似乎简化为“我可以为我的表达式模板实现迭代器吗?” 我认为这很简单。假设“表达式模板”知道它们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_;
};

现在您只需安排“表达式模板”具有返回beginand的成员。enditerator{*this, 0}iterator{*this, size()}

于 2015-08-31T17:42:05.867 回答
2

这里的问题是什么b+c返回。如果它返回一个 real ExprArray,你就不能真正进行惰性评估。数组需要填充。您无法存储对 and 的引用bc因为您不知道它们的生命周期。

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

如果您尝试ExprArray在幕后实现智能指针,事情会变得非常糟糕。当然,您可以实现 Copy-On-Write,这样它b+c就是一个 ExprArray,它保持指向两个原始数组的指针。但是,只要您调用T& ExprArray<T>::operator[]COW,COW 就会启动,并将整个数组复制到单个元素read上!(C++ 运算符重载规则const不适用于operator[],当参数本身为 const 时选择 const 版本,而不是用于读取访问时)

于 2015-08-31T11:52:13.950 回答