Пример 3. Шаблоны классов: связный список

Понятия контейнера и итератора являются ключевыми для стандартной библиотеки шаблонов (STL). В этой библиотеке содержится богатый набор шаблонов общеупотребительных функций (быстрая сортировка, двоичный поиск, генерация перестановок и т. п.) и классов (массив, связный список, дек, строка, потоки ввода-вывода и др.). Любой уважающий себя программист просто обязан уметь пользоваться этими готовыми средствами, вместо того, чтобы (по мере необходимости) тратить время на создание таких же собственных.

Контейнер - объект, который может содержать набор некоторых объектов. Понятие контейнера обобщает понятие массива в C++. В C++ массиве элементы хранятся в памяти линейно, один за другим. Для контейнера способ хранения не важен (т. е. может быть любым), важен сам факт хранения объектов.

Итератор - объект, обеспечивающий доступ к элементам контейнера. Понятие итератор обобщает понятие указатель. Обобщение заключается в том, что операции, применяемые к указателям для доступа к элементам массива, распространяются на более "широкий" класс объектов - итераторы. Например, применение операции ++ к итератору предполагает его смещение к следующему элементу контейнра, а применение разыменовывания - получение "ссылки" на элемент. В общем случае, "ссылка" предстваляет собой объект специального класса, позволяющего считать и/или изменить значение элемента контейнера. В большинстве же случаев достаточно обычной C++ ссылки.
Очевидно, что из-за различия во внутренней организации контейнеров, операции "доступа" не могут быть определены (в отличие от указателей) одним способом для всех контейнеров. В C++ это реализуется за счет определения для каждого класса-контейнера, собственного класса-итератора. Класс-итератор, "знает" о способе хранения элементов в "его" классе-контейнере, и требуемые операции перегружаются соответсвующим образом.

Отметим еще несколько особенностей программирования контейнеров/итераторов.
Обычно класс-итератор определяется как открытый вложенный класс для класса-контейнера, а не как отдельный класс.
Класс-контейнер содержит функции, возвращающие итератор, указывающий на первый и "конечный" элементы. Под "конечным" подразумевается не последний, а некоторый мнимый элемент, "расположенный" сразу после последнего. Итератор на "конечный" элемент нельзя разыменовывать, т. к. этот элемент не существует. Этот итератор имеет логический смысл и используется только в условиях. Например, осуществляется перебор элементов контейнера с использованием операции ++ для смещения итератора к следующему элементу. Если после приращения итератор стал равен итератору на "конечный" элемент, то перебор нужно заканчивать.
Пример (сравнение использования некоторого контейнера и обычного массива, с использованием итераторов для доступа к элементам):

class Container {
  ...

  public:
  Container(unsigned number_of_elements) { ... }
  ...

  class Iterator { ... };

  Iterator Begin() { return ...; }
  Iterator End() { return ...; }
  ...
  };

...
const unsigned Size = 10;
{
int с[Size];
// Итераторы для массива.
int *i, *begin, *end;
begin = с;
end = с + Size;
...
// Вывод на печать элементов.
for (i = begin; i != end; i++)
  cout << *i;
}
{
Container c(Size);
// Итераторы для контейнера.
Container::Iterator i, begin, end;
begin = c.Begin();
end = c.End();
// Вывод на печать элементов.
for (i = begin; i != end; i++)
  cout << *i;
}

В качестве примера класса-контейнера мы рассмотрим шаблон List класса-контейнера, реализующего понятие связного списка. Параметром-типом шаблона является тип элемента списка.
Каждый элемент списка располагается в узле (структура Node, определенная внутри List как закрытый вложенный класс). Дополнительно узле хранятся адреса предыдущего и последующего узла списка. Если таковых узлов нет, то соответствующие указатели имеют значение NULL.
Сам список хранит адрес первого и последнего узлов. Оба адреса равны NULL, если список пуст.

Итератор списка (класс Iterator) также определен как вложенный класс для List, но является открытым. Итератор хранит адрес узла списка, в котором хранится элемент, на который этот итератор указывает. Для класса Iterator определены следующие операции:

Учитывая способ связи узлов списка, очевидно сделать итератором на "конечный" элемент итератор, содержащий NULL-указатель. При этом получается, что такой итератор может использоваться как ограничитель при переборе элементов списка от первого к последнему, так и в обратном порядке.

