Задача

1/9

Списки: Начало

Теория Нажмите, чтобы прочитать/скрыть

Изучая массивы мы видели, что индексом элемента массива может быть только целое число, но это не всегда удобно.
Для решения этой проблемы существует ассоциативный массив, значения в котором представлены в виде "ключ-значение", где ключом может все, что угодно.
Самый распространенный случай это когда индексом (ключом) является слово, таким образом мы можем легко решать задачи вида: подсчитать количество слов в заданном тексте.

В С++ два вида ассоциативных массивов: map и multimap. Отличаются они тем, что в map ключи уникальные, а в multimap могут повторятся.

Асимптотика:
Поиск, вставка и удаление за О(logn).

Рассмотрим map:
 

Для использования map вам необходимо сначала его подключить:
#include <map>

Пример создания map, у которого ключом является строка, а значением целое число:
map<string, int> mymap;

Основные операторы:
 
empty() - возвращает истину, если размер контейнера равен 0;
size() - возвращает число элементов;
max_size() - максимально возможный размер контейнера.
 
count(key) - число элементов соответствующих указанному ключу. Для класса map значения 1 или 0;
find(key) - итератор на первый элемент с указанным ключом;
lower_bound(key) - итератор на первый элемент, чей ключ больше или равен указанному ключу;
upper_bound(key) - итератор на первый элемент, чей ключ больше указанного ключа;
equal_range(key) - диапазон элементов, чей ключ равен указанному ключу;
[] - операция индексации по ключу.
 
 
insert(el) - вставка элемента, возвращается его позиция;
insert(beg,end) - вставка элементов из указанного диапазона;
erase(el) - удалить указанный элемент;
erase(beg) - удалить элемент в указанной позиции;
erase(beg,end) - удалить элемент из указанного диапазона;
clear() - удалить все элементы.

Обратите внимание на count:
проверять наличие индекса таким образом нельзя:

if( mymap["one"] == 0)
это вызовет автоматическое создание в массиве элемента с ключом one. Поэтому проверять надо так:

if( mymap.count("one") == 0 )
 

Увеличение значения для ключа (слова) "one": 
mymap["one"]++;


Для вывода содержимого map можно использовать iterator, который позволяет получать доступ к элементам массива без использования описаний каждого из агрегированных объектов:

map<string, int>::iterator it;

for (it = mymap.begin(); it != mymap.end(); ++it)
cout << it->first << " " << it->second << '\n';

где:
 
begin() - итератор на первый элемент,
end() - итератор на элемент идущий после последнего,
first - указатель на ключ
second  - указатель на значение

либо с помощью ключевого слова auto (C++ 11):

for( auto& kv : mymap)
    cout << kv.first << "\t " << kv.second << endl;



 

Задача

Построить алфавитно-частотный словарь: список слов в алфавитном порядке, справа от каждого слова должно быть указано, сколько раз оно встречается в исходном файле. Признаком окончания текста является "END!". Порядок вывода слов роли не играет.
 
Ввод Вывод
Съешь ещё этих мягких французских булок END! Съешь 1
ещё 1
этих 1
мягких 1
французских 1
булок 1