Язык программирования C++. Вводный курс. С для начинающих

• Название: С для начинающих
• Дата: 24.08.2022
• Размер: 5.41 Mb.
• Имя файла: Язык программирования C++. Вводный курс.pdf
• Тип: Документы; #652350
• страница: 27 из 93

290
Если элемент отображения вставляется в отображение с помощью операции взятия индекса, то значением этого элемента становится значение по умолчанию для его типа данных. Для встроенных арифметических типов – 0.
Следовательно, если инициализация отображения производится оператором взятия индекса, то каждый элемент сначала получает значение по умолчанию, а затем ему явно присваивается нужное значение. Если элементы являются объектами класса, у которого инициализация по умолчанию и присваивание значения требуют больших затрат времени, программа будет работать правильно, но недостаточно эффективно.
Для вставки одного элемента предпочтительнее использовать следующий метод:
);
В контейнере map определен тип value_type для представления хранимых в нем пар ключ/значение. Строки value_type( string("Anna"), 1 ) создают объект pair, который затем непосредственно вставляется в map. Для удобства чтения можно использовать typedef: typedef map::value_type valType;
Теперь операция вставки выглядит проще: word_count.insert( valType( string("Anna"), 1 ));
Чтобы вставить элементы из некоторого диапазона, можно использовать метод insert(), принимающий в качестве параметров два итератора. Например: word_count_two.insert(word_count.begin(),word_count.end());
Мы могли бы сделать то же самое, просто проинициализировав одно отображение другим:
// предпочтительный метод вставки одного элемента word_count.insert( map:: value_type( string("Anna"), 1 ) map< string,int >:: map< string, int > word_count;
// ... заполнить map< string,int > word_count_two;
// скопируем все пары ключ/значение

С++ для начинающих
291
map< string, int > word_count_two( word_count );
Посмотрим, как можно построить отображение для хранения нашего текста. Функция separate_words()
, описанная в разделе 6.8, создает два объекта: вектор строк, хранящий все слова текста, и вектор позиций, хранящий пары (номер строки, номер колонки) для каждого слова. Таким образом, первый объект дает нам множество значений ключей нашего отображения, а второй – множество ассоциированных с ними значений. separate_words()
возвращает эти два вектора как объект типа pair, содержащий указатели на них. Сделаем эту пару аргументом функции build_word_map(), в результате которой будет получено соответствие между словами и позициями: build_word_map( const text_loc *text_locations );
Сначала выделим память для пустого объекта map и получим из аргумента-пары указатели на векторы: vector *text_locs = text_locations->second;
Теперь нам надо синхронно обойти оба вектора, учитывая два случая:
•
слово встретилось впервые. Нужно поместить в 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* >* map *word_map = new map< string, loc* >; vector *text_words = text_locations->first;

С++ для начинающих
292
}
Синтаксически сложное выражение push_back((*text_locs)[ix]); будет проще понять, если мы разложим его на составляющие: ploc->push_back(loc);
Выражение все еще остается сложным, так как наши векторы представлены указателями.
Поэтому вместо употребления оператора взятия индекса: string word = text_words[ix]; // ошибка мы вынуждены сначала разыменовать указатель на вектор: string word = (*text_words) [ix]; // правильно register 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; 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]]->
// возьмем слово, которое надо обновить string word = (*text_words) [ix];
// возьмем значение из вектора позиций vector *ploc = (*word_map) [ word ];
// возьмем позицию - пару координат loc = (*text_locs)[ix];
// вставим новую позицию

