11.9. Представление числового вектора фиксированного размера
11.9. Представление числового вектора фиксированного размера
Проблема
Требуется иметь эффективное представление числовых векторов фиксированного размера.
Решение
В программном обеспечении обычного типа часто более эффектный результат по сравнению с valarray дает применение специальной реализации вектора, когда его размер заранее известен на этапе компиляции. Пример 11.17 показывает, как можно реализовать шаблон вектора фиксированного размера, названный здесь kvector.
Пример 11.17. kvector.hpp
#include <algorithm>
#include <cassert>
template<class Value_T, unsigned int N>
class kvector {
public:
// открытые поля
Value_T m[N];
// открытые имена, вводимые typedef
typedef Value_T value_type;
typedef Value_T* iterator;
typedef const Value_T* const_iterator;
typedef Value_T& reference;
typedef const Value_T& const_reference;
typedef size_t size_type;
// определение более короткого синонима для kvector
typedef kvector self;
// функции-члены
template<typename Iter_T>
void copy(Iter_T first, Iter_T last) {
copy(first, last, begin());
}
iterator begin() { return m; }
iterator end() { return m + N; }
const_iterator begin() const { return m; }
const_iterator end() const { return m + N; }
reference operator[](size_type n) { return m[n]; }
const_reference operator[](size_type n) const { return m[n]; }
static size_type size() { return N; }
// векторные операции
self& operator+=(const self& x) {
for (int i=0; i<N; ++i) m[i] += x.m[i];
return *this;
}
self& operator-=(const self& x) {
for (int i=0; i<N; ++i) m[i] -= x.m[i];
return *this;
}
// скалярные операции
self& operator=(value_type x) {
std::fill(begin(), end(), x);
return *this;
}
self& operator+=(value_type x) {
for (int i=0; i<N; ++i) m[i] += x;
return *this;
}
self& operator-=(value_type x) {
for (int i=0; i<N; ++i) m[i] -= x;
return *this;
}
self& operator*=(value_type x) {
for (int i=0; i<N; ++i) m[i] *= x;
return *this;
}
self& operator/=(value_type x) {
for (int i=0; i<N; ++i) m[i] /= x;
return *this;
}
self& operator%=(value_type x) {
for (int i=0; i<N; ++i) m[i] %= x;
return *this;
}
self operator-() {
self x;
for (int i=n; i<N; ++i) x.m[i] = -m[i];
return x;
}
// дружественные операторы
friend self operator+(self x, const self& y) { return x += у; }
friend self operator-(self x, const self& y) { return x -= y; }
friend self operator+(self x, value_type y) { return x += y; }
friend self operator-(self x, value_type y) { return x -= y; }
friend self operator*(self x, value_type y) { return x *= y; }
friend self operator/(self x, value_type y) { return x /= y; }
friend self operator%(self x, value type y) { return x %= y; }
};
Пример 11.18 показывает, как можно применять шаблон класса kvector.
Пример 11.18. Применение вектора kvector
#include "kvector.hpp"
#include <algorithm>
#include <numeric>
#include <iostream>
using namespace std;
int main() {
kvector<int, 4> v = { 1, 2, 3, 4 };
cout << "sum = " << accumulate(v.begin(), v.end(), 0) << endl;
v *= 3;
cout << "sum = " << accumulated.begin(), v.end(), 0) << endl;
v += 1;
cout << "sum = " << accumulate(v.begin(), v.end(), 0) << endl;
}
Программа примера 11.18 выдаст следующий результат.
sum = 10
sum = 30
sum = 34
Обсуждение
Представленный в примере 11.17 шаблон kvector является гибридом valarray и шаблона массива, предложенного в TR1. Как и valarray, вектор kvector представляет собой последовательность значений заданного числового типа, однако подобно массиву TR1::array его размер известен на этапе компиляции.
Характерной особенностью шаблона kvector является то, что для его инициализации может использоваться синтаксис, применяемый для массивов, и то, что он имеет функции-члены begin и end. Фактически kvector можно рассматривать как псевдоконтейнер, т.е. он удовлетворяет некоторым, но не всем требованиям концепции стандартного контейнера. Следствие этого — более легкое применение kvector в стандартных алгоритмах по сравнению с valarray.
Другое преимущество шаблонного класса kvector состоит в том, что он поддерживает синтаксис, используемый при инициализации массивов.
int x;
kvector<int, 3> k = { x = 1, x+2, 5}
Этот синтаксис возможен только потому, что kvector является агрегатом. Агрегат (aggregate) — это массив или класс, который не имеет объявленных пользователем конструкторов, закрытых или защищенных данных-членов, базового класса и виртуальных функций. Следует отметить, что все же можно при объявлении kvector его заполнить значениями по умолчанию.
kvector<int, 3> k = {};
В результате этот вектор будет заполнен нулями.
Как вы видите, при его реализации мной был найден компромисс между полным удовлетворением требований, предъявляемых к стандартным контейнерам, и возможностью использования синтаксиса, применяемого при инициализации массивов. Аналогичный компромисс был найден при проектировании шаблона array, удовлетворяющего требованиям TR1.
Возможно, самое большое преимущество kvector над реализациями динамического вектора проявляется в его высокой производительности. По двум причинам шаблон kvector значительно эффективнее, чем большинство реализаций динамических векторов: компиляторы очень хорошо справляются с оптимизацией циклов фиксированною размера, и здесь нет динамического распределения памяти. Различия в производительности особенно проявляются при работе с небольшими матрицами (например, 2?2 или 3?3), которые часто встречаются во многих приложениях.
Что означает имя «self», введенное оператором typedef?
Введенное с помощью typedef имя self я использую в примере 11.17 и в последующих примерах; оно представляет собой удобное краткое имя, которое я использую для ссылки на тип текущего класса. Программу значительно легче писать и воспринимать при использовании self вместо имени класса.