Нетривиальное использование шаблонов. Часть первая.

Учимся генерировать массивы

Идея статьи навеяна такой задачей:

В общем, такая тема: мне нужно сделать 2 класса: Stack_Numbers и Stack_Operations. Как вы уже поняли в одном хранятся числа, в другом -арифметические операции. Нужно вытаскивать из Stack_Numbers два числа, потом из Stack_Operations операцию, делать ее и результат обратно в Stack_Numbers. Теперь вопрос: как мне понять какая операция, если мне нельзя пользоваться не "if", не "switch", не..., в общем, ничем для сравнивания???

Т. е. у человека есть код операции. Ему нужно вызвать некую функцию, соответствующую этому коду, но при этом нельзя пользоваться сравнениями. Очевидное решение - завести массив и в соответствующие его элементы поместить указатели на соответствующие функции. Все, вроде бы, хорошо. И решение полностью удовлетворяет условию задачи. Но есть несколько но. Зададимся несколькими вопросами:

Что мы будем делать, если количество операций увеличится?

Что мы будем делать, если коды операций изменятся?

Что мы будем делать, если изменится сигнатура метода?

Если первый вопрос еще имеет достаточно простой ответ (руками добавляем нужные функции в нужные места массива), то второй гораздо сложнее - придется перестраивать весь массив. И делать это "руками". А при таком раскладе есть риск ошибиться.

Еще задачка:

Необходимо вызвать метод, соответствующий заданному числу. Например, для числа 1 вызвать метод Method1, для числа 2 - метод Method2 и т. д.

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

Для возьмем решение, использующее массив. Для простоты будем считать, что методов у нас 4:

void Method0();
void Method1();
void Method2();
void Method3();

Вызывать мы их будем через некоторый метод-диспетчер:

void CallMethod(int methodId);
На первой итерации мы создаем массив этих методов:
typedef void (*MethodPtr)();
MethodPtr Methods[] = {
Method0, 
	Method1,
	Method2,
	Method3
};

и реализуем диспетчер таким образом:

void CallMethod(int methodId)
{
	return Methods[methodId]();
}

Примечание: я намеренно не обращаю внимания на контроль передаваемых значений, дабы не загромождать код лишними проверками.

Улучшать, вроде бы, и нечего. Но это только на первый взгляд. Сейчас достаточно сказать, что мы можем "попросить" компилятор самому сгенерировать нам массив Methods. Но "попросить" его надо хорошо, так, чтобы он не отказался :).

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

template struct Int2Type {};

После чего объявим методы следующим образом:

void Method(const Int2Type<0>&)
{
	std::cout << "Method 0" << std::endl;
}

void Method(const Int2Type<1>&)
{
	std::cout << "Method 1" << std::endl;
}

void Method(const Int2Type<2>&)
{
	std::cout << "Method 2" << std::endl;
}

void Method(const Int2Type<3>&)
{
	std::cout << "Method 3" << std::endl;
}

Может возникнуть логичный вопрос - "зачем? Ведь методы, объявленные таким образом, нельзя поместить в один массив!". Да, методы - нельзя. Но зато такой метод легко вызывается из класса, объявленного следующим образом:

template struct MethodThunk
{
	void operator()() {Method(Int2Type());}
};

Для завершения "подготовительной" работы сделаем этот класс производный от некоторого базового:

struct MethodThunkBase
{
	virtual void operator()() = 0;
};

template struct MethodThunk : public MethodThunkBase {...};

Что мы получили? Мы получили шаблонный класс, который, в зависимости от параметра шаблона, вызывает необходимый метод.

Сейчас мы можем реализовать поставленную задачу так:

MethodThunkBase* Methods[] = 
{
	new MethodThunk<0>(),
	new MethodThunk<1>(),
	new MethodThunk<2>(),
	new MethodThunk<3>()
};

, а функцию CallMethod так:

MethodThunkBase& CallMethod(int idx)
{
	return *Methods[idx];
}

Что нам дает такой подход? Тип элементов массива никак не завязан на сигнатуру метода. Также не завязан на сигнатуру и метод доступа - функция CallMethod. Кроме того - такой подход позволяет нам сгенерировать такой массив автоматически, поскольку все, что нам теперь нужно - это создать экземпляр класса MethoThunk с параметром шаблона, соответствующему индексу массива. Попытаемся это сделать. Для этого напишем следующий класс:

template class Derived, int NMethods> struct MethodsArray
{
	template class Initer;
	friend class Initer;
	Base* m_Methods[NMethods];

	template struct ThunkItem
	{
		Derived m_MethodThunk;
		ThunkItem(Base** methods)
		{
			methods[n] = &m_MethodThunk;
		}
	};
	template struct Initer
	{
		ThunkItem m_Item;
		Initer m_Initer;
		Initer(Base** methods) : m_Item(methods), m_Initer(methods)
		{
		}
	};
	template<> struct Initer<0>
	{
		ThunkItem<0> m_Item;
		Initer(Base** methods) : m_Item(methods)
		{
		}
	};
	Initer m_Initer;
public:
	MethodsArray() : m_Initer(m_Methods)
	{
	}
	Base& operator[](int idx)
	{
		return *m_Methods[idx];
	}
};

Как работает этот класс? На вход он принимает 3 параметра:

Base - тип базового класса, указатели на который будут помещены в массив;

Derived - шаблонный тип производного класса, экземпляры на который будут помещены в массив;

NMethods - размер массива.

