Оглавление
Set (абстрактный тип данных)
-
Определение и свойства множеств
- Множество – это набор объектов, которые не имеют повторяющихся элементов.
- Множество может быть конечным или бесконечным, а также может быть пустым.
- Множество обладает свойствами мощности, мощности дополнения и пересечения.
-
Операции с множествами
- Множество может быть объединено с другим множеством, образуя новое множество.
- Множество может быть пересечено с другим множеством, образуя подмножество.
- Множество может быть разложено на подмножества, образуя декомпозицию множества.
- Множество может быть инвертировано, образуя антимножество.
-
Реализация множеств
- Множество может быть реализовано с использованием списков, хэш-таблиц или деревьев.
- Специализированные структуры данных, такие как union-find, могут оптимизировать операции с множествами.
-
Языковая поддержка множеств
- Многие языки, включая C++, Java и Python, поддерживают множества.
- Существуют специализированные структуры данных для множеств, такие как hash_set и unordered_set в C++.
-
Мультимножества
- Мультимножество – это обобщение множества, которое допускает повторяющиеся элементы.
- Мультимножества могут быть реализованы с использованием хэш-таблиц или деревьев.
-
Операции с мультимножествами
- Мультимножества поддерживают операции, аналогичные множествам, включая операции с подмножествами и объединение.
-
Мультинаборы в SQL
- В SQL таблица может быть представлена как множество или мультимножество в зависимости от ограничений уникальности.
- Ключевое слово MULTISET используется для преобразования подзапроса в выражение коллекции.