С.Б. Липпман, Ж. Лажойе - Язык программирования С++ Вводный курс (1114944), страница 50
Текст из файла (страница 50)
Напишите программу, которая выбирает для вас книгу извектора при условии, что вы ее еще не прочитали. Выбранное название программадолжна заносить в множество прочитанных. Однако вы могли отложить книгу;следовательно, нужно обеспечить возможность удалять ее название из множествапрочитанных. По окончании шести виртуальных месяцев распечатайте списокпрочитанного и непрочитанного.6.14. Окончательная программаНиже представлен полный текст программы, разработанной в этой главе, с двумямодификациями: мы инкапсулировали все структуры данных и функции в классTextQuery (в последующих главах мы обсудим подобное использование классов), крометого, текст был изменен, так как наш компилятор поддерживал стандарт С++ неполностью.301С++ для начинающихНапример, библиотека iostream не соответствовала текущему стандарту.
Шаблоны неподдерживали значения аргументов по умолчанию. Возможно, вам придется изменитькое-что в этой программе, чтобы она компилировалась в вашей системе.302// стандартные заголовочные файлы С++#include <algorithm>#include <string>С++для начинающих#include<vector>#include <utility>#include <map>#include <set>// заголовочный файл iostream, не отвечающий стандарту#include <fstream.h>// заголовочные файлы С#include <stddef.h>#include <ctype.h>// typedef для удобства чтенияtypedef pair<short,short>typedef vector<location,allocator>typedef vector<string,allocator>typedef pair<text*,loc*>location;loc;text;text_loc;class TextQuery {public:TextQuery() { memset( this, 0, sizeof( TextQuery )); }static voidfilter_elements( string felems ) { filt_elems = felems; }void query_text();void display_map_text();void display_text_locations();void doit() {retrieve_text();separate_words();filter_text();suffix_text();strip_caps();build_word_map();}private:voidvoidvoidvoidvoidvoidvoidretrieve_text();separate_words():filter_text();strip_caps();suffix_textQ;suffix_s( string& );build_word_map();private:vector<string,allocator>text_locmap< string,loc*,less<string>,allocator>static string};*lines_of_text;*text_locations;*word_map;filt_elems;string TextQuery::filt_elems( "\", •;: !?)(\V" );int main(){TextQuery tq;tq.doit();tq.query_text();tq.display_map_text();}voidTextQuery::retrieve_text(){string file_name;cout << "please enter file name: ";cin >> file_name;ifstream infile( file_name.c_str(), ios::in );303С++ для начинающих}Упражнение 6.25Объясните, почему нам потребовался специальный класс inserter для заполненияset<string> exclusion_set;ifstreaminfile( "exclusion_set" );copy( default_excluded_words, default_excluded_words+25,набора стоп-слов (это упоминается в разделе 6.13.1, а детально рассматривается в 12.4.1).inserter(exclusion_set, exclusion_set.begin() ));Упражнение 6.26Первоначальная реализация поисковой системы отражает процедурный подход: наборглобальных функций оперирует набором независимых структур данных.
Окончательныйвариант представляет собой альтернативный подход, когда мы инкапсулируем функциии данные в класс TextQuery. Сравните оба способа. Каковы недостатки и преимуществакаждого?Упражнение 6.27В данной версии программы имя файла с текстом вводится по запросу. Более удобнобыло бы задавать его как параметр командной строки; в главе 7 мы покажем, как этоделается.
Какие еще параметры командной строки желательно реализовать?6.15. Контейнеры multimap и multisetКонтейнеры map и set не допускают повторяющихся значений ключей, а multimap(мультиотображение) и multiset (мультимножество) позволяют сохранять ключи сдублирующимися значениями. Например, в телефонном справочнике можетпонадобиться отдельный список номеров для каждого абонента. В перечне книг одногоавтора может быть несколько названий, а в нашей программе с одним словом текстасопоставляется несколько позиций.
Для использования multimap и multiset нужно#include <map>multimap< key_type, value_type > multimapName;// ключ - string, значение - list< string >multimap< string, list< string > > synonyms;#include <set>включить соответствующий заголовочный файл – map или set:multiset< type > multisetName;Для прохода по мультиотображению или мультимножеству можно воспользоватьсякомбинацией итератора, который возвращает find() (он указывает на первыйнайденный элемент), и значения, которое возвращает count().
(Это работает, посколькув данных контейнерах элементы с одинаковыми ключами обязательно являютсясоседними). Например:304С++ для начинающих#include <map>#include <string>void code_fragment(){multimap< string, string > authors;string search_item( "Alain de Botton" );// ...int number = authors.count( search_item );mu1timap< string,string >::iterator iter;iter = authors.find( search_item );for ( int cnt = 0; cnt < number; ++cnt, ++-iter )do_something( *iter );// ...}Более элегантный способ перебрать все значения с одинаковыми ключами используетспециальную функцию-член equal_range(), которая возвращает пару итераторов.
Одиниз них указывает на первое найденное значение, а второй – на следующее за последнимнайденным. Если последний из найденных элементов является последним в контейнере,второй итератор содержит величину, равную end():305С++ для начинающих#include <map>#include <string>#include <utility>void code_fragment(){multimap< string, string > authors;// ...string search_item( "Haruki Murakami" );while ( cin && cin >> search_item )switch ( authors.count( search_item )){// не найденоcase 0:break;// найден 1, обычный find()case 1: {multimap< string, string >: iterator iter;iter = authors.find( search_item );// обработка элемента ...break;}// найдено несколько ...default:{typedef multimap<string,string>::iterator iterator;pair< iterator, iterator > pos;// pos.first - адрес 1-го найденного// pos.second - адрес 1-го отличного// от найденногоpos = authors.equa1_range( search_item );for (; pos.first != pos.second; pos.first++ )// обработка элемента ...}}}Вставка и удаление элементов в multimap и multiset ничем не отличаются отаналогичных операций с контейнерами map и set.
Функция equal_range() доставляет#include <multimap>#include <string>typedef multimap< string, string >::iterator iterator;pair< iterator, iterator > pos;string search_item( "Kazuo Ishiguro" );// authors - multimap<string, string>// эквивалентно// authors.erase( search_item );pos = authors.equa1_range( search_item );итераторную пару, задающую диапазон удаляемых элементов:authors.erase( pos.first, pos.second );306С++ для начинающих307При каждом вызове функции-члена insert() добавляется новый элемент, даже если вtypedef multimap<string,string>::value_type valType;multimap<string,string> authors;// первый элемент с ключом Barthauthors.insert( valType (string( "Barth, John" ),string( "Sot-Weed Factor" )));// второй элемент с ключом Barthauthors.insert( va1Type(string( "Barth, John" ),контейнере уже был элемент с таким же ключом.
Например:string( "Lost in the Funhouse" )));Контейнер multimap не поддерживает операцию взятия индекса. Поэтому следующеевыражение ошибочно:authors[ "Barth, John" ]; // ошибка: multimapУпражнение 6.28Перепишите программу текстового поиска из раздела 6.14 с использованием multimapдля хранения позиций слов.
Каковы производительность и дизайн в обоих случаях?Какое решение вам больше нравится? Почему?6.16. СтекВ разделе 4.5 операции инкремента и декремента были проиллюстрированы на примеререализации абстракции стека. В общем случае стек является очень полезным механизмомдля сохранения текущего состояния, если в разные моменты выполнения программыодновременно существует несколько состояний, вложенных друг в друга. Посколькустек – это важная абстракция данных, в стандартной библиотеке С++ предусмотрен классstack, для использования которого нужно включить заголовочный файл:#include <stack>В стандартной библиотеке стек реализован несколько иначе, чем у нас. Разница состоит втом, что доступ к элементу с вершины стека и удаление его осуществляются двумяфункциями – top() и pop().
Полный набор операций со стеком приведен в таблице 6.5.Таблица 6.5. Операции со стекомОперацияДействиеempty()Возвращает true, если стек пуст, и false впротивном случаеsize()Возвращает количество элементов в стекеpop()Удаляет элемент с вершины стека, но невозвращает его значенияtop()Возвращает значение элемента с вершиныС++ для начинающих308стека, но не удаляет егоpush(item)Помещает новый элемент в стек#include <stack>#include <iostream>int main(){const int ia_size = 10;int ia[ia_size ]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9};// заполним стекint ix = 0;stack< int > intStack;for ( ; ix < ia_size; ++ix )intStack.push( ia[ ix ] );int error_cnt = 0;if ( intStack.size() != ia_size ) {cerr << "Ошибка! неверный размер IntStack: "<< intStack.size()<< "\t ожидается: " << ia_size << endl,++error_cnt;}int value;while ( intStack.empty() == false ){// считаем элемент с вершиныvalue = intStack.top();if ( value != --ix ) {cerr << "Ошибка! ожидается " << ix<< " получено " << value << endl;++error_cnt;}// удалим элементintStack.pop();}cout << "В результате запуска программы получено "<< error_cnt << " ошибок" << endl;В нашей программе приводятся примеры использования этих операций:}Объявлениеstack< int > intStack;определяет intStack как пустой стек, предназначенный для хранения элементов типаint.
Стек является надстройкой над некоторым контейнерным типом, посколькуреализуется с помощью того или иного контейнера. По умолчанию это deque, посколькуименно эта структура обеспечивает эффективную вставку и удаление первого элемента, аvector эти операции не поддерживает. Однако мы можем явно указать другой типконтейнера, задав его как второй параметр:С++ для начинающих309stack< int, list<int> > intStack;Элементы, добавляемые в стек, копируются в реализующий его контейнер.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
