Язык программирования C++. Вводный курс. С для начинающих
 Скачать 5.41 Mb.
|
запретили его использование. Лучше уж полностью лишить пользователя какой-либо операции, чем допустить возможные ошибки. (В разделе 14.5 объясняется, почему действия копирующего конструктора по умолчанию в подобных случаях неверны.) Вот реализация конструктора, использующая функцию insert_end(): } Оператор присваивания должен сначала вызвать remove_all(), а затем с помощью insert_end() вставить все элементы второго списка. Поскольку эта операция повторяется в обеих функциях, вынесем ее в отдельную функцию insert_all(): } после чего копирующий конструктор и оператор присваивания можно реализовать так: } Теперь осталось обеспечить пользователя возможностью путешествовать по списку, например с помощью доступа к члену _at_front: ilist_item *ilist::front() { return _at_front(); } После этого можно применить ilist_item::next(), как мы делали в функциях-членах: ilist::ilist( const ilist &rhs ) { ilist_item *pt = rhs._at_front; while ( pt ) { insert_end( pt->value() ); pt = pt->next(); } void ilist::insert_all ( const ilist &rhs ) { ilist_item *pt = rhs._at_front; while ( pt ) { insert_end( pt->value() ); pt = pt->next(); } inline ilist::ilist( const ilist &rhs ) : _at_front( 0 ), _at_end( 0 ) { insert_all ( rhs ); } inline ilist& ilist::operator=( const ilist &rhs ) { remove_all(); insert_all( rhs ); return *this; С++ для начинающих 235 } Хотя это решает проблему, лучше поступить иначе: реализовать общую концепцию прохода по элементам контейнера. В данном разделе мы расскажем об использовании цикла такого вида: do_something( iter->value() ); (В разделе 2.8 мы уже касались понятия итератора. В главах 6 и 12 будут рассмотрены итераторы для имеющихся в стандартной библиотеке контейнерных типов и обобщенных алгоритмов.) Наш итератор представляет собой несколько больше, чем просто указатель. Он должен уметь запоминать текущий элемент, возвращать следующий и определять, когда все элементы кончились. По умолчанию итератор инициализируется значением _at_front, однако пользователь может задать в качестве начального любой элемент списка. next_iter() возвращает следующий элемент или 0, если элементов больше нет. Для реализации пришлось ввести дополнительный член класса: }; init_iter() выглядит так: } next_iter() перемещает указатель _current на следующий элемент и возвращает его адрес, если элементы не кончились. В противном случае он возвращает 0 и устанавливает _current в 0. Его реализацию можно представить следующим образом: ilist_item *pt = mylist.front(); while ( pt ) { do_something( pt->value() ); pt = pt->next(); for ( ilist_item *iter = mylist.init_iter(); iter; iter = mylist.next_iter() ) 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; С++ для начинающих 236 } Если элемент, на который указывает _current, удален, могут возникнуть проблемы. Их преодолевают модификацией кода функций remove() и remove_front(): они должны проверять значение _current. Если он указывает на удаляемый элемент, функции изменят его так, чтобы он адресовал следующий элемент либо был равен 0, когда удаляемый элемент – последний в списке или список стал пустым. Модифицированная remove_front() выглядит так: } Вот модифицированный фрагмент кода remove(): _current = prev->next(); Что произойдет, если элемент будет вставлен перед тем, на который указывает _current? Значение _current не изменяется. Пользователь должен начать проход по списку с помощью вызова init_iter(), чтобы новый элемент попал в число перебираемых. При инициализации списка другим и при присваивании значение _current не копируется, а сбрасывается в 0. Тестовая программа для проверки работы копирующего конструктора и оператора присваивания выглядит так:: inline ilist_item* ilist:: next_iter() { ilist_item *next = _current ? _current = _current->next() : _current; return next; inline void ilist::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; } while ( plist ) { if ( plist->value() == value ) { prev->next( plist->next() ); if ( _current == plist ) С++ для начинающих 237 } Результат работы программы: Применение 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). #include #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"; С++ для начинающих 238 При использовании шаблона вместо параметра подставляется реальный тип данных. Например: list< string > slist; создает экземпляр списка, способного содержать объекты типа string, а list< int > ilist; создает список, в точности повторяющий наш ilist. С помощью шаблона класса можно обеспечить поддержку произвольных типов данных одним экземпляром кода. Рассмотрим последовательность действий, уделив особое внимание классу list_item. Определение шаблона класса начинается ключевым словом template, затем следует список параметров в угловых скобках. Параметр представляет собой идентификатор, перед которым стоит ключевое слово class или typename. Например: class list_item; Эта инструкция объявляет list_item шаблоном класса с единственным параметром- типом. Следующее объявление эквивалентно предыдущему: class list_item; Ключевые слова class и typename имеют одинаковое значение, можно использовать любое из них. Более удобное для запоминания typename появилось в стандарте С++ сравнительно недавно и поддерживается еще не всеми компиляторами. Поскольку наши тексты были написаны до появления этого ключевого слова, в них употребляется class. Шаблон класса list_item выглядит так: template С++ для начинающих 239 }; Все упоминания типа int в определении класса ilist_item заменены на параметр elemType . Когда мы пишем: list_item Аналогичным образом модифицируем класс ilist в шаблон класса list: template : _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; С++ для начинающих 240 }; Объекты шаблона класса list используются точно так же, как и объекты класса ilist. Основное преимущество шаблона в том, что он обеспечивает поддержку произвольных типов данных с помощью единственного определения. (Шаблоны являются важной составной частью концепции программирования на С++. В главе 6 мы рассмотрим набор классов контейнерных типов, предоставляемых стандартной библиотекой С++. Неудивительно, что она содержит шаблон класса, реализующего операции со списками, равно как и шаблон класса, поддерживающего векторы; мы рассматривали их в главах 2 и 3.) Наличие класса списка в стандартной библиотеке представляет некоторую проблему. Мы выбрали для нашей реализации название list, но, к сожалению, стандартный класс также носит это название. Теперь мы не можем использовать в программе одновременно оба класса. Конечно, проблему решит переименование нашего шаблона, однако во многих случаях эта возможность отсутствует. Более общее решение состоит в использовании механизма пространства имен, который позволяет разработчику библиотеки заключить все свои имена в некоторое поименованное пространство и таким образом избежать конфликта с именами из глобального пространства. Применяя нотацию квалифицированного доступа, мы можем template : _at_front( 0 ), _at_end( 0 ), _current( 0 ), _size( 0 ) {} 1ist( const list& ); list& operator=( const list& ); list() { remove_all(); } void insert ( list_item 1ist_item С++ для начинающих 241 употреблять эти имена в программах. Стандартная библиотека С++ помещает свои имена в пространство std. Мы тоже поместим наш код в собственное пространство: } Для использования такого класса в пользовательской программе необходимо написать следующее: // ... (Пространства имен описываются в разделах 8.5 и 8.6.) Упражнение 5.16 Мы не определили деструктор для ilist_item, хотя класс содержит указатель на динамическую область памяти. Причина заключается в том, что класс не выделяет память для объекта, адресуемого указателем _next, и, следовательно, не несет ответственности за ее освобождение. Начинающий программист мог бы допустить ошибку, вызвав деструктор для ilist_item: } Посмотрите на функции remove_all() и remove_front() и объясните, почему наличие такого деструктора является ошибочным. Упражнение 5.17 Наш класс ilist не поддерживает следующие операции: namespace Primer_Third_Edition { template // ... // наш заголовочный файл #include "list.h" // сделаем наши определения видимыми в программе using namespace Primer_Third_Edition; // теперь можно использовать наш класс list list< int > ilist; ilist_item::ilist_item() { delete _next; void ilist::remove_end(); С++ для начинающих 242 void ilist::remove( ilist_item* ); Как вы думаете, почему мы их не включили? Реализуйте их. Упражнение 5.18 Модифицируйте функцию find() так, чтобы вторым параметром она принимала адрес элемента, с которого нужно начинать поиск. Если этот параметр не задан, поиск начинается с первого элемента. (Поскольку мы добавляем второй параметр, имеющий значение по умолчанию, открытый интерфейс данной функции не меняется. Программы, использующие предыдущую версию find(), будут работать без модификации.) }; Упражнение 5.19 Используя новую версию find(), напишите функцию count(), которая подсчитывает количество вхождений элементов с заданным значением. Подготовьте тестовую программу. Упражнение 5.20 Модифицируйте insert(int value) так, чтобы она возвращала указатель на вставленный объект ilist_item. Упражнение 5.21 Используя модифицированную версию insert(), напишите функцию: int elem_cnt ); где array_of_value указывает на массив значений, который нужно вставить в ilist, elem_cnt – на размер этого массива, а begin – на элемент, после которого производится вставка. Например, если есть ilist: (3)( 0 1 21 ) и массив: int ia[] = { 1, 2, 3, 5, 8, 13 }; вызов этой новой функции class ilist { public: // ... ilist_item* find( int value, ilist_item *start_at = 0 ); // ... void ilist:: insert( ilist_item *begin, int *array_of_value, С++ для начинающих 243 mylist.insert( it, ia, 6 ); изменит список таким образом: (9) ( 0 1 1 2 3 5 8 13 21 ) Упражнение 5.22 Функции concat() и reverse() модифицируют оригинальный список. Это не всегда желательно. Напишите аналогичную пару функций, которые создают новый объект ilist : ilist ilist::concat_copy( const ilist &rhs ); ilist_item *it = mylist.find( 1 ); ilist ilist::reverse_copy(); С++ для начинающих 244 6. Абстрактные контейнерные типы В этой главе мы продолжим рассмотрение типов данных, начатое в главе 3, представим дополнительную информацию о классах vector и string и познакомимся с другими контейнерными типами, входящими в состав стандартной библиотеки С++. Мы также расскажем об операторах и выражениях, упомянутых в главе 4, сосредоточив внимание на тех операциях, которые поддерживаются объектами контейнерных типов. Последовательный контейнер содержит упорядоченный набор элементов одного типа. Можно выделить два основных типа контейнеров – вектор (vector) и список (list). (Третий последовательный контейнер – двусторонняя очередь (deque) – обеспечивает ту же функциональность, что и vector, но особенно эффективно реализует операции вставки и удаления первого элемента. deque следует применять, например, при реализации очереди, из которой извлекается только первый элемент. Все сказанное ниже относительно вектора применимо также и к deque.) Ассоциативный контейнер эффективно реализует операции проверки существования и извлечения элемента. Два основных ассоциативных контейнера – это отображение (map) и множество (set). map состоит из пар ключ/значение, причем ключ используется для поиска элемента, а значение содержит хранимую информацию. Телефонный справочник хорошо иллюстрирует понятие отображения: ключом является фамилия и имя абонента, а значением – его телефонный номер. Элемент контейнера set содержит только ключ, поэтому set эффективно реализует операцию проверки его существования. Этот контейнер можно применить, например, при реализации системы текстового поиска для хранения списка так называемых стоп-слов – слов, не используемых при поиске, таких, как и, или, не, так и тому подобных. Программа обработки текста считывает каждое слово и проверяет, есть ли оно в указанном списке. Если нет, то слово добавляется в базу данных. В контейнерах map и set не может быть дубликатов – повторяющихся ключей. Для поддержки дубликатов существуют контейнеры multimap и multiset. Например, multimap можно использовать при реализации такого телефонного справочника, в котором содержится несколько номеров одного абонента. В последующих разделах мы детально рассмотрим контейнерные типы и разработаем небольшую программу текстового поиска. 6.1. Система текстового поиска В систему текстового поиска входят текстовый файл, указанный пользователем, и средство для задания запроса, состоящего из слов и, возможно, логических операторов. Если одно или несколько слов запроса найдены, печатается количество их вхождений. По желанию пользователя печатаются предложения, содержащие найденные слова. С++ для начинающих 245 Например, если нужно найти все вхождения словосочетаний Civil War и Civil Rights , запрос может выглядеть таким образом 9 : Civil && ( War || Rights ) Результат запроса: Civil: 12 вхождений War: 48 вхождений Rights: 1 вхождение Civil && War: 1 вхождение Civil && Rights: 1 вхождение (8) Civility, of course, is not to be confused with Civil Rights, nor should it lead to Civil War Здесь (8) представляет собой номер предложения в тексте. Наша система должна печатать фразы, содержащие найденные слова, в порядке возрастания их номеров (т.е. предложение номер 7 будет напечатано раньше предложения номер 9), не повторяя одну и ту же несколько раз. Наша программа должна уметь: • запросить имя текстового файла, а затем открыть и прочитать этот файл; • организовать внутреннее представление этого файла так, чтобы впоследствии соотнести найденное слово с предложением, в котором оно встретилось, и определить порядковый номер этого слова ; • понимать определенный язык запросов. В нашем случае он включает следующие операторы: && два слова непосредственно следуют одно за другим в строке || одно или оба слова встречаются в строке ! слово не встречается в строке () группировка слов в запросе Используя этот язык, можно написать: Lincoln чтобы найти все предложения, включающие слово Lincoln, или 9 Замечание. Для упрощения программы мы требуем, чтобы каждое слово было отделено пробелом от скобок и логических операторов. Таким образом, запросы вида (War || Rights) Civil&&(War||Rights) не будут поняты нашей системой. Хотя удобство пользователей не должно приноситься в жертву простоте реализации, мы считаем, что в данном случае можно смириться с таким ограничением. |