Определение структуры Node и класса Iterator расположены в заголовочных файлах "ListNode.h" и "ListIterator.h" соответсвенно. Эти файлы включаютсяв заголовке "List.h" при определении шаблона List. Используется механизм условной компиляции для предотвращения использования этих заголовочных файлов самих по себе.
Такая методика (разделение определения класса на несколько заголовочных файлов) не используется. Здесь она применена только для улучшения читабельности программы; попутно демонстрируется и условная компиляция.

Использование шаблона List показано в программе "Ex_List.cpp". Создайте консольное Win32-приложение, используя этот модуль как главный.


List.h

//---------------------------------------------------------------------------
#ifndef ListH
#define ListH

// Определяем макрос, кот-й используется как условие того,
// что компилируется "List.h".
#define ListInterior
//---------------------------------------------------------------------------
#include <assert.h>
//---------------------------------------------------------------------------
/*
Шаблон класса: связный список из элементов типа T.
*/
template <class T>
class List {

  private:

  // Включаем определение структуры "узел списка".
  #include "ListNode.h"

  Node *FFirst,	// первый узел списка
       *FLast;    // последний узел

  // Делаем конструктор копии и операцию присваивания закрытыми.
  List(const List&) { }
  void operator =(const List&) { }

  public:

  // Включаем определение класса "итератор списка".
  #include "ListIterator.h"

  // Конструктор пустого списка
  List()
    : FFirst(NULL), FLast(NULL)
  {
  }

  // Деструктор (освобождает память).
  ~List()
  {
  Clear();
  }

  // Возвращает константный итератор на первый элемент (для константного списка).
  const Iterator First() const
  {
  return Iterator(FFirst);
  }

  // Возвращает итератор на первый элемент (для не константного списка).
  Iterator First()
  {
  return Iterator(FFirst);
  }

  // Возвращает константный итератор на последний элемент (для константного списка).
  const Iterator Last() const
  {
  return Iterator(FLast);
  }

  // Возвращает итератор на последний элемент (для не константного списка).
  Iterator Last()
  {
  return Iterator(FLast);
  }

  // Возвращает константный итератор на "конец" (для константного списка).
  const Iterator End() const
  {
  return Iterator();
  }

  // Возвращает итератор на "конец" (для не константного списка).
  Iterator End()
  {
  return Iterator();
  }

  // Проверка пустоты списка.
  bool Empty() const
  {
  return !FFirst;
  }

  // Вставляет элемент в список перед элементом, на который указывает итератор iter.
  // Если iter указывает на "конец", то эл-т добавляется в конец списка.
  void Insert(const Iterator& iter, const T& data);

  // Удаляет эл-т, на который указывает итератор iter.
  void Delete(const Iterator& iter);

  // Удаляет все эл-ты из списка.
  void Clear();

  // Добавление эл-та в начало списка.
  void PushFront(const T& data) { Insert(First(), data); }

  // Добавление эл-та в конец списка.
  void PushBack(const T& data) { Insert(End(), data); }

  // Удаление первого эл-та.
  void PopFront() { Delete(First()); }

  // Удаление последнего эл-та.
  void PopBack() { Delete(Last()); }

  };
