АТД Ассоциативный массив, словарь (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`` для повторяющихся ключей.
--
Варианты реализации ассоциативного массива:
* неупорядоченный список пар (``vector, list``)
* упорядоченный список пар (``flat_map``)
* сбалансированное дерево поиска (``map`` - красно-черное дерево)
* декартово дерево
* хэш-таблицы (``unordered_map``)
Линейные АТД
Начало
Учебные материалы