Множества (Set)

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

Множество - это коллекция уникальных неупорядоченных однотипных данных.

Множество в Swift можно представить как мешок с разными игрушками, которые не повторяются. Если доставать игрушки по одной, то неизвестно какую именно игрушку можно достать в следующий раз.

Что из себя представляет множество?

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

let player: Set<String> = ["Bob", "Alice", "Daisy"]
 
print(player)

// Output
// ["Bob", "Daisy", "Alice"]

Нельзя изменить тип множества после того, как он был объявлен.

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

Все элементы множества должны быть единого типа данных.

Если в качестве значений элементов необходимо указать данные разных типов, тогда тип данных для элементов в множестве будет по типу “Any”.

Создание множества

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

Тип множества в Swift в полной форме пишется как Set<Element>, где Element - это тип данных множества.

При этом следует учитывать, что тип данных множества Element должен подчиняться протоколу Hashable.

Тип “Set” указывается явно. В противном случае - создаётся массив. Поэтому короткой формы объявления множества нету.

Декларирование множества:

var collectionSet: Set<String>

После объявления множества для дальнейшей работы необходимо инициализировать множество:

collectionSet = ["Adam"]

Общая форма объявления множества:

var collectionSetOne: Set<String> = ["Adam", "Ben"]
var collectionSetTwo: Set = ["Adam", "Ben"]

Или так (с литералами массива):

var collectionSet = Set<String>(arrayLiteral: "Adam", "Ben", "Ben")

Объявление пустого множества:

let collectionSet = Set<String>()
print(collectionSet)

// Output
// []

Еще один способ объявления пустого множества:

let collectionSet: Set<String> = []
print(collectionSet)

// Output
// []

Хеш значения для типа Set

Тип должен быть хешируемым для того, чтобы мог храниться в множестве, таким образом тип должен предоставлять возможность для вычисления собственного значения хеша. Тип значения хеша “Int” должен быть для всех объектов одинаковым, чтобы можно было провести сравнение, что если a == b, то и a.hashValue == b.hashValue.

Все базовые типы Swift (Int, String, Double, Float, Bool) являются хешируемыми типами по умолчанию и могут быть использованы в качестве типов значений множества или в качестве типов ключей словаря.

Можно использовать собственный тип в качестве типа значения множества или типа ключа словаря, подписав его под протокол “Hashable” из стандартной библиотеки Swift. Типы, которые подписаны под протокол “Hashable” должны обеспечивать “gettable” свойство “hashValue”. Значение, которое возвращает “hashValue” не обязательно должно иметь одно и то же значение при выполнении одной и той же программы или разных программ.

Так как протокол “Hashable” подписан под протокол “Equatable”, то подписанные под него типы так же должны предоставлять реализацию оператора равенства “==”. Протокол “Equatable” требует любую реализацию оператора равенства для реализации возможности сравнения. Таким образом, реализация оператора “==” должна удовлетворять следующим трем условиям, для всех трех значений a, b, c.

• a == a (Рефлексивность)
• a == b, значит b == a (Симметрия)
• b == a && b == c, значит a == c (Транзитивность)

Работа с множеством

Объявляем множество:

let fruit: Set = ["apple", "banana", "strawberry", "jackfruit"]
print(fruit)

// Output
// ["banana", "apple", "jackfruit", "strawberry"]

Добавление элемента в множество с помощью метода insert():

fruit.insert("pineapple")

Удаление элемента из множества с помощью метода remove():

fruit.remove("banana")

Метод remove(_:) удаляет элемент, который является членом множества и возвращает удаленное значение или nil, если удаляемого элемента нет. Так же все объекты множества могут быть удалены единовременно при помощи метода removeAll().

Предметы в множестве должны быть уникальными. Вы не можете добавить одинаковые элементы в одно множество:

var fruit: Set = ["apple", "banana", "orange"]

print(fruit)

// Output
// ["banana", "orange", "apple"]

let result = fruit.insert("orange")

print(result)

// Output
// (inserted: false, memberAfterInsert: "orange")

Так же, как массивы и словари, множества имеют ряд полезных функций:

• isEmpty — возвращает true, когда в множестве нет элементов;
• count — возвращает количество элементов в множестве;
• contains() - позволяет проверить наличие в множестве элемента;
• first — возвращает первый элемент в множестве;
• randomElement() — возвращает случайный элемент из множества;
• sorted() - сортировка множества.

Количество элементов в множестве:

print(fruit.count)

// Output
// 3

