#include <iostream> #include "ilist.h"

int main()

{

ilist mylist;

for ( int ix = 0; ix < 10; ++ix ) { mylist.insert_front( ix ); mylist.insert_end( ix );

}

cout << "\n" << "Применение init_iter() и next_iter() " << "для обхода всех элементов списка:\n";

ilist_item *iter;

for ( iter = mylist.init_iter();

iter; iter = mylist.next_iter() ) cout << iter->value() << " ";

cout << "\n" << "Применение копирующего конструктора\n";

ilist mylist2( mylist ); mylist.remove_all();

for ( iter = mylist2.init_iter();

iter; iter = mylist2.next_iter() ) cout << iter->value() << " ";

cout << "\n" << "Применение копирующего оператора присваивания\n"; mylist = mylist2;

for ( iter = mylist.init_iter();

iter; iter = mylist.next_iter() ) cout << iter->value() << " ";

cout << "\n";

}

Результат работы программы:

Применение init_iter() и next_iter() для обхода всех элементов списка: 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9

Применение копирующего конструктора

9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9

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

9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9

5.11.1. Обобщенный список

Наш класс ilist имеет серьезный недостаток: он может хранить элементы только целого типа. Если бы он мог содержать элементы любого типа – как встроенного, так и определенного пользователем, – то его область применения была бы гораздо шире.

Модифицировать ilist для поддержки произвольных типов данных позволяет механизм шаблонов (см. главу 16).

При использовании шаблона вместо параметра подставляется реальный тип данных. Например:

list< string > slist;

создает экземпляр списка, способного содержать объекты типа string, а

list< int > ilist;

создает список, в точности повторяющий наш ilist. С помощью шаблона класса можно обеспечить поддержку произвольных типов данных одним экземпляром кода. Рассмотрим последовательность действий, уделив особое внимание классу list_item.

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

template <class elemType>

перед которым стоит ключевое слово class или typename. Например: class list_item;

Эта инструкция объявляет list_item шаблоном класса с единственным параметром-

template <typename elemType>

типом. Следующее объявление эквивалентно предыдущему: class list_item;

Ключевые слова class и typename имеют одинаковое значение, можно использовать любое из них. Более удобное для запоминания typename появилось в стандарте С++ сравнительно недавно и поддерживается еще не всеми компиляторами. Поскольку наши тексты были написаны до появления этого ключевого слова, в них употребляется class. Шаблон класса list_item выглядит так:

template <class elemType> class list_item { public:

list_item( elemType value, list_item *item = 0 ) : _value( value ) {

if ( !item ) _next = 0;

else {

_next = item->_next; item->_next = this;

}

}

elemType value() { return _value; } list_item* next() { return _next; }

void next( list_item *link ) { _next = link; }

void value( elemType new_value ) { _value = new_value; }

private:

elemType _value; list_item *_next;

};

Все упоминания типа int в определении класса ilist_item заменены на параметр elemType. Когда мы пишем:

list_item<doub1e> *ptr = new list_item<doub1e>( 3.14 );

компилятор подставляет double вместо elemType и создает экземпляр list_item, поддерживающий данный тип.

Аналогичным образом модифицируем класс ilist в шаблон класса list:

template <class elemType> class list {

public:

list()

: _at_front( 0 ), _at_end( 0 ), _current( 0 ), _size( 0 ) {}

1ist( const list& );

list& operator=( const list& ); ~list() { remove_all(); }

void insert ( list_item<elemType> *ptr, elemType value ); void insert_end( elemType value );

void insert_front( elemType value ); void insert_all( const list &rhs );

int remove( elemType value ); void remove_front();

void remove_all();

list_item<elemType> *find( elemType value ); list_item<elemType> *next_iter();

list_item<elemType>* init_iter( list_item<elemType> *it );

void disp1ay( ostream &os = cout );

void concat( const list& ); void reverse ();

int size() { return _size; }

private:

void bump_up_size() { ++_size; } void bump_down_size() { --_size; }

list_item<elemType> *_at_front; 1ist_item<elemType> *_at_end; list_item<elemType> *_current; int _size;

};

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

