2.2. Множество

Автор: Мария Горденко

В этой статье вы познакомитесь с множествами — структурами данных, в которых каждый элемент встречается не более одного раза. Вы узнаете, как устроены множества в Python и C++, какие бывают разновидности множеств и как различается поведение упорядоченных и неупорядоченных коллекций. Научитесь выполнять базовые операции — добавление, удаление, проверку наличия, объединение и пересечение.

Ключевые вопросы статьи

• Чем множество отличается от списка и в каких случаях его удобнее использовать?
• Как реализованы множества в разных языках — упорядоченные и неупорядоченные?
• Какие операции над множествами поддерживаются и в чём их сложность?

Определение множества (set)Определение множества (set)

Следующей структурой данных, которую мы рассмотрим, будет множество (set). Множество представляет собой контейнер, содержащий неповторяющиеся элементы в произвольном порядке.

Далее в данной статье мы будем разграничивать упорядоченные и неупорядоченные множества.

Кроме того, существует такое понятие, как мультимножество (multiset), которое может включать в себя несколько одинаковых элементов.

Вы можете посмотреть на различия между множеством и мультимножеством на рисунке ниже.

Внутренняя реализация множества осуществляется различными способами, включая использование хэш-таблицы, бинарного дерева поиска и других алгоритмов. В данной статье мы сосредоточимся на функциях, которые можно производить со множеством, а не на внутренней его реализации.

Основные операции со множеством:

• Добавление элемента в множество.
• Удаление элемента из множества.
• Проверка наличия элемента в множестве.
• Объединение двух множеств.
• Пересечение двух множеств.
• Разность двух множеств.

Рассмотрим основные операции со множеством на примере двух языков С++ и 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}. Для данных множеств найдите объединение, пересечение и разность.

Что дальшеЧто дальше

Теперь вы умеете работать с множествами: добавлять и удалять элементы, проверять их наличие, объединять и находить пересечение. Вы узнали, что множества полезны, когда важна уникальность, а не порядок, и что разные реализации дают разную эффективность.

Далее — структура, где каждому ключу сопоставлено значение. Вы познакомитесь со словарями, научитесь использовать ассоциативные массивы и узнаете, в чём их сила.

Ключевые выводы статьи

• Множество — это структура, содержащая только уникальные элементы.
• В Python используется неупорядоченное множество, а в C++ — упорядоченное.
• Основные операции: добавление, удаление, проверка наличия, объединение и пересечение.
• Эффективность зависит от реализации: хеш-таблицы обеспечивают быстрые операции, но не сохраняют порядок.