В классе объявляется две переменных. Первая - m_Methods - массив указателей на базовые класс. Ее, собственно, и будем в итоге индексировать. Вторая - m_Initer - переменная, отвечающая за инициализацию массива m_Methods, и хранит конкретные экземпляры шаблонного класса Derived.

При конструировании экземпляра класса MethodsArray производится конструирование его члена m_Initer. При этом класс m_Initer реализован так, что он рекурсивно включает самого себя (но с разными аргументами шаблона), что позволяет нам сконструировать необходимое количество экземпляров класса Derived. Для того, чтобы рекурсия не была бесконечной -применяется механизм частичной специализации. Если класс Initer инстанцируется с аргументом шаблона, равным нулю, то рекурсивного включения класса не происходит.

Конкретный экземпляр класса Derived хранится в экземпляре класса ThunkItem. Это сделано исключительно для удобства инициализации, дабы не переписывать дважды код, помещяющий в массив нужный элемент. Класс ThunkItem инстанцируется индексом в массиве, по которому нужно разместить экземпляр класса Derived. Этим же числом инстанцируется и класс Derived. Таким образом мы получаем то, что хотели - в нужное места массива помещается экземпляр класса, отвечающего за вызов метода с соответствующим индексом.

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

MethodsArray handlers;

handlers[0]();
handlers[1]();
handlers[2]();
handlers[3]();

выводит на экран вполне ожидаемое

В реализации этого класса применены два "трюка". Трюк первый - так называемый шаблонный параметр шаблона. Это позволяет нам внутри класса ThunkItem инстанцировать этот параметр с разными аргументами шаблона. Второй трюк - полная специализация. Этот трюк позволяет нам не уйти в бесконечную рекурсию при заполнении массива.

Что мы имеем в итоге? В итоге мы имеем универсальный класс (MethodsArray), объявив который мы автоматически создаем массив указателей на методы (а точнее, на объекты), поведение которых полностью зависит от их местоположения в массиве, а также от реализации соответствующих классов, передаваемых в качестве параметра шаблона. Если нам необходимо объявить метод, зависящий от любой другой константы - достаточно объявить соответствующий метод и увеличить количество элементов в массиве. "Местоположения" метода в массиве выбирается самим компилятором, по этому, при изменении "зависимости" метода от константы, достаточно внести необходимые изменения в объявление метода. Все остальное компилятор может сделать сам.

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

class OperationBase
{
public:
	virtual int operator()(int val1, int val2) = 0;
};

enum
{
	Plus = '+',
	Minus = '-',
	Mul = '*',
	Div = '/'
};

template class Operator : public OperationBase
{
public:
	virtual int operator()(int val1, int val2)
	{
		std::cout << "Invalid operation" << std::endl;
		return 0;
	}
};

template<> class Operator : public OperationBase
{
public:
	virtual int operator()(int val1, int val2)
	{
		return val1 + val2;
	}
};

template<> class Operator : public OperationBase
{
public:
	virtual int operator()(int val1, int val2)
	{
		return val1 - val2;
	}
};

template<> class Operator : public OperationBase
{
public:
	virtual int operator()(int val1, int val2)
	{
		return val1 * val2;
	}
};

template<> class Operator
 : public OperationBase
{
public:
	virtual int operator()(int val1, int val2)
	{
		return val1 / val2;
	}
};

MethodsArray handlers;

std::cout << handlers['-'](20, 10) << std::endl;
std::cout << handlers['+'](20, 10) << std::endl;
std::cout << handlers['*'](20, 10) << std::endl;
std::cout << handlers['/'](20, 10) << std::endl;
std::cout << handlers[' '](20, 10) << std::endl;

Выдает нам:

что вполне ожидаемо.

При этом необходимо обратить внимание - нас абсолютно не интересует, какие коды каким обработчикам соответствуют. Главное, чтобы они попадали в указанную размерность массива. Все остальное компилятор сделает сам. Также нас абсолютно не заботит конкретная сигнатура вызываемого метода - достаточно того, что клиентский код и класс MethodThunkBase владеют этой информацией.

Но в этой бочке меда есть и не малая ложка дегтя. Основное ограничение этого подхода - размер получаемого массива. В частности, компилятор MSVC++ 7.1 позволяет генерировать массивы размером около 1000 элементов. Дальше у него начинаются проблемы во внутренних структурах, о чем он сообщает в виде ошибки компиляции. Кроме того, с увеличением размера массива увеличивается и время компиляции, а также размер получаемого кода. Но это очевидные ограничения, поскольку в этом случае вся работа переложена на плечи компилятора. Еще одна особенность такого подхода - в получаемом массиве не должно быть "дыр", как в примере с арифметическими операциями. В принципе, в этом нет ничего страшного, но в этом случае ресурсы компилятора расходуются не самым эффективным образом.

Итоговый вывод такой - предложенный механизм хорошо подходит для генерации "сплошных" массивов небольшого размера, как то списки обработчиков состояний в конечных автоматах, обработчиков событий, обработчиков входных последовательностей, коды элементов которых лежат в "разумных" диапазонах, и т. п. Но он не подходит для генерации сильно "разреженных" массивов и массивов большого размера, как то - списков обработчиков событий в системе Windows, списков реакций на последовательности символов и т. п.

Надо отметить, что при желании некоторые описанные ограничения можно обойти. В частности, можно "заставить" компилятор заполнять структуры типа std::map, а также реализовать не такую глубокую вложенность шаблонов. Но это - тема отдельной статьи.