Building Custom Swift Collections: From Sequence to BidirectionalCollection

Swift’s standard library gives you Array, Set, and Dictionary right out of the box. They’re fast, well-tested, and handle most day-to-day tasks. But sometimes you hit a wall—maybe you need a fixed-capacity ring buffer for real-time audio, or a data structure that keeps elements in a specific order without the overhead of a full sort. That’s when you start thinking about rolling your own collection. It’s not as scary as it sounds. By conforming to a few key protocols, you can build a type that feels native, works with for-in loops, and plugs into every algorithm in the standard library. This article walks through the process using a ring buffer as our example, starting with Sequence and working up to BidirectionalCollection.

Why Build a Custom Collection Instead of Using an Array?

Arrays are generalists. They do a lot, but they also make assumptions—like the ability to grow dynamically and shift elements on insert or remove. For a ring buffer, those assumptions become liabilities. A ring buffer overwrites old data when full, and it needs O(1) enqueue and dequeue without the linear cost of Array.removeFirst(). By writing a custom type that conforms to Collection, you keep that performance profile and still get map, filter, reduce, slicing, and all the other goodies. The trade-off is that you have to provide a correct Index type and four essential requirements: startIndex, endIndex, index(after:), and subscript. Once those are in place, the compiler fills in the rest.

Step 1: Conform to Sequence with a Custom Iterator

Every collection starts life as a Sequence. The protocol asks for one thing: makeIterator(), which returns a type that conforms to IteratorProtocol. For a ring buffer, the iterator needs to walk elements in logical order, wrapping around the underlying array when it hits the end. Here’s a minimal implementation:

struct RingBuffer<Element> {
    private var storage: [Element?]
    private var readIndex = 0
    private var writeIndex = 0
    private(set) var count = 0

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

extension RingBuffer: Sequence {
    struct Iterator: IteratorProtocol {
        let buffer: RingBuffer
        var index = 0
        var traversed = 0

        mutating func next() -> Element? {
            guard traversed < buffer.count else { return nil }
            let element = buffer.storage[(buffer.readIndex + index) % buffer.storage.count]
            index += 1
            traversed += 1
            return element
        }
    }

    func makeIterator() -> Iterator {
        Iterator(buffer: self)
    }
}

At this point, you can loop over a ring buffer with for element in buffer, but you can’t grab an element by index, get a count in O(1), or slice it. That’s where Collection comes in.

Conforming to Collection: The Indexing Model

The Collection protocol needs an Index type that’s Comparable and a subscript that returns elements in O(1). For a ring buffer, a plain integer offset works fine as an index. But because the buffer wraps, the index has to encode both the offset and the buffer’s base state to stay valid across mutations—or you just document that indices go stale after structural changes, the same way Array does.

extension RingBuffer: Collection {
    struct Index: Comparable {
        let offset: Int
        static func < (lhs: Index, rhs: Index) -> Bool {
            lhs.offset < rhs.offset
        }
    }

    var startIndex: Index { Index(offset: 0) }
    var endIndex: Index { Index(offset: count) }

    subscript(position: Index) -> Element {
        let actualIndex = (readIndex + position.offset) % storage.count
        return storage[actualIndex]!
    }