С++ для начинающих
293
В конце концов build_word_map() возвращает построенное отображение: return word_map;
Вот как выглядит вызов этой функции из main():
}
6.12.2.
Поиск и извлечение элемента отображения
Оператор взятия индекса является простейшим способом извлечения элемента.
Например: int count = word_count[ "wrinkles" ];
Однако этот способ работает так, как надо, только при условии, что запрашиваемый ключ действительно содержится в отображении. Иначе оператор взятия индекса поместит в отображение элемент с таким ключом. В данном случае в word_count занесется пара string( "wrinkles" ), 0
Класс map предоставляет две операции для того, чтобы выяснить, содержится ли в нем определенное значение ключа.
•
count(keyValue)
: функция-член count() возвращает количество элементов с данным ключом. (Для отображения оно равно только 0 или 1). Если count() вернула 1, мы можем смело использовать индексацию: count = word_count[ "wrinkles" ]; int main()
{
// считываем файл и выделяем слова vector *text_file = retrieve_text(); text_loc *text_locations = separate_words( text_file );
// обработаем слова
// ...
// построим отображение слов на векторы позиций map,allocator>
*text_map = build_word_map( text_locatons );
// ...
// map word_count; int count = 0; if ( word_count.count( "wrinkles" ))

С++ для начинающих
294
•
find(keyValue)
: функция-член find() возвращает итератор, указывающий на элемент, если ключ найден, и итератор end() в противном случае. Например: count = (*it).second;
Значением итератора является указатель на объект pair, в котором first содержит ключ, а second – значение. (Мы вернемся к этому в следующем подразделе.)
6.12.3.
Навигация по элементам отображения
После того как мы построили отображение, хотелось бы распечатать его содержимое. Мы можем сделать это, используя итератор, начальное и конечное значение которого получают с помощью функций-членов begin() и end(). Вот текст функции display_map_text()
:
}
Если наше отображение не содержит элементов, данная функция не нужна. Проверить, пусто ли оно, можно с помощью функции-члена size(): int count = 0; map::iterator it = word_count.find( "wrinkles" ); if ( it != word_count.end() ) void display_map_text( map *text_map )
{ typedef map 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;

С++ для начинающих
295
display_map_text( text_map );
Но более простым способом, без подсчета элементов, будет вызов функции-члена empty()
: display_map_text( text_map );
6.12.4.
Словарь
Вот небольшая программа, иллюстрирующая построение отображения, поиск в нем и обход элементов. Здесь используются два отображения. Первое, необходимое для преобразования слов, содержит два элемента типа string. Ключом является слово, которое нуждается в специальной обработке, а значением – слово, заменяющее ключ. Для простоты мы задали пары ключ/значение непосредственно в тексте программы (вы можете модифицировать программу так, чтобы она читала их из стандартного ввода или из файла). Второе отображение используется для подсчета произведенных замен. Текст программы выглядит следующим образом: if ( text_map->size() ) if ( ! text_map->empty() )

С++ для начинающих
296
#include

С++ для начинающих
297
}
Вот результат работы программы:
Наш словарь подстановок: key: 'em value: them key: cuz value: because key: gratz value: grateful key: nah value: no key: pos value: suppose key: sez value: says key: tanx value: thanks key: wuz value: was
Исходный вектор строк: nah I sez tanx cuz I wuz pos to not cuz I wuz gratz
Преобразованный вектор строк: no I says thanks because I was suppose to not because I was grateful
И напоследок статистика: cuz было заменено 2 раз(а) gratz было заменено 1 раз(а) nah было заменено 1 раз(а) pos было заменено 1 раз(а) sez было заменено 1 раз(а) tanx было заменено 1 раз(а) wuz было заменено 2 раз(а)
6.12.5.
Удаление элементов map
Существуют три формы функции-члена erase() для удаления элементов отображения.
Для единственного элемента используется erase() с ключом или итератором в качестве аргумента, а для последовательности эта функция вызывается с двумя итераторами.
Например, мы могли бы позволить удалять элементы из text_map таким образом: else cout << "
увы: " << remova1_word << " не найдено!\n";
Альтернативой является проверка: действительно ли слово содержится в text_map? string removal_word; cout << "
введите удаляемое слово: "; cin >> removal_word; if ( text_map->erase( remova1_word )) cout << "ok: " << remova1_word << " удалено\n";

С++ для начинающих
298
}
В нашей реализации text_map с каждым словом сопоставляется множество позиций, что несколько усложняет их хранение и извлечение. Вместо этого можно было бы иметь по одной позиции на слово. Но контейнер map не допускает дублирующиеся ключи. Нам следовало бы воспользоваться классом multimap, который рассматривается в разделе
6.15.
Упражнение 6.20
Определите отображение, где ключом является фамилия, а значением – вектор с именами детей. Поместите туда как минимум шесть элементов. Реализуйте возможность делать запрос по фамилии, добавлять имена и распечатывать содержимое.
Упражнение 6.21
Измените программу из предыдущего упражнения так, чтобы вместе с именем ребенка записывалась дата его рождения: пусть вектор-значение хранит пары строк – имя и дата.
Упражнение 6.22
Приведите хотя бы три примера, в которых нужно использовать отображение. Напишите определение объекта map для каждого примера и укажите наиболее вероятный способ вставки и извлечения элементов.
6.13.
Построение набора стоп-слов
Отображение состоит из пар ключ/значение. Множество (set), напротив, содержит неупорядоченную совокупность ключей. Например, бизнесмен может составить “черный список” bad_checks, содержащий имена лиц, в течение последних двух лет присылавших фальшивые чеки. Множество полезно тогда, когда нужно узнать, содержится ли определенное значение в списке. Скажем, наш бизнесмен, принимая чек от кого-либо, может проверить, есть ли его имя в bad_checks.
Для нашей поисковой системы мы построим набор стоп-слов – слов, имеющих семантически нейтральное значение (артикли, союзы, предлоги), таких, как the, and, into,
with, but и т.д. (это улучшает качество системы, однако мы уже не сможем найти первое предложение из знаменитого монолога Гамлета: “To be or not to be?”). Прежде чем добавлять слово к word_map, проверим, не содержится ли оно в списке стоп-слов. Если содержится, проигнорируем его.
6.13.1.
Определение объекта set и заполнение его
элементами
Перед использованием класса set необходимо включить соответствующий заголовочный файл: map::iterator where; where = text_map.find( remova1_word ); if ( where == text_map->end() ) cout << "
увы: " << remova1_word << " не найдено!\n"; else { text_map->erase( where ); cout << "ok: " << remova1_word << " удалено!\n";