//---------------------------------------------------------------------------
// Определение не встраиваемых функций-элементов
//---------------------------------------------------------------------------
template <class T>
void List<T>::Insert(const Iterator& iter, const T& data)
{
Iterator i;
Node *t,
     *n = new Node(data);		// создаем отдельный узел
// Если iter указывает на "конец", то добавляем эл-т в конец списка.
if (iter == End()) {
  // Если список не пуст, то
  if (FFirst)
    // связываем последний узел с новым;
    FLast->Next = n;
  else
    // иначе новый последний узел является и первым.
    FFirst = n;
  // Связываем новый узел с последним,
  n->Prev = FLast;
  // и делаем новый последним.
  FLast = n;
  }
else
  // Иначе, если iter указывает на первый, то добавляем эл-т в начало списка.
  if (iter == First()) {
    // Если список не пуст, то
    if (FFirst)
      // связываем первый узел с новым;
      FFirst->Prev = n;
    else
      // иначе новый первый узел является и последним.
      FLast = n;
    // Связываем новый узел с первым,
    n->Next = FFirst;
    // и делаем его первым.
    FFirst = n;
    }
  // Иначе вставляем эл-т в "середину" списка.
  else {
    // Ищем узел X, перед которым нужно вставить.
    for (i = First(); i != End(); i++)
      if (i == iter) break;
    // Если не найден, то iter не корректен: ошибка.
    assert(i != End());
    t = i.P->Prev;
    t->Next = n;        // связываем предшествующий X с новым
    n->Prev = t;		   // связываем новый с предшествующим X
    n->Next = i.P;	   // связываем новый с X
    i.P->Prev = n;      // связываем X с новым
    }
}
//---------------------------------------------------------------------------
template <class T>
void List<T>::Delete(const Iterator& iter)
{
Node *t;
Iterator i;
// Ищем узел X, содержащий удаляемый эл-т.
for (i = First(); i != End(); i++)
  if (i == iter) break;
// Если не найден, то iter не корректен: ошибка.
assert(i != End());
t = i.P;
// Если X первый.
if (i == First()) {
  // Смещаем первый узел на следующий за ним.
  FFirst = t->Next;
  // Если он отсутсвует, то список состоит из одного эл-та и
  // нужно сбросить указатель на последний.
  if (!FFirst) FLast = NULL;
  }
else
  // Иначе, если X последний.
  if (i == Last()) {
    // Смещаем последний узел на ему предшествующий.
    FLast = t->Prev;
    // Если он отсутсвует, то список состоит из одного эл-та и
    // нужно сбросить указатель на первый.
    if (!FLast) FFirst = NULL;
    }
  else {
    // Иначе X средний.
    t->Prev->Next = t->Next;	// связываем предыдущий X со следующим за X,
    t->Next->Prev = t->Prev;  // отделяя X от списка
    }
// Удаляем X (уничтожаем и освобождаем память).
delete t;
}
//---------------------------------------------------------------------------
template <class T>
void List<T>::Clear()
{
// Если список не пуст.
if (!Empty()) {
  Node *n;
  Iterator i;
  // Удаляем все узлы.
  for (i = First(); i != End(); ) {
    n = i.P;	// сохраняем адрес узла
    i++;			// переходим к следующему
    delete n;	// и удаляем текущий
    }
  // Сбрасываем указатели на первый и последний.
  FFirst = FLast = NULL;
  }
}
//---------------------------------------------------------------------------
// Убираем макрос ListInterior, т. к. "List.h" закончился.
#undef ListInterior

#endif


ListNode.h

// Если "ListNode.h" включен вне "List.h",
#ifndef ListInterior
// то выдать ошибку компиляции.
#error "ListNode.h" is internal for "List.h". Do not include directly.
#endif

//template <class T>
//class List {
//...

  // Узел списка.
  struct Node {
    T Data;					// данные (значение эл-та списка)
    Node *Prev, *Next;  // указатель на предыдущий и следующий узлы

    // Создание отдельного узла.
    Node(const T& data)
      : Data(data),		// копируем данные;
        Prev(NULL),	   // предыдущего и
        Next(NULL)		// последующего узлов нет
    {
    }

    };

//...
//};


ListIterator.h

// Если "ListIterator.h" включен вне "List.h",
#ifndef ListInterior
// то выдать ошибку компиляции.
#error "ListIterator.h" is internal for "List.h". Do not include directly.
#endif

