Можно ли сделать алгоритмы совместимыми с шаблонами выражений?
Предположим, у меня есть некоторый код на основе массива, который может использоваться шаблонами выражений. Например, у меня есть 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, 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,
Решение
Этот вопрос, кажется, сводится к «Могу ли я реализовать итераторы для моих шаблонов выражений?» что я думаю довольно просто. Предполагая, что «шаблоны выражений» знают их 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_;
};
Теперь вам просто нужно сделать так, чтобы «Шаблоны выражений» имели begin а также end члены, которые возвращаются iterator{*this, 0} а также iterator{*this, size()},
Другие решения
Вопрос здесь в том, что 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[] корова начнет работу и скопирует все массив на один элемент читать ! (Правила перегрузки операторов C ++ на const не работают хорошо для operator[]версия const выбирается, когда сам аргумент является const, а не когда используется для доступа на чтение)
detector