A deep dive into Collections, Sequences, and Iterators in Swift – Donny Wals

Once you write for merchandise in record the compiler quietly units a whole lot of equipment in movement. Normally writing a for loop is a reasonably mundane activity, it is not that complicated of a syntax to put in writing. Nevertheless, it is at all times enjoyable to dig a bit deeper and see what occurs beneath the hood. On this submit I’ll unpack the items that make iteration tick so you may purpose about loops with the identical confidence you have already got round optionals, enums, or consequence builders.

Right here’s what you’ll decide up:

• What Sequence and Assortment promise—and why iterators are virtually at all times structs.
• How for … in desugars, plus the pitfalls of mutating when you loop.
• How async iteration and customized collections lengthen the identical core concepts.

Understanding Sequence

Sequence is the smallest unit of iteration in Swift and it comes with a really intentional contract: “when any individual asks for an iterator, give them one that may hand out parts till you’re out”. Meaning a conforming kind must outline two related varieties (Factor and Iterator) and return a contemporary iterator each time makeIterator() known as.

public protocol Sequence {
    associatedtype Factor
    associatedtype Iterator: IteratorProtocol the place Iterator.Factor == Factor

    func makeIterator() -> Iterator
}

The iterator itself conforms to IteratorProtocol and exposes a mutating subsequent() operate:

public protocol IteratorProtocol {
    associatedtype Factor
    mutating func subsequent() -> Factor?
}

You’ll see most iterators applied as structs. subsequent() is marked mutating, so a value-type iterator can replace its place with none additional ceremony. Once you copy the iterator, you get a contemporary cursor that resumes from the identical level, which retains iteration predictable and prevents shared mutable state from leaking between loops. Lessons can undertake IteratorProtocol too, however worth semantics are a pure match for the contract.

There are two necessary implications to bear in mind:

• A sequence solely must be single-pass. It’s completely legitimate handy out a “consumable” iterator that can be utilized as soon as after which returns nil endlessly. Lazy I/O streams or generator-style APIs lean on this behaviour.
• makeIterator() ought to produce a contemporary iterator every time you name it. Some sequences select to retailer and reuse an iterator internally, however the contract encourages the “new iterator per loop” mannequin so for loops can run independently with out odd interactions.

When you’ve ever used stride(from:to:by:) you’ve already labored with a plain Sequence. The usual library exposes it proper subsequent to ranges, and it’s excellent for strolling an arithmetic development with out allocating an array. For instance:

for angle in stride(from: 0, by means of: 360, by: 30) {
    print(angle)
}

This prints 0, 30, 60 … 360 after which the iterator is completed. When you ask for one more iterator you’ll get a brand new run, however there’s no requirement that the unique one resets itself or that the sequence shops all of its values. It simply retains the present step and palms out the subsequent quantity till it reaches the tip. That’s the core Sequence contract in motion.

So to summarize, a Sequence incorporates n objects (we do not know what number of as a result of there is not any idea of depend in a Sequence), and we will ask the Sequence for an Iterator to obtain objects till the Sequence runs out. As you noticed with stride, the Sequence would not have to carry all values it’ll ship in reminiscence. It might probably generate the values each time its Iterator has its subsequent() operate known as.

When you want a number of passes, random entry, or counting, Sequence received’t offer you that by itself. The protocol doesn’t forbid throwing the weather away after the primary move; AsyncStream-style sequences do precisely that. An AsyncStream will vend a brand new worth to an async loop, after which it discards the worth endlessly.

In different phrases, the one promise is “I can vend an iterator”. Nothing says the iterator will be rewound or that calling makeIterator() twice produces the identical outcomes. That’s the place Assortment steps in.

Assortment’s Further Ensures

Assortment refines Sequence with the guarantees we lean on day-to-day: you may iterate as many instances as you want, the order is secure (so long as the gathering’s personal documentation says so), and also you get indexes, subscripts, and counts. Swift’s Array, Dictionary, and Set all conform to the Assortment protocol for instance.

public protocol Assortment: Sequence {
    associatedtype Index: Comparable

    var startIndex: Index { get }
    var endIndex: Index { get }

    func index(after i: Index) -> Index
    subscript(place: Index) -> Factor { get }
}

