1. Set в Swift

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

В Swift Set (множество) — это неупорядоченная коллекция уникальных значений одного типа. В отличие от массивов, где элементы могут повторяться и имеют определенный порядок, Set гарантирует, что каждый элемент присутствует только один раз, и не обеспечивает определенного порядка хранения.

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

Синтаксис¶

Создание Set¶

Создание пустого Set с явным указанием типа¶

var emptySet = Set<Int>()

Создание пустого Set с использованием литерала массива¶

var anotherEmptySet: Set<String> = []

Важно: Если вы используете литерал массива для создания Set и не указываете тип явно, Swift будет считать эту коллекцию массивом. Поэтому для создания Set необходимо либо явно указать тип Set, либо использовать тип Set в объявлении переменной.

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

Добавление элементов¶

insert(_:)¶

Добавляет новый элемент в множество. Если элемент уже существует, он не будет добавлен повторно.

var colors: Set = ["Red", "Green"]
colors.insert("Blue")
print(colors) // ["Red", "Green", "Blue"]

Удаление элементов¶

remove(_:)¶

Удаляет указанный элемент из множества. Возвращает удаленный элемент, если он существовал, или nil в противном случае.

if let removedColor = colors.remove("Green") {
    print("\(removedColor) был удален")
}
print(colors) // ["Red", "Blue"]

removeAll()¶

Удаляет все элементы из множества.

colors.removeAll()
print(colors) // Пустое множество

Проверка на наличие элемента/элементов¶

contains(_:)¶

let cities: Set = ["Moscow", "London", "New York"]
if cities.contains("London") {
    print("London есть в множестве городов")
}

count¶

Свойство, возвращающее количество элементов в множестве.

print("Количество городов: \(cities.count)") // Количество городов: 3

isEmpty¶

Свойство, возвращающее true, если множество пусто.

let emptySet = Set<Int>()
if emptySet.isEmpty {
    print("Множество пусто")
}

Итерация по элементам Set¶

Поскольку Set соответствует протоколу Sequence, вы можете использовать цикл for-in для перебора элементов.

for city in cities {
    print(city)
}

Порядок элементов при итерации по множеству не гарантируется.

Сортировка элементов¶

Чтобы получить отсортированный список элементов из множества, используйте метод sorted(), который возвращает массив отсортированных элементов.

let numbers: Set = [3, 1, 2]
let sortedNumbers = numbers.sorted()
print(sortedNumbers) // [1, 2, 3]

Операции над множествами¶

Объединение (Union)¶

union(_:)¶

Возвращает новое множество, содержащее все уникальные элементы обоих множеств.

let setA: Set = [1, 2, 3]
let setB: Set = [3, 4, 5]
let unionSet = setA.union(setB)
print(unionSet) // [1, 2, 3, 4, 5]

formUnion(_:)¶

Модифицирует текущее множество, добавляя в него элементы из другого множества.

var setC: Set = [1, 2]
setC.formUnion([2, 3, 4])
print(setC) // [1, 2, 3, 4]

Пересечение (Intersection)¶

intersection(_:)¶

Возвращает новое множество, содержащее общие элементы обоих множеств.

let intersectionSet = setA.intersection(setB)
print(intersectionSet) // [3]

formIntersection(_:)¶

Модифицирует текущее множество, оставляя в нем только общие элементы с другим множеством.

var setD: Set = [1, 2, 3]
setD.formIntersection([2, 3, 4])
print(setD) // [2, 3]

Разность (Subtracting)¶

subtracting(_:)¶

Возвращает новое множество, содержащее элементы текущего множества, которые не содержатся в указанном множестве.

let subtractingSet = setA.subtracting(setB)
print(subtractingSet) // [1, 2]

subtract(_:)¶

Модифицирует текущее множество, удаляя из него элементы другого множества.

var setE: Set = [1, 2, 3, 4]
setE.subtract([3, 4])
print(setE) // [1, 2]

Симметрическая разность (Symmetric Difference)¶

symmetricDifference(_:)¶

Возвращает новое множество, содержащее элементы, которые есть в одном из множеств, но не в обоих.

let symmetricSet = setA.symmetricDifference(setB)
print(symmetricSet) // [1, 2, 4, 5]

formSymmetricDifference(_:)¶

Модифицирует текущее множество, заменяя его симметрической разностью с другим множеством.

var setF: Set = [1, 2, 3]
setF.formSymmetricDifference([3, 4, 5])
print(setF) // [1, 2, 4, 5]

