C++. Ассоциативные массивы: 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;

Задача для тренировки:

Отсортированные списки №1

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

Задача для тренировки:

Отсортированные списки №2

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

В Python словари (начиная с версии 3.7) сохраняют порядок добавления элементов, но для сортировки словарей по ключам или значениям можно использовать несколько подходов.
 

1. Сортировка по ключам

Использование функции sorted()

Вы можете использовать функцию sorted() для получения отсортированного списка ключей, а затем создать новый словарь: 
my_dict = {'b': 2, 'a': 1, 'c': 3}

# Сортировка по ключам
sorted_dict_by_keys = {key: my_dict[key] for key in sorted(my_dict)}
print(sorted_dict_by_keys)  # Вывод: {'a': 1, 'b': 2, 'c': 3}



2. Сортировка по значениям

Использование функции sorted()

Для сортировки по значениям 
my_dict = {'b': 2, 'a': 1, 'c': 3}

# Сортировка по значениям
sorted_dict_by_values = {key: value for key, value in sorted(my_dict.items(), key=lambda item: item[1])}
print(sorted_dict_by_values)  # Вывод: {'a': 1, 'b': 2, 'c': 3}



3. Сортировка с использованием lambda и key

Вы можете использовать  lambda для более сложных критериев сортировки:
  
my_dict = {'b': 2, 'a': 1, 'c': 3, 'd': 2}

# Сортировка по значениям, а затем по ключам
sorted_dict = {key: value for key, value in sorted(my_dict.items(), key=lambda item: (item[1], item[0]))}
print(sorted_dict)  # Вывод: {'a': 1, 'b': 2, 'd': 2, 'c': 3}

Задача для тренировки:

Сортируем словарь

Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация