Подразделы

Другие разделы

Дата и время

01/04/2025 16:51:05

Авторизация

Зарегистрироваться
Восстановить пароль

Линейные АТД

Список Массив и Строка Стек Очередь Двухсторонняя очередь Очередь с приоритетами Множество Словарь

Словарь

АТД Ассоциативный массив, словарь (map) обобщает АТД Массив, в котором в качестве индекса может выступать любое значение, и позволяет хранить пары вида (ключ, значение). Также можно рассматривать как АТД Множество, у которого только часть ключа используется для поиска.

Основные операции

Операция	Эффективность	Вызов
конструктор (пустой набор)	$O(1)$	`map<string,int> m;` `flat_map<string,int> m;` `unordered_map<string,int> m;`
количество элементов	$O(1)$	`size_t kol=m.size();`
получение итератора на первый элемент (конец набора)	$O(log N)$	`auto b=m.begin(), e=m.end();`
поиск элемента с указанным ключом	$O(log N)$	`auto it=m.find("a")` возвращается "конец набора", если не найден
добавление элемента	$O(log N)$	`m.insert({"a",5}), m["a"]=5;`
удаление элемента	$O(log N)$	`m.erase("a"); m.erase(it);`

АТД Итератор словаря

Операция	Эффективность	Вызов
cледующий (предыдущий)	$O(log N)$ в худшем случае $O(1)$ амортизированная	`++it; --it;`
конец набора	$O(1)$	`if(it==s.end())...`
ключ элемента	$O(1)$	`auto k=it->first`
значение элемента	$O(1)$	`auto v=it->second; it->second=v;`

Также есть варианты multimap, unordered_multimap и flat_multimap для повторяющихся ключей.

Варианты реализации ассоциативного массива: