Следующей структурой данных, которую мы рассмотрим, будет множество (). Множество представляет собой контейнер, содержащий неповторяющиеся элементы в произвольном порядке. Обратите внимание, в стандартной библиотеке С++ реализовано упорядоченное множество, что накладывает свои особенности на вычислительную сложность некоторых операций. Далее в данном параграфе мы будем разграничивать упорядоченные и неупорядоченные множества.
Кроме того, существует такое понятие, как мультимножество (), которое может включать в себя несколько одинаковых элементов.
Вы можете посмотреть на различия между множеством и мультимножеством на рисунке ниже.
Внутренняя реализация множества осуществляется различными способами, включая использование хэш-таблицы, бинарного дерева поиска и других алгоритмов. В данном параграфе мы сосредоточимся на функциях, которые можно производить со множеством, а не на внутренней его реализации.
Основные операции со множеством:
- Добавление элемента в множество.
- Удаление элемента из множества.
- Проверка наличия элемента в множестве.
- Объединение двух множеств.
- Пересечение двух множеств.
- Разность двух множеств.
Рассмотрим основные операции со множеством на примере двух языков С++ и Python. В STL языка С++ реализовано упорядоченное множество, в то время как в Python — неупорядоченное множество.
Добавление элемента в множество можно произвести следующим образом.
my_set = {1, 2, 3}
my_set.add(2)
print(my_set)
my_set.add(4)
print(my_set)
В результате исполнения фрагмента кода выше на экран будет выведено две строки: 1 2 3 и 1 2 3 4. Сложность операции добавления элемента во множество в Python — , так как множество не упорядочено и не нужно искать позиции для его вставки.
В языке С++ добавление элемента может быть осуществлено следующим образом (не забудьте добавить #include<set> в начало вашего кода).
set<int> val = {6, 10, 5, 1};
val.insert(6);
val.insert(10);
val.insert(2);
cout << val.size();
В итоге на экран будет выведено 5. В случае реализации на С++ мы имеем дело с упорядоченным множеством, что накладывает дополнительные временные издержки. Асимптотическая сложность добавления элемента – .
Не менее важной операцией является операция удаления элемента из множества.
set<int> val = {6, 10, 5, 1};
val.erase(6)
cout << val.size();
Благодаря фрагменту кода выше произошло удаление элемента, поэтому на экране появится число 3. Сложность операции удаления в упорядоченном множестве — .
Рассмотрим удаление элемента из множества в Python:
my_set = {1, 2, 3}
my_set.remove(1);
print(len(my_set))
Размер множества после удаления элемента становится равным двум. Сложность операции удаления в неупорядоченном множестве — .
Проверка наличия элемента в множестве предполагает просмотр элементов в нём. В случае неупорядоченного множества, реализованного на хэш-таблицах, сложность — О(1). Однако, при использовании упорядоченного множества сложность становится O(logn).
Объединение множеств предполагает их слияние в единое множество. Например, пусть было два множества. Первое содержало элементы 1, 2 и 3, а второе 2, 3 и 4. В результате объединения получится множество, содержащее четыре элемента 1, 2, 3 и 4.
Пересечение множеств представляет из себя поиск в двух множествах одинаковых элементов. Пусть первое множество содержит элементы 1, 2 и 3, а второе — 2, 3 и 4. Тогда пересечением множеств будут являться элементы 2 и 3.
Разность двух множеств предполагает нахождение всех элементов из первого множества, за исключением тех, которые находятся во втором множестве. Пусть первое множество содержит элементы 1, 2 и 3, а второе — 2, 3 и 4. Тогда разностью множеств будет элемент 1.
💡 Упражнение:
Поработайте с двумя множествами А = {1, 3, 4, 5, 6}, B = {1, 2, 4, 6, 8, 9}. Для данных множеств найдите объединение, пересечение и разность.