Сравнение множеств¶

Проверка на подмножество и надмножество¶

isSubset(of:)¶

Проверяет, является ли текущее множество подмножеством другого множества.

let smallSet: Set = [1, 2]
let largeSet: Set = [1, 2, 3, 4]
print(smallSet.isSubset(of: largeSet)) // true

isSuperset(of:)¶

Проверяет, является ли текущее множество надмножеством другого множества.

print(largeSet.isSuperset(of: smallSet)) // true

isStrictSubset(of:) и isStrictSuperset(of:)¶

Проверяют строгие отношения подмножества и надмножества (исключая равенство множеств).

Проверка на пересечение и равенство¶

isDisjoint(with:)¶

Проверяет, не имеют ли множества общих элементов.

let setG: Set = [1, 2]
let setH: Set = [3, 4]
print(setG.isDisjoint(with: setH)) // true

Либо, можно использовать классическое: ==

Преобразование между Set и Array¶

Из Set в Array

let numberSet: Set = [1, 2, 3]
let numberArray = Array(numberSet)
print(numberArray) // Может быть [2, 3, 1] — порядок не гарантируется

Из Array в Set

let numberArray = [1, 2, 2, 3, 3, 3]
let numberSet = Set(numberArray)
print(numberSet) // [1, 2, 3]

Алгоритмическая сложность основных операций¶

Добавление элементов¶

insert(_:)¶

Амортизированная O(1)

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

Удаление элементов¶

remove(_:)¶

Амортизированная O(1)

Удаление всех элементов требует обхода всей структуры данных и освобождения памяти, поэтому сложность линейна по количеству элементов n.

Проверка на наличие элемента/элементов¶

contains(_:)¶

O(1)

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

count¶

O(1)

Свойство count хранится и обновляется при каждой операции добавления или удаления элемента, поэтому доступ к нему выполняется за константное время.

isEmpty¶

O(1)

Проверка на пустоту — это простая проверка значения свойства count, что выполняется за константное время.

Итерация по элементам¶

Перебор элементов с помощью цикла for-in¶

O(n)

Для перебора всех элементов множества необходимо пройти по каждому из n элементов, что требует линейного времени.

Сортировка элементов¶

sorted()¶

O(n log n)

Метод sorted() возвращает отсортированный массив элементов множества. Сортировка требует времени O(n log n), где n — количество элементов в множестве.

Операции над множествами¶

union(_:)¶

O(n + m)

Возвращает новое множество, содержащее все уникальные элементы из двух множеств. Необходимо пройти по каждому элементу обоих множеств (размеры n и m) и добавить их в новое множество, что требует O(n + m) времени.

formUnion(_:)¶

O(m)

Модифицирует текущее множество, добавляя в него элементы из другого множества размером m. Каждая вставка выполняется за амортизированное O(1), итого O(m).

Пересечение (Intersection)¶

intersection(_:)¶

O(n)

Возвращает новое множество с общими элементами. Необходимо пройти по каждому элементу текущего множества (размер n) и проверить, содержится ли он в другом множестве (проверка за O(1)). Итого O(n).

formIntersection(_:)¶

O(n)

Модифицирует текущее множество, оставляя только общие элементы. Аналогично предыдущему, требуется пройти по всем элементам текущего множества.

Разность (Subtracting)¶

subtracting(_:)¶

O(n)

Возвращает новое множество с элементами, которые есть в текущем множестве, но отсутствуют в другом. Проход по каждому элементу текущего множества с проверкой наличия в другом множестве за O(1). Итого O(n).

subtract(_:)¶

O(m)

Модифицирует текущее множество, удаляя из него элементы другого множества размера m. Для каждого элемента из другого множества выполняется удаление за O(1), итого O(m).

Симметрическая разность (Symmetric Difference)¶

symmetricDifference(_:)¶

O(n + m)

Возвращает новое множество с элементами, которые присутствуют в одном из множеств, но не в обоих. Требуется пройти по элементам обоих множеств и выполнить операции вставки и удаления, итого O(n + m).

Сравнение множеств¶

Проверка на подмножество и надмножество¶

isSubset(of:)¶

O(n)

Проверяет, являются ли все элементы текущего множества (размер n) элементами другого множества. Проходит по каждому элементу текущего множества и проверяет наличие в другом множестве за O(1), итого O(n).

isSuperset(of:)¶

O(m)

