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;
}


 

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

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

Сортировка словаря в С++

Главное

1. Обычный map - всегда отсортирован по ключам (A-Z, 0-9)
2. Чтобы сортировать по значениям - делаем вектор из пар и сортируем его
3. Для обратного порядка - используем greater<> или меняем знак в функции сравнения

// 1. Берем словарь
map<string, int> dict = {{"banana", 3}, {"apple", 1}, {"cherry", 2}};

// 2. Делаем из него вектор
vector<pair<string, int>> items(dict.begin(), dict.end());

// 3. Сортируем вектор по числам (значениям)
sort(items.begin(), items.end(), compareByValue);

// 4. Используем отсортированный вектор

---

compareByValue - это простая функция, которая говорит сортировке как сравнивать элементы.

Как работает

bool compareByValue(pair<string, int> a, pair<string, int> b) {
    return a.second < b.second;
}

Что означают a.second и b.second?

• a.second - значение первого элемента (число)
• b.second - значение второго элемента (число)

Правило простое:

• return a.second < b.second = сортировать по возрастанию (1, 2, 3)
• return a.second > b.second = сортировать по убыванию (3, 2, 1)

 

---

Что такое pair?

pair - это контейнер для двух значений. Как карманы в штанах - в левый положили одно, в правый - другое.
 

pair<string, int> fruit = {"apple", 5};

cout << fruit.first;   // "apple" - первое значение
cout << fruit.second;  // 5       - второе значение

Используется при:

• работе со словарями, 
• возврате двух значений из функции
• хранении координаты точки (x,y) 

Pair - это просто два значения в одной упаковке!