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 вместо имени класса.