Проверка на пустое множество:

if fruit.isEmpty {
	print("set is empty")
} else {
	print("set is no empty")
}

Проверка на наличие элемента в множестве:

var isPresent = fruit.contains("apple") // isPresent = true

Отсортировать множество:

print(fruit.sorted()) // ["apple", "banana", "orange"]

Итерация по множеству

Можно совершать итерации по множеству при помощи цикла for-in:

for element in fruit {
    print("\(element)")
}

// Output
// banana
// apple
// orange

Множества в Swift не имеют определенного порядка. Для того, чтобы провести итерацию по множеству в определенном порядке, нужно использовать метод sorted(), который возвращает элементы коллекции в виде отсортированного массива, по умолчанию используя оператор <.

for element in fruit.sorted() {
    print("\(element)")
}

// Output
// apple
// banana
// orange

Отличия множеств от массивов и словарей

Множества похожи на массивы и словари, но на самом деле они разные.

• Массив связывает числовые индексы (0…n) со значениями. Массивы имеют фиксированный порядок;
• Словарь связывает ключи со значениями.

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

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

Например, с помощью функции мы проверяем, существует ли данная строка в множестве:

let movies: Set = ["Рокки", "Матрица", "Властелин Колец"]
 
if movies.contains("Рокки") {
    print("Рокки - мой любимый фильм!")
}

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

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

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

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

• union — сочетание множеств (объединение);
• subtraction — вычитание множеств;
• intersection — множество элементов, которые присутствуют в обоих множествах;
• symmetric difference — множество элементов, которые присутствуют в одном или другом множестве, но не в обоих.

Сравним ингредиенты в различных сортах кофе:

let cappuccino: Set = ["espresso", "milk", "milk foam"]
let americano: Set = ["espresso", "water"]
let machiato: Set = ["espresso", "milk foam"]
let latte: Set = ["espresso", "milk"]

Union

Используем union для machiato и latte:

let result = machiato.union(latte)
print(result)

// Output
// ["espresso", "milk foam", "milk"]

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

Subtraction

Применим subtraction для вычитания americano из cappuccino:

let result = cappuccino.subtracting(americano)
print(result)

// Output
// ["milk foam", "milk"]

Неважно, что там в cappuccino нет water, потому что все равно нельзя вычесть то, чего нет.

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

Важно! a — b — это не то же самое, что b — a:

let result = americano.subtracting(cappuccino)
print(result)

// Output
// ["water"]

Intersection

Применим intersection для latte и cappuccino:

let result = latte.intersection(cappuccino)
print(result)

// Output
// ["espresso", "milk"]

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

Можно найти, что есть общего между всеми видами кофе:

let result = latte.intersection(cappuccino).intersection(machiato).intersection(americano)
print(result)

// Output
// ["espresso"]

Symmetric difference

Какая разница между americano и latte?

let result = latte.symmetricDifference(americano)
print(result)

// Output
// ["milk", "water"]

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

Логическое сравнение множеств

Взаимосвязь между множествами

Если одно множество содержит в себе все элементы второго множества, то тогда первое множество по отношению ко второму будет надмножеством; второе множество, по отношению к первому - подмножеством.

Два множества называются разделенными в случае, если у них нет общих элементов.

Проверка взаимосвязи множеств

Чтоб проверить, все ли значения двух множеств одинаковы - следует использовать оператор равенства (==).

Для определения все ли значения множества содержатся в указанном множестве - следует использовать метод isSubset(of:).

Для того, чтоб определить содержит ли множество все значения указанного множества - следует использовать метод isSuperset(of:).

Для определения является ли множество подмножеством или надмножеством, но не равным указанному сету - следует использовать методы isStrictSubset(of:) или isStrictSuperset(of:) соответственно.

Для определения того, отсутствуют ли общие значения в двух множествах или нет - следует использовать метод isDisjoint(with:).

Пример:

let houseAnimals: Set = ["собака", "кошка"]
let farmAnimals: Set = ["корова", "курица", "баран", "собака", "кошка"]
let cityAnimals: Set = ["ворона", "мышь"]
 
houseAnimals.isSubset(of: farmAnimals)
// true
farmAnimals.isSuperset(of: houseAnimals)
// true
farmAnimals.isDisjoint(with: cityAnimals)
// true

Использование множеств с пользовательскими объектами

Что, если мы хотим сохранить список любимых фильмов с нужными нам свойствами? Для этого мы можем создать свой собственный тип данных:

struct Movie {
    var name: String
    var year: Int
    var rating: Int
}

