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

While you write for merchandise in checklist the compiler quietly units loads of equipment in movement. Normally writing a for loop is a reasonably mundane activity, it isn’t that advanced of a syntax to jot down. Nonetheless, it is all the time enjoyable to dig a bit deeper and see what occurs beneath the hood. On this put up I’ll unpack the items that make iteration tick so you possibly can cause about loops with the identical confidence you have already got round optionals, enums, or end result builders.

Right here’s what you’ll decide up:

• What Sequence and Assortment promise—and why iterators are nearly all the time structs.
• How for … in desugars, plus the pitfalls of mutating when you loop.
• How async iteration and customized collections prolong 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 person asks for an iterator, give them one that may hand out components till you’re out”. Which means a conforming sort must outline two related sorts (Aspect and Iterator) and return a contemporary iterator each time makeIterator() known as.

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

    func makeIterator() -> Iterator
}

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

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

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. While 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 needs to be single-pass. It’s completely legitimate handy out a “consumable” iterator that can be utilized as soon as after which returns nil perpetually. 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.

In case 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 way of: 360, by: 30) {
    print(angle)
}

This prints 0, 30, 60 … 360 after which the iterator is completed. In case you ask for an additional 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 top. That’s the core Sequence contract in motion.

So to summarize, a Sequence comprises n gadgets (we do not know what number of as a result of there isn’t any idea of depend in a Sequence), and we are able to ask the Sequence for an Iterator to obtain gadgets till the Sequence runs out. As you noticed with stride, the Sequence would not have to carry all values it can ship in reminiscence. It could possibly generate the values each time its Iterator has its subsequent() operate referred to as.

In case 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 cross; AsyncStream-style sequences do precisely that. An AsyncStream will vend a brand new worth to an async loop, after which it discards the worth perpetually.

In different phrases, the one promise is “I can vend an iterator”. Nothing says the iterator could 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 possibly can iterate as many instances as you want, the order is steady (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) -> Aspect { get }
}

These additional necessities unlock optimisations. map can preallocate precisely the correct quantity of storage. depend doesn’t must stroll your entire information 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 though their order can change after you mutate them. The protocols don’t promise order, so if iteration order issues to you be sure to decide a sort that paperwork the way it behaves.

How for … in Truly Works

Now that you realize a bit extra about collections and iterating them in Swift, right here’s what a easy loop appears to be like like when you have been to jot down 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 way 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 midst of iterating it. An array iterator assumes the buffer stays steady; when 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 you could cull gadgets, 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 to be like 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 format. It additionally calls firstIndex on each cross, so every iteration scans the entire array once more—a simple method 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.

In case you desire to maintain the originals round, construct a filtered copy as an alternative:

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

Each approaches maintain iteration and mutation separated, which suggests you received’t journey over the iterator mid-loop. All the things we’ve checked out up to now assumes the weather are prepared the second you ask for them. In trendy apps, it isn’t unusual to wish to iterate over collections (or streams) that generate new values over time. Swift’s concurrency options prolong 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 Aspect
    associatedtype AsyncIterator: AsyncIteratorProtocol the place AsyncIterator.Aspect == Aspect

    func makeAsyncIterator() -> AsyncIterator
}

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

You devour async sequences with for await:

for await ingredient in stream {
    print(ingredient)
}

Below the hood the compiler builds a looping activity that repeatedly awaits subsequent(). If subsequent() can throw, swap to for attempt await. Errors propagate identical to they might in every other async context.

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

func makeProgressStream() -> AsyncStream {
    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() whenever 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 best sample is to examine for cancellation inside subsequent():

struct PollingIterator: AsyncIteratorProtocol {
    mutating func subsequent() async throws -> Merchandise? {
        attempt Activity.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 group from scratch—and that’s a great factor. Arrays, dictionaries, and units already cowl the vast majority of circumstances with battle-tested semantics. While you do roll your personal, tread rigorously: 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 authentic causes to create a specialised assortment. You may want a hoop buffer that overwrites previous entries, or a sliding window that exposes simply sufficient information for a streaming algorithm. Everytime you go down this path, maintain the floor space tight, doc the invariants, and write exhaustive exams to show the gathering acts like a regular 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: 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: Aspect) {
        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) -> Aspect {
        precondition((0..

Just a few particulars in that snippet are value highlighting:

• storage shops optionals so the buffer can maintain 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 could be partially stuffed, so counting on storage.depend would lie about what number of components are literally obtainable.
• index(after:) and the subscript settle for logical indexes (0 by way of depend) and translate them to the best slot in storage by offsetting from head and wrapping with the modulo operator. That bookkeeping retains iteration steady even after the buffer wraps round.
• Every accessor defends the invariants with precondition. Skip these checks and a stray index can pull stale information or stroll off the top with out warning.

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

In Abstract

Iteration appears to be like easy as a result of Swift hides the boilerplate, however there’s a surprisingly wealthy protocol hierarchy behind each loop. As soon as you understand how Sequence, Assortment, and their async siblings work together, you possibly can construct information constructions that really feel pure in Swift, cause about efficiency, and bridge legacy callbacks into clear async code.

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