| Меню сайта |
|
 |
| Категория |
|
|
| Развлечение |
|
|
| ON - LINE |
|
|
| Опрос |
|
|
| Оbserver Ward |
Онлайн всего: 1 Гостей: 1 Пользователей: 0
|
|
| Друзья сайта |
|
|
| Hаша кнопка |
Для обмена банерами , наша кнопка для размещения у вас на сайте
|
|
|
6. Абстрактные контейнерные типы (3)
6.12.1. Определение объекта map и заполнение его элементами
Чтобы определить объект класса map, мы должны указать, как минимум, типы ключа и значения. Например:
map<string,int> word_count;
Здесь задается объект word_count типа map, для которого ключом служит объект типа string, а ассоциированным с ним значением – объект типа int. Аналогично
class employee;
map<int,employee*> personnel;
определяет personnel как отображение ключа типа int (уникальный номер служащего) на указатель, адресующий объект класса employee.
Для нашей поисковой системы полезно такое отображение:
typedef 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());
Мы могли бы сделать то же самое, просто проинициализировав одно отображение другим:
// инициализируем копией всех пар ключ/значение
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 новую пару ключ/значение;
* слово встречается повторно. Нам нужно обновить вектор позиций, добавив дополнительную пару (номер строки, номер колонки).
Вот текст функции:
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<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;
Вот как выглядит вызов этой функции из main():
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 );
// ...
}
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() вернула 1, мы можем смело использовать индексацию:
int count = 0;
if ( word_count.count( "wrinkles" ))
count = word_count[ "wrinkles" ];
* find(keyValue): функция-член find() возвращает итератор, указывающий на элемент, если ключ найден, и итератор end() в противном случае. Например:
int count = 0;
map<string,int>::iterator it = word_count.find( "wrinkles" );
if ( it != word_count.end() )
count = (*it).second;
Значением итератора является указатель на объект pair, в котором first содержит ключ, а second – значение. (Мы вернемся к этому в следующем подразделе.)
6.12.3. Навигация по элементам отображения
После того как мы построили отображение, хотелось бы распечатать его содержимое. Мы можем сделать это, используя итератор, начальное и конечное значение которого получают с помощью функций-членов begin() и end(). Вот текст функции display_map_text():
void
display_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;
}
Если наше отображение не содержит элементов, данная функция не нужна. Проверить, пусто ли оно, можно с помощью функции-члена size():
if ( text_map->size() )
display_map_text( text_map );
Но более простым способом, без подсчета элементов, будет вызов функции-члена empty():
if ( ! text_map->empty() )
display_map_text( text_map );
6.12.4. Словарь
Вот небольшая программа, иллюстрирующая построение отображения, поиск в нем и обход элементов. Здесь используются два отображения. Первое, необходимое для преобразования слов, содержит два элемента типа string. Ключом является слово, которое нуждается в специальной обработке, а значением – слово, заменяющее ключ. Для простоты мы задали пары ключ/значение непосредственно в тексте программы (вы можете модифицировать программу так, чтобы она читала их из стандартного ввода или из файла). Второе отображение используется для подсчета произведенных замен. Текст программы выглядит следующим образом:
#include <map>
#include <vector>
#include <iostream>
#include <string>
int main()
{
map< string, string > trans_map;
typedef map< string, string >::value_type valType;
// первое упрощение:
// жестко заданный словарь
trans_map.insert( va1Type( "gratz", "grateful" ));
trans_map.insert( va1Type( "'em", "them" ));
trans_map.insert( va1Type( "cuz", "because" ));
trans_map.insert( va1Type( "nah", "no" ));
trans_map.insert( va1Type( "sez", "says" ));
trans_map.insert( va1Type( "tanx", "thanks" ));
trans_map.insert( va1Type( "wuz", "was" ));
trans_map.insert( va1Type( "pos", "suppose" ));
// напечатаем словарь
map< string,string >::iterator it;
cout << "Наш словарь подстановок: \n\n";
for ( it = trans_map.begin();
it != trans_map.end(); ++it )
cout << "ключ: " << (*it).first << "\t"
<< "значение: " << ("it).second << "\n";
cout << "\n\n";
// второе упрощение: жестко заданный текст
string textarray[14]={ "nah", "I", "sez", "tanx",
"cuz", "I", "wuz", "pos", "to", "not",
"cuz", "I", "wuz", "gratz" };
vector< string > text( textarray, textarray+14 );
vector< string >::iterator iter;
// напечатаем текст
cout << "Исходный вектор строк:\n\n";
int cnt = 1;
for ( iter = text-begin(); iter != text.end();
++iter,++cnt )
cout << *iter << ( cnt % 8 ? " " : "\n" );
cout << "\n\n\n";
// map для сбора статистики
map< string,int > stats;
typedef map< string,int >::value_type statsValType;
// здесь происходит реальная работа
for ( iter=text.begin(); iter != text.end(); ++iter )
if (( it = trans_map.find( *iter ))
!= trans_map.end() )
{
if ( stats.count( *iter ))
stats [ *iter ] += 1;
else stats.insert( statsVa1Type( *iter, 1 ));
*iter = (*it).second;
}
// напечатаем преобразованный текст
cout << "Преобразованный вектор строк:\n\n";
cnt = 1;
for ( iter = text.begin(); iter != text.end();
++iter, ++cnt )
cout << *iter << ( cnt % 8 ? " " : "\n" );
cout << "\n\n\n";
// напечатаем статистику
cout << "И напоследок статистика:\n\n";
map<string,int,less<string>,allocator>::iterator siter;
for (siter=stats.begin(); siter!=stats.end(); ++siter)
cout << (*siter).first << " "
<< "было заменено "
<< (*siter).second
<< (" раз(а)\n" );
}
Вот результат работы программы:
Наш словарь подстановок:
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 таким образом:
string removal_word;
cout << "введите удаляемое слово: ";
cin >> removal_word;
if ( text_map->erase( remova1_word ))
cout << "ok: " << remova1_word << " удалено\n";
else cout << "увы: " << remova1_word << " не найдено!\n";
Альтернативой является проверка: действительно ли слово содержится в text_map?
map<string,loc*>::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";
}
В нашей реализации 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 необходимо включить соответствующий заголовочный файл:
#include <set>
Вот определение нашего множества стоп-слов:
set<string> exclusion_set;
Отдельные элементы могут добавляться туда с помощью операции insert(). Например:
exclusion_set.insert( "the" );
exclusion_set.insert( "and" );
Передавая insert() пару итераторов, можно добавить целый диапазон элементов. Скажем, наша поисковая система позволяет указать файл со стоп-словами. Если такой файл не задан, берется некоторый набор слов по умолчанию:
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<string,diff_type> input_set(infile),eos;
copy( input_set, eos, inserter( exclusion_set,
exclusion_set.begin() ));
}
В этом фрагменте кода встречаются два элемента, которые мы до сих пор не рассматривали: тип difference_type и класс inserter. difference_type – это тип результата вычитания двух итераторов для нашего множества строк. Он передается в качестве одного из параметров шаблона istream_iterator.
copy() –один из обобщенных алгоритмов. (Мы рассмотрим их в главе 12 и в Приложении.) Первые два параметра – пара итераторов или указателей – задают диапазон. Третий параметр является либо итератором, либо указателем на начало контейнера, в который элементы копируются.
Проблема с этой функцией вызвана ограничением, вытекающим из ее реализации: количество копируемых элементов не может превосходить числа элементов в контейнере-адресате. Дело в том, что copy() не вставляет элементы, она только присваивает каждому элементу новое значение. Однако ассоциативные контейнеры не позволяют явно задать размер. Чтобы скопировать элементы в наше множество, мы должны заставить copy() вставлять элементы. Именно для этого служит класс inserter (детально он рассматривается в разделе 12.4).
6.13.2. Поиск элемента
Две операции, позволяющие отыскать в наборе определенное значение, – это find() и count(). find() возвращает итератор, указывающий на найденный элемент, или значение, равное end(), если он отсутствует. count() возвращает 1 при наличии элемента и 0 в противном случае. Добавим проверку на существование в функцию build_word_map():
if ( exclusion_set.count( textword ))
continue;
// добавим отсутствующее слово
6.13.3. Навигация по множеству
Для проверки наших кодов реализуем небольшую функцию, выполняющую поиск по одному слову (поддержка языка запросов будет добавлена в главе 17). Если слово найдено, мы будем показывать каждую строку, в которой оно содержится. Слово может повторяться в строке, например:
tomorrow and tomorrow and tomorrow
однако такая строка будет представлена только один раз.
Одним из способов не учитывать повторное вхождение слова в строку является использование множества, как показано в следующем фрагменте кода:
// получим указатель на вектор позиций
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;
}
Контейнер set не допускает дублирования ключей. Поэтому можно гарантировать, что occurrence_lines не содержит повторений. Теперь нам достаточно перебрать данное множество, чтобы показать все номера строк, где встретилось данное слово:
register int size = occurrence_lines.size();
cout << "\n" << query_text
<< " встречается " << size
<< " раз(а):")
<< "\n\n";
set< short >::iterator it=occurrence_lines.begin();
for ( ; it != occurrence_lines.end(); ++it ) {
int line = -it;
cout << "\t( строка "
<< line + 1 << " ) "
<< (*text_file)[line] << endl;
}
(Полная реализация query_text() представлена в следующем разделе.)
Класс set поддерживает операции size(), empty() и erase() точно таким же образом, как и класс map, описанный выше. Кроме того, обобщенные алгоритмы предоставляют набор специфических функций для множеств, например set_union() (объединение) и set_difference() (разность). (Они использованы при реализации языка запросов в главе 17.)
Упражнение 6.23
Добавьте в программу множество слов, в которых заключающее 's' не подчиняется общим правилам и не должно удаляться. Примерами таких слов могут быть Pythagoras, Brahms и Burne_Jones. Включите в функцию suffix_s() из раздела 6.10 проверку этого набора.
Упражнение 6.24
Определите вектор, содержащий названия книг, которые вы собираетесь прочесть в ближайшие шесть виртуальных месяцев, и множество, включающее названия уже прочитанных произведений. Напишите программу, которая выбирает для вас книгу из вектора при условии, что вы ее еще не прочитали. Выбранное название программа должна заносить в множество прочитанных. Однако вы могли отложить книгу; следовательно, нужно обеспечить возможность удалять ее название из множества прочитанных. По окончании шести виртуальных месяцев распечатайте список прочитанного и непрочитанного.
|
| Категория: С++ | Добавил: r2d2 (29.09.2011)
|
| Просмотров: 702
| Рейтинг: 0.0/0 |
Добавлять комментарии могут только зарегистрированные пользователи. [ Регистрация | Вход ] |
|
| Born in Ussr |
|
|
| Залогиниться |
|
|
|
| Турниры |
|
|
|
