Модуль: C++. Ассоциативные массивы: map

Обычные массивы в программировании обращаются к элементам по номерам: 0, 1, 2 и так далее. Это не всегда удобно. Например, если вы хотите хранить, сколько раз каждое слово встретилось в тексте, вам хочется искать по самому слову, а не по номеру. Для таких задач в C++ есть ассоциативные контейнеры — структуры данных, где каждому значению соответствует ключ (ассоциативные массивы).

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

В C++ чаще всего используют два контейнера такого типа: map и multimap. В map каждый ключ встречается только один раз, то есть одному ключу соответствует одно значение. В multimap допускаются повторяющиеся ключи: одному и тому же ключу могут соответствовать несколько значений, и контейнер хранит их все. Обе структуры устроены так, что операции поиска, вставки и удаления работают быстро — примерно за O(log⁡n), где n — количество элементов. Это означает “очень быстро”, даже если элементов много.
 

Контейнер map

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

Основные операторы

Функция	Описание	Пример
empty()	Проверяет, пустой ли контейнер	if (m.empty()) std::cout << "empty";
size()	Количество элементов	std::cout << m.size();
max_size()	Теоретически максимальный размер	auto mx = m.max_size();
count(key)	Сколько элементов с ключом. В map: 0 или 1	if (m.count("one")) { /* есть */ }
find(key)	Итератор на элемент с ключом или end()	auto it = m.find("one"); if (it != m.end()) std::cout << it->second;
lower_bound(key)	Первый элемент с ключом ≥ key	auto it = m.lower_bound("b");
upper_bound(key)	Первый элемент с ключом > key	auto it = m.upper_bound("b");
equal_range(key)	Пара итераторов [первый, после последнего]	auto [l, r] = m.equal_range("b"); for (auto it=l; it!=r; ++it) {}
operator[] (m[key])	Доступ по ключу. Если нет — создаёт со значением по умолчанию	m["one"]++;
at(key)	Доступ без создания. Если нет — исключение	int v = m.at("one");
insert(el)	Вставка элемента (пары ключ-значение)	m.insert({"cat", 3});
insert(beg, end)	Вставка диапазона	m.insert(v.begin(), v.end());
erase(key)	Удалить по ключу, вернуть кол-во удалённых	m.erase("cat");
erase(pos)	Удалить по итератору	m.erase(m.find("cat"));
erase(beg, end)	Удалить диапазон	m.erase(m.begin(), m.end());
clear()	Удалить все элементы	m.clear();
begin() / end()	Итераторы на начало/конец	for (auto it=m.begin(); it!=m.end(); ++it) {}
contains(key) (C++20)	Быстрая проверка существования без вставки	if (m.contains("one")) { /* ... */ }

Подсказка:

• Для счётчиков удобно использовать m[key]++.

• Для “просто узнать, есть ли ключ” — count или contains (C++20).

• Для безопасного чтения без создания — at.

 

Вывод содержимого map

Чтобы вывести все пары ключ–значение из std::map, можно проходить по контейнеру итератором. Итератор — это “указатель-стрелка” по контейнеру, который двигается от начала к концу.
 

// Обход с явным итератором:
map<string, int>::iterator it;
for (it = mymap.begin(); it != mymap.end(); ++it) {
    cout << it->first << " " << it->second << '\n';
}

где:

begin() - итератор на первый элемент,

end() - итератор на элемент идущий после последнего,

first - указатель на ключ

second  - указатель на значение

Тот же обход можно написать короче с помощью range-based for (C++11):

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

Если у вас C++17, ещё нагляднее использовать распаковку пары:

for (const auto& [key, value] : mymap) {
    cout << key << "\t" << value << endl;
}