Лекция N. Шаблоны

Примеры шаблонов

Пример шаблонной функции:

template <class T>

void swap (T& a, T& b)
{
  T t(a);
  a = b;
  b = t;
}

По умолчанию шаблонные функции считаются inline (могут совпадать в различных единицах трансляции).

Параметрами шаблонов могут быть

• типы,
• целочисленные значения,
• указатели на типы,
• ссылки,
• указатели на функции (в том числе и на методы).

Пример — функция интегрирования:

double log (double x);

template <class F>
integrate (double a, double b, double eps, F s);

integrate (1, 2, 1e-10, log);

(Здесь log приводится к указателю на функцию.)

Пример с целочисленными параметрами — библиотека линейной алгебры, в которой операции определяются только для операндов одинаковой размерности (векторов, матриц):

template <size_t N>
struct vector
{
  ...
};

template <size_t M, size_t N>
struct matrix
{
  ...
};

template <size_t N>
vector<N> operator+ (const vector<N>& a, const vector<N>& b)
{

  for (size_t i=0; i!= N; i++)
  {
    ...
  }

}

template <size_t L, size_t M, size_t N>
Matrix<L,N> operator* (const Matrix<L,M>& m1,
                       const Matrix<M,N>& m2)
{

  for (size_t i=0; i != L; i++)
  {
    for (size_t j=0; j != N; j++)
    {
      for (size_t k=0; k != M; k++)
      {
        ...
      }
    }
  }

}

Пример шаблонного конструктора копирования:

template <class T>
struct vector
{

  template <class V>
  vector (vector<V> const&)
  {
    ...
  }

};

Указатели можно было бы использовать, скажем, в гипотетическом классе, который имеет в качестве параметра ключ шифрования в виде массива:

template <int* key>
...

Здесь key должен быть указателем на переменную со внешней линковкой (глобальную в сильном смысле).

Отступление: внутренняя линковка

Иногда возникает необходимость в переменных с внутренней линковкой. Пусть имеется очень сложный алгоритм (например, он что-нибудь перестраивает, и в честь этого зовётся reorder), использующий много вспомогательных методов и имеющий внутреннее состояние. В таком случае может оказаться удобным определить класс прямо внутри функции, и там же создать его экземпляр и что-то с ним сделать:

void reorder()
{

  // Внутренняя линковка!
  struct Reorder
  {
    ...
  }

  Reorder x(...);

}

Специализация шаблонов

Специализация — это переопределение шаблона для конкретного значения параметра.

Например, обычный шаблон массива vector<T> не хотелось бы использовать в случае vector<bool>, так как булевы значения разумно упаковывать в целые слова.

template <class T>
struct vector
{
  // обычный массив
};

template <>
struct vector <bool>
{
  // компактный массив булевых значений
};

То, что тут происходит (обратите внимание на синтаксис), и называется (полной) специализацией.

Тонкий момент — перегрузка задействуется до выбора специализации. Если что-то подходит лучше шаблонов, то оно и вызывается.

void f (float);

template <class T>
void f(T);

template <>
void f<double> (double);


f (1.5);           // вызов первой функции
f ((double) 1.5);  // вызов второй функции

Иногда нужно использовать частичную специализацию, такую как в следующем примере.

template <class T>
struct vector
{
  ...
};

template <class V>
struct vector<vector<V> >
{
  ...
};

Здесь после специализации остался не зафиксированный параметр — V. Без надобности частичную специализацию использовать не стоит.

Отступление: польза typedef

С шаблонами бывает удобно использовать typedef, чтобы записывать имена типов более коротко:

typedef vector<vector<int> > VVInt;

Важно, что typedef вводит имя, к которому потом можно обращаться:

template <class T>
struct vector
{

  typedef T value_type;

};

Иногда возникают зависимые имена типов (не путать с dependent types :-) — такие, которые вычисляются из шаблонных параметров. Они могут не опознаваться компилятором, поэтому бывает необходимо указывать ключевое слово typename:

template <class V>
void f (V const& v)
{
  typename V::value_type t = v[0];
  v[0] = v[1];
  v[1] = t;
}

Забавный пример

Следующий код вычисляет при помощи шаблонов N-е число Фибоначчи на стадии компиляции.

// Индуктивное определение:
template <size_t N> struct fib
{
  static const int value = fib<N-1>::value + fib<N-2>::value;
};

// Базовые значения задаются при помощи специализации:
template<> struct fib<0>
{
  static const int value = 0;
};

template<> struct fib<1>
{
  static const int value = 1;
};

В соответствии с правилами раскрытия шаблонов, мы даже знаем, что вычисление будет линейным.

Другие забавные примеры cм. в книге David Abrahams, Aleksey Gurtovoy, C++ Template Metaprogramming, AW, 2004.