Пример: шаблонная реализация связного списка

 

Более сложная задача - создание шаблона для связного списка. Основное усложнение здесь вносит наличие в списке внутренних классов для узлов и итераторов. Ниже представлено объявление шаблона класса List, в основе которого пример из предыдущих лекций. Код полностью переработан под применение шаблонов, и реализация всех методов перенесена в заголовочный файл. Необходимости в list.cpp больше нет. Т.е., для компоновки будет применяться обычная модель включения, поскольку набор возможных аргументов для инстанцирования не является конечным.

 

В приведенном ниже фрагменте листинга изменения, связанные с шаблонами, выделены синим. Ссылка на полную версию примера приведена в конце лекции.

 

list.hpp

 

#ifndef _LIST_HPP_

#define _LIST_HPP_

 

/*****************************************************************************/

 

#include <initializer_list>

#include <utility>

#include <stdexcept>

 

/*****************************************************************************/

 

template < typename T >

class List

{

 

/*-----------------------------------------------------------------*/

 

private:

 

/*-----------------------------------------------------------------*/

 

// Внутренний узел списка

class Node

{

 

/*-------------------------------------------------------------*/

 

public:

 

/*-------------------------------------------------------------*/

 

Node (const T & _value)

: m_value(_value)

, m_pNext(nullptr)

{}

 

const T & GetValue () const { return m_value; }

 

T & GetValue () { return m_value; }

 

Node const * GetNext () const { return m_pNext; }

 

Node * GetNext () { return m_pNext; }

 

void SetNext (Node * _pNext) { m_pNext = _pNext; }

 

void ClearNext () { m_pNext = nullptr; }

 

/*-------------------------------------------------------------*/

 

private:

 

/*-------------------------------------------------------------*/

 

// Хранимое значение обобщенного типа

T m_value;

 

Node * m_pNext;

 

/*-------------------------------------------------------------*/

 

};

 

/*-----------------------------------------------------------------*/

 

public:

 

/*-----------------------------------------------------------------*/

 

// Итератор списка

class Iterator

{

 

/*-------------------------------------------------------------*/

 

public:

 

/*-------------------------------------------------------------*/

 

explicit Iterator (Node * _pNode = nullptr);

 

const T & operator * () const;

T & operator * ();

 

bool operator == (Iterator i) const;

bool operator!= (Iterator i) const;

 

Iterator & operator ++ ();

Iterator operator ++ (int);

 

/*-------------------------------------------------------------*/

 

private:

 

/*-------------------------------------------------------------*/

 

friend class List;

 

void validate () const;

 

/*-------------------------------------------------------------*/

 

Node * m_pCurrent;

 

/*-------------------------------------------------------------*/

 

};

 

/*-----------------------------------------------------------------*/

 

// Конструктор по умолчанию

List ();

 

// Конструктор по списку инициализаторов

template < typename U >

List (std::initializer_list< U > _l);

 

// Конструктор копий

template < typename U >

List (const List< U > & _l);

 

// Конструктор перемещения

List (List< T > && _l);

 

// Деструктор

~List ();

 

// Оператор копирующего присвоения

template < typename U >

List< T > & operator = (const List< U > & _l);

 

// Оператор перемещающего присвоения

List< T > & operator = (List< T > && _l);

 

/*-----------------------------------------------------------------*/

 

// Методы доступа к итераторам

 

Iterator begin () const;

 

Iterator end () const;

 

/*-----------------------------------------------------------------*/

 

// Метод определения пустоты списка

bool IsEmpty () const;

 

// Метод вычисления количества элементов в списке

int Size () const;

 

// Метод очистки списка

void Clear ();

 

// Метод вставки нового значения в конец списка

void PushBack (const T & _value);

 

// Метод вставки нового значения в начало списка

void PushFront (const T & _value);

 

// Метод удаления значения с конца списка

void PopBack ();

 

// Метод удаления значения с начала списка

void PopFront ();

 

// Метод вставки значения после указанной итератором позиции

void InsertAfter (Iterator _prevPos, const T & _value);

 

// Метод вставки значения перед указанной итератором позицией

void InsertBefore (Iterator _nextPos, const T & _value);

 

// Метод удаления узла по указанной итератором позиции

void Delete (Iterator _pos);

 

// Метод удаления узла, стоящего до указанной итератором позиции

void DeleteBefore (Iterator _nextPos);

 

// Метод удаления узла, стоящего после указанной итератором позиции

void DeleteAfter (Iterator _prevPos);

 

/*-----------------------------------------------------------------*/

 

private:

 

/*-----------------------------------------------------------------*/

 

// Метод копирования данных

void CopyDataFrom (const List< T > & _l);

 

// Метод проверки принадлежности итератора списку

bool Owns (Iterator _pos) const;

 

/*-----------------------------------------------------------------*/

 

// Начальный и конечный узлы списка

Node * m_pFirst;

Node * m_pLast;

 

/*-----------------------------------------------------------------*/

 

};

 

/*****************************************************************************/

//... реализация операций списка и его итератора...

/*****************************************************************************/

 

#endif // _LIST_HPP

 

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

 

template < typename T >

void List< T >::Iterator::validate () const

{

if (!m_pCurrent)

throw std::logic_error("Invalid list iterator state");

}

 

Еще более интересный синтаксис используется при возврате объекта-итератора. Здесь необходимо использовать вложенный в шаблон класса тип еще до того, как становится понятным класс, в состав которого входит данный метод. Чтобы помочь прочитать данное определение правильно, каждый элемент шаблона вынесен в отдельную строку:

 

template < typename T >

typename List< 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 class List< int >;

template class List< double >;

template class List< std::string >;

 

/*****************************************************************************/

 

// Вспомогательный шаблон функции для вывода содержимого списка на экране

template < typename T >

void printRange (const List< T > & _l)

{

std::cout << "List(" << _l.Size() << "): ";

 

for (const T & val: _l)

std::cout << val << ' ';

 

std::cout << std::endl;

}

 

/*****************************************************************************/

 

int main ()

{

// 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 < 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 >

typename List< T >::Iterator // Результатом поиска является итератор в нужной позиции

MyFind (const List< T > & _list, const T & _value)

{

// Начинаем поиск в начальной позиции

List< T >::Iterator it = _list.begin();

 

// Перебираем элементы от начала до конца

while (it!= _list.end())

{

// Разыменовываем итератор для извлечения текущего значения.
// Сравниваем его с искомым

if (* it == _value)

// В случае успеха, возвращаем итератор в текущей позиции досрочно

return it;

 

// Переход к следующему элементу

++it;

}

 

return _list.end();

}

 

int main ()

{

List < int > myList{ 1, 2, 3, 4, 5 };

const List< int >::Iterator it = MyFind(myList, 3);

assert((it!= myList.end()) && (* it == 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;

++ 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;

}

 

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

 

List< int > myList{ 1, 2, 3, 4, 5 };

const List< 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 < typename T >

class istream_iterator

{

 

public:

 

istream_iterator (std::istream & _stream)

: m_pStream(& _stream), m_currentValue(T())

{

update();

}

 

istream_iterator ()

: m_pStream(nullptr)

{

}

 

bool operator == (const istream_iterator & _it) const

{

return m_pStream == _it.m_pStream;

}

 

bool operator!= (const istream_iterator & _it) const

{

return!(* this == _it);

}

 

istream_iterator& operator ++ ()

{

update();

return * this;

}