How do you write your own Collection, and what do you get for free?
Predict first
Does this compile?
struct Countdown: RandomAccessCollection {
let from: Int
var startIndex: Int { 0 }
var endIndex: Int { from }
subscript(i: Int) -> Int { from - i }
}- Yes
- No — index(after:) is missing
Mental model. You hand the standard library a map of your data: where it starts, where it ends, and how to step. It builds every tool on top.
The minimum is four requirements: startIndex, endIndex, a read-only subscript(position), and index(after:). From those you get iteration, map, filter, first, isEmpty, indices, and slicing (the default subsequence is Slice<Self>).
The defaults are correct but not always fast: count walks the indices, O(n). If your index is an Int and you adopt RandomAccessCollection, Swift supplies O(1) offsetting, so you only write startIndex, endIndex, and the subscript. Remember endIndex is one past the last element, and a slice of your collection keeps your indices.
With Int indices a RandomAccessCollection inherits index(after:), count and the rest. Three members are enough.
Code
struct Ring<Element>: RandomAccessCollection {
var storage: [Element]
var head: Int
var startIndex: Int { 0 }
var endIndex: Int { storage.count }
subscript(i: Int) -> Element { storage[(head + i) % storage.count] }
}
let r = Ring(storage: [1, 2, 3, 4], head: 2)
print(Array(r), r.count, r.map { $0 * 10 })[3, 4, 1, 2] 4 [30, 40, 10, 20]Common traps
- Off-by-one
endIndex. It is the position after the last element, not the last element. - Claiming RandomAccess with O(n) steps. The protocol promises O(1); algorithms rely on that.
They might follow up with
- When would you override
count? When you can answer it in O(1) but the default would walk the indices. - Why define your own index type? To stop callers mixing indices from different collections, or to carry extra state such as a tree position.