Understanding Swift's Collection Protocols: A Deep Dive into Sequence, Collection, and Beyond

#swift #ios #datastructures

Introduction

The Swift programming language is known for its rich set of protocols that help define what behaviors are expected from a particular type. These protocols are not only powerful tools in building reusable and modular code, but they also provide certain guarantees about a type's characteristics and performance.Among the many protocols in Swift's standard library, a few stand out when it comes to collections.

In this post, we're going to break down four collection-related protocols in Swift, starting from the basics and building up to more advanced concepts. Whether you're new to Swift or just looking to refresh your understanding, let's explore how these protocols shape the behavior of collections.

1. Sequence

At the very base of the hierarchy lies the Sequence protocol.

A Sequence type in Swift provides sequential access to its elements. But there's an important catch: using sequential access may destructively consume the elements i.e. once you traverse a sequence, you may not be able to revisit those elements without regenerating them

This is often seen in lazy sequences or streams, where the data isn't stored all at once but generated or consumed on the fly.
When a type conforms to Sequence, it must implement:

func makeIterator() -> Iterator

A Real world example:
Suppose you're generating fibonacci numbers - you don't have all the elements up front, and you don't want to store them in memory. You just want to yield one number item at a time.
The below code defines a lazy, infinite Fibonacci number generator using the Sequence protocol.

struct Fibonacci: Sequence {
    func makeIterator() -> some IteratorProtocol {
        var a = 0, b = 1
        // AnyIterator lets us define quick inline iterators
        return AnyIterator {
            defer { (a, b) = (b, a + b) }
            return a
        }
    }
}

let fibonacciSequence = Fibonacci().prefix(10)
// prefix 10 prevents the infinite loop while consuming the sequence
for num in fibonacciSequence {
    print(num)
}
// Prints - 0 1 1 2 3 5 8 13 21 34

Key takeaway:

Sequence provides simple, one-way, sequential access to elements, but accessing them is potentially destructive
It may not be rewindable (can only be used once)
It's optimized for streaming/one-pass access
It's minimal - you only implement iteration logic

2. Collection: Repeated, Non-Destructive Access

Moving up a tier, we have the Collection protocol.

A Collection is a finite sequence of elements, and one of the key differences between a collection and a basic sequence is that a collection allows for repeated, non-destructive access. This means you can revisit the elements multiple times without losing access to them

If you think of a Sequence as a movie that you can only watch once, a Collection is more like a DVD or streaming service where you can watch the movie over and over again. It's guaranteed to be finite, meaning the collection will have a defined, known number of elements, and it supports safe, repeated access without any side effects. Collection inherits from Sequence, so you also get for-in, map, filter, etc.

A type that conforms to the Collection protocol must:

Be multi-pass (can be iterated more than once)
Provide startIndex and endIndex
Provide subscript access by index
Advance through the collection using index(after:)

A Real world example:
A simple example which stores words from a sentence which conforms to Collection

// To keep the example simple, we are using a simple array as 
// storage under the hood.
struct ReadOnlyWords: Collection {
    private let words: [String]

    init(text: String) {
        self.words = text.split(separator: " ").map(String.init)
    }

    // MARK: - Collection protocol confirmance

    var startIndex: Int { words.startIndex }
    var endIndex: Int { words.endIndex }

    subscript(index: Int) -> String {
        words[index]
    }

    func index(after i: Int) -> Int {
        words.index(after: i)
    }

    // makeIterator() is synthesized automatically based on above properties
}

let words = ReadOnlyWords(text: "hello from swift collections")

for word in words {
    print(word)
}
// Prints
// hello
// from 
// swift
// collections

Key takeaway:

Collection is a more powerful type than Sequence, offering multiple non-destructive accesses to its elements and guaranteeing that the collection is finite.
Provides only forward iteration

3. BidirectionalCollection: Going Both Ways

Next up is the BidirectionalCollection protocol.

BidirectionalCollection protocol enables the ability to traverse a Collection both forwards and backwards.

A BidirectionalCollection guarantees that you can start at the front of the collection, move towards the end, and then reverse direction to traverse back from the end to the start.