//template <class T>
//class List {
//...

  // Итератор списка.
  class Iterator {
    // Класс список объявляется дружественным для доступа к указателю на узел.
    friend List<T>;

    Node* P;	// ук-ль на узел списка, содержащий значение эл-та, на кот-й указывает итератор

    public:
    // Создает итератор, указывающий на эл-т списка, хранящийся в узле по адресу p.
    // По умолчанию ни на что не указывает. Т. к. Node - закрытый тип класса List,
    // то итератор на эл-т может быть создан только функциями-элементами List.
    Iterator(Node* p = NULL)
      : P(p)
    {
    }

    // Операция разыменовывания для константного итератора.
    // Возвращает константую ссылку на значение эл-та.
    const T& operator *() const
    {
    return P->Data;
    }

    // Операция разыменовывания для не константного итератора.
    // Возвращает не константного ссылку на значение эл-та, по которой
    // оно может быть изменено.
    T& operator *()
    {
    return P->Data;
    }

    // Префиксная операция инкремента. Перемещает итератор к следующему эл-ту списка.
    Iterator operator ++()
    {
    P = P->Next;		// переходим к следующему эл-ту
    return *this;		// возвращаем "увеличенный" итератор
    }

    // Постфиксная операция инкремента. Перемещает итератор к следующему эл-ту списка.
    // Аргумент типа int указывает компилятору, что данная функция-операция operator ++
    // является постфиксной.
    Iterator operator ++(int)
    {
    Iterator t(*this);	// сохраняем "не увеличенное" значение итератора
    P = P->Next;			// переходим к следующему эл-ту
    return t;				// возвращаем "не увеличенное" значение итератора
    }

    // Префиксная операция декремента. Перемещает итератор к предыдущему эл-ту списка.
    Iterator operator --()
    {
    P = P->Prev;     // переходим к предыдущему эл-ту
    return *this;		// возвращаем "уменьшенный" итератор
    }

    // Постфиксная операция декремента. Перемещает итератор к предыдущему эл-ту списка.
    // Аргумент типа int указывает компилятору, что данная функция-операция operator --
    // является постфиксной.
    Iterator operator --(int)
    {
    Iterator t(*this);	// сохраняем "не уменьшенное" значение итератора
    P = P->Prev;        // переходим к предыдущему эл-ту
    return t;				// возвращаем "не уменьшенное" значение итератора
    }

    // Операция равенства.
    friend bool operator ==(const Iterator& x, const Iterator& y)
    {
    return x.P == y.P;
    }

    // Операция неравенства.
    friend bool operator !=(const Iterator& x, const Iterator& y)
    {
    return x.P != y.P;
    }

    };

//...
//};


Ex_List.cpp

#include <iostream.h>
#include <stdlib.h>
#include "List.h"

// Определяем синоним L для списка целых чисел.
typedef List<int> L;

// Т. к. в "List.h" операции ввода-вывода списков не определены, а использовать
// их удобно, то определим операцию вывода в поток значений типа L здесь.
ostream& operator <<(ostream& s, const L& l)
{
L::Iterator i;
s << '[';
// Выводим все элементы кроме последнего, разделяя их запятой.
for (i = l.First(); i != l.Last(); i++)
  s << *i << ", ";
// Выводим последний элемент (если список не пуст).
if (i != l.End()) s << *i;
s << "]\n";
return s;
}

void main()
{
// Пустые списки m и l.
L l, m;
L::Iterator i, j;
int c;

// Добавляем в конец l десять случайных чисел от 1 до 10.
randomize();
for (c = 10; c--; )
  l.PushBack(random(10) + 1);
cout << "Push back 10 random el-ts to l.\nl = " << l << endl;

// Удваиваем элемнты l.
for (i = l.First();	// начинаем с первого
     i != l.End();   // продолжаем, пока не "выскочим" за пределы списка
     i++)				//                                     затем переходим к следующему за i-м.
  // Сначала вставляем элемент перед i-м эл-том его компию,
  l.Insert(i, *i);
cout << "Double each el-t in l.\nl = " << l << endl;

// Вставляем эл-ты l в m в обратном порядке.
for (i = l.Last();	// начинаем с последнего
     i != l.End();   // продолжаем, пока не "выскочим" за пределы списка
     i--)            //                                    и переходим к предшествующему.
  m.PushBack(*i);    // Добавляем в конец m i-й эл-т из l,
cout << "Push back l's el-ts to m in reverse order.\nm = " << m << endl;

// Удаляем каждый второй эл-т в m (начиная с первого).
for (i = m.First();	// начинаем с первого
     i != m.End();   // продолжаем, пока не "выскочим" за пределы списка
     i++)            // (*) затем пропускаем оставляемый элемент
  m.Delete(i++);     // Удаляем i-й эл-т, предварительно смещая i на один эл-т вперед, (*).
cout << "Delete each second el-t from m.\nm = " << m << endl;

// Вставляем в начало m три нуля.
for (c = 3; c--; )
  m.PushFront(0);
cout << "Push front 3 zeros to m.\nm = " << m << endl;

// Добавляем к эл-м l значения соответствующих эл-в m, пока один из списков не кончится.
for (i = l.First(), j = m.First(); i != l.End() && j != m.End(); i++, j++)
  *i += *j;
cout << "Add m's el-ts to l's el-ts until one of the lists isn't done.\nl = " << l << endl;

// Удаляем из m три первых нуля.
for (c = 3; c--; )
  m.PopFront();
cout << "Remove lead zeros form m.\nm = " << m << endl;

// Очищаем список m.
m.Clear();
cout << "Remove all el-ts from m.\nm = " << m;

cin.ignore(100, 'q');
}
Примеры Предыдущий Следующий