С.Б. Липпман, Ж. Лажойе - Язык программирования С++ Вводный курс (1114944), страница 40
Текст из файла (страница 40)
В данном разделе мы расскажем об использованииfor ( ilist_item *iter = mylist.init_iter();iter;iter = mylist.next_iter() )цикла такого вида:do_something( iter->value() );(В разделе 2.8 мы уже касались понятия итератора. В главах 6 и 12 будут рассмотреныитераторы для имеющихся в стандартной библиотеке контейнерных типов и обобщенныхалгоритмов.)Наш итератор представляет собой несколько больше, чем просто указатель.
Он долженуметь запоминать текущий элемент, возвращать следующий и определять, когда всеэлементы кончились. По умолчанию итератор инициализируется значением _at_front,однако пользователь может задать в качестве начального любой элемент списка.next_iter() возвращает следующий элемент или 0, если элементов больше нет.
Дляclass ilist {public:// ...init_iter( ilist_item *it = 0 );private://...ilist_item *_current;реализации пришлось ввести дополнительный член класса:};inline ilist_item*ilist::init_iter( i1ist_item *it ){return _current = it ? it : _at_front;init_iter() выглядит так:}next_iter() перемещает указатель _current на следующий элемент и возвращает егоадрес, если элементы не кончились.
В противном случае он возвращает 0 и устанавливает_current в 0. Его реализацию можно представить следующим образом:235С++ для начинающихinline ilist_item*ilist::next_iter(){ilist_item *next = _current? _current = _current->next(): _current;return next;}Если элемент, на который указывает _current, удален, могут возникнуть проблемы. Ихпреодолевают модификацией кода функций remove() и remove_front(): они должныпроверять значение _current. Если он указывает на удаляемый элемент, функцииизменят его так, чтобы он адресовал следующий элемент либо был равен 0, когдаудаляемый элемент – последний в списке или список стал пустым. Модифицированнаяinline voidilist::remove_front(){if ( _at_front ) {ilist_item *ptr = _at_front;_at_front = _at_front->next();// _current не должен указывать на удаленный элементif ( _current == ptr )_current = _at_front;bump_down_size();delete ptr;}remove_front() выглядит так:}while ( plist ) {if ( plist->value() == value ){prev->next( plist->next() );if ( _current == plist )Вот модифицированный фрагмент кода remove():_current = prev->next();Что произойдет, если элемент будет вставлен перед тем, на который указывает _current?Значение _current не изменяется.
Пользователь должен начать проход по списку спомощью вызова init_iter(), чтобы новый элемент попал в число перебираемых. Приинициализации списка другим и при присваивании значение _current не копируется, асбрасывается в 0.Тестовая программа для проверки работы копирующего конструктора и оператораприсваивания выглядит так::236С++ для начинающих#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 95.11.1.
Обобщенный списокНаш класс ilist имеет серьезный недостаток: он может хранить элементы только целоготипа. Если бы он мог содержать элементы любого типа – как встроенного, так иопределенного пользователем, – то его область применения была бы гораздо шире.Модифицировать ilist для поддержки произвольных типов данных позволяет механизмшаблонов (см. главу 16).237С++ для начинающихПри использовании шаблона вместо параметра подставляется реальный тип данных.Например: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 выглядит так:238С++ для начинающих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:239С++ для начинающих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(); }voidvoidvoidvoidinsert ( list_item<elemType> *ptr, elemType value );insert_end( elemType value );insert_front( elemType value );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, но, к сожалению, стандартный класстакже носит это название.
Теперь мы не можем использовать в программе одновременнооба класса. Конечно, проблему решит переименование нашего шаблона, однако вомногих случаях эта возможность отсутствует.Более общее решение состоит в использовании механизма пространства имен, которыйпозволяет разработчику библиотеки заключить все свои имена в некотороепоименованное пространство и таким образом избежать конфликта с именами изглобального пространства. Применяя нотацию квалифицированного доступа, мы можем240С++ для начинающихупотреблять эти имена в программах.
Стандартная библиотека С++ помещает свои именаnamespace Primer_Third_Edition{template <typename elemType>class list_item{ ... };template <typename elemType>class list{ ... };// ...в пространство std. Мы тоже поместим наш код в собственное пространство:}Для использования такого класса в пользовательской программе необходимо написать// наш заголовочный файл#include "list.h"// сделаем наши определения видимыми в программеusing namespace Primer_Third_Edition;// теперь можно использовать наш класс listlist< int > ilist;следующее:// ...(Пространства имен описываются в разделах 8.5 и 8.6.)Упражнение 5.16Мы не определили деструктор для ilist_item, хотя класс содержит указатель надинамическую область памяти.
Причина заключается в том, что класс не выделяетпамять для объекта, адресуемого указателем _next, и, следовательно, не несетответственности за ее освобождение. Начинающий программист мог бы допуститьilist_item::~ilist_item(){delete _next;ошибку, вызвав деструктор для ilist_item:}Посмотрите на функции remove_all() и remove_front() и объясните, почему наличиетакого деструктора является ошибочным.Упражнение 5.17void ilist::remove_end();Наш класс ilist не поддерживает следующие операции:241С++ для начинающихvoid ilist::remove( ilist_item* );Как вы думаете, почему мы их не включили? Реализуйте их.Упражнение 5.18Модифицируйте функцию find() так, чтобы вторым параметром она принимала адресэлемента, с которого нужно начинать поиск.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
