Building Custom Swift Collections: From Sequence to RandomAccessCollection

You reach for Array, Set, and Dictionary without thinking. They’re the workhorses. But then you hit a data model that doesn’t slot into those shapes—maybe you’re wrapping a C pointer, juggling a sparse bitmap, or exposing a virtual view over a remote API. That’s when building a custom Swift collection stops being a theoretical detour and becomes the straightest path to giving your own types the same ergonomic API the first-party collections enjoy. This piece walks the protocol hierarchy, the minimum you need at each level, and the tradeoffs that surface the moment you move past a thin wrapper.

The Collection Protocol Hierarchy

Swift’s collection types rest on a stack of protocols. Grasping that stack is step one if you want your type to feel native. At the bottom sits Sequence—it lets you iterate over elements one at a time. Conform to Sequence and you get for-in loops, map, filter, and a pile of other operations for free. One rung up is Collection, which introduces a position—an Index—and guarantees you can walk the elements multiple times without destroying them. Above Collection, BidirectionalCollection lets you step backward from an index, and RandomAccessCollection promises that measuring the distance between indices and moving an index by a distance are O(1) operations. MutableCollection and RangeReplaceableCollection then layer on write access and insertion/deletion.

For most custom types, the sweet spot is Collection or BidirectionalCollection. RandomAccessCollection is seductive—it unlocks integer subscripting and more efficient algorithms—but it demands constant-time index advancement, a constraint that can force you to rethink your storage. The decision tree is simple: if your data lives contiguously in memory, aim for RandomAccessCollection. If you’re dealing with a linked structure or a stream, stick with Collection or BidirectionalCollection and let the standard library’s default implementations carry the weight.

Starting with Sequence: The Minimal Viable Protocol

Sequence is the gatekeeper. To conform, your type needs exactly one method: makeIterator(), which returns an IteratorProtocol. The iterator itself asks for a single mutating func next() -> Element?. That bare-bones requirement makes Sequence a natural fit for lazy or one-pass data sources—reading lines from a file, spitting out Fibonacci numbers, or streaming sensor data. Conform, and you instantly pick up higher-order functions like map, filter, and reduce, all eager by default. Want lazy evaluation? Wrap your sequence in LazySequence and computation waits until elements are actually requested.

Here’s a concrete example: a Fibonacci sequence that generates numbers on the fly. The iterator holds the last two values and advances each time next() is called. Because the sequence itself is stateless, makeIterator() just hands back a fresh iterator. This pattern works for any infinite or computationally generated series.

struct Fibonacci: Sequence {
    typealias Element = Int

    func makeIterator() -> FibonacciIterator {
        return FibonacciIterator()
    }
}

struct FibonacciIterator: IteratorProtocol {
    private var current = 0
    private var nextValue = 1

    mutating func next() -> Int? {
        let result = current
        current = nextValue
        nextValue = result + nextValue
        return result
    }
}

// Usage
for num in Fibonacci().prefix(10) {
    print(num) // 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
}

Notice that Fibonacci itself stores no elements. The state lives entirely in the iterator. That separation is intentional: a sequence describes how to produce values, while the iterator tracks where you are in that production. For one-shot data sources like a network stream, you might even make the sequence itself the iterator by conforming to both protocols at once—but be warned, that makes the sequence non-repeatable, since the first traversal eats the state.

Building a Custom Collection

Moving from Sequence to Collection means you define a concrete Index type and implement startIndex, endIndex, and subscript access via index. The index must be Comparable, and the collection must guarantee O(1) subscript access. A classic example is a fixed-size ring buffer that overwrites old elements when full. Let’s build one step by step.

Our RingBuffer stores elements in a fixed-capacity array and uses a head pointer to track the logical start. The index type wraps an integer offset from the head, and we supply methods to advance and measure distance between indices. Because the underlying storage is a contiguous array, we can safely promise O(1) subscript access and make the type conform to RandomAccessCollection.

struct RingBuffer<T> {
    private var storage: [T?]
    private var head: Int = 0
    private var count: Int = 0
    let capacity: Int

    init(capacity: Int) {
        self.capacity = capacity
        self.storage = Array(repeating: nil, count: capacity)
    }

