Изучая массивы мы видели, что индексом элемента массива может быть только целое число, но это не всегда удобно.
Для решения этой проблемы существует ассоциативный массив, значения в котором представлены в виде "ключ-значение", где ключом может все, что угодно.
Самый распространенный случай это когда индексом (ключом) является слово, таким образом мы можем легко решать задачи вида: подсчитать количество слов в заданном тексте.
В С++ два вида ассоциативных массивов: map и multimap. Отличаются они тем, что в map ключи уникальные, а в multimap могут повторятся.
Асимптотика:
Поиск, вставка и удаление за О(logn).
Рассмотрим map:
Для использования map вам необходимо сначала его подключить:
Пример создания map, у которого ключом является строка, а значением целое число:
Основные операторы:
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":
Для вывода содержимого 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;