С.Б. Липпман, Ж. Лажойе - Язык программирования С++ Вводный курс (1114944), страница 48
Текст из файла (страница 48)
begin()+3;// заменяем ADT на Abstract Data TypeА здесь мы используем пару итераторов:sentence.repiace( start, start+3, "Abstract Data Type" );Оставшиеся четыре варианта допускают задание заменяющей строки как объекта типаstring, символа, повторяющегося N раз, пары итераторов и C-строки.Вот и все, что мы хотели сказать об операциях со строками. Для более полнойинформации обращайтесь к определению стандарта С++ [ISO-C++97].286С++ для начинающих287Упражнение 6.18Напишите программу, которая с помощью функций-членов assign() и append() изstring quote1( "When lilacs last in the dooryard bloom'd" );строкstring quote2( "The child "is father of the man" );составит предложение"The child is in the dooryard"Упражнение 6.19string generate_salutation( string generic1,string lastname,string generic2,string::size_type pos,Напишите функцию:int length );которая в строкеstring generic1( "Dear Ms Daisy:" );заменяет Daisy и Ms (миссис).
Вместо Daisy подставляется параметр lastname, а вместоMs подстрокаstring generic2( "MrsMsMissPeople" );длины length, начинающаяся с pos.string lastName( "AnnaP" );string greetings =Например, вызовgenerate_salutation( generici, lastName, generic2, 5, 4 );вернет строку:Dear Miss AnnaP:С++ для начинающих2886.12. Строим отображение позиций словВ этом разделе мы построим отображение (map), позволяющее для каждого уникальногослова текста сохранить номера строк и колонок, в которых оно встречается.
(Вследующем разделе мы изучим ассоциативный контейнер set.) В общем случаеконтейнер set полезен, если мы хотим знать, содержится ли определенный элемент внекотором множестве, а map позволяет связать с каждым из них какую-либо величину.В map хранятся пары ключ/значение. Ключ играет роль индекса для доступа кассоциированному с ним значению.
В нашей программе каждое уникальное слово текстабудет служить ключом, а значением станет вектор, содержащий пары (номер строки,string query( "pickle" );vector< location > *locat;// возвращается location<vector>*, ассоциированный с "pickle"номер колонки). Для доступа применяется оператор взятия индекса. Например:locat = text_map[ query ];Ключом здесь является строка, а значение имеет тип location<vector>*.Для использования отображения необходимо включить соответствующий заголовочныйфайл:#include <map>Какие основные действия производятся над ассоциативными контейнерами? Ихзаполняют элементами или проверяют на наличие определенного элемента. В следующемподразделе мы покажем, как определить пару ключ/значение и как поместить такие парыв контейнер. Далее мы расскажем, как сформулировать запрос на поиск элемента иизвлечь значение, если элемент существует.6.12.1.
ОпределениеэлементамиобъектаmapизаполнениеегоЧтобы определить объект класса map, мы должны указать, как минимум, типы ключа изначения. Например:map<string,int> word_count;Здесь задается объект word_count типа map, для которого ключом служит объект типаclass employee;string, а ассоциированным с ним значением – объект типа int. Аналогичноmap<int,employee*> personnel;определяет personnel как отображение ключа типа int (уникальный номер служащего)на указатель, адресующий объект класса employee.С++ для начинающих289typedef pair<short,short> location;typedef vector<location> loc;Для нашей поисковой системы полезно такое отображение:map<string,loc*> text_map;Поскольку имевшийся в нашем распоряжении компилятор не поддерживал аргументы поумолчанию для параметров шаблона, нам пришлось написать более развернутоеmap<string,loc*,less<string>,allocator>// ключ, значение// оператор сравнения// распределитель памяти по умолчаниюопределение:text_map;По умолчанию сортировка ассоциативных контейнеров производится с помощьюоперации “меньше”.
Однако можно указать и другой оператор сравнения (см. раздел 12.3об объектах-функциях).Послетогокакотображениеопределено,необходимозаполнитьегопарами#include <map>#include <string>map<string,int> word_count;word_count[ string("Anna") ] = 1;word_count[ string("Danny") ] = 1;word_count[ string("Beth") ] = 1;ключ/значение.
Интуитивно хочется написать примерно так:// и так далее ...Когда мы пишем:word_count[ string("Anna") ] = 1;на самом деле происходит следующее:1. Безымянный временный объект типа string инициализируется значением "Anna" ипередается оператору взятия индекса, определенному в классе map.2. Производится поиск элемента с ключом "Anna" в массиве word_count.
Такогоэлемента нет.3. В word_count вставляется новая пара ключ/значение. Ключом является, естественно,строка "Anna". Значением – 0, а не 1.4. После этого значению присваивается величина 1.С++ для начинающихЕсли элемент отображения вставляется в отображение с помощью операции взятияиндекса, то значением этого элемента становится значение по умолчанию для его типаданных.
Для встроенных арифметических типов – 0.Следовательно, если инициализация отображения производится оператором взятияиндекса, то каждый элемент сначала получает значение по умолчанию, а затем ему явноприсваивается нужное значение. Если элементы являются объектами класса, у которогоинициализация по умолчанию и присваивание значения требуют больших затратвремени, программа будет работать правильно, но недостаточно эффективно.// предпочтительный метод вставки одного элементаword_count.insert(map<string,i nt>::value_type( string("Anna"), 1 )Для вставки одного элемента предпочтительнее использовать следующий метод:);В контейнере map определен тип value_type для представления хранимых в нем парmap< string,int >::ключ/значение.
Строкиvalue_type( string("Anna"), 1 )создают объект pair, который затем непосредственно вставляется в map. Для удобствачтения можно использовать typedef:typedef map<string,int>::value_type valType;Теперь операция вставки выглядит проще:word_count.insert( valType( string("Anna"), 1 ));Чтобы вставить элементы из некоторого диапазона, можно использовать метод insert(),map< string, int > word_count;// ... заполнитьmap< string,int > word_count_two;// скопируем все пары ключ/значениепринимающий в качестве параметров два итератора. Например:word_count_two.insert(word_count.begin(),word_count.end());Мы могли бы сделать то же самое, просто проинициализировав одно отображениедругим:290С++ для начинающих291// инициализируем копией всех пар ключ/значениеmap< string, int > word_count_two( word_count );Посмотрим, как можно построить отображение для хранения нашего текста.
Функцияseparate_words(), описанная в разделе 6.8, создает два объекта: вектор строк,хранящий все слова текста, и вектор позиций, хранящий пары (номер строки, номерколонки) для каждого слова. Таким образом, первый объект дает нам множествозначений ключей нашего отображения, а второй – множество ассоциированных с нимизначений.separate_words() возвращает эти два вектора как объект типа pair, содержащийуказатели на них. Сделаем эту пару аргументом функции build_word_map(), в// typedef для удобства чтенияtypedef pair< short,short > location;typedef vector< location >loc;typedef vector< string >text;typedef pair< text*,loc* >text_loc;extern map< string, loc* >*результате которой будет получено соответствие между словами и позициями:build_word_map( const text_loc *text_locations );Сначала выделим память для пустого объекта map и получим из аргумента-парыmap<string,loc*> *word_map = new map< string, loc* >;vector<string>*text_words = text_locations->first;указатели на векторы:vector<location> *text_locs= text_locations->second;Теперь нам надо синхронно обойти оба вектора, учитывая два случая:•слово встретилось впервые.
Нужно поместить в map новую пару ключ/значение;•слово встречается повторно. Нам нужно обновить вектор позиций, добавивдополнительную пару (номер строки, номер колонки).Вот текст функции:С++ для начинающих292register int elem_cnt = text_words->size();for ( int ix=0; ix < elem_cnt; ++ix ){string textword = ( *text_words )[ ix ];// игнорируем слова короче трех букв// или присутствующие в списке стоп-словif ( textword.size() < 3 ||exclusion_set.count( textword ))continue;// определяем, занесено ли слово в отображение// если count() возвращает 0 - нет: добавим егоif ( ! word_map->count((*text_words)[-ix] )){loc *ploc = new vector<location>;ploc->push_back( (*text_locs) [ix] );word_map->insert(value_type((*text_words)[ix],ploc));}else// добавим дополнительные координаты(*word_map)[(*text_words)[ix]]->push_back((*text_locs)[ix]);}(*word_map)[(*text_words)[ix]]->Синтаксически сложное выражениеpush_back((*text_locs)[ix]);// возьмем слово, которое надо обновитьstring word = (*text_words) [ix];// возьмем значение из вектора позицийvector<location> *ploc = (*word_map) [ word ];// возьмем позицию - пару координатloc = (*text_locs)[ix];// вставим новую позициюбудет проще понять, если мы разложим его на составляющие:ploc->push_back(loc);Выражение все еще остается сложным, так как наши векторы представлены указателями.Поэтому вместо употребления оператора взятия индекса:string word = text_words[ix]; // ошибкамы вынуждены сначала разыменовать указатель на вектор:string word = (*text_words) [ix]; // правильноС++ для начинающихВ конце концов build_word_map() возвращает построенное отображение:return word_map;int main(){// считываем файл и выделяем словаvector<string, allocator> *text_file = retrieve_text();text_loc *text_locations = separate_words( text_file );// обработаем слова// ...// построим отображение слов на векторы позицийmap<string,lос*,less<string>,allocator>*text_map = build_word_map( text_locatons );// ...Вот как выглядит вызов этой функции из main():}6.12.2.
Поиск и извлечение элемента отображенияОператор взятия индекса является простейшим способом извлечения элемента.// map<string,int> word_count;Например:int count = word_count[ "wrinkles" ];Однако этот способ работает так, как надо, только при условии, что запрашиваемыйключ действительно содержится в отображении. Иначе оператор взятия индекса поместитв отображение элемент с таким ключом.
В данном случае в word_count занесется параstring( "wrinkles" ), 0Класс map предоставляет две операции для того, чтобы выяснить, содержится ли в немопределенное значение ключа.•count(keyValue): функция-член count() возвращает количество элементов сданным ключом. (Для отображения оно равно только 0 или 1). Если count()int count = 0;if ( word_count.count( "wrinkles" ))вернула 1, мы можем смело использовать индексацию:count = word_count[ "wrinkles" ];293С++ для начинающих•find(keyValue): функция-член find() возвращает итератор, указывающий наint count = 0;map<string,int>::iterator it = word_count.find( "wrinkles" );if ( it != word_count.end() )элемент, если ключ найден, и итератор end() в противном случае. Например:count = (*it).second;Значением итератора является указатель на объект pair, в котором first содержитключ, а second – значение.
(Мы вернемся к этому в следующем подразделе.)6.12.3. Навигация по элементам отображенияПосле того как мы построили отображение, хотелось бы распечатать его содержимое. Мыможем сделать это, используя итератор, начальное и конечное значение которогополучают с помощью функций-членов begin() и end(). Вот текст функцииvoiddisplay_map_text( map<string,loc*> *text_map ){typedef map<string,loc*> tmap;tmap::iterator iter = text_map->begin(),iter_end = text_map->end();while ( iter != iter_end ){cout << "word: " << (*iter).first << " (";int loc_cnt = 0;loc *text_locs = (*iter).second;loc::iterator liter = text_locs->begin(),liter_end = text_locs->end();while (liter != liter_end ) {if ( loc_cnt )cout << ',';else ++loc_cnt;cout << '(' << (*liter).first<< ',' << (*liter).second << ')';++liter;}cout << ")\n";++iter;}cout << endl;display_map_text():}Если наше отображение не содержит элементов, данная функция не нужна.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
