Подразделы

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

01/04/2025 16:01:38

АТД Множество является представлением математического множества, то есть набора элементов, в котором порядок элементов не важен.

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

Операция	Эффективность	Вызов
конструктор (пустое множество)	$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())`

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

АТД Мультимножество представлением математического мультимножества, в котором элементы могут повторяться.

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

Операция	Эффективность	Вызов
конструктор (пустое множество)	$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);`