Множества

Представьте коллекцию наклеек с номерами. Вы складываете их в мешок и следите за одним правилом: каждая наклейка лежит в мешке один раз. Попалась вторая такая же — в мешок её не кладут. Порядка в мешке нет: сверху может оказаться любая.

Такая коллекция в Swift называется множеством: она хранит значения без повторов и без порядка. Значения множества перечисляют в квадратных скобках, как у массива, а тип указывают аннотацией : Set:

var album: Set = [3, 7, 12]
album.insert(7)
album.insert(15)
print(album.count) // 4
print(album.contains(12)) // true
print(album.contains(5)) // false

Давайте разберём программу по строкам:

1. var album: Set = [3, 7, 12] создаёт множество из трёх наклеек. Swift сам выводит тип элементов, и полный тип album — Set<Int>, то есть множество целых чисел.
2. album.insert(7) ничего не меняет: наклейка 7 уже есть. Ошибки при этом нет.
3. album.insert(15) добавляет новую наклейку.
4. print(album.count) печатает 4: в мешке наклейки 3, 7, 12 и 15.
5. contains проверяет, есть ли значение во множестве: 12 есть, а 5 нет.

Здесь картинка с мешком неточна. В настоящий мешок вторую такую же наклейку положить можно, и следить за повторами пришлось бы вам. Множество следит само: повтор оно молча пропускает.

Пустое множество создают с полным типом: var seen: Set<String> = [] или Set<String>().

Убрать повторы из массива

Множество часто строят из массива, чтобы убрать повторы. Set(pack) берёт элементы массива pack и оставляет каждое значение по одному разу:

let pack = [5, 3, 5, 9, 3]
let unique = Set(pack)
print(pack.count, unique.count) // 5 3

В пачке пять наклеек, но разных среди них только три: 5, 3 и 9. Сам массив pack при этом не меняется: множество получает свою копию значений.

Порядка у множества нет, поэтому для печати по порядку его сортируют. unique.sorted() возвращает массив [3, 5, 9].

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

Анна и Борис собирают одну серию наклеек и сравнивают свои альбомы. Для этого у множеств есть три операции, и каждая возвращает новое множество:

let anna: Set = [1, 2, 5, 8]
let boris: Set = [2, 3, 5]
print(anna.union(boris).sorted()) // [1, 2, 3, 5, 8]
print(anna.intersection(boris).sorted()) // [2, 5]
print(anna.subtracting(boris).sorted()) // [1, 8]

union

anna.union(boris) — объединение: все наклейки, которые есть хотя бы у одного из двоих. Общие 2 и 5 попадают в него по одному разу.

intersection

anna.intersection(boris) — пересечение: наклейки, которые есть у обоих. Здесь это 2 и 5.

subtracting

anna.subtracting(boris) — разность: наклейки Анны, которых нет у Бориса. Здесь это 1 и 8, их Анна может предложить ему в обмен. Порядок в этой операции важен: boris.subtracting(anna) даёт только 3.

Почему множество ищет быстро

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

Поэтому элементы множества и ключи словаря должны быть Hashable: такой тип умеет превращать значение в число, по которому вычисляется место. Знакомые вам Int, Double, String, Character и Bool подходят.

На собеседовании часто спрашивают, чем Set отличается от Array. Хороший ответ называет три отличия:

• массив хранит порядок и повторы, а множество — ни то ни другое;
• contains у массива проверяет элементы по очереди, а множество сразу смотрит в нужное место;
• элементы множества должны быть Hashable.

Частая ошибка

Множество объявили без аннотации : Set:

var stickers = [3, 7, 12]
stickers.insert(15) // ✗

error: missing argument for parameter 'at' in call

Без : Set квадратные скобки создают массив [Int]. У массива тоже есть insert, но ему нужно место вставки: insert(15, at: 0). Компилятор не знает, что задумано множество, и просит недостающее место. Исправление — var stickers: Set = [3, 7, 12].

Главное

• Множество Set хранит значения без повторов и без порядка; квадратным скобкам нужна аннотация : Set, иначе получится массив.
• insert пропускает повтор, contains проверяет значение, а Set(array) собирает значения массива без повторов.
• union, intersection и subtracting возвращают новое множество: всё вместе, общее и разницу.
• Элементы множества, как и ключи словаря, должны быть Hashable, поэтому contains у множества не перебирает элементы по очереди.