Могут ли алгоритмы быть совместимыми с шаблонами выражений?

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] 

Дать lib::any_of в условия operator[] на его входе будут выполнять эту работу, как это было сделано для перегруженного operator+. Однако для этого потребуются аналогичные повторные реализации всех алгоритмов STL, которые я мог бы запускать на таких массивах.

Вопрос: Так предположим, что я хочу, чтобы повторно использовать существующие алгоритмы диапазона на основе (Boost.Range, диапазон-v3) лишь модификацией ExprArray iterators. Возможно ли изменить итератор ExprArrayoperator* и 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

Этот вопрос, кажется, сводится к «Могу ли я реализовать итераторы для моего шаблоны выражений? " который я считаю довольно простым.Предполагая, что «выражение шаблоны» знают их 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 шаблоны "иметь begin и end членов, которые возвращают iterator{*this, 0} и iterator{*this, size()}.

Answer 2

Вопрос здесь, что b+c возвращается. Если он возвращает реальный ExprArray, вы не можете иметь ленивую оценку. Массив необходимо заполнить. Вы не можете хранить ссылки на b и c, так как вы понятия не имеете о своей жизни.

Однако, если она возвращает LazyAdditionкоторого преобразование в ExprArray выполняет сложение, то это тривиально, чтобы видеть, что LazyAddition::iterator может реализовать ленивое добавление, а также. Здесь риск auto a = b+c - это создаст объект LazyAddition с отложенными ссылками, а не объект ExprArray.

Все становится очень неприятным, если вы попытаетесь реализовать ExprArray в качестве умного указателя за кулисами. Конечно, вы можете реализовать Copy-On-Write так, чтобы b+c был ExprArray, который хранит указатель на оба оригинальных массива. Но как только вы позвоните T& ExprArray<T>::operator[], COW вылетел и скопировал массив на один элемент , прочитав! (Правила перегрузки оператора C++ на const не работают хорошо для operator[], версия const выбирается, когда сам аргумент является константой, а не когда используется для доступа для чтения)