Sequences and collections

Swift’s collection protocols are the best-designed part of the standard library and the part most people use without ever conforming to. Understanding the hierarchy pays off twice: you get hundreds of methods for free on your own types, and you finally understand why Array and String behave the way they do.

The hierarchy

• Sequence — can be iterated at least once. That is the whole promise.
• Collection — can be iterated repeatedly, has indices, count is finite.
• BidirectionalCollection — can step backwards, so last and reversed() are cheap.
• RandomAccessCollection — index arithmetic is O(1), so count and shuffled() are cheap.
• MutableCollection — elements can be replaced (not inserted or removed).
• RangeReplaceableCollection — elements can be inserted and removed; this is where append and remove(at:) live.

Each step is a promise about cost, not just capability. That is the design insight worth carrying around: RandomAccessCollection does not add methods you could not write yourself — it promises they are O(1), so generic algorithms can pick a better strategy.

Conforming properly

To make a type a Collection, supply startIndex, endIndex, index(after:) and a subscript. You get map, filter, reduce, first, contains, sorted, prefix, dropLast and the rest for free.

struct RingBuffer<Element> {
    private var storage: [Element?]
    private var head = 0
    private(set) var count = 0
}

extension RingBuffer: Collection {
    var startIndex: Int { 0 }
    var endIndex: Int { count }

    func index(after index: Int) -> Int { index + 1 }

    subscript(position: Int) -> Element {
        precondition(position < count, "index out of range")
        return storage[(head + position) % storage.count]!
    }
}

That is the entire conformance, and RingBuffer now works with for … in, pattern matching, sorted(), and any generic function anyone else wrote against Collection.

Note the index type is Int here, but it does not have to be — String.Index exists precisely because a String index is a byte offset that only makes sense for the string that produced it. Dictionary.Index is opaque for the same reason. When your storage is not a flat array, an opaque index type is the honest choice.

Laziness

Every chained map/filter allocates a new array:

let result = hugeArray.map(transform).filter(isInteresting).first

That builds one array the size of hugeArray, then a second one, then throws both away to take one element. lazy turns the chain into a view that computes on demand:

let result = hugeArray.lazy.map(transform).filter(isInteresting).first

Now transform runs only until the first interesting element is found, and nothing is allocated. The cost is that laziness is viral and the types get long (LazyFilterSequence<LazyMapSequence<…>>), and if you iterate a lazy chain twice, the work happens twice. Use it for early exit over large inputs; skip it when you will consume everything anyway.

Slices share storage

prefix, suffix, dropFirst and range subscripts return slices, and a slice keeps the whole original buffer alive:

func firstLine(of file: [UInt8]) -> ArraySlice<UInt8> {
    file.prefix { $0 != 0x0A }
}

Hold that slice and the entire file stays in memory. If a slice will outlive its parent, copy it: Array(file.prefix(…)).

The other slice trap is indices. A slice keeps the parent’s indices, so it does not start at zero:

let numbers = [10, 20, 30, 40]
let tail = numbers.dropFirst(2)
tail[0]           // crash — the slice's startIndex is 2
tail[tail.startIndex]  // 30

Writing [0] on anything that might be a slice is a bug waiting for a rename. Use first, startIndex, or iterate.