Понятие обобщенной концепции. Статический полиморфизм по сравнению с динамическим полиморфизмом
Рассмотрим простейший обобщенный алгоритм поиска элемента в массиве:
#include <cassert>
template< typename T >
const T * MyFind ( const T * _pArray, int _nElements, const T & _value )
{
for ( int i = 0; i < _nElements; i++ )
if ( _pArray[ i ] == _value )
return _pArray + i;
return nullptr;
}
int main ()
{
int data[ 5 ] = { 1, 2, 3, 4, 5 };
const int * pResult = MyFind( data, 5, 3 );
assert( pResult && ( ( pResult - data ) == 2 ) );
}
Данный алгоритм может быть использован для организации линейного поиска в массиве любого типа. К сожалению, его нельзя применить к более сложным структурам данных, например к связными спискам. Тем не менее, суть алгоритма линейного поиска для связного списка бы выглядела практически идентично, с отличиями в способе перебора элементов для сравнения с искомым значением.
В обычном массиве данные расположены в памяти последовательно, и достаточно сдвигать на каждом шаге значение индекса. В связном списке необходимо перебирать узлы двигаясь по межузловым связям. Соответственно, нужна подобная реализация алгоритма, отличающаяся от предыдущей лишь способом выбора следующего значения для сравнения.
template< typename T >
class List
{
public:
struct Node
{
T m_value;
Node * m_pNextNode;
Node ( const T& _value )
: m_value( _value ),
m_pNextNode( nullptr )
{
}
};
private:
Node * m_pFirstNode, * m_pLastNode;
List ( const List< T >& );
List< T > & operator = ( const List< T > & );
public:
List ()
{
m_pFirstNode = m_pLastNode = nullptr;
}
~List ()
{
Node * pCurrent = m_pFirstNode;
while ( pCurrent )
{
Node * pTemp = pCurrent->m_pNextNode;
delete pCurrent;
pCurrent = pTemp;
}
}
void push_back ( const T & _value )
{
Node * pNewNode = new Node( _value );
if ( m_pLastNode )
{
m_pLastNode->m_pNextNode = pNewNode;
m_pLastNode = pNewNode;
}
else
m_pFirstNode = m_pLastNode = pNewNode;
}
const Node * first_node () const
{
return m_pFirstNode;
}
};
template< typename T >
const typename List< T >::Node *
MyFind ( const List< T > & _list, const T & _value )
{
const List< T >::Node* pCurrentNode = _list.first_node();
while ( pCurrentNode )
{
if ( pCurrentNode->m_value == _value )
return pCurrentNode;
pCurrentNode = pCurrentNode->m_pNextNode;
}
return nullptr;
}
int main ()
{
List < int > myList;
myList.push_back( 1 );
myList.push_back( 2);
myList.push_back( 3 );
myList.push_back( 4 );
myList.push_back( 5 );
const List< int >::Node * pNode = MyFind( myList, 3 );
assert( pNode && pNode->m_value == 3 );
}
Хотелось бы универсализировать алгоритм поиска таким образом, чтобы он работал с любой структурой данных, допускающей перебирание элементов. Это бы позволило инстанцировать один и тот же обобщенный алгоритм для различных хранилищ данных не зависимо от природы и сложности их внутренней организации.
Осуществим ряд предварительных шагов, преследующих данное намерение. Во-первых, незначительно видоизменим вариант реализации для массива, заменив количество элементов в массиве на адрес элемента, следующего за последним. Если элемент не будет найден вообще, реализация возвращает переданный адрес элемента, следующего за последним. Технически прежняя реализация остается практически неизменной, функционально идентичной, однако это принципиальный шаг к достижению преследуемой цели, как будет показано ниже.
template< typename T >
const T * MyFind ( const T * _pArrayFirst,
const T * _pArrayLast,
const T & _value )
{
const T * pCurrent = _pArrayFirst;
while ( pCurrent != _pArrayLast )
{
if ( * pCurrent == _value )
return pCurrent;
}
return _pArrayLast;
}
Тестовый код также меняется незначительно:
int main ()
{
int data[ 5 ] = { 1, 2, 3, 4, 5 };
const int * pResult = MyFind( data, data + 5, 3 );
assert( pResult && ( ( pResult - data ) == 2 ) );
}
На первом шаге мы избавились от непосредственной работы с элементами массивов напрямую через индексы, полностью заменив их указателями.
Пара передаваемых указателей задает интервал последовательности, которую необходимо обработать. Когда эти указатели корректны и адресуют существующий цельный набор значений в памяти, такой интервал называют ДЕЙСТВИТЕЛЬНЫМ, в противном случае интервал был бы НЕДЕЙСТВИТЕЛЬНЫМ.
На втором шаге преобразовываем код в форму, избегающую явного использования указателей. Для этой цели вводим дополнительный уровень косвенности - специальный аргумент шаблона функции, скрывающий указатели. При этом требуем от данного аргумента шаблона наличия операций сравнения со значением такого же типа (==, !=), присвоения (=), операции префиксного инкремента (++X), означающего переход к следующему элементу, а также операцию разыменования ( * x ), выбирающую адресуемое в данный момент значение. Во всех прежних контекстах использования указателя на аргумент-тип используем новый аргумент шаблона.
template< typename It, typename T >
It MyFind ( It _first, It _last, const T & _value )
{
It current = _first;
while ( current != _last )
{
if ( * current == _value )
return current;
++ current;
}
return _last;
}
Тестовый код остается без изменений. При инстанцировании с массивом, компилятор автоматически выводит, что в качестве фактического аргумента шаблона используется указатель на целочисленный тип.
Такой обобщенный аргумент, скрывающий указатель на обрабатываемые данные, называется ИТЕРАТОРОМ. Итератор представляет собой пример понятия ОБОБЩЕННОЙ КОНЦЕПЦИИ (generic concept) - именованного набора операций, которые должен поддерживать тип-аргумент для взаимодействия с тем или иным алгоритмом. В случае итератора, речь идет о наборе операций, необходимых для обеспечения последовательного доступа алгоритма к данным, хранящимся в структуре любой сложности. Если в качестве типа для инстанцирования в качестве итератора будет предоставлено нечто, что соответствует требованиям обобщенной концепции итератора, то такой тип и будет являться итератором (принцип “если это похоже на черепаху, движется как черепаха, значит это черепаха”).
Ключевая роль итераторов состоит в минимизации зависимости между конкретным способом хранения данных и алгоритмами обработки этих данных. Имея в распоряжении подходящий итератор, однажды написанный алгоритм можно применить к любой структуре данных.
В частности, чтобы этот код алгоритма заработал будучи примененным к связным спискам, необходимо передать объекты некоторого типа, которые способны перебирать внутренние узлы списка и извлекать из них значения. Ниже приведен пример реализации концепции итератора для узлов односвязного списка:
template< typename T >
class List
{
public:
// ...
struct Iterator
{
Node * m_pCurrentNode;
Iterator ( Node * _pCurrentNode )
: m_pCurrentNode( _pCurrentNode )
{
}
bool operator == ( const Iterator & _it ) const
{
return m_pCurrentNode == _it.m_pCurrentNode;
}
bool operator != ( const Iterator & _it ) const
{
return !( * this == _it );
}
Iterator & operator ++ ()
{
assert( m_pCurrentNode );
m_pCurrentNode = m_pCurrentNode->m_pNextNode;
return * this;
}
const T& operator * () const
{
assert( m_pCurrentNode );
return m_pCurrentNode->m_value;
}
};
Iterator begin ()
{
return Iterator( m_pFirstNode );
}
Iterator end ()
{
return Iterator( nullptr );
}
// ...
};
Соответственно, можем инстанцировать единый обобщенный алгоритм поиска для узлов нашего связного списка при помощи следующего кода:
const List< int >::Iterator it = MyFind( myList.begin(), myList.end(), 3 );
assert( * it == 3 );
Алгоритм будет успешно взаимодействовать с любой структурой данных, способной предоставить некоторый объект встроенного или пользовательского типа, реализующий описанную обобщенную концепцию итератора. Примечательно, что как алгоритм может быть применен к любому набору структур данных, так и итераторы, соответствующие различным структурам данных широко используются в различного рода алгоритмах.
Статический полиморфизм
Обобщенные концепции в целом напоминают абстрактные классы -
интерфейсы. От фактического типа, при помощи которого допускается
инстанцировать алгоритм, требуется наличие конкретного набора определенных
операций (в случае итератора для алгоритма поиска этот набор включает
присвоение, сравнение, постфиксный инкремент, разыменование с целью чтения).
Однако, в отличие от интерфейсов, обобщенные концепции в явном виде никаким
образом в коде не задаются (идеи явного выражения требований к обобщенной
концепции рассматривались при принятии стандарта C++11, однако в итоге не стали
частью языка из-за разногласий экспертов). Код шаблонов просто использует
необходимые для реализации операции, и предполагает, что конкретный тип их
предоставит. Если это не соответствует действительности в момент
инстанцирования, компилятор не позволит инстанцировать шаблон с таким типом
аргумента.
Обобщенные концепции иногда называют инструментом СТАТИЧЕСКОГО
ПОЛИМОРФИЗМА, В отличие от обычного, или динамического полиморфизма, реализуемого
на основе механизма виртуальных функций, такая форма полиморфизма имеет ряд
преимуществ и недостатков. К плюсам относится следующее:
·
нет необходимости в явном написании ограничивающих базовых классов
или интерфейсов, возможность дополнять интерфейс чем угодно;
·
отсутствуют накладные расходы на вызов во время выполнения, в
отличие от виртуальных функций, работающих через косвенные вызовы через
указатель vptr;
·
возможность частичной реализации общего интерфейса, если остальные
случаи не используются (и соответственно, не подлежат инстанцированию и
проверкам).
К минусам, по сравнению с динамическим полиморфизмом, можно
отнести такие свойства:
·
нельзя привести указатели и ссылки к какому-либо базовому классу,
а значит нельзя создать массив/контейнер указателей на объекты базового класса;
·
компиляция шаблонов приведет к большему объему генерируемого
машинного кода и увеличению времени компиляции.
Ниже приведен пример системы объектов, реализованных сначала с
использованием динамического полиморфизма на основе абстрактного класса и
виртуальных функций, а затем аналогичный пример с использованием статического
полиморфизма на основе шаблонов.
В примере речь идет о двух различных системах оценивания студентов
- классической 5-бальной советской системы и используемой в высших учебных
заведения в настоящее время Болонской 100-бальной системы. К центральной
абстракции - таблице оценок студентов (класс AcademicGroupMarks) - подключается
конкретный объект, отвечающий за выбранную систему оценивания. Задача системы
оценивания состоит в определении организационного вывода в зависимости от
набранного балла - неудача, сдача без стипендии, сдача со стипендией.
Начнем с динамического варианта. Потребуется создать интерфейс
MarkSystem и описать необходимые для взаимодействия виртуальные функции. Затем
этот интерфейс нужно реализовать в двух классах - SovietMarkSystem и
BolognaMarkSystem. Конкретный объект системы оценивания создается динамически и
прикрепляется к объекту AcademicGroupMarks, образуя отношение композиции с
ответственностью за уничтожение. Взаимодействие с дочерним объектом происходит
через механизм виртуальных функций.
Аналогичной функциональности можно добиться
применяя статический полиформизм. Среди основных отличий реализации от
динамической версии следующее:
●
отсутствует необходимость в интерфейсе
MarkSystem, поскольку обобщенные концепции в явном виде не описываются;
●
методы классов BolognaMarkSystem и
SovietMarkSystem более не виртуальные, а статические;
●
связь между таблицей оценок и системой оценивания
реализуется без создания объектов на основе аргумента шаблона;
●
таблица оценок более не нуждается в конструкторе.
Поскольку набор фактических аргументов шаблона конечен и заранее известен,
применяется модель явного инстанцирования шаблона.
Результат выполнения аналогичен динамическому варианту. Программируя в
таком стиле представляется возможным получить потенциально более
быстродействующее решение за счет отказа от виртуальных функций. За лучшие
показатели во время выполнения придется заплатить более долгим временем
компиляции и, скорее всего, бОльшим временем, необходимым программисту для
создания стабильной реализации.