6.1. Шаблоны.
Подобно тому как класс представляет собой схематичес-кое описание объекта, так и шаблон представляет собой схе-матическое описание построения функций и классов. Шаблоны особенно полезны в библиотеках классов, которыми пользу-ются программисты. Иногда их называют параметризованными типами, так как они указывают лишь спецификации для фун-кций и классов, но не детали настоящей реализации.

6.1.1 Шаблонные функции.

Шаблоны функций описывают общие свойства функций и обычно объявляются в заголовочном файле, например:

template<classT> void f(T param)
{ // Тело функции }

Шаблон начинается строкой template<class T>, указыва-ющей компилятору, что Т — определяемое пользователем имя функции. Слова class не обязательно и означает класс С++. Необходим, хотя бы один параметр Т в скобках для передачи функции данных для обработки. Можно задать также значе-ние (T param), указатель (T* param) или ссылку (T& param). Шаблон может объявлять несколько параметров этих типов и возвращать значение типа Т, например:

template<class T> T f(int a, T b) //тип T будет определяться позже
{ // Тело функции }

Прототип функции будет выглядеть следующим образом:
double f(int a, double b);
Если бы функция была обычной, то необходима была бы ее реализация. Но поскольку она шаблонная, то компилятор сам реализует код функции, заменив Т в данном случае на double.
//Программа 1

#ifndef _MINMAX
#define _MINMAX
template<class T> T max(T a, T b)
{
if( a>b )
return a;
else
return b;
}
template<class T> T min(T a, T b)
{
if( a<b )
return a;
else
return b;
}
#endif
Эти шаблонные функции можно использовать для любых типов данных.
#include <iostream.h>
#include <conio.h>
#include «minmax.h»
int max (int a, int b);
double max (double a, double b);
char max (char a, char b);
void main()
{
clrscr();
int i1 = 100, i2 = 200;
double d1 = 3.14, d2 = 9.87;
char c1 = ‘A’, c2 = ‘z’;
cout << «100, 200 \n»;
cout << «max(i1, i2) == » << max(i1, i2) << endl;
cout << «3.14, 9.87 \n»;
cout << «max(d1, d2) == » << max(d1, d2) << endl;
cout << c1 << c2 << «\n»;
cout << «max(c1, c2) == » << max(c1, c2) << endl;
}
В программе объявлены три прототипа. Поскольку прог-рамма не содержит их реализаций, то компилятор ищет их шаблон, совпадающий по типу возвращаемого значения и ее па-раметров. Найдя такой шаблон, он реализуют три перегру-женные функции max.

6.1.2. Шаблонные классы.

Шаблон класса обеспечивает скелет обобщенного класса для его последующей реализации с помощью типов данных, оп-ределенных пользователем. Как и шаблоны функций шаблоны классов обычно объявляются в заголовочных файлах.
// Программа 2
#ifndef _DB
#define _DB
template<class T>
class TDatabase {
private:
T *rp; //указатель на записи
int num; //число записей
public:
TDatabase(int n)
{ pr = new T[ num = n];}
~TDatabase() {delete[] rp }
void DoNothing(void);
T &GetRecord(int recnum);
};
template<class T>
void TDatabase<T>::DoNothing(void) { }

template<class T>
T &TDatabase<T>::GetRecord(int recnum)
{
T *crp = rp;
if (0 <= recnum && recnum < num)
while (recnum — >0)
crp++;
return *crp;
}
#endif
#include <iostream.h>
#include <string.h>
#include «db.h»
class TRecord {
private:
char name[41];
public:
TRecord() { name[0] = 0; }
TRecord(const char *s) { Assign(s); }
void Assign(const char *s) { strcpy(name, s); }
char *GetName(void) { return name; }
};
void main()
{
int rn; //индекс числа записей
TDatabase<TRecord> db(3); //база данных из трех записей
TDatabase<TRecord*> dbp(3); //база данных из трех указателей
TDatabase<TRecord> *pdb; //указатель на БД
TDatabase<TRecord*> *ppdb; //указатель на БД указателей

cout << endl << «Database of 3 TRecord» << endl;
db.GetRecord(0).Assign(«George Washington»);
db.GetRecord(1).Assign(«John Adams»);
db.GetRecord(2).Assign(«Thomas Jefferson»);
for ( rn = 0; rn < 3; rn++ )
cout << db.GetRecord(rn).GetName() << endl;

cout << endl << «Database of 3 TRecord pointers» << endl;
dbp.GetRecord(0) = new TRecord(«George Washington»);
dbp.GetRecord(1) = new TRecord(«John Adams»);
dbp.GetRecord(2) = new TRecord(«Thomas Jefferson»);
for ( rn = 0; rn < 3; rn++ )
cout << dbp.GetRecord(rn)->GetName() << endl;

cout << endl << «Pointer to database of 3 TRecord » << endl;
pdb= new TDatabase<TRecord>(3);
pdb->GetRecord(0).Assign(«George Washington»);
pdb->GetRecord(1).Assign(«John Adams»);
pdb->GetRecord(2).Assign(«Thomas Jefferson»);
for ( rn = 0; rn < 3; rn++ )
cout << pdb->GetRecord(rn).GetName() << endl;

cout << endl << «Pointer to database of 3 TRecord pointers» << endl;
ppdb = new TDatabase<TRecord *>(3);
ppdb->GetRecord(0) = new TRecord(«George Washington»);
ppdb->GetRecord(1) = new TRecord(«John Adams»);
ppdb->GetRecord(2) = new TRecord(«Thomas Jefferson»);
for ( rn = 0; rn < 3; rn++ )
cout << ppdb->GetRecord(rn)->GetName() << endl;

}
Можно создать базу данных из других типов значений, для этого не обязательно использовать такие типы классов как TRecord.
Например: TDatabase<double> dbd(100);
Наиболее широкое применение шаблоны классов находят при создании контейнерных классов. Контейнерными классами называются классы, в которых хранятся организованные данные. Например, массивы, связные списки.
Основные типы контейнеров:
— ограниченный («защищенный») массив
— очередь
— стек
— связный список
— бинарное дерево
Каждый из контейнеров выполняет конкретные операции сохранения и извлечения над заданной информацией и получен-ными запросами.

6.2. Связные списки

Связные списки допускают гибкие методы доступа к элементам данных, поскольку каждый элемент данных содержит ссылку на следующий элемент данных в цепочке. Кроме того, операция извлечение элемента из связных списков не приво-дит к его удалению из списка и потере данных.
Связные списки могут иметь одиночные и двойные свя-зи. В списке с одиночными связями каждый элемент содержит ссылку на следующий элемент данных. В списке с двойными связями каждый элемент содержит ссылки на предыдущий и последующий элементы.
Списки с двойными ссылками представляют собой динами-ческие структуры данных, которые могут растягиваться или сжиматься в процессе выполнения программы. При удалении или добавлении элементов ссылки соответствующим образом перестраиваются.
// Программа 3
// Параметризованный класс связного списка с двойными
// ссылками
// Описание шаблона класса списка с двойными связями

template <class DataT> class listob {
public:
DataT info; //информация
listob<DataT> *next; //указатель на след. объект
listob<DataT> *prior; //указатель на пред. объект
listob() {
info = 0;
next = NULL;
prior = NULL;
};
listob (DataT c) {
info = c;
next = NULL;
prior = NULL;
};
listob<DataT> *getnext() { return next; }
listob<DataT> *getprior() { return prior; }
void getinfo (DataT &c) { c = info; }
void change (DataT c) { info = c; } //изменение элемента
friend ostream &operator<<(ostream &stream,listob<DataT> o);
friend ostream &operator<<(ostream &stream,listob<DataT> *o);
friend istream &operator>>(istream &stream,listob<DataT> &o);
};
// Перегрузка << для объекта listob
template <class DataT>
ostream &operator<<(ostream &stream,listob<DataT> o)
{
stream << o.info << endl;
return stream;
}
// Перегрузка << для указателя на объект типа listob
template <class DataT>
ostream &operator<<(ostream &stream,listob<DataT> *o)
{
stream << o->info << endl;
return stream;
}
// Перегрузка >> для ccылки на объект типа listob
template <class DataT>
istream &operator>>(istream &stream,listob<DataT> &o)
{
cout << «Введите информацию: » ;
stream >> o.info;
return stream;
}

//Класс, реализующий связнный список

template <class DataT> class dllist : public listob<DataT> {
listob<DataT> *start, *end; //*next, *prior
public:
dllist() { start = end = NULL; }
~dllist() ;

void store(DataT c); //ввод нового элемента
void remove(listob<DataT> *ob); //удаление элемента
void frwdlist(); //отображение списка с начала
void bkwdlist(); // отображение списка с конца
listob<DataT> *find(DataT c); //ук. на найденное совпадение
listob<DataT> *getstart() { return start; }
listob<DataT> *getend() { return end; }
};
// Деструктор dllist
template <class DataT> dllist<DataT> :: ~dllist()
{
listob<DataT> *p, *p1;
p = start;
while (p) {
p1 = p->next;
delete p;
p = p1;
}
}

Класс dllist поддерживает целый ряд операций над списком с двойными ссылками:
— ввод нового элемента списка — функция store();
— удаление элемента из списка — функция remove();
— просмотр списка в любом направлении — функции frwdlist() от начала к концу и bkwdlist() от конца к началу
— поиск в списке конкретного элемента — функция find();
— получение указателей на начало и коней списка

//Добавление нового элемента
template <class DataT> void dllist<DataT> :: store(DataT c)
{
listob<DataT> *p;
p = new listob<DataT>;
if (!p) {
cout << «Ошибка выделения памяти\n»;
exit(1);
}
p->info = c;
if (start == NULL) { //первый элемент списка
end = start = p;
}
else {
p->prior = end;
end->next = p;
end = p;
}
}

//Удаление элемента из списка с обновлением указателей

template <class DataT> void
dllist<DataT> :: remove(dllist<DataT> *ob)
{
if (ob->prior) { //не первый элемент
ob->prior->next = ob->next;
if (ob->next) //не последний элемент
ob->next->prior = ob->prior;
else //иначе удаляется последний элемент
end = ob->prior; //на конец списка
}
else { //удаляется первый элемент списка
if (ob->next) { // список не пуст
ob->next->prior = NULL;
start = ob->next;
}
else //список пуст
start = end = NULL;
}
}

// Просмотр списка от начала к концу

template <class DataT> void dllist<DataT> :: frwdlist()
{
listob<DataT> *temp;
temp = start;
while (temp) {
cout << temp->info << » «;
temp = temp->getnext();
}
cout << endl;
}

// Просмотр списка от конца к началу

template <class DataT> void dllist<DataT> :: bkwdlist()
{
listob<DataT> *temp;
temp = end;
while (temp) {
cout << temp->info << » «;
temp = temp->getprior();
}
cout << endl;
}

// Поиск объекта, содержащего информацию, совпадающую с
// указанной

template <class DataT> listob<DataT>
*dllist<DataT> :: find(DataT c)
{
listob<DataT> *temp;
temp = start;
while (temp) {
if (c == temp->info) return temp;
temp = temp->getnext();
}
return NULL;
}