С++ для начинающих
299
#include
Вот определение нашего множества стоп-слов: set exclusion_set;
Отдельные элементы могут добавляться туда с помощью операции insert(). Например: exclusion_set.insert( "and" );
Передавая insert() пару итераторов, можно добавить целый диапазон элементов.
Скажем, наша поисковая система позволяет указать файл со стоп-словами. Если такой файл не задан, берется некоторый набор слов по умолчанию:
}
В этом фрагменте кода встречаются два элемента, которые мы до сих пор не рассматривали: тип difference_type и класс inserter. difference_type – это тип результата вычитания двух итераторов для нашего множества строк. Он передается в качестве одного из параметров шаблона istream_iterator. copy()
–один из обобщенных алгоритмов. (Мы рассмотрим их в главе 12 и в
Приложении.) Первые два параметра – пара итераторов или указателей – задают диапазон. Третий параметр является либо итератором, либо указателем на начало контейнера, в который элементы копируются.
Проблема с этой функцией вызвана ограничением, вытекающим из ее реализации: количество копируемых элементов не может превосходить числа элементов в контейнере- адресате. Дело в том, что copy() не вставляет элементы, она только присваивает exclusion_set.insert( "the" ); typedef set< string >::difference_type diff_type; set< string > exclusion_set; ifstream infile( "exclusion_set" ); if ( ! infile )
{ static string default_excluded_words[25] = {
"the","and","but","that","then","are","been",
"can"."can't","cannot","could","did","for",
"had","have","him","his","her","its","into",
"were","which","when","with","would"
}; cerr << "
предупреждение! невозможно открыть файл стоп-слов! -- "
<< "
используется стандартный набор слов \n"; copy( default_excluded_words, default_excluded_words+25, inserter( exclusion_set, exclusion_set.begin() ));
} else { istream_iterator input_set(infile),eos; copy( input_set, eos, inserter( exclusion_set, exclusion_set.begin() ));

С++ для начинающих
300
каждому элементу новое значение. Однако ассоциативные контейнеры не позволяют явно задать размер. Чтобы скопировать элементы в наше множество, мы должны заставить copy()
вставлять элементы. Именно для этого служит класс inserter (детально он рассматривается в разделе 12.4).
6.13.2.
Поиск элемента
Две операции, позволяющие отыскать в наборе определенное значение, – это find()
и count(). find() возвращает итератор, указывающий на найденный элемент, или значение, равное end(), если он отсутствует. count() возвращает 1 при наличии элемента и 0 в противном случае. Добавим проверку на существование в функцию build_word_map():
// добавим отсутствующее слово
6.13.3.
Навигация по множеству
Для проверки наших кодов реализуем небольшую функцию, выполняющую поиск по одному слову (поддержка языка запросов будет добавлена в главе 17). Если слово найдено, мы будем показывать каждую строку, в которой оно содержится. Слово может повторяться в строке, например: tomorrow and tomorrow and tomorrow однако такая строка будет представлена только один раз.
Одним из способов не учитывать повторное вхождение слова в строку является использование множества, как показано в следующем фрагменте кода:
} if ( exclusion_set.count( textword )) continue;
// получим указатель на вектор позиций loc ploc = (*text_map)[ query_text ];
// переберем все позиции
// вставим все номера строк в множество set< short > occurrence_lines; loc::iterator liter = ploc->begin(), liter_end = ploc->end(); while ( liter != liter_end ) { occurrence_lines.insert( occurrence_lines.end(),
(*liter).first );
++liter;

С++ для начинающих