These additional necessities unlock optimisations. map can preallocate precisely the correct quantity of storage. depend doesn’t must stroll your entire knowledge set. If a Assortment additionally implements BidirectionalCollection or RandomAccessCollection the compiler can apply much more optimizations without spending a dime.

Value noting: Set and Dictionary each conform to Assortment regardless that their order can change after you mutate them. The protocols don’t promise order, so if iteration order issues to you be sure you decide a kind that paperwork the way it behaves.

How for … in Really Works

Now that you recognize a bit extra about collections and iterating them in Swift, right here’s what a easy loop appears like in the event you have been to put in writing one with out utilizing for x in y:

var iterator = container.makeIterator()
whereas let ingredient = iterator.subsequent() {
    print(ingredient)
}

To make this concrete, right here’s a small customized sequence that may depend down from a given beginning quantity:

struct Countdown: Sequence {
    let begin: Int

    func makeIterator() -> Iterator {
        Iterator(present: begin)
    }

    struct Iterator: IteratorProtocol {
        var present: Int

        mutating func subsequent() -> Int? {
            guard present >= 0 else { return nil }
            defer { present -= 1 }
            return present
        }
    }
}

Working for quantity in Countdown(begin: 3) executes the desugared loop above. Copy the iterator midway by means of and every copy continues independently because of worth semantics.

One factor to keep away from: mutating the underlying storage when you’re in the course of iterating it. An array iterator assumes the buffer stays secure; in the event you take away a component, the buffer shifts and the iterator not is aware of the place the subsequent ingredient lives, so the runtime traps with Assortment modified whereas enumerating. When it’s worthwhile to cull objects, there are safer approaches: name removeAll(the place:) which handles the iteration for you, seize the indexes first and mutate after the loop, or construct a filtered copy and substitute the unique when you’re executed.

Right here’s what an actual bug appears like. Think about an inventory of duties the place you wish to strip the finished ones:

struct TodoItem {
    var title: String
    var isCompleted: Bool
}

var todoItems = [
    TodoItem(title: "Ship blog post", isCompleted: true),
    TodoItem(title: "Record podcast", isCompleted: false),
    TodoItem(title: "Review PR", isCompleted: true),
]

for merchandise in todoItems {
    if merchandise.isCompleted,
       let index = todoItems.firstIndex(the place: { $0.title == merchandise.title }) {
        todoItems.take away(at: index) // ⚠️ Deadly error: Assortment modified whereas enumerating.
    }
}

Working this code crashes the second the primary accomplished activity is eliminated as a result of the iterator nonetheless expects the previous structure. It additionally calls firstIndex on each move, so every iteration scans the entire array once more—a simple option to flip a fast cleanup into O(n²) work. A safer rewrite delegates the traversal:

todoItems.removeAll(the place: .isCompleted)

As a result of removeAll(the place:) owns the traversal, it walks the array as soon as and removes matches in place.

When you favor to maintain the originals round, construct a filtered copy as a substitute:

let openTodos = todoItems.filter { !$0.isCompleted }

Each approaches hold iteration and mutation separated, which suggests you received’t journey over the iterator mid-loop. Every thing we’ve checked out to date assumes the weather are prepared the second you ask for them. In trendy apps, it is not unusual to wish to iterate over collections (or streams) that generate new values over time. Swift’s concurrency options lengthen the very same iteration patterns into that world.

Async Iteration in Observe

Swift Concurrency introduces AsyncSequence and AsyncIteratorProtocol. These look acquainted, however the iterator’s subsequent() methodology can droop and throw.

public protocol AsyncSequence {
    associatedtype Factor
    associatedtype AsyncIterator: AsyncIteratorProtocol the place AsyncIterator.Factor == Factor

    func makeAsyncIterator() -> AsyncIterator
}

public protocol AsyncIteratorProtocol {
    associatedtype Factor
    mutating func subsequent() async throws -> Factor?
}

You eat async sequences with for await:

for await ingredient in stream {
    print(ingredient)
}

Beneath the hood the compiler builds a looping activity that repeatedly awaits subsequent(). If subsequent() can throw, change to for strive await. Errors propagate similar to they might in every other async context.

Most callback-style APIs will be bridged with AsyncStream. Right here’s a condensed instance that publishes progress updates:

