Ассоциативные массивы: map

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

В С++ два вида ассоциативных массивов: 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;



 

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

Пример компаратора, который сортирует по убыванию ключа (пишется перед main):

struct cmp
{
	bool operator()(const string &a, const string &b) const
	{
		return a > b;
	}
};

и используется при создании списка:

map<string, int, cmp> mymap;

Простого решения провести сортировку по значению нет, поэтому приходится из словаря делать вектор пар, и уже его сортировать с помощью компаратора.