Проверяет, содержит ли текущее множество все элементы другого множества размера m. Проходит по каждому элементу другого множества и проверяет наличие в текущем множестве за O(1), итого O(m).

isStrictSubset(of:), isStrictSuperset(of:)¶

O(n) или O(m)

Аналогично предыдущим методам с дополнительной проверкой на неравенство размеров множеств.

Проверка на пересечение и равенство¶

isDisjoint(with:) или ==¶

O(n)

Проверяет, не имеют ли множества общих элементов. Проходит по каждому элементу текущего множества и проверяет наличие в другом множестве за O(1), останавливается при нахождении общего элемента. В худшем случае — O(n).

Итоговая таблица¶

Операция	Метод	Сложность	Объяснение
Добавление элемента	`insert(_:)`	Амортизированная O(1)	Добавление элемента в `Set` реализовано через хеш-таблицу. В среднем операция выполняется за O(1), хотя в редких случаях может потребоваться больше времени из-за рехеширования.
Удаление элемента	`remove(_:)`	Амортизированная O(1)	Удаление элемента также использует хеш-таблицу для быстрого доступа. Амортизированная сложность составляет O(1), с учетом возможного рехеширования.
Удаление всех элементов	`removeAll()`	O(n)	Требуется пройти по всей структуре данных для освобождения памяти и удаления элементов, поэтому сложность линейна от количества элементов n.
Проверка наличия элемента	`contains(_:)`	O(1)	Используя хеш-таблицу, проверка наличия элемента выполняется за константное время, обращаясь напрямую по хешу.
Получение количества элементов	`count`	O(1)	Свойство `count` хранится и обновляется при каждой модификации множества, поэтому доступ к нему занимает константное время.
Проверка на пустоту	`isEmpty`	O(1)	Проверка выполняется через сравнение свойства `count` с нулем, что занимает константное время.
Итерация по элементам	Цикл `for-in`	O(n)	Необходимо пройти по каждому из n элементов множества, что требует линейного времени. Порядок элементов не гарантируется.
Сортировка элементов	`sorted()`	O(n log n)	Сортировка требует сравнения элементов и организации их в порядке, что занимает O(n log n) времени. Возвращает отсортированный массив.
Объединение множеств	`union(_:)`	O(n + m)	Создает новое множество, проходя по элементам обоих множеств размером n и m соответственно. Каждая вставка в новое множество занимает O(1).
Модификация при объединении	`formUnion(_:)`	O(m)	Добавляет элементы из другого множества размера m в текущее множество. Каждая операция вставки выполняется за O(1).
Пересечение множеств	`intersection(_:)`	O(n)	Проходит по элементам текущего множества размера n и проверяет наличие каждого в другом множестве за O(1).
Модификация при пересечении	`formIntersection(_:)`	O(n)	Удаляет из текущего множества элементы, отсутствующие в другом. Проход по n элементам с проверкой за O(1).
Разность множеств	`subtracting(_:)`	O(n)	Проходит по элементам текущего множества и исключает те, что присутствуют в другом множестве. Проверка присутствия за O(1).
Модификация при разности	`subtract(_:)`	O(m)	Удаляет из текущего множества элементы другого множества размера m. Каждое удаление выполняется за O(1).
Симметрическая разность	`symmetricDifference(_:)`	O(n + m)	Создает новое множество, включая элементы, присутствующие только в одном из множеств. Требуется пройти по обоим множествам.
Модификация при симметрической разности	`formSymmetricDifference(_:)`	O(m)	Для каждого элемента из другого множества размера m проверяется присутствие и выполняется добавление или удаление за O(1).
Проверка на подмножество	`isSubset(of:)`	O(n)	Проходит по каждому элементу текущего множества размера n и проверяет его наличие в другом множестве за O(1).
Проверка на надмножество	`isSuperset(of:)`	O(m)	Проверяет, содержатся ли все элементы другого множества размера m в текущем. Проход по m элементам с проверкой за O(1).
Проверка на пересечение	`isDisjoint(with:)`	O(n)	Проходит по элементам текущего множества и проверяет отсутствие каждого в другом множестве. Останавливается при первом совпадении.

Примечания:

n — размер текущего множества.
m — размер другого множества или коллекции.
Амортизированная сложность учитывает среднее время выполнения операций, сглаживая редкие случаи увеличения времени выполнения (например, при рехешировании).
Операции с пользовательскими типами: Элементы должны соответствовать протоколу Hashable. Операции хеширования и сравнения должны выполняться за O(1) для сохранения общей сложности операций с множеством.