    func index(after i: Index) -> Index {
        Index(offset: i.offset + 1)
    }
}

With Collection conformance, the ring buffer picks up default implementations for count, isEmpty, first, prefix, suffix, and slicing. The subscript returns a slice that’s itself a Collection, so you can chain things like buffer.dropFirst(3).prefix(2) without extra work.

Adding BidirectionalCollection for Reverse Traversal

If your data structure can walk backward efficiently, add BidirectionalCollection. It requires one extra method: index(before:). For the ring buffer, moving backward is just as simple as moving forward:

extension RingBuffer: BidirectionalCollection {
    func index(before i: Index) -> Index {
        Index(offset: i.offset - 1)
    }
}

Now reversed(), last, and suffix work in O(1) without creating temporary arrays. This is handy for algorithms that scan from both ends, like palindrome checks or double-ended priority queues.

MutableCollection and RangeReplaceableCollection: When to Go Further

If you need in-place element mutation, add MutableCollection by providing a setter on the subscript. For a ring buffer, that’s rarely necessary—the main use case is FIFO queue behavior. But if you’re building a deque (double-ended queue) or a gap buffer for a text editor, RangeReplaceableCollection becomes useful. That protocol requires init(), replaceSubrange(_:with:), and append, which together enable the + operator, insert, remove, and removeAll. Be careful: implementing RangeReplaceableCollection on a fixed-capacity structure like a ring buffer can lead to unexpected growth unless you explicitly handle overflow.

Practical Considerations: Index Invalidation and Value Semantics

Swift collections are value types with copy-on-write optimization, but a naive struct wrapping a class-based storage won’t get CoW for free. If your ring buffer uses an internal class to hold the array, you must check isKnownUniquelyReferenced before mutating. Otherwise, two copies of the buffer share the same storage, breaking value semantics. The standard library’s Array handles this internally, but custom collections have to do it manually when using reference-typed backing.

Index invalidation is another subtle area. The ring buffer’s Index stores an integer offset; if an element is dequeued, the offset becomes stale. Document this clearly, and consider adopting the index validation pattern used by String: store a version token in the index and compare it against the collection’s current version on each access. This adds a small runtime cost but prevents silent data corruption.

Performance Characteristics and Benchmarking

Apple’s documentation for Collection specifies expected complexity for each operation. When you provide custom implementations, you implicitly promise those performance guarantees. For a ring buffer, startIndex and endIndex are O(1), index(after:) is O(1), and subscript is O(1). If you add count as a stored property, it stays O(1); otherwise, the default implementation walks the collection in O(n). Always override count if you can provide a faster implementation.

To verify, use XCTest’s performance testing or the swift-collections-benchmark package from the Swift project. This package provides a standardized way to measure throughput and latency of custom collection operations against Array and Deque baselines. For a ring buffer with 1024 elements, enqueue and dequeue should complete in constant time regardless of buffer size, while Array.removeFirst() degrades linearly.

When to Use a Custom Collection vs. Existing Types

Before writing a custom collection, check whether a standard library type or a community package already does the job. The Swift Collections package from Apple provides Deque, OrderedSet, and OrderedDictionary, which cover many use cases. A ring buffer is a good custom choice when you need a fixed-capacity, overwriting queue—common in real-time audio processing or sliding-window algorithms. For a general-purpose double-ended queue, Deque is already optimized and tested. The decision to build custom should be driven by a specific constraint that existing types can’t satisfy without unacceptable overhead.

FAQ

What is the minimum conformance required to make a custom type a Swift collection?

You must conform to Sequence and Collection. Sequence requires makeIterator(). Collection requires an Index type, startIndex, endIndex, index(after:), and a read-only subscript. With these, you get default implementations for dozens of methods.

How do I ensure my custom collection works correctly with Swift’s slicing?

Slicing returns a Slice<YourCollection>, which shares indices with the original collection. Ensure your index type is lightweight and that your subscript correctly handles indices that may have been created before a mutation. If your collection’s structure changes, document that existing indices are invalidated, or implement index validation with a version token.

Can I make my custom collection conform to both MutableCollection and RangeReplaceableCollection?

Yes, but the order matters. MutableCollection adds a setter to the subscript. RangeReplaceableCollection requires init(), replaceSubrange(_:with:), and append. If your type has a fixed capacity, think carefully before conforming to RangeReplaceableCollection, because the protocol assumes the collection can grow arbitrarily. You may need to throw errors or implement a resizing strategy.

What are the most common mistakes when implementing a custom index type?

The most frequent errors are: (1) using an integer index that does not account for the collection’s logical order, (2) failing to make the index Comparable, and (3) not handling index invalidation after mutations. Always test edge cases: empty collections, single-element collections, and indices created before a mutation that changes the collection’s count.

Building a custom Swift collection is a deliberate engineering choice that pays off when you need precise control over memory layout, performance, or invariants. By starting with Sequence, layering on Collection and BidirectionalCollection, and carefully managing index semantics, you create a type that feels native to the language and integrates with every algorithm in the standard library. The next natural step is to explore LazySequenceProtocol and LazyCollectionProtocol, which let you chain transformations without intermediate allocations—a topic I’ll cover in a follow-up article on building lazy evaluation pipelines for custom data structures.