ВведениеВ данной заметке речь пойдёт об одном из важных применений шаблонного метапрограммирования, а именно о т.н. шаблонах выражений. Шаблоны выражений позволяют кардинально оптимизировать некоторые виды вычислений и при этом сохранить естественную запись математических выражений.
Впервые такое применение шаблонам было найдено в 1994 г. Тоддом Вельдхузеном и Дэвидом Вандерворде. В последствии этот приём был положен в основу таких мат. библиотек как:
Blitz
Matrix Template Library
POOMA
boost ublas
и др.
Для большей ясности, зачем всё это нужно, рассмотрим типичные операции линейной алгебры, такие как сложение, вычитание векторов:
V = c1*V1 + c2*V2 + c3*V3 + c4*V4,
где V1, V2, V3, V4 - вектора, а c1, c2, c3 и c4 - числа.
В примитивной реализации этого выражения создаются временные объекты: вначале для c1*V1, c2*V2, c3*V4 и c4*V4. Затем будут созданы временные объекты (c1*V1 + c2*V2) и (c3*V3 + c4*V4) и в конце будет создан ещё один временный объект для последней суммы.
Если вектора имеют большой размер то затраты на создание и уничтожение временных объектов могут оказаться неприемлемыми.
Но с использованием шаблонов выражений можно писать подобные мат. конструкции без создания временных объектов.
Я покажу на примере класса vector, как это можно реализовать.
Реализация Шаблонов выражений на примере класса vectorИ так, вначале приведу реализацию класса vector.
C++ (Qt)
template <class, size_t, class, class, class> class expr; // Предварительное объявление класса выражений
template <class T, size_t N>
class vector
{
public:
typedef T value_type;
typedef T* iterator;
typedef const T* const_iterator;
typedef T& reference;
typedef const T& const_reference;
typedef size_t size_type;
vector() { m_elems = new T[size()]; }
explicit vector(const T& value) {
m_elems = new T[size()];
std::fill(begin(), end(), value);
}
vector(const vector<T, N>& other) {
m_elems = new T[size()];
std::copy(other.begin(), other.end(), begin());
}
~vector() { delete [] m_elems; }
vector &operator=(const vector<T, N>& v) {
if (this != &v) {
std::copy(v.begin(), v.end(), begin());
}
return *this;
}
template <class L, class R, class F> // Оператор присваивания для шаблонного выражения
vector &operator=(const expr<T, N, L, R, F>& expr) {
for (size_t i = 0; i < N; ++i)
m_elems[i] = expr[i];
return *this;
}
reference operator()(size_type i) throw(std::out_of_range) {
if (i >= size())
throw std::out_of_range("specmath::vector<T, N>: index out of range");
return m_elems[i];
}
const_reference operator()(size_type i) const throw(std::out_of_range) {
if (i >= size())
throw std::out_of_range("specmath::vector<T, N>: index out of range");
return m_elems[i];
}
reference operator[](size_type i) {
return m_elems[i];
}
const_reference operator[](size_type i) const {
return m_elems[i];
}
static size_type size() { return N; }
iterator begin() { return m_elems; }
iterator end() { return m_elems + N; }
const_iterator begin() const { return m_elems; }
const_iterator end() const { return m_elems + N; }
vector &operator*=(const T &value) {
std::transform(begin(), end(), begin(), std::bind2nd(std::multiplies<T>(), value));
return *this;
}
vector &operator/=(const T &value) {
std::transform(begin(), end(), begin(), std::bind2nd(std::divides<T>(), value));
return *this;
}
vector &operator+=(const vector<T, N>& v) {
std::transform(begin(), end(), v.begin(), begin(), std::plus<T>());
return *this;
}
vector &operator-=(const vector<T, N>& v) {
std::transform(begin(), end(), v.begin(), begin(), std::minus<T>());
return *this;
}
template <class L, class R, class F>
vector &operator+=(const expr<T, N, L, R, F>& expr) {
for (size_t i = 0; i < N; ++i)
m_elems[i] += expr[i];
return *this;
}
template <class L, class R, class F>
vector &operator-=(const expr<T, N, L, R, F>& expr) {
for (size_t i = 0; i < N; ++i)
m_elems[i] -= expr[i];
return *this;
}
private:
value_type *m_elems;
};
// ...
Здесь следует обратить внимание на пару тонких моментов.
Во-первых, вначале идёт предварительное объявление шаблонного класса expr, который фактически и будет являться шаблоном выражения. Его реализация будет описана ниже.
Во-вторых, появились дополнительные операторы:
C++ (Qt)
template <class L, class R, class F> // Оператор присваивания для шаблонного выражения
vector &operator=(const expr<T, N, L, R, F>& expr) {
for (size_t i = 0; i < N; ++i)
m_elems[i] = expr[i];
return *this;
}
template <class L, class R, class F>
vector &operator+=(const expr<T, N, L, R, F>& expr) {
for (size_t i = 0; i < N; ++i)
m_elems[i] += expr[i];
return *this;
}
template <class L, class R, class F>
vector &operator-=(const expr<T, N, L, R, F>& expr) {
for (size_t i = 0; i < N; ++i)
m_elems[i] -= expr[i];
return *this;
}
которые принимают в качестве аргумента наше шаблонное выражение.
Теперь посмотрим на реализацию класса expr:
C++ (Qt)
template <class T, size_t N, class Left, class Right, class F>
class expr
{
public:
expr(const Left& lhs, const Right& rhs)
: left(lhs), right(rhs) {}
T operator[](size_t index) const {
return _f(left[index], right[index]);
}
private:
const Left& left;
const Right& right;
F _f;
};
Первые два параметра шаблона T и N - определяют тип элементов вектора и его длину. Далее идут параметры Left и Right - это левое и правое выражения, которые нужно объединить в одно выражение. Последний параметр F - задаёт бинарную функцию(std::plus<T>, std::minus<T>, std::multiplies<T> и т.д.) в зависимости от того, какая операция должна быть произведена над выражениями Left и Right.
Конструктор класса expr просто копирует ссылки на объекты Left и Right.
Далее объявляется оператор[] в котором с помощью объекта бинарной функции конструируется итоговое выражение.
Чтоб было понятно, как это всё работает рассмотрим операцию сложения двух векторов. Для этого определим оператор+
C++ (Qt)
template <class T, size_t N>
const expr<T, N, vector<T, N>, vector<T, N>, std::plus<T> > operator+(const vector<T, N> &x, const vector<T, N> &y)
{
return expr<T, N, vector<T, N>, vector<T, N>, std::plus<T> >(x, y);
}
Возвращаемое значение в данном случае представляет из себя не вектор, а шаблонное выражение. при этом временных объектов не создаётся. при создании expr в его конструктор передаются ссылки, которые он просто копирует.
Однако это ещё не всё..
Сейчас мы уже можем писать выражения типа:
V = V1+V2
и это будет работать. Но мы пока не можем написать выражения типа:
V = V1+V2+V3+...
Для этого нужно определить ещё такие операторы+, а именно:
1) вектор + выражение
2) выражение + вектор
3) выражение + выражение
Приведу лишь первый вариант (остальные пишутся аналогично)
C++ (Qt)
template <class T, size_t N, class L, class R, class F>
const expr<T, N, vector<T, N>, expr<T, N, L, R, F>, std::plus<T> > operator+(const vector<T, N> &x, const expr<T, N, L, R, F> &y)
{
return expr<T, N, vector<T, N>, expr<T, N, L, R, F>, std::plus<T> >(x, y);
}
Теперь, после того, как мы реализовали все 4 оператора+ мы спокойно можем писать любые комбинации, наподобии следующих:
v = v1+(V2+V3)+V4+(V5+V6+V7)+V8, и т.д.
Теперь, если аналогично определить оператор- (минус) то мы почти будем у цели) Для этого оператора всё в точности аналогично, нужно лишь везде поменять std::plus<T> на std::minus<T>
C++ (Qt)
template <class T, size_t N>
const expr<T, N, vector<T, N>, vector<T, N>, std::minus<T> > operator-(const vector<T, N> &x, const vector<T, N> &y)
{
return expr<T, N, vector<T, N>, vector<T, N>, std::minus<T> >(x, y);
}
template <class T, size_t N, class L, class R, class F>
const expr<T, N, vector<T, N>, expr<T, N, L, R, F>, std::minus<T> > operator-(const vector<T, N> &x, const expr<T, N, L, R, F> &y)
{
return expr<T, N, vector<T, N>, expr<T, N, L, R, F>, std::minus<T> >(x, y);
}
//...
Теперь осталось реализовать лишь оператор умножения вектора на число и деление на число.
Предлагаю это проделать в качестве самостоятельного задания)
После полной реализации всех операторов мы получаем возможность писать абсолютно любые выражения с нашим вектором. И самое главное, что ещё на этапе компиляции выражение, например вида:
C++ (Qt)
v = a*v1 + a2*(v2+a3*v3)-(v4+v5) + v6*a4
будет развёрнуто в конструкцию вида:
C++ (Qt)
for (size_t i = 0; i < v.size(); ++i)
v[i] = a*v1[i] + a2*(v2[i]+a3*v3[i])-(v4[i]+v5[i]) + v6[i]*a4
причём без создания и уничтожения дополнительных временных объектов.
Надеюсь, это было кому то полезным)
Исходники с примером приатачены.
