Пример: шаблонная реализация связного списка
Более сложная задача - создание шаблона для связного списка. Основное усложнение здесь вносит наличие в списке внутренних классов для узлов и итераторов. Ниже представлено объявление шаблона класса List, в основе которого пример из предыдущих лекций. Код полностью переработан под применение шаблонов, и реализация всех методов перенесена в заголовочный файл. Необходимости в list.cpp больше нет. Т.е., для компоновки будет применяться обычная модель включения, поскольку набор возможных аргументов для инстанцирования не является конечным.
В приведенном ниже фрагменте листинга изменения, связанные с шаблонами, выделены синим. Ссылка на полную версию примера приведена в конце лекции.
list.hpp
#ifndef _LIST_HPP_
#define _LIST_HPP_
/*****************************************************************************/
#include <initializer_list>
#include <utility>
#include <stdexcept>
/*****************************************************************************/
template< typenameT >
classList
{
/*-----------------------------------------------------------------*/
private:
/*-----------------------------------------------------------------*/
// Внутренний узел списка
classNode
{
/*-------------------------------------------------------------*/
public:
/*-------------------------------------------------------------*/
Node ( constT & _value )
: m_value( _value )
, m_pNext( nullptr)
{}
constT & GetValue () const{ returnm_value; }
T & GetValue () { returnm_value; }
Node const* GetNext () const{ returnm_pNext; }
Node * GetNext () { returnm_pNext; }
voidSetNext ( Node * _pNext ) { m_pNext = _pNext; }
voidClearNext () { m_pNext = nullptr; }
/*-------------------------------------------------------------*/
private:
/*-------------------------------------------------------------*/
// Хранимое значение обобщенного типа
T m_value;
Node * m_pNext;
/*-------------------------------------------------------------*/
};
/*-----------------------------------------------------------------*/
public:
/*-----------------------------------------------------------------*/
// Итератор списка
classIterator
{
/*-------------------------------------------------------------*/
public:
/*-------------------------------------------------------------*/
explicitIterator ( Node * _pNode = nullptr);
constT & operator* () const;
T & operator* ();
bool operator== ( Iterator i ) const;
bool operator!= ( Iterator i ) const;
Iterator & operator++ ();
Iterator operator++ ( int);
/*-------------------------------------------------------------*/
private:
/*-------------------------------------------------------------*/
friend classList;
voidvalidate () const;
/*-------------------------------------------------------------*/
Node * m_pCurrent;
/*-------------------------------------------------------------*/
};
/*-----------------------------------------------------------------*/
// Конструктор по умолчанию
List ();
// Конструктор по списку инициализаторов
template< typenameU >
List ( std::initializer_list< U > _l );
// Конструктор копий
template< typenameU >
List ( constList< U > & _l );
// Конструктор перемещения
List ( List< T > && _l );
// Деструктор
~List ();
// Оператор копирующего присвоения
template< typenameU >
List< T > & operator= ( constList< U > & _l );
// Оператор перемещающего присвоения
List< T > & operator= ( List< T > && _l );
/*-----------------------------------------------------------------*/
// Методы доступа к итераторам
Iterator begin () const;
Iterator end () const;
/*-----------------------------------------------------------------*/
// Метод определения пустоты списка
boolIsEmpty () const;
// Метод вычисления количества элементов в списке
intSize () const;
// Метод очистки списка
voidClear ();
// Метод вставки нового значения в конец списка
voidPushBack ( constT & _value );
// Метод вставки нового значения в начало списка
voidPushFront ( constT & _value );
// Метод удаления значения с конца списка
voidPopBack ();
// Метод удаления значения с начала списка
voidPopFront ();
// Метод вставки значения после указанной итератором позиции
voidInsertAfter ( Iterator _prevPos, constT & _value );
// Метод вставки значения перед указанной итератором позицией
voidInsertBefore ( Iterator _nextPos, constT & _value );
// Метод удаления узла по указанной итератором позиции
voidDelete ( Iterator _pos );
// Метод удаления узла, стоящего до указанной итератором позиции
voidDeleteBefore ( Iterator _nextPos );
// Метод удаления узла, стоящего после указанной итератором позиции
voidDeleteAfter ( Iterator _prevPos );
/*-----------------------------------------------------------------*/
private:
/*-----------------------------------------------------------------*/
// Метод копирования данных
voidCopyDataFrom ( constList< T > & _l );
// Метод проверки принадлежности итератора списку
boolOwns ( Iterator _pos ) const;
/*-----------------------------------------------------------------*/
// Начальный и конечный узлы списка
Node * m_pFirst;
Node * m_pLast;
/*-----------------------------------------------------------------*/
};
/*****************************************************************************/
// ... реализация операций списка и его итератора ...
/*****************************************************************************/
#endif // _LIST_HPP
Среди элементов реализации интересен сложный синтаксис при работе с внутренними классами. Чтобы разобраться с данным синтаксисом, необходимо помнить, что класс-список является шаблоном, а итератор и узел внутри него - нет, что определяет необходимость в угловых скобках.
template< typenameT >
voidList< T >::Iterator::validate () const
{
if ( !m_pCurrent )
throwstd::logic_error( "Invalid list iterator state" );
}
Еще более интересный синтаксис используется при возврате объекта-итератора. Здесь необходимо использовать вложенный в шаблон класса тип еще до того, как становится понятным класс, в состав которого входит данный метод. Чтобы помочь прочитать данное определение правильно, каждый элемент шаблона вынесен в отдельную строку:
template< typenameT >
typenameList< T >::Iterator & // возврат ссылки на итератор списка
List< T >::Iterator::operator ++ ()
{
validate();
m_pCurrent = m_pCurrent->GetNext();
return* this;
}
Ниже приведена тестовая программа. Здесь используется определение явного инстанцирования в тестовом файле, исключительно для целей проверки реализации всех 100% методов абстракции на нескольких типах данных. В реальной библиотеке, такой заголовочный файл просто включается в программу без явного инстанцирования.
test_list.cpp
/*****************************************************************************/
#include "list.hpp"
#include <iostream>
#include <string>
/*****************************************************************************/
// Тестовое явное инстанцирование
template classList< int>;
template classList< double>;
template classList< std::string >;
/*****************************************************************************/
// Вспомогательный шаблон функции для вывода содержимого списка на экране
template< typenameT >
voidprintRange ( constList< T > & _l )
{
std::cout << "List(" << _l.Size() << "): ";
for( constT & val : _l )
std::cout << val << ' ';
std::cout << std::endl;
}
/*****************************************************************************/
intmain ()
{
// 3 списка с разными типами элементов
List< int> l1{ 1, 2, 3, 4, 5 };
List< double> l2{ 1.0, 2.0, 3.0, 4.0 };
List< std::string > l3{ "A", "B", "C" };
// Распечатываем содержимое на экране, используя один и тот же шаблон
printRange( l1 );
printRange( l2 );
printRange( l3 );
}
/*****************************************************************************/
Обобщенные алгоритмы
Рассмотрим простейший обобщенный алгоритм поиска элемента в массиве:
#include <cassert>
template< typenameT >
constT * MyFind ( constT * _pArray, int_nElements, constT & _value )
{
for( inti = 0; i < _nElements; i++ )
if( _pArray[ i ] == _value )
return_pArray + i;
return nullptr;
}
intmain ()
{
intdata[ 5 ] = { 1, 2, 3, 4, 5 };
const int* pResult = MyFind( data, 5, 3 );
assert( pResult && ( ( pResult - data ) == 2 ) );
}
В таком виде алгоритм может быть использован для организации линейного поиска в массиве любого типа. К сожалению, его нельзя применить к более сложным структурам данных, например к связными спискам. Тем не менее, суть алгоритма линейного поиска для связного списка выглядела бы практически идентично, с отличиями лишь в способе перебора элементов структуры при сравнении с искомым значением. В обычном массиве данные расположены в памяти последовательно, и достаточно сдвигать на каждом шаге значение индекса. В связном списке же необходимо перебирать узлы двигаясь вперед по связям. Соответственно, нужна подобная реализация алгоритма, отличающаяся от предыдущей лишь способом выбора следующего значения для сравнения.
Приведенная ранее реализация связных списков поддерживает перебор элементов при помощи вспомогательных объектов - итераторов. Итераторы списка полностью скрывают от внешнего мира особенности его внутренней организации и понятие узла вообще. Применяя итераторы, алгоритм поиска для связного списка можно было бы написать следующим образом:
template< typenameT >
typenameList< T >::Iterator // Результатом поиска является итератор в нужной позиции
MyFind ( constList< T > & _list, constT & _value )
{
// Начинаем поиск в начальной позиции
List< T >::Iterator it = _list.begin();
// Перебираем элементы от начала до конца
while( it != _list.end() )
{
// Разыменовываем итератор для извлечения текущего значения.
// Сравниваем его с искомым
if( * it == _value )
// В случае успеха, возвращаем итератор в текущей позиции досрочно
returnit;
// Переход к следующему элементу
++it;
}
return_list.end();
}
intmain ()
{
List < int> myList{ 1, 2, 3, 4, 5 };
constList< int >::Iterator it = MyFind( myList, 3 );
assert( ( it != myList.end() ) && ( * it == 3 ) );
}
Хотелось бы универсализировать алгоритм поиска таким образом, чтобы он работал с любой структурой данных, допускающей перебирание элементов. Это бы позволило инстанцировать один и тот же обобщенный алгоритм для различных хранилищ данных не зависимо от природы и сложности их внутренней организации. Возьмем алгоритм для массивов в качестве основы и сделаем ряд последовательных преобразований.
Во-первых, заменим количество элементов в массиве на адрес элемента, следующего за последним. Если элемент не будет найден вообще, реализация возвращает переданный адрес элемента, следующего за последним. Технически прежняя реализация останется практически неизменной, функционально идентичной, однако это принципиальный шаг к достижению преследуемой цели, как будет показано ниже.
template< typenameT >
constT * MyFind ( constT * _pArrayFirst,
constT * _pArrayLast,
constT & _value )
{
constT * pCurrent = _pArrayFirst;
while( pCurrent != _pArrayLast )
{
if( * pCurrent == _value )
returnpCurrent;
++ pCurrent;
}
return_pArrayLast;
}
Тестовый код также меняется незначительно:
intmain ()
{
intdata[ 5 ] = { 1, 2, 3, 4, 5 };
const int* pResult = MyFind( data, data + 5, 3 );
assert( pResult && ( ( pResult - data ) == 2 ) );
}
На первом шаге мы избавились от непосредственной работы с элементами массивов напрямую через индексы, полностью заменив их указателями.
На втором шаге преобразовываем код в форму, избегающую явного использования указателей. Для этой цели вводим дополнительный уровень косвенности - специальный аргумент шаблона функции, скрывающий указатели. При этом требуем от данного аргумента шаблона наличия операций сравнения со значением такого же типа (==, !=), присвоения (=), операции префиксного инкремента (++X), означающего переход к следующему элементу, а также операцию разыменования ( * x ), выбирающую адресуемое в данный момент значение. Во всех прежних контекстах использования указателя на аргумент-тип используем новый аргумент шаблона.
template< typenameIt, typenameT >
It MyFind ( It _first, It _last, constT & _value )
{
It current = _first;
while( current != _last )
{
if( * current == _value )
returncurrent;
++ current;
}
return_last;
}
Тестовый код остается без изменений. При инстанцировании с массивом, компилятор автоматически выводит, что в качестве фактического аргумента шаблона используется указатель на целочисленный тип. При инстанцировании со связным списком можно воспользоваться итераторами:
List< int> myList{ 1, 2, 3, 4, 5 };
constList< int>::Iterator it = MyFind( myList.begin(), myList.end(), 3 );
assert( ( it != myList.end() ) && ( *it == 3 ) );
Если для инстанцирования в качестве итератора будет предоставлено нечто, что соответствует требованиям идеи итератора, то такой тип и будет являться итератором (принцип “если ЭТО похоже на черепаху, движется как черепаха, значит ЭТО - черепаха”). Алгоритм будет успешно взаимодействовать с любой структурой данных, способной предоставить некоторый объект встроенного или пользовательского типа, с которым алгоритм может быть успешно инстанцирован.
Итератор представляет собой пример понятия ОБОБЩЕННОЙ КОНЦЕПЦИИ(generic concept) - именованного набора операций, которые должен поддерживать тип-аргумент для взаимодействия с тем или иным алгоритмом. В ряде языков обобщенные концепции описываются явно, перечисляя необходимые для аргумента-типа операции для обеспечения инстанцирования. В С++ обобщенные концепции никак не декларируются, а набор требований к типу формируется неявно, исходя из всех фактических способов использования. Комитет по стандартизации С++ в течение нескольких последних лет обсуждает необходимость во введении в язык конструкций явного декларирования обобщенных концепций, однако к общему мнению всех сторон пока прийти не удается.
Универсальность обобщенных концепций позволяет применить данный алгоритм даже для источников данных, не являющихся постоянными хранилищами. Например, можно воспользоваться стандартным итератором входного потока:
std::istream_iterator< int> result =
MyFind(
std::istream_iterator< int>( std::cin ),
std::istream_iterator< int>(),
);
assert( * result == 3 );
При этом реализация потокового итератора могла бы выглядеть следующим образом:
template< typenameT >
classistream_iterator
{
public:
istream_iterator ( std::istream & _stream )
: m_pStream( & _stream ), m_currentValue( T() )
{
update();
}
istream_iterator ()
: m_pStream( nullptr)
{
}
bool operator== ( constistream_iterator & _it ) const
{
returnm_pStream == _it.m_pStream;
}
bool operator!= ( constistream_iterator & _it ) const
{
return!( * this== _it );
}
istream_iterator& operator++ ()
{
update();
return* this;
}