    mutating func append(_ element: T) {
        if count < capacity {
            storage[count] = element
            count += 1
        } else {
            storage[head] = element
            head = (head + 1) % capacity
        }
    }
}

extension RingBuffer: RandomAccessCollection {
    typealias Index = Int

    var startIndex: Int { return 0 }
    var endIndex: Int { return count }

    subscript(position: Int) -> T {
        let actualIndex = (head + position) % capacity
        return storage[actualIndex]!
    }

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

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

This implementation makes a deliberate tradeoff: the subscript force-unwraps because we guarantee every position between startIndex and endIndex holds a value. If your collection might have gaps, you’d need a different approach—maybe a sparse index type that skips nil entries. The key insight: the protocol requirements are minimal, but the semantic guarantees you choose to uphold determine how safe and predictable your collection will be.

MutableCollection and RangeReplaceableCollection

Once you have a working Collection, you can add mutation support. MutableCollection requires a setter on your subscript. For RingBuffer, that’s straightforward—just write to the correct offset in storage. RangeReplaceableCollection is heavier: you need to implement replaceSubrange(_:with:), which handles insertions, deletions, and replacements in a single method. The standard library then derives append, insert, remove, and + from that one method.

But blindly conforming to RangeReplaceableCollection can drag performance down. The default implementations often assume you’re backed by a growable array and may trigger unnecessary copies. If your collection has fixed capacity or odd insertion semantics, ask yourself whether you truly need full range-replaceable behavior. Sometimes a narrower API that matches your type’s actual capabilities beats forcing a square peg into a round protocol.

Lazy Views and Wrapper Types

Swift’s standard library leans heavily on wrapper types like ReversedCollection, Slice, and LazyMapCollection. These don’t store their own data; they hold a reference to a base collection and an operation to apply on access. You can follow the same pattern to create efficient transformations. For instance, a KeyPathSortedCollection could wrap any RandomAccessCollection and present its elements sorted by a given key path, computing the sorted indices once on initialization and then providing O(1) subscript access.

When building wrappers, watch index invalidation like a hawk. If the base collection mutates, your wrapper’s indices may turn stale. Document these invariants clearly, and consider making the wrapper a value type that copies the base collection if mutation safety matters. The standard library’s Slice documentation explicitly warns that indices of the slice are valid only as long as the original collection isn’t mutated—a lesson worth heeding.

Conforming to the Collection Ecosystem

Beyond the core protocols, Swift offers additional conformances that make your collection feel finished. Equatable and Hashable on the element type enable collection-level equality and hashing. Codable conformance lets you serialize your custom collection to JSON or property lists. ExpressibleByArrayLiteral allows initialization from array literal syntax, which is especially nice for testing and prototyping. Each is optional but adds polish that users of your type will notice.

One detail that often gets skipped is CustomStringConvertible and CustomDebugStringConvertible. The default description for a custom collection can be verbose and unhelpful. Overriding description to print a concise representation—similar to how Array prints its elements—makes debugging sessions far more pleasant. A simple implementation can delegate to Array(self) for the description, but be mindful that this forces eager evaluation of the entire collection.

Performance Considerations and Index Design

Index design is where custom collections often shine or stumble. An index should be lightweight—preferably an Int or a simple wrapper—and its operations should match the complexity guarantees you’re promising. If you claim RandomAccessCollection conformance but your index(_:offsetBy:) method actually walks a linked list, you’re violating the protocol contract and standard library algorithms may show surprising O(n) behavior where O(1) is expected.

For tree-based collections, consider an opaque index type that stores a path through the tree. This keeps the index small while allowing O(log n) advancement. The standard library’s String.Index is a real-world example: it’s not a simple integer because characters can have variable width in UTF-8 storage. Your custom collection may face similar constraints if elements aren’t uniformly sized.

Another performance trap is eager copying. Swift collections are value types with copy-on-write semantics, but your custom type won’t get CoW automatically. If your collection wraps a reference type (like a class holding the storage), you’ll need to implement isKnownUniquelyReferenced checks before mutating to avoid unintended sharing. The standard library’s Array does this internally; you can replicate the pattern by wrapping your storage in a class and checking uniqueness in every mutating method.

Practical Example: A SortedCollection

Let’s build a SortedCollection that keeps elements in sorted order. This type wraps an internal array and uses binary search for insertion. It conforms to RandomAccessCollection, so users get integer subscripting and efficient prefix/suffix operations. The tradeoff: insertion is O(n) due to array shifting, but lookup is O(log n) and iteration is O(1) per element. This is the right design when reads vastly outnumber writes.

struct SortedCollection<Element: Comparable> {
    private var elements: [Element] = []

