Сравнение эффективности различных реализаций списков (2014-2015)

[Alexey Sidnev]

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

1. Реализовать шаблонный класс, представляющий список.
template <class Data>
class ListT
{
struct CNode
{
CNode *next;
Data *data;
} *head;
};

2. Реализовать класс, представляющий абстрактный список. Унаследовать от CNode экземпляр конкретных данных.
class ListA
{
struct CNode
{
CNode *next;
} *head;
};

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

Звено списка должно хранить дату: год, месяц, день, час, минута, секунда.

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