Набора обобщенных алгоритмов

L.print__back();

L.print();

L.insert(2, 200);

L.print_back();

L.print();

if (!L.remove(5)) cout << "not found":

}

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

Ниже перечислены еще раз правила описания шаблонов.

• Локальные классы не могут содержать шаблоны в качестве своих элементов.

• Шаблоны методов не могут быть виртуальными.

• Шаблоны классов могут содержать статические элементы, дружественные функции и классы.

• Шаблоны могут быть производными как от шаблонов, так и от обычных классов, а также являться базовыми и для шаблонов, и для обычных классов.

• Внутри шаблона нельзя определять friend-шаблоны.

В качестве примера шаблона рассмотрим полное описание параметризованного класса двусвязного списка List.

template <class Data> class List{

class Node{

public:

Data d;

Node *next, *prev;

Node (Data dat = 0){d = dat; next = 0; prev = 0;}

};

Node *pbeg, *pend;

public:

List(){ pbeg = 0; pend = 0;}

~List();

void add(Data d);

Node * find(Data i);

Node * insert(Data key, Data d);

bool remove(Data key);

void print();

void print_back();

};

//-----------------------------------

template <class Data>

List <Data>::~List(){

if (pbeg!=0){

Node *pv = pbeg;

while (pv){

pv = pv->next; delete pbeg;

pbeg = pv;}

//--------------------------------------

template <class Data>

void List <Data>::print(){

Node *pv = pbeg;

cout << endl<< "list: ";

while (pv){

cout << pv->d << ' ';

pv = pv->next;}

cout << endl;

}

//--------------------------------------------

template <class Data>

void List <Data>::print_back(){

Node *pv = pend;

cout << endl << " list back: ";

while (pv){

cout << pv->d << ' ';

pv = pv->prev;}

cout << endl;

}

//-----------------------------------

template <class Data>

void List <Data>::add(Data d){

Node *pv = new Node(d);

if (pbeg == 0)pbeg = pend = pv;

else{

pv->prev = pend;

pend->next = pv;

pend = pv;}

}

//----------------------------------------------------

template <class Data>

Node * List <Data>::find(Data d){

Node *pv = pbeg;

while (pv){

if(pv->d == d)break;

pv = pv->next;

}

return pv;

}

//------------------------------------------------------------

template <class Data>

Node * List <Data>::insert(Data key, Data d){

if(Node *pkey = find(key)){

Node *pv = new Node(d);

pv->next = pkey->next;

pv->prev = ркеу;

pkey->next =pv;

i f (ркеу!= pend)(pv->next)->prev = pv;

else pend = pv;

return pv;}

return 0:

}

// -------------------------------------------

template <class Data>

bool List <Data>::remove(Data key){

if(Node *pkey = find(key)){

i f (pkey == pbeg){

pbeg = pbeg->next; pbeg->prev = 0:}

else if (pkey == pend){

pend = pend->prev; pend->next = 0:}

else {

(pkey->prev)->next = pkey->next;

(pkey->next)->prev = pkey->prev;}

delete pkey;

return true;

}

return false:

}

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

Механизмы, используемые при построении STL (Standard Template Library – стандартная библиотека шаблонов)

Стандартная библиотека функций и классовязыкаС++включает некоторое подмножество – STL, обеспечивающее программиста типовыми структурами данных и наиболее эффективными алгоритмами, настроенными на обработку информации, представленной этими данными. В отличие от традиционных библиотек в STL типовые структуры данных и алгоритмы для их обработки представлены в виде шаблонов.

Стандартная библиотека шаблонов STL состоит из двух основных частей:

набора контейнерных классов и

Контейнеры — это объекты, содержащие другие однотипные объекты. Контейнерные классы являются шаблонными, поэтому хранимые в них объекты могут быть как встроенных, так и пользовательских типов.

Эти объекты должны допускать копирование и присваивание. Встроенные типы этим требованиям удовлетворяют; то же самое относится к классам, если конструктор копирования или операция присваивания не объявлены в них закрытыми или защищенными.

В контейнерных классах реализованы такие типовые структуры данных, как стек, список, очередь ит. д.

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

Однако они не являются методами контейнерных классов. Наоборот, алгоритмы представлены в STL в форме глобальных шаблонных функций.

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

Независимость от типов контейнеров достигается за счет косвенной связи функции с контейнером: в функцию передается не сам контейнер, а пара адресов first, last, задающая диапазон обрабатываемых элементов.

Реализация указанного механизма взаимодействия базируется на использовании так называемых итераторов.

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

Итераторы предназначены для предоставления единого метода последовательного доступа (перебора) элементов контейнера, не зависящего от вида контейнера и типа элементов в нем. Итератор может пробегать как все элементы, так и некоторое их подмножество

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

Итератор обеспечивает:

· единый механизм перебора элементов контейнера, не зависящий ни от его вида, ни от его реализации, ни от типа элементов;

· множественный доступ к контейнеру, позволяющий работать с контейнером сразу нескольким клиентам, при этом каждый из клиентов будет пользоваться своим итератором.

При последовательном переборе элементов контейнера итератор не обязательно перемещается только по смежным (соседним) элементам.

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

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

Итератор – это абстракция, обобщающая понятие указателя. Подобно тому, как значением указателя является адрес элемента массива, так значением итератора служит позиция элемента в контейнере.

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

Так перемещение итератора к следующему элементу контейнера (операция ++) по-разному реализуется в векторе и в списке.

Следовательно, для каждого класса контейнеров должен быть определен свой класс (или несколько классов) итераторов (локальный или дружественный), предоставляющий средства для создания итератора для обхода элементов контейнера.

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

Эти значения доступны с помощью методов любого контейнерного класса:

begin()- возвращает значение итератора (позицию в контейнере), установленного на начало последовательности;

end()- возвращает значение итератора, установленного за последним элементом последовательности.