Can algorithms be made compatible with expression templates?

Question

Suppose I have some array-based code that is enabled to be used by expression templates. E.g., I have operator[] for these arrays overloaded and also have overloaded the arithmetic operator + etc.

Now I would like to let the STL algorithm any_of run on such arrays. The simple way is to do

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

Of course, I would like to be able to short-circuit the computation and have a modified (range-based) lib::any_of that does

// 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]

Writing lib::any_of in terms of operator[] on its input will do that job, the same as it was done for the overloaded operator+. However, this would require similar reimplementations of all STL algorithms that I could possibly run on such arrays.

Question: So suppose I want to re-use existing range-based algorithms (Boost.Range, range-v3) by only modifying the ExprArray iterators. Is it possible to modify the ExprArray iterator operator* and operator++ in such a way that this is transparent to range-based algorithms?

// 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{});

So if the algorithm version actually is implemented in terms of iterators, the loop for (auto it = first; it != last; ++it) needs *it to be aware of the fact that it needs to compute b[i] + c[i], and ++it has to know that it needs to do ++i.

Answer 1

This question seems to reduce to "Can I implement iterators for my expression templates?" which I think is fairly straightforward. Assuming that "expression templates" know their size and have overloaded operator[] an iterator simply needs to hold a reference to the expression object and an offset into the range it represents:

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_;
};

Now you simply have to arrange for "Expression templates" to have begin and end members that return iterator{*this, 0} and iterator{*this, size()}.

Answer 2

The question here is what b+c returns. If it returns a real ExprArray, you can't really have lazy evaluation. The array needs to be filled. You can't store references to b and c since you have no idea about their lifetime.

However, if it returns a LazyAddition whose conversion to ExprArray performs the addition, then it's trivial to see that LazyAddition::iterator can implement lazy addition as well. The risk here is auto a = b+c - this will create a LazyAddition object with pending references, not an ExprArray object.

Things get really nasty if you try to implement the ExprArray as a smart pointer behind the scenes. Sure, you could implement Copy-On-Write so that b+c is an ExprArray which keeps pointer to both original arrays. But as soon as you call T& ExprArray<T>::operator[] the COW will kick in, and copy the whole array on a single element read ! (C++ operator overloading rules on const do not work well for operator[], the const version gets selected when the argument itself is const, not when used for read access)