Обобщенный список
Наш класс ilist имеет серьезный недостаток: он может хранить элементы только целого типа. Если бы он мог содержать элементы любого типа– как встроенного, так и определенного пользователем, – то его область применения была бы гораздо шире. Модифицировать ilist для поддержки произвольных типов данных позволяет механизм шаблонов (см. главу 16).
При использовании шаблона вместо параметра подставляется реальный тип данных. Например:
list< string > slist;
создает экземпляр списка, способного содержать объекты типа string, а
list< int > ilist;
создает список, в точности повторяющий наш ilist. С помощью шаблона класса можно обеспечить поддержку произвольных типов данных одним экземпляром кода. Рассмотрим последовательность действий, уделив особое внимание классу list_item.
Определение шаблона класса начинается ключевым словом template, затем следует список параметров в угловых скобках. Параметр представляет собой идентификатор, перед которым стоит ключевое слово class или typename. Например:
template <class elemType>
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, но, к сожалению, стандартный класс также носит это название. Теперь мы не можем использовать в программе одновременно оба класса. Конечно, проблему решит переименование нашего шаблона, однако во многих случаях эта возможность отсутствует.
Более общее решение состоит в использовании механизма пространства имен, который позволяет разработчику библиотеки заключить все свои имена в некоторое поименованное пространство и таким образом избежать конфликта с именами из глобального пространства. Применяя нотацию квалифицированного доступа, мы можем употреблять эти имена в программах. Стандартная библиотека С++ помещает свои имена в пространство std. Мы тоже поместим наш код в собственное пространство:
namespace Primer_Third_Edition
{
template <typename elemType>
class list_item{ ... };
template <typename elemType>
class list{ ... };
// ...
}
Для использования такого класса в пользовательской программе необходимо написать следующее:
// наш заголовочный файл
#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::~ilist_item()
{
delete _next;
}
Посмотрите на функции remove_all() и remove_front() и объясните, почему наличие такого деструктора является ошибочным.
Упражнение 5.17
Наш класс ilist не поддерживает следующие операции:
void ilist::remove_end();
void ilist::remove( ilist_item* );
Как вы думаете, почему мы их не включили? Реализуйте их.
Упражнение 5.18
Модифицируйте функцию find() так, чтобы вторым параметром она принимала адрес элемента, с которого нужно начинать поиск. Если этот параметр не задан, поиск начинается с первого элемента. (Поскольку мы добавляем второй параметр, имеющий значение по умолчанию, открытый интерфейс данной функции не меняется. Программы, использующие предыдущую версию find(), будут работать без модификации.)
class ilist {
public:
// ...
ilist_item* find( int value, ilist_item *start_at = 0 );
// ...
};
Упражнение 5.19
Используя новую версию find(), напишите функцию count(), которая подсчитывает количество вхождений элементов с заданным значением. Подготовьте тестовую программу.
Упражнение 5.20
Модифицируйте insert(int value) так, чтобы она возвращала указатель на вставленный объект ilist_item.
Упражнение 5.21
Используя модифицированную версию insert(), напишите функцию:
void ilist::
insert( ilist_item *begin,
int *array_of_value,
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 ilist::reverse_copy();
ilist ilist::concat_copy( const ilist &rhs );
