Пример: реализация класса «список». Он состоит из узлов, связанных между собой с помощью указателей. Каждый узел хранит целое число, являющееся ключом списка.
Опишем вспомогательный класс для представления одного узла списка:
class Node{
public:
int d; // Данные
Node *next; // Указатель на последующий узел
Node *prev; // Указатель на предыдущий узел
Node (int dat = 0){ // Конструктор
d = dat; next = 0; prev = 0;
}
};
Этот класс будет описан внутри класса, представляющего список (класс List), поэтому для простоты доступа из внешнего класса поля сделаны доступными (public). Это позволяет обойтись без функций доступа и изменения полей.
class List{
class Node{…};
Node *pbeg, *pend; // Указатели на начало и конец списка
public:
List(){pbeg = 0; pend =0;} // Конструктор
~List (); // Деструктор
void add(int d); // Добавление узла в конец списка
Node * find (int i); // Поиск узла по ключу
Node * insert (int key, int d); // Вставка узла d после узла с ключом key:
bool remove (int key); // Удаление узла
void print(); // Печать списка в прямом направлении
void print_back(); // Печать списка в обратном направлении
};
Метод add выделяет память под новый объект типа Node и присоединяет его к списку, обновляя указатели на его начало и конец:
void List::add(int d) {
Node *pv = new Node(d); // Выделение памяти под новый узел
if (pbeg == 0) pbeg = pend = pv; // Первый узел списка
else {
// Связывание нового узла с предыдущим:
pv->prev = pend;
pend->next = pv;
pend = pv; } // Обновление указателя на конец списка
}
Можно получить отсортированный список, заменив данный метод на метод, аналогичный функции формирования отсортированного списка add_sort (лекция «Линейные списки»).
Метод find выполняет поиск узла с заданным ключом и возвращает указатель на него в случае успешного поиска и 0 в случае отсутствия такого узла в списке:
Node * List::find(int d){
Node *pv = pbeg;
while (pv){
if (pv->d == d) break;
pv = pv->next;
}
return pv;
}
Метод insert вставляет в список узел после узла с ключом key и возвращает указатель на вставленный узел. Если такого узла в списке нет, вставка не выполняется и возвращается значение 0:
Node * List::insert(int key, int d){
if(Node *pkey = find(key)){ // Поиск узла с ключом key
// Выделение памяти под новый узел и его инициализация:
Node *pv = new Node(d);
// Установление связи нового узла с последующим:
pv->next = pkey->next;
// Установление связи нового узла с предыдущим:
pv->prev = рkеу;
// Установление связи предыдущего узла с новым:
pkey->next = pv;
// Установление связи последующего узла с новым:
if (рkеу!= pend) (pv->next)->prev = pv;
// Обновление указателя на конец списка.
// если узел вставляется в конец:
else pend = pv;
return pv;
}
return 0;
}
Метод remove удаляет узел с заданным ключом из списка и возвращает значение true в случае успешного удаления и false, если узел с таким ключом в списке не найден:
bool List::remove(int key){
if(Node *pkey = find(key)){
if (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;
}
Методы печати списка в прямом и обратном направлении поэлементно просматривают список, переходя по соответствующим ссылкам:
void List::print (){
Node *pv = pbeg;
cout << endl << "1ist: ";
while (pv){
cout << pv->d << ' ';
pv = pv->next;}
cout << endl;
}
void List::print_back(){
Node *pv = pend;
cout << endl << "List back: ";
while (pv){
cout << pv->d << ' ';
pv = pv->prev;}
cout << endl;
}
Деструктор списка освобождает память из-под всех его элементов:
List::~List () {
if (pbeg!= 0){
Node *pv = pbeg;
while (pv){
pv = pv->next;
delete pbeg;
pbeg = pv;}
}
}
В функции main, используется класс List: формируется список из 5 чисел, выводится на экран, добавляется число в список, удаляется число из списка и снова выводится список на экран:
int main(){
List L;
for (int i = 2; i<6; i++) L.add(i);
L.print();
L.print_back();
L.insert(2, 200);
if (!L.remove(5)) cout << "not found";
L.print();
L.print_back(); }
Тема 2.11
Шаблоны классов
Шаблоны классов позволяют создавать параметризованные классы. Параметризованный класс - семейство родственных классов, которые можно применять к любому типу данных, передаваемому в качестве параметра.
Наиболее широкое применение шаблоны находят при создании контейнерных классов. Такие классы предназначены для хранения каким-либо образом организованных данных и работы с ними. Стандартная библиотека C++ содержит множество контейнерных классов для организации структур данных различного вида.
Преимущество использования шаблонов состоит в том, что если определен алгоритм работы с данными, он может применяться к любым типам данных без переписывания кода.
Пример:
Определить в виде класса параметризованного класса двухсвязный список (список может потребоваться хранить данные различных типов).
Класс List предназначен для хранения целых чисел. Чтобы хранить в нем данные любого типа, требуется описать этот класс как шаблон и передать тип в качестве параметра.
Синтаксис описания шаблона:
template <описание_параметров_шаблона> определение_класса;
Параметры шаблона перечисляются через запятую. В качестве параметров могут использоваться типы, шаблоны и переменные. Типы могут быть стандартными или определенными пользователем. Для их описания используется ключевое слово class. Внутри шаблона параметр типа может применяться в любом месте, где допустимо использовать спецификацию типа:
template <class Data> class List{
class Node{
public:
Data d;
Node *next;
Node *prev;
Node (Data dat = 0){d = dat; next = 0; prev = 0;}
};
…
}
Класс Data является формальным параметром. На его место при компиляции будет подставлен конкретный тип данных.
Для любых параметров шаблона могут задаваться значения по умолчанию:
template <class Т> class myarray {/*..*/};
template <class K, class V, template <class T> class С = myarray>
class Map{
C<K> key;
C<V> value;
…
};
Область действия параметра шаблона – от точки описания до конца шаблона, поэтому параметр можно использовать при описании следующих за ним:
template <class Т, Т* p, class U = Т> class X { /*... */ };
Методы шаблона класса автоматически становятся шаблонами функций. Если метод описывается вне шаблона, его заголовок должен иметь следующие элементы:
template <описание_параметров_шаблона>
возвр_тип имя_класса <параметры_шаблона>::
имя_функции (список_параметров функции)
Описание параметров шаблона в заголовке функции должно соответствовать шаблону класса. При этом имена параметров могут не совпадать.
template <class Data> void List<Data>::print()
{ / * тело функции */ }
<class Data> - описание параметра шаблона, void – тип возвращаемого функцией значения, List – имя класса, <Data> - параметр шаблона, print — имя функции без параметров.
В случае нескольких параметров порядок их следования в списках <описание_параметров_шаблона> и <параметры_шаблона> должен совпадать:
template<class T1, class T2> struct A{
void f1 ();
};
template <class T2, class T1> void A<T2, T1>::f1() {... }
Правила описания шаблонов:
· Локальные классы не могут содержать шаблоны в качестве элементов,
· Шаблоны методов не могут быть виртуальными,
· Шаблоны классов могут содержать статические элементы, дружественные функции и классы,
· Шаблоны могут быть производными от шаблонов и от обычных классов, а также являться базовыми для шаблонов и обычных классов,
· Внутри шаблона нельзя определять 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 = рkеу;
pkey->next = pv;
if (рkеу!= 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)){
if (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 для хранения данных пользовательского типа, в описание этого типа необходимо добавить перегрузку операции вывода в поток и сравнения на равенство, а если для его полей используется динамическое выделение памяти, то и операцию присваивания.
Переменные, передаваемые в шаблон, могут быть целого или перечисляемого типа, а также указателями или ссылками на объект или функцию. В теле шаблона они могут применяться в любом месте, где допустимо использовать константное выражение.
Пример: шаблон класса, содержащего блок памяти определенной длины и типа:
template <class Type, int kol>
class Block{
public:
Block(){p = new Type [kol];}
~Block(){delete [] p;}
operator Type *();
protected:
Type * p;
}:
template <class Type, int kol>
Block <Type, kol>:: operator Type *(){
return p;
}
После создания и отладки шаблоны классов удобно помещать в заголовочные файлы.
