Определение объекта 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 >:: |
создают объект 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; // скопируем все пары ключ/значение |
Мы могли бы сделать то же самое, просто проинициализировав одно отображение другим:
// инициализируем копией всех пар ключ/значение |
Посмотрим, как можно построить отображение для хранения нашего текста. Функция separate_words(), описанная в разделе 6.8, создает два объекта: вектор строк, хранящий все слова текста, и вектор позиций, хранящий пары (номер строки, номер колонки) для каждого слова. Таким образом, первый объект дает нам множество значений ключей нашего отображения, а второй – множество ассоциированных с ними значений.
}
Синтаксически сложное выражение
(*word_map)[(*text_words)[ix]]-> |
будет проще понять, если мы разложим его на составляющие:
// возьмем слово, которое надо обновить string word = (*text_words) [ix]; // возьмем значение из вектора позиций vector<location> *ploc = (*word_map) [ word ]; // возьмем позицию - пару координат loc = (*text_locs)[ix]; // вставим новую позицию |
Выражение все еще остается сложным, так как наши векторы представлены указателями. Поэтому вместо употребления оператора взятия индекса:
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 ); // ... |
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* >* |
Сначала выделим память для пустого объекта map и получим из аргумента-пары указатели на векторы:
map<string,loc*> *word_map = new map< string, loc* >; vector<string> *text_words = text_locations->first; |
Теперь нам надо синхронно обойти оба вектора, учитывая два случая:
· слово встретилось впервые. Нужно поместить в 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]); |
