Как достигается уникальность коллекций, размещенных в куче в Swift

Что проверяют

Понимаете ли вы, как коллекции Swift совмещают семантику значений с хранением данных в куче. Речь о copy-on-write и проверке уникальности ссылки на буфер, а не о Set. Следом часто просят реализовать COW для своей структуры.

Как отвечать

Array, Dictionary, Set и String это структуры, но элементы лежат в буфере в куче, а структура хранит на него ссылку. При let b = a копируется только ссылка, счётчик ссылок буфера растёт, данные остаются общими.

Копия создаётся при первой мутации. Перед изменением коллекция проверяет, единственный ли она владелец буфера. Если да, меняет его на месте. Если нет, сначала копирует буфер и дальше работает со своей копией. Так две переменные ведут себя как независимые значения, хотя до первого изменения делят память.

Для своей структуры то же делается через isKnownUniquelyReferenced:

struct Matrix {
    private var storage: Storage // final class
    mutating func set(_ v: Double, at i: Int) {
        if !isKnownUniquelyReferenced(&storage) {
            storage = storage.copy()
        }
        storage.values[i] = v
    }
}

Функция принимает inout, поэтому вызывается из mutating-метода, и возвращает true, только если на объект есть ровно одна сильная ссылка.

Где спотыкаются

Думают, что копирование происходит при присваивании. Отсюда лишняя тревога о передаче массивов в функции и непонимание, откуда на самом деле берутся дорогие копии.

Создают вторую ссылку на буфер прямо перед изменением. Классика: var list = dict[key]!; list.append(x); dict[key] = list. В момент append буфер принадлежит и словарю, и list, поэтому копируется целиком, и в цикле это даёт квадратичную сложность. Менять надо на месте: dict[key, default: []].append(x).

Считают, что любая структура получает COW сама. Автоматически он есть только у коллекций стандартной библиотеки. Структура с полем-классом без ручной проверки делит изменяемое состояние между копиями, и правка в одной копии видна в другой.