(Шаблоны являются важной составной частью концепции программирования на С++. В главе 6 мы рассмотрим набор классов контейнерных типов, предоставляемых стандартной библиотекой С++. Неудивительно, что она содержит шаблон класса, реализующего операции со списками, равно как и шаблон класса, поддерживающего векторы; мы рассматривали их в главах 2 и 3.)

Наличие класса списка в стандартной библиотеке представляет некоторую проблему. Мы выбрали для нашей реализации название list, но, к сожалению, стандартный класс также носит это название. Теперь мы не можем использовать в программе одновременно оба класса. Конечно, проблему решит переименование нашего шаблона, однако во многих случаях эта возможность отсутствует.

Более общее решение состоит в использовании механизма пространства имен, который

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

употреблять эти имена в программах. Стандартная библиотека С++ помещает свои имена

namespace Primer_Third_Edition

{

template <typename elemType> class list_item{ ... };

template <typename elemType> class list{ ... };

//...

впространство std. Мы тоже поместим наш код в собственное пространство:

}

Для использования такого класса в пользовательской программе необходимо написать

//наш заголовочный файл

#include "list.h"

//сделаем наши определения видимыми в программе using namespace Primer_Third_Edition;

//теперь можно использовать наш класс list list< int > ilist;

следующее:

// ...

(Пространства имен описываются в разделах 8.5 и 8.6.)

Упражнение 5.16

Мы не определили деструктор для ilist_item, хотя класс содержит указатель на динамическую область памяти. Причина заключается в том, что класс не выделяет память для объекта, адресуемого указателем _next, и, следовательно, не несет ответственности за ее освобождение. Начинающий программист мог бы допустить

ilist_item::~ilist_item()

{

delete _next;

ошибку, вызвав деструктор для ilist_item:

}

Посмотрите на функции remove_all() и remove_front() и объясните, почему наличие такого деструктора является ошибочным.

Упражнение 5.17

void ilist::remove_end();

Наш класс ilist не поддерживает следующие операции:

void ilist::remove( ilist_item* );

Как вы думаете, почему мы их не включили? Реализуйте их.

Упражнение 5.18

Модифицируйте функцию find() так, чтобы вторым параметром она принимала адрес элемента, с которого нужно начинать поиск. Если этот параметр не задан, поиск начинается с первого элемента. (Поскольку мы добавляем второй параметр, имеющий значение по умолчанию, открытый интерфейс данной функции не меняется. Программы,

class ilist {

public:

// ...

ilist_item* find( int value, ilist_item *start_at = 0 );

// ...

использующие предыдущую версию find(), будут работать без модификации.)

};

Упражнение 5.19

Используя новую версию find(), напишите функцию count(), которая подсчитывает количество вхождений элементов с заданным значением. Подготовьте тестовую программу.

Упражнение 5.20

Модифицируйте insert(int value) так, чтобы она возвращала указатель на вставленный объект ilist_item.

Упражнение 5.21

void ilist::

insert( ilist_item *begin, int *array_of_value,

Используя модифицированную версию insert(), напишите функцию: int elem_cnt );

где array_of_value указывает на массив значений, который нужно вставить в ilist, elem_cnt – на размер этого массива, а begin – на элемент, после которого производится вставка. Например, если есть ilist:

(3)( 0 1 21 )

и массив:

int ia[] = { 1, 2, 3, 5, 8, 13 };

вызов этой новой функции

ilist_item *it = mylist.find( 1 );

mylist.insert( it, ia, 6 );

изменит список таким образом:

(9) ( 0 1 1 2 3 5 8 13 21 )

Упражнение 5.22

Функции concat() и reverse() модифицируют оригинальный список. Это не всегда желательно. Напишите аналогичную пару функций, которые создают новый объект

ilist ilist::reverse_copy();

ilist:

ilist ilist::concat_copy( const ilist &rhs );