It extends Collection, and adds:

func index(before: Index) -> Index

A Real world example:
Imagine you're implementing a browser-like history stack where the user can - Go forward (next page), Go backward (previous page) and Iterate over visited pages
So we would expect:

Ordered, navigable collection of history
Ability to traverse forward/backward
Don't need random access (e.g., history[3] instantly)

struct HistoryEntry {
    let url: String
    let timestamp: Date
}

// To keep the example simple, we are using a simple array as 
// storage under the hood.
struct History: BidirectionalCollection {
    private let entries: [HistoryEntry]

    init(_ entries: [HistoryEntry]) {
        self.entries = entries
    }

    // MARK: - Collection
    typealias Index = Int
    typealias Element = HistoryEntry

    var startIndex: Int { entries.startIndex }
    var endIndex: Int { entries.endIndex }

    subscript(position: Int) -> HistoryEntry {
        entries[position]
    }

    func index(after i: Int) -> Int {
        entries.index(after: i)
    }

    // MARK: - Bidirectional
    func index(before i: Int) -> Int {
        entries.index(before: i)
    }
}

let logs = [
    HistoryEntry(url: "apple.com", timestamp: .now),
    HistoryEntry(url: "swift.org", timestamp: .now),
    HistoryEntry(url: "google.com", timestamp: .now)
]

let history = History(logs)

for page in history.reversed() {
    print("Visited: \(page.url)")
}

Key takeaway:

A BidirectionalCollection allows traversal in both directions, but not all collection types support this
For example, a singly linked list is a common data structure that cannot qualify as a BidirectionalCollection, since it only allows traversal from the head (beginning) to the tail (end), but not in reverse order

4.RandomAccessCollection: Constant Time Access

The final protocol we'll cover is RandomAccessCollection.

RandomAccessCollection protocol builds on top of the BidirectionalCollection, but adds an important guarantee: elements can be accessed in constant time, regardless of their position in the collection.

For a RandomAccessCollection, accessing an element at any index should take the same amount of time. This is crucial for certain performance-sensitive tasks, such as when working with arrays, where accessing the 5th element is just as fast as accessing the 1,000th element.
Conforming to RandomAccessCollection means you're promising:

subscript(index: Index) O(1)
distance(from:to:) O(1)
index(_:offsetBy:) O(1)

A Real world example:

struct Article {
    let title: String
    let content: String
}

struct ArticleFeed: RandomAccessCollection {
    // Internally stored as an array of preloaded articles
    private var pages: [[Article]]

    // Flattened view
    private var flattened: [Article] {
        pages.flatMap { $0 }
    }

    // MARK: - Collection Conformance
    typealias Index = Int
    typealias Element = Article

    var startIndex: Int { flattened.startIndex }
    var endIndex: Int { flattened.endIndex }

    subscript(position: Int) -> Article {
        flattened[position] // O(1) because we are using array here
    }

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

    // We don't need to implement index(_:offsetBy:) or distance(from:to:)
    // because Int already conforms to Strideable with O(1)
}

let page1 = [Article(title: "Blog notes", content: "..."),
             Article(title: "Collection notes", content: "...")]

let page2 = [Article(title: "Vacation Notes", content: "...")]

let feed = ArticleFeed(pages: [page1, page2])

print(feed[0].title) // Blog notes - Guaranteed O(1)
print(feed[2].title) // Vacation Notes - Guaranteed O(1)

Key takeaway:

RandomAccessCollection provides constant-time access to elements at any index, making it optimal for use cases where performance is critical.
The RandomAccessCollection protocol adds further constraints on the associated Indices and SubSequence types, but otherwise imposes no additional requirements over the BidirectionalCollection protocol.
To meet the complexity guarantees of a random-access collection, either the index for your custom type must conform to the Strideable protocol or you must implement the index(_:offsetBy:) and distance(from:to:) methods with O(1) efficiency

Conclusion:

Here's a time complexity comparison table for the protocols we've discussed

Note: subscript(index) in Collection and BidirectionalCollection must be documented as O(1). If it's not O(1), the implementor must explicitly warn about it.