Шаблонная рекурсия

Когда я узнал, что с помощью шаблонов C++ можно еще и рекурсию организовать, некоторое время пребывал в состоянии приятного восхищения. А когда узнал, как это все просто делается, то границ моему восторгу и вовсе не было :)

Вот пример вычисления факториала с помощью шаблонов (источник - http://peter.infosreda.com/ru/2008/06/23/template_recursion):

template<int i>
struct Factorial {
 enum { value = i * Factorial<i-1>::value };
};

template<>
struct Factorial<0> {
 enum { value = 1 };
};

А вот пример использования:

unsigned int a = Factorial<10>::value;
int b = Factorial<11>::value;

Если возник вопрос, причем тут enum, ответ прост: enum компилируется всегда, даже если шаблон не инстанцирован. Поэтому даже если мы не используем шаблон, компилятор все равно проверит корректность нашего кода.

Я немножко модифицировал пример, чтобы расширить диапазон с int до long long. Правда, пришлось отказаться от enum:

template<long long i>
struct Factorial {
 const static long long value = i * Factorial<i-1>::value;
};

template<>
struct Factorial<0ll> {
 const static long long value = 1;
};

Думаю, общую идею Вы уловили: описываем в шаблоне константное рекурсивное выражение, в специализации - ограничение рекурсии.

У этого кода, конечно же, есть ряд недостатков:

• В качестве аргумента можно передавать только константные выражения
• Глубина шаблонной рекурсии ограничена. Например, мой g++ 4.4.1 ругнулся, что больше 500 глубину он инстанцировать не будет :)
• Увеличение объема бинарника (простое вычисление Factorial<20> генерирует 20 классов)
• Увеличение времени компиляции

Правда эти недостатки сглаживаются и плюсами:

• О превышении глубины рекурсии мы узнаем от компилятора явно
• О переполнении мы тоже узнаем сразу от компилятора (например, Factorial<30>::value уже не влезает в long long)
• Если мы вычислили Factorial<20>, то все меньшие значения факториала уже вычислены и все необходимые классы инстанцированы

Теперь мое личное мнение: согласен, это все попахивает извращениями, но ведь правда хороший способ весело разобраться в тонкостях работы шаблонов С++ :)

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

Очередное откровенное знание о C++ спешу изложить :)
Короткий ответ на вопрос в сабже, очевидно: ДА.
Теперь на секунду задумайтесь, как это возможно...
Подумали? Я лично ничего придумать не смог. Но все гениальное, как известно, просто:


class C : private A {
private:
 B b;
public:
 C::C()
 try
  : A (...),
   b(...)
 {
 }
 catch(...) {
  ...
 }
};


А теперь задумайтесь: стоит ли вообще перехватывать подобные исключения и если перехватили, что с ними делать?
Для этого сначала полезно ответить на вопросы:

• Что такое время жизни объекта?
• Можно ли считать объект "живым" внутри конструктора/деструктора?
• Можно ли считать, что объект хоть сколько-то просуществовал, если в конструкторе было сгенерировано исключение?

Источник: Герб Саттер "Решение сложных задач на C++" (Задачи 2.13-2.15)

Тест. Хорошо ли вы знаете шаблоны C++?

Встретил в книге Герба Саттера "Решение сложных задач на C++" следующий интересный тест на знание шаблонов C++:

1. Что такое специализация шаблона? Приведите пример.

2. Что такое частичная специализация шаблона? Приведите пример.

3. Рассмотрим следующие объявления:


// 1
template<typename T1, typename T2>
void g(T1, T2);

// 2
template<typename T>
void g(T);

// 3
template<typename T>
g(T, T);

// 4
template<typename T>
g(T*);

// 5
template<typename T>
g(T*, T);

// 6
template<typename T>
g(T, T*);

// 7
template<typename T>
g(int, T*);

// 8
template<>
void g<int>(int);

// 9
void g(int, double);

// 10
void g(int);


Какие из этих функций будут вызваны в каждой из следующих инструкций?
Где это возможно, укажите типы параметров шаблонов:


int i;
double d;
float f;
complex c;

// a
g( i );

// b
g<int>( i );

// c
g( i, i );

// d
g( c );

// e
g( i, f );

// f
g( i, d );

// g
g( c, &c );

// h
g( i, &d );

// i
g( &d, d );

// j
g( &d );

// k
g( d, &i );

// l
g( &i, &i );


