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

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

Наш класс 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_itemdoub1e *ptr = new list_itemdoub1e( 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_itemelemType *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_itemelemType *find( elemType value );

list_itemelemType *next_iter();

list_itemelemType* init_iter( list_itemelemType *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_itemelemType *_at_front;

1ist_itemelemType *_at_end;

list_itemelemType *_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 );

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

Список литературы

Из книги Введение в Perl автора Маслов Владимир Викторович

Список литературы При написании книги автор в основном пользовался описаниемПерл «Perl Programmers Reference Guide».Наиболее известная зарубежная литература:Programming Perl (the Camel Book)Learning Perl (Llama


Список (List)

Из книги Руководство по стандартной библиотеке шаблонов (STL) автора Ли Менг

Список (List) list - вид последовательности, которая поддерживает двунаправленные итераторы и позволяет операции вставки и стирания с постоянным временем в любом месте последовательности, с управлением памятью, обрабатываемым автоматически. В отличие от векторов и


7.6. Список литературы

Из книги Word 2007.Популярный самоучитель автора Краинский И

7.6. Список литературы При работе с большими документами удобно использовать новинку Word 2007 – возможность автоматического создания списка литературы. Оформление такого списка – обязательная часть работы над любым научным или учебным трудом, будь то школьный реферат или


19.5 Обобщенный формат URL

Из книги TCP/IP Архитектура, протоколы, реализация (включая IP версии 6 и IP Security) автора Фейт Сидни М

19.5 Обобщенный формат URL Обобщая вышесказанное, отметим, что:? URL начинается с указания используемого протокола доступа.? Для всех приложений, кроме сетевых новостей и электронной почты, далее следует разделитель ://.? Затем указывается имя хоста сервера.? Наконец


Список литературы

Из книги О чём не пишут в книгах по Delphi автора Григорьев А. Б.

Список литературы 1. Фень Юань. Программирование графики для Windows. — СПб.: Питер, 2002.2. Рихтер Дж. Windows. Для профессионалов. — СПб.: Питер. 2000.3. Джонс Э., Оланд Д. Программирование в сетях Microsoft Windows. — СПб.: Питер; М.: Издательско-торговый дом "Русская редакция", 2002.4. Вишневский


67. Пишите максимально обобщенный код

Из книги Стандарты программирования на С++. 101 правило и рекомендация автора Александреску Андрей

67. Пишите максимально обобщенный код РезюмеИспользуйте для реализации функциональности наиболее обобщенные и абстрактные средства.ОбсуждениеКогда вы пишете тот или иной код, используйте наиболее абстрактные средства, позволяющие решить поставленную задачу. Всегда


Список литературы

Из книги Программирование игр и головоломок автора Арсак Жак

Список литературы Произведения, цитируемые в тексте[ARS] Arsac J., Les bases de la programmation, Paris, Dunod, 1983.[BAI] Baillif J.-C. Les casse — t?te logiques de Baillif, Paris, Dunod, 1979.[BAL] Ball W.-W. Rouse, Mathematical recreations and essays, Macmillan and C°, London, 1963.[BER] Berloquin P., Le jardin du sphynx, Paris, Dunod, 1981.[ENG] Engel A., Math?matique ?l?mentaire d?un point de vue algorithmique, Paris, Cedic, 1979.[GRI] Gries


Контрольный список

Из книги Facebook: как найти 100 000 друзей для вашего бизнеса бесплатно автора Албитов Андрей

Контрольный список Итак, вы узнали, как собрать 100 000 друзей на вашу страницу Facebook. Пора за работу! Вот список задач, которые вам предстоит решить:– Создать страницу на Facebook (если нет).Это сделать легко, зайдите на Facebook.com. Если есть вопросы, прочитайте раздел «Помощь». От


СПИСОК ЛИТЕРАТУРЫ

Из книги Планирование закупок, производства и продаж в 1С:Предприятие 8 автора Гартвич А В

СПИСОК ЛИТЕРАТУРЫ 1.          Ситосенко Е. А. Управление заказами в системе программ 1С: Предприятие 8.0. — М.: ООО «1С-Паблишинг», 2005. — 219 е., ил.2.          Комплект документации по прикладному решению «1С: Предпри— ятие 8.0. Управление производственным предприятием». — М.:


23.4.4. Список

Из книги Linux: Полное руководство автора Колисниченко Денис Николаевич

23.4.4. Список Виджит CList представляет собой список, состоящий из нескольких колонок. Ячейки такого списка могут содержать текстовые значения. Мы можем обратиться отдельно к каждой ячейке списка. Создать список можно одной из функций:GtkWidget *gtk_clist_new(gint columns);GtkWidget


Список литературы

Из книги Фундаментальные алгоритмы и структуры данных в Delphi автора Бакнелл Джулиан М.

Список литературы Ниже приведен список литературы, которая использовалась при написании этой книги. Некоторые из указанных работ имеют исключительно большое значение - без них я не смог бы разобраться в некоторых алгоритмах и пояснить их читателям применительно к Delphi.


Список Web-сайтов

Из книги Firebird РУКОВОДСТВО РАЗРАБОТЧИКА БАЗ ДАННЫХ автора Борри Хелен

Список Web-сайтов Сайты проекта Firebird http://sourceforge.net/projects/firebird является сайтом разработчиков, где вы можете получить доступ к дереву CVS, к исходным и двоичным кодам комплекта поставки и просмотреть список выявленных ошибок.http://www.firebirdsql.org, алиас http://firebird.sourceforge.net. Здесь вы


3. Список

Из книги Инфобизнес за один день автора Ушанов Азамат

3. Список «10 способов, как сделать то-то», «17 секретов, как добиться успеха», «Пять способов, как избежать неудачи» – статья, видеоурок или скрин-каст. Это делается легко, потому что любой вопрос можно разбить на несколько частей, секретов, фишек и технологий, и описать их в


2.1.1. Список аргументов

Из книги Программирование для Linux. Профессиональный подход автора Митчелл Марк

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


БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Из книги Основы программирования на Java автора Сухов С. А.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК 1. Стефен Р. Дэвис. Программирование на Microsoft Visual Java++: пер. с англ. - М.: Издательский отдел «Русская редакция», 1997.2. Ленди М., Сиддикви С., Свишер Д., Borland JBuilder. Руководство разработчика.: пер. с англ. - М.: Издательский дом «Вильямс», 2004.3. Нотон П. Java.


6.2. Вектор или список?

Из книги C++ для начинающих автора Липпман Стенли

6.2. Вектор или список? Первая задача, которую должна решить наша программа, – это считывание из файла заранее неизвестного количества слов. Слова хранятся в объектах типа string. Возникает вопрос: в каком контейнере мы будем хранить слова – в последовательном или