Добавим также инициализаторы:

init(name: String, year: Int, rating: Int) {
    self.name = name
    self.year = year
    self.rating = rating
}
 
init(withName name: String) {
    self.name = name
    self.year = 0
    self.rating = 0
}

Первая функция init() создает объект типа Movie с 3 свойствами: name, year и rating. Этот инициализатор обычно создается по умолчанию, если только вы не добавляете свои собственные инициализаторы.

Второй инициализатор init(withName:) создан для нашего удобства. Свойства year и rating установлены в 0.

Прежде чем мы сможем использовать структуру Movie в множестве, структура должна соответствовать протоколу Hashable. Для этого нам нужно будет сделать 3 дополнения к нашему коду.

Во-первых, добавим протокол Hashable:

struct Movie: Hashable {
    ...

Во-вторых, нужно добавить следующую функцию в структуру Movie:

static func == (lhs: Movie, rhs: Movie) -> Bool {
    return lhs.name == rhs.name
}

Вот что она делает:

• Данная функция является частью протокола Hashable, который используется для сравнения двух объектов Movie, чтобы определить, равны ли они;
• Если они равны, функция возвращает true. Если это не так, функция возвращает false;
• Два Movie объекта, которые мы сравниваем, называются lhs и rhs, которые обозначают левую и правую стороны нашего сравнения;
• Определяем равенство, сравнивая свойства name двух Movie-объектов. То есть мы сравниваем названия фильмов. Если имена совпадают, объекты совпадают.

В-третьих, нужно реализовать hash(into:) функцию. Эта функция также является частью протокола Hashable:

func hash(into hasher: inout Hasher) {
    hasher.combine(name)
}

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

Далее используется название фильма для hasher, используя функцию combine(_:). Важно, чтобы функции использовали одинаковые свойства.

На данный момент объект Movie имеет свойство с именем hashValue. Можно проверить, что два Movie-объекта совпадают:

let a = Movie(name: "Рокки", year: 1976, rating: 5)
let b = Movie(withName: "Рокки")
 
print(a == b)

// Output
// true
 
print(a.hashValue)

// Output
// something like "5474910254413230307"

Создадим множество фильмов:

let movies: Set = [
    Movie(name: "Рокки", year: 1976, rating: 5),
    Movie(name: "Матрица", year: 1999, rating: 10),
    Movie(name: "Властелин Колец", year: 2001, rating: 8),
    Movie(name: "Невероятная жизнь Уолтера Митти", year: 2013, rating: 7),
    Movie(name: "Дедпул", year: 2016, rating: 3)
]

Теперь мы можем узнать, является ли выбранный фильм любимым:

if movies.contains(Movie(withName: "Рокки")) {
    print("Рокки - мой любимый фильм!")
}

В приведенном выше коде мы создаем новый объект Movie с инициализатором Movie(withName:). Так как мы реализовали протокол Hashable, мы можем использовать Movie объекты для проверки наличия данного элемента в множестве. Приведенный выше код проверяет, существует ли Rocky в множестве movies. Это операция типа O(1).

Также мы можем найти любимый фильм по рейтингу:

if let movie = movies.sorted(by: { $0.rating > $1.rating }).first {
    print("Мой любимый фильм - \(movie.name)")
}

Приведенный выше код использует функцию sorted(by:) для сортировки movies по своему свойству rating (от высшего к низшему). В результате sorted(by:) возвращает массив, отсортированный по самому высокому рейтингу, в котором мы получаем первый элемент массива с помощью свойства first.

Мы можем найти рейтинг конкретного фильма:

if let index = movies.firstIndex(of: Movie(withName: "Властелин Колец")) {
    let lotr = movies[index]
    print("Я оценил фильм = \(lotr.rating)")
}

В приведенном выше коде мы получаем индекс фильма с помощью функции firstIndex(of:). Как и в случае с фильмом, используем его индекс (хеш-значение).

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

Мы можем выбрать фильм с рейтингом 8 и выше:

let top = movies.filter({ $0.rating >= 8 })
 
for movie in top {
    print(movie.name)
}

Данный пример выведет в консоль список из названий фильмов с рейтингом 8 и больше.

Еще полезные ссылки

• Массивы
• Словари
• Диапазоны
• Операции с коллекциями
• Функции высшего порядка

Также информацию по множествам можно получить на странице официальной документации (Узнать больше про методы и свойства множеств).

Ссылки на официальную документацию:

• Apple Developer Documentation - Set