Очевидно, задача на понимание и знание правил разрешения перегрузок, а также приоритетов перегрузок и специализаций. Но решение не так очевидно. Развлекайтейсь :)
(ответы смотрите сами в Саттере (задача 1.17), либо могу по просьбе прислать в личку)

Статическая проверка наличия функций-членов и наследования в С++

Некогда мне пришлось столкнуться со следующей проблемой: требуется, чтобы в качестве шаблонного параметра классу могли быть переданы лишь наследники определенного класса.
Конечно, при инстанцировании шаблона будет произведена проверка наличия вызываемых у шаблонного параметра методов. Но этого бывает не достаточно, если:

• необходимо, чтобы шаблонный параметр не просто удовлетворял концепции, а реализовывал определенный интерфейс;
• пока метод, использующий функции-члены этого интерфейса не будет инстанцирован, мы не получим ошибки компиляции.

Я решил этот вопрос следующим образом:


template<typename T>
class TSomeClass {
public:
 ~TSomeClass() {
  T *p = 0;
  TBase *pb = static_cast<TBase*>(p);
  pb; // для подавления предупреждения компилятора о неиспользуемой переменной
 }
};

Принцип работы достаточно прост. Деструктор инстанцируется всегда, поэтому код в нем всегда компилируется. Однако у этого метода есть следующие недостатки:

• в run-time в деструкторе выполняется лишний код, пусть и совсем незначительный;
• метод работает в одну сторону, т.е. мы не можем использовать его для условной компиляции; код либо скомпилирован, если условие наследования выполнилось, либо нет.

Теперь рассмотрим намного более интересное и мощное решение этой проблемы. Его я встретил в книге Герба Саттера "Решение сложных задач на С++" (Задача 1.11 "Расширяемые шаблоны").

Требование наличия функций-членов

В приведенном ниже коде осуществляется проверка наличия у шаблонного типа функции-члена с определенной сигнатурой.


template<typename T>
class HasClone {
public:
 static void Constraints() {
  T* (T::*test)() const = &T::Clone;
  test; // для подавления предупреждения компилятора о неиспользуемой переменной
 }
 HasClone() { void (*p)() = Constraints; }
};


Метод Contstaints() здесь введен для обобщения: все подобные проверки помещаем в него. Сама идея проверки заключается в присваивании указателей на функции. Если сигнатуры функций не совпадают (или функция с таким именем отсутствует) код не скомпилируется. Использовать приведенный класс достаточно просто:


class TFoo : HasClone<TFoo> {
 ...
};


Как видите, можно использовать приватное наследование, т.к. по сути мы не используем никакой функциональности этого класса в run-time. Это решение обладает теми же недостатками, что и мое, но оно обобщенное и может быть легко использовано.

Проверка наследования

Для проверки наследования шаблонного параметра от определенного класса Саттер приводит следующие 2 способа.


// Способ 1
template<typename D, typename B>
class IsDerivedFrom1 {
private:
 class No {};
 class Yes { No no[2]; };
 static Yes Test(B*); // Объявлена, но не определена
 static No Test(...); // Объявлена, но не определена
public:
 enum
 { Is = sizeof(Test(static_cast<D*>(0))) == sizeof(Yes) };
};

// Способ 2
template<typename D, typename B>
class IsDerivedFrom2 {
private:
 static void Constraints(D* p) {
  B *pb = p;
  pb = p;
 }
protected:
 IsDerivedFrom2() { void(*p)(D*) = Constraints; }
};

// Специализация для типа void, т.к. любой указатель преобразуется в void* и обратно
template<typename D>
class IsDerivedFrom2 {
 IsDerivedFrom2 { char *p = (int*)0; /* Error */ }
};


Первый способ не так прост для понимания, зато он дает возможность не просто "ругнуться" во время компиляции, а получить выражение, которое можно использовать. Например, нам необходимо написать специализацию шаблона для всех типов, являющихся наследниками некоторого базового. Обычно в таком случае это решается копи-пастом специализаций для всей иерархии. Думаю, нет смысла объяснять, что такое решение негибкое, нерасширяемое и чревато ошибками. Зато вот как эту проблему можно решить, используя класс IsDerivedFrom1:


template<typename T, int>
class XImpl {
 ...
};

template<typename T>
class XImpl<T, 1> {
 ...
};

template<typename T>
class X {
 XImpl<T, IsDerivedFrom1<T, Cloneable>::Is> impl_;
};