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

Определение объекта 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 );

        // ...

    }


    Содержание раздела