Начало
Учебные материалы
Линейные АТД
Множество
Основные операции
Операция|Эффективность|Вызов
--|--|--
конструктор (пустое множество) | `O(1)`| ``set<int> s;``\
``unordered_set<int> s;``\
``flat_set<int> s;``
количество элементов | `O(1)`| ``size_t n=s.size();``
получение итератора на первый элемент (конец набора) | `O(1)`| ``auto b=s.begin(), e=s.end();``
поиск элемента |`O(log N)`\
меньше для ``unordered_set``| ``if(s.contains(5)) ...``\
``auto it=s.find(5)``\
возвращается "конец набора", если не найден
добавление элемента |`O(log N)` для ``set``\
`O(N)` для ``flat_set``| ``auto it=s.insert(5);``\
возвращается пара (итератор на добавленный элемент, true)\
или (итератор на существующий элемент, false)
удаление элемента |`O(log N)` для ``set``\
`O(N)` для ``flat_set``| ``int k=s.erase(5);`` возвращается количество удаленных элементов\
``auto ne=s.erase(it);`` возвращается итератор на следующий элемент
Операции над двумя множествами (для ``set`` и ``flat_set``)
Операция|Эффективность|Вызов
--|--|--
Пересечение |`O(N log N)`| ``set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), std::inserter(s3, s3.begin()))``
Объединение |`O(N log N)`| ``set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), std::inserter(s, s.begin()))``
Разность |`O(N log N)`| ``set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), std::inserter(s3, s3.begin()))``
Подмножество |`O(N log N)`| ``bool r=includes(s1.begin(), s1.end(), s2.begin(), s2.end())``
--
Варианты реализации множества:
* неупорядоченный список (``vector, list`` -- быстрое добавление)
* упорядоченный список (``flat_set``)
* сбалансированное дерево поиска (``set`` -- красно-черное дерево)
* декартово дерево
* битовый массив (``bitset`` -- для ограниченного диапазона целых чисел)
* хэш-таблицы (``unordered_set``)
--
АТД Мультимножество представлением математического мультимножества, в котором элементы могут повторяться.
Основные операции
Операция|Эффективность|Вызов
--|--|--
конструктор (пустое множество) | `O(1)`| ``multiset<int> s;``\
``unordered_multiset<int> s;``\
``flat_multiset<int> s;``
количество элементов | `O(1)`| ``int n=s.size();``
получение итератора на первый элемент (конец набора) | `O(1)`| ``auto b=s.begin(), e=s.end();``
поиск элемента |`O(log N)`\
меньше для ``unordered_multiset``| ``if(s.contains(5)) ...``\
``auto it=s.find(5)``\
возвращается "конец набора", если не найден
добавление элемента |`O(log N)` для ``multiset``\
`O(N)` для ``flat_multiset``| ``auto it=s.insert(5);``\
возвращается итератор на добавленный элемент
удаление всех элементов с заданным ключом,\
одного элемента по итератору |`O(log N+k)`\
`O(N)` для ``flat_multiset``| ``int k=s.erase(5);`` возвращается количество удаленных элементов\
``auto ne=s.erase(it);`` возвращается итератор на следующий элемент
количество элементов, равных значению |`O(k)`| ``int k=s.count(5);``
