Сollection Framework и структуры данных в ООП

Junior

Суть

Коллекции — абстракции для хранения групп значений: массив, множество, словарь. В ООП-языках вроде Java это иерархия классов (Collection Framework). В Swift коллекции устроены иначе, и это главное, что ждёт интервьюер.

Коллекции в Swift

• Array, Set, Dictionary, String — value types (struct), но хранят данные в буфере в куче и используют copy-on-write: копирование — это O(1) до первой мутации, буфер копируется только когда на него есть несколько ссылок (isKnownUniquelyReferenced).
• Иерархия протоколов вместо классов: Sequence → Collection → BidirectionalCollection → RandomAccessCollection; плюс MutableCollection, RangeReplaceableCollection. Алгоритмы (map, filter, sorted, firstIndex) живут в extension протоколов и достаются любому конформеру.
• Set/Dictionary требуют Hashable для элементов/ключей; Equatable, Hashable, Codable синтезируются компилятором.
• Ленивость: array.lazy.map { } не создаёт промежуточные массивы.

var a = [1, 2, 3]
var b = a            // no copy yet: both share one buffer (copy-on-write)
b.append(4)          // the buffer is copied here, `a` is untouched
print(a, b)          // [1, 2, 3] [1, 2, 3, 4]

// Any type can join the collection family by adopting the protocols.
struct Countdown: Sequence, IteratorProtocol {
    var count: Int
    mutating func next() -> Int? {
        guard count > 0 else { return nil }
        defer { count -= 1 }
        return count
    }
}
print(Array(Countdown(count: 3)))                   // [3, 2, 1]
print(Countdown(count: 5).filter { $0.isMultiple(of: 2) }) // [4, 2]

Сложность операций

• Array: доступ по индексу O(1), append амортизированно O(1), вставка в начало O(n), contains O(n).
• Set/Dictionary: вставка, поиск, удаление — O(1) в среднем (хеш-таблица).
• String — не random access: индексы по String.Index, count — O(n), потому что графемные кластеры.

На что смотрит интервьюер

• Почему value-семантика коллекций удобна для конкурентности: копия не делит состояние, [Int] — Sendable.
• Когда нужны ContiguousArray (нет bridging с NSArray) и reserveCapacity.
• Что NSArray/NSMutableArray — reference types; при мосте из ObjC семантика меняется.