    mutating func insert(_ element: Element) {
        let index = elements.firstIndex(where: { $0 >= element }) ?? elements.endIndex
        elements.insert(element, at: index)
    }

    func contains(_ element: Element) -> Bool {
        let index = elements.firstIndex(where: { $0 >= element })
        return index.map { elements[$0] == element } ?? false
    }
}

extension SortedCollection: RandomAccessCollection {
    typealias Index = Int

    var startIndex: Int { return elements.startIndex }
    var endIndex: Int { return elements.endIndex }

    subscript(position: Int) -> Element {
        return elements[position]
    }
}

This type is intentionally simple—it delegates most work to the internal array. In a production implementation, you’d want to add remove, removeAll, and perhaps a sortedInsert that takes a predicate. You might also consider making the element type generic over a Comparable key path rather than requiring the element itself to be Comparable, which would allow sorting by a specific property.

When Not to Build a Custom Collection

Before you commit to a custom collection, ask whether a composition of existing types would do the job. A Dictionary with Array values can model many relationships. A Set combined with sorted() gives you ordered unique elements. The standard library’s IndexSet efficiently stores integer ranges. And OrderedSet from the Swift Collections package (maintained by the Swift team) provides ordered unique elements without requiring you to write your own data structure.

Custom collections shine when you have specific performance requirements or when you’re wrapping an external data source that doesn’t map cleanly to existing types. If you’re working with a C library that exposes a pointer and a count, a custom RandomAccessCollection wrapper around UnsafeBufferPointer gives you safe, idiomatic Swift access with zero overhead. Similarly, if you’re building a disk-backed data structure, a custom collection can transparently page data in and out of memory.

FAQ

What’s the minimum I need to implement for a custom Collection?

You need four things: a concrete Index type that is Comparable, a startIndex property, an endIndex property, and a subscript that takes an Index and returns an Element. You must also implement index(after:) to advance an index. If you want BidirectionalCollection, add index(before:). For RandomAccessCollection, you need index(_:offsetBy:) and distance(from:to:) with O(1) complexity.

Can I make my custom collection work with for-in loops?

Yes—any type that conforms to Sequence works with for-in. Since Collection inherits from Sequence, any custom collection automatically supports iteration. You don’t need to implement anything extra beyond the Collection requirements.

How do I add copy-on-write behavior to my custom collection?

Wrap your mutable storage in a class and store a reference to it in your struct. Before any mutating operation, check isKnownUniquelyReferenced(&storage). If it returns false, create a copy of the storage before mutating. This is the same pattern used by Array and other standard library types. The Swift Collections package includes a _makeUniqueAndReserveCapacityIfNotUnique() helper that you can study for reference.

Why does my custom collection’s index type need to be Comparable?

The Comparable requirement allows the standard library to form ranges like startIndex..<endIndex and to check whether an index falls within the collection’s bounds. Without it, you couldn’t use your collection with slicing or with algorithms that take range parameters. The requirement is part of the Collection protocol definition in Swift 4 and later.

Should I always aim for RandomAccessCollection?

Not necessarily. RandomAccessCollection requires O(1) index advancement and distance measurement. If your underlying data structure is a linked list, a tree, or a stream, you can’t honestly provide those guarantees. Conforming to a protocol you can’t satisfy leads to performance bugs. It’s better to conform to Collection or BidirectionalCollection and let the standard library’s algorithms adapt. Users can always wrap your collection in Array() if they need random access.

Building custom Swift collections is a skill that separates intermediate developers from those who truly understand the language’s design philosophy. Start with Sequence, move to Collection when you need multi-pass traversal, and add BidirectionalCollection or RandomAccessCollection only when your data structure genuinely supports those operations. The protocols are designed to be composed incrementally—use that to your advantage.