func makeProgressStream() -> AsyncStream<Double> {
    AsyncStream { continuation in
        let token = progressManager.observe { fraction in
            continuation.yield(fraction)
            if fraction == 1 { continuation.end() }
        }

        continuation.onTermination = { _ in
            progressManager.removeObserver(token)
        }
    }
}

for await fraction in makeProgressStream() now suspends between values. Don’t overlook to name end() if you’re executed producing output, in any other case downstream loops by no means exit.

Since async loops run inside duties, they need to play properly with cancellation. The simplest sample is to examine for cancellation inside subsequent():

struct PollingIterator: AsyncIteratorProtocol {
    mutating func subsequent() async throws -> Merchandise? {
        strive Job.checkCancellation()
        return await fetchNextItem()
    }
}

If the duty is cancelled you’ll see CancellationError, which ends the loop robotically until you resolve to catch it.

Implementing your personal collections

Most of us by no means should construct a set from scratch—and that’s a very good factor. Arrays, dictionaries, and units already cowl nearly all of instances with battle-tested semantics. Once you do roll your personal, tread fastidiously: you’re promising index validity, multi-pass iteration, efficiency traits, and all the opposite traits that callers anticipate from the usual library. A tiny mistake can corrupt indices or put you in undefined territory.

Nonetheless, there are legit causes to create a specialised assortment. You may want a hoop buffer that overwrites previous entries, or a sliding window that exposes simply sufficient knowledge for a streaming algorithm. Everytime you go down this path, hold the floor space tight, doc the invariants, and write exhaustive exams to show the gathering acts like a typical one.

Even so, it is value exploring a customized implementation of Assortment for the sake of learning it. Right here’s a light-weight ring buffer that conforms to Assortment:

struct RingBuffer<Factor>: Assortment {
    personal var storage: [Element?]
    personal var head = 0
    personal var tail = 0
    personal(set) var depend = 0

    init(capability: Int) {
        storage = Array(repeating: nil, depend: capability)
    }

    mutating func enqueue(_ ingredient: Factor) {
        storage[tail] = ingredient
        tail = (tail + 1) % storage.depend
        if depend == storage.depend {
            head = (head + 1) % storage.depend
        } else {
            depend += 1
        }
    }

    // MARK: Assortment
    typealias Index = Int

    var startIndex: Int { 0 }
    var endIndex: Int { depend }

    func index(after i: Int) -> Int {
        precondition(i < endIndex, "Can't advance previous endIndex")
        return i + 1
    }

    subscript(place: Int) -> Factor {
        precondition((0..<depend).incorporates(place), "Index out of bounds")
        let precise = (head + place) % storage.depend
        return storage[actual]!
    }
}

Just a few particulars in that snippet are value highlighting:

• storage shops optionals so the buffer can hold a set capability whereas monitoring empty slots. head and tail advance as you enqueue, however the array by no means reallocates.
• depend is maintained individually. A hoop buffer is likely to be partially stuffed, so counting on storage.depend would lie about what number of parts are literally accessible.
• index(after:) and the subscript settle for logical indexes (0 by means of depend) and translate them to the proper slot in storage by offsetting from head and wrapping with the modulo operator. That bookkeeping retains iteration secure even after the buffer wraps round.
• Every accessor defends the invariants with precondition. Skip these checks and a stray index can pull stale knowledge or stroll off the tip with out warning.

Even in an instance as small because the one above, you may see how a lot duty you tackle when you undertake Assortment.

In Abstract

Iteration appears easy as a result of Swift hides the boilerplate, however there’s a surprisingly wealthy protocol hierarchy behind each loop. As soon as you know the way Sequence, Assortment, and their async siblings work together, you may construct knowledge buildings that really feel pure in Swift, purpose about efficiency, and bridge legacy callbacks into clear async code.

If you wish to hold exploring after this, revisit the posts I’ve written on actors and knowledge races to see how iteration interacts with isolation. Or take one other have a look at my items on map and flatMap to dig deeper into lazy sequences and useful pipelines. Both approach, the subsequent time you attain for for merchandise in record, you’ll know precisely what’s taking place beneath the hood and the way to decide on the proper strategy for the job.