Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 146 ยท Collections

Collection Protocols

Learn Swift's Sequence, Collection, BidirectionalCollection and RandomAccessCollection protocols - iterators, indices, custom collections, slices and generic algorithms.

Arrays, sets, dictionaries, strings, ranges and the results of reversed() or lazy all feel similar: you can loop over them, call map and filter, ask for first or count. That is not a coincidence and it is not magic. They all conform to a small family of protocols in the standard library, and almost every method you use on them is written once, on the protocol, and shared by everything that conforms.

Understanding this family pays off in three ways. You can read the standard library's documentation and error messages ('C.Index', 'some Sequence<Int>'), you can write generic functions that accept any collection instead of only [Int], and you can make your own types behave like first-class collections by writing a handful of members and getting a hundred methods for free. This lesson climbs the ladder one rung at a time: Sequence, Collection, BidirectionalCollection and RandomAccessCollection, plus the two "mutation" protocols on the side.

The ladder of protocols

Each protocol adds one capability to the one below it, and each capability makes more algorithms possible or faster.

Protocol Adds Examples
Sequence Go through the elements once, from the front Array, Set, Dictionary, String, ranges, stride, sequence(first:next:)
Collection Multi-pass traversal, indices, a subscript, count Array, Set, Dictionary, String, Range<Int>
BidirectionalCollection Step backwards: last, reversed(), suffix Array, String, Range<Int> (not Set, not Dictionary)
RandomAccessCollection Jump any distance in O(1): fast count, fast [i], fast distance Array, ArraySlice, Range<Int> (not String)

Two further protocols describe what you can change: MutableCollection (replace elements in place, as with swapAt or sort()) and RangeReplaceableCollection (insert and remove, as with append and removeFirst). Array conforms to all of them; String is range-replaceable but not mutable element by element; Set is neither.

The ladder is about promises. Set is a Collection, so you can loop over it as often as you like, but it does not promise any order, so it cannot be bidirectional. String can walk both ways, but a character can be several bytes wide, so jumping to the 500th character costs a scan, so it is not random access. When a method needs a stronger promise, it asks for a stronger protocol.

Sequence: one pass, from the front

A Sequence is anything that can hand out its elements one at a time. The single requirement is makeIterator(), which returns an iterator: a value with one method, next(), that returns the next element or nil when the elements run out. The for-in loop is nothing but sugar over exactly that.

Swift What a for-in loop really does

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Conforming to Sequence yourself takes a few lines. Here is a countdown that gives out n, n-1, ..., 1:

Swift A custom Sequence

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Writing two small types (a sequence and an iterator) is the formal route. For a quick one-off, you can make a type its own iterator by conforming to IteratorProtocol and Sequence together: because Sequence supplies a default makeIterator() for iterators (it returns self), you only write next(). For one-off streams that need no new type, sequence(state:next:) and sequence(first:next:) are shorter still; Lazy Sequences uses them.

A Sequence is only promised to be traversable once. Many sequences can be walked again (arrays, ranges), but some cannot: a sequence that reads lines from a socket or a file has consumed them after the first loop. If an algorithm must visit the elements twice, ask for Collection, which guarantees multi-pass traversal.

What a Sequence gives you

Because these methods are written on the protocol, any conformer gets them: map, compactMap, flatMap, filter, reduce, forEach, contains, allSatisfy, first(where:), min(), max(), sorted(), enumerated(), zip, prefix, dropFirst, joined(), reversed() (which on a plain Sequence builds an array) and more. map, filter, reduce and Friends covers the most common ones.

A subtle point: a Sequence has no count property that is fast, because counting means consuming it. What it has is underestimatedCount, a cheap lower bound that Array(sequence) uses to reserve memory.

Collection: multi-pass, with indices

A Collection is a Sequence that you can traverse repeatedly without changing it, and whose elements have positions. The minimum a conformer supplies is:

  • startIndex and endIndex: the first position and the position one past the last;
  • subscript(position): read the element at a valid index;
  • index(after:): the position that follows another one.

In return you get count, isEmpty, first, indices, index(_:offsetBy:), distance(from:to:), slicing with ranges, prefix(while:), firstIndex(of:), split, randomElement() and plenty more. Indices are an associated type, Index, which only needs to be Comparable. They are often integers but need not be.

Here is a type that holds the square numbers 0, 1, 4, 9, ... without storing any of them. It computes the value from the index:

Swift A custom RandomAccessCollection

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Look at what is missing from Squares: no index(after:), no index(before:), no count calculation, no first, last, reversed() or slicing code. Because the Index type is Int, Swift knows Int is a strideable integer and supplies the index arithmetic. That is why only the three requirements were needed, even though the type claims RandomAccessCollection.

The slice squares[2..<5] is not a copy. It has the type Slice<Squares>: a small view that holds the original collection and a range of indices. Its indices keep their original numbers (2, 3, 4), they do not restart at 0. Slices and Views explains why and what to watch out for.

Violating the contract

Reading outside startIndex..<endIndex is a programmer error, and the standard collections stop the program rather than return garbage. Our Squares does the same with precondition:

Swift An index out of range (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The first print shows 9, and then the program traps: the process dies with Illegal instruction (signal 4, SIGILL) plus a backtrace, and not reached never appears. The runner's optimized build does not show the precondition message, a debug build does. Output printed before the crash is kept. Use indices, first, last or firstIndex(where:) instead of hand-computed numbers whenever you can.

Indices are not always integers

Array happens to use Int positions, which makes people think all collections do. String uses String.Index, Dictionary uses Dictionary.Index, Set uses Set.Index. You obtain them from the collection, and you move them with the collection's own methods:

Swift Non-integer indices

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The names start, third and afterT are plain String.Index values. An index is only meaningful for the collection that produced it (and only until that collection is mutated), so never carry a String.Index from one string to another. Strings goes deeper into why string indices are shaped this way.

BidirectionalCollection: stepping backwards

A bidirectional collection adds index(before:). That single member is enough to give you last, suffix(_:), dropLast, removeLast (when also range-replaceable), last(where:), lastIndex(of:) and an efficient, lazy reversed():

Swift Going backwards

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

On a bidirectional collection reversed() does not copy anything. It returns a ReversedCollection, a thin wrapper that walks from the end. On a plain Sequence it must build and return an array. Wrap the result in Array(...) or String(...) only when you need an independent copy.

Set and Dictionary are not bidirectional: with no defined order, "the previous element" has no meaning. That is why set.last is a compile error, and why dict.reversed() gives you an array of pairs in whatever order the dictionary happens to have.

RandomAccessCollection: constant-time distance

Random access means you can compute index(i, offsetBy: n) and distance(from:to:) in O(1). Array, ArraySlice, ContiguousArray and Range<Int> have it. String does not, which is why string.count is O(n) while array.count is O(1).

This matters for algorithms. Binary search, for example, is only logarithmic if jumping to the middle is cheap. Compare these two signatures:

Swift Choosing the protocol for an algorithm

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The last line shows the lesson of slice indices again: searching the slice data[2...] for 3 returns index 2, a position in the original array, because that is where the slice starts. Note also the name lowerBound: it returns where the target belongs, found or not. (The standard library has no binary search; Sorting and Searching Arrays shows another version.)

Writing generic code against collections

A function that accepts [Int] can only ever be called with arrays. If it needs only to read a sequence of integers, accepting the protocol is more flexible. Since Swift 5.7 the standard protocols have primary associated types, so you can write the element type in angle brackets after the protocol:

Swift some and any with Sequence and Collection

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

some Sequence<Int> means "one specific type chosen by the caller, whatever it is, whose elements are Int". The compiler generates specialised code for each, so there is no overhead. any Collection<Int> is a box that can hold different types at runtime, which costs an indirection. Use some for parameters and any only when you need a heterogeneous array or property; Opaque and Existential Types compares them in depth.

The older spelling, func total<S: Sequence>(_ numbers: S) -> Int where S.Element == Int, is equivalent and still necessary when you need to refer to the type S several times or add richer constraints.

The most common generic mistake

The most frequent error when generalising array code is using integer subscripts on a generic Collection:

Swift Integer subscript on a generic Collection (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The compiler answers with error: cannot convert value of type 'Int' to expected argument type 'C.Index'. A generic Collection does not promise integer positions, so items[0] is not allowed. Use the collection's own indices: items[items.startIndex], items.index(after: items.startIndex), or the safe helpers first, dropFirst().first and prefix(2). Here is the fix:

Swift Using the collection's own indices

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Conforming your own type: a ring of values

Let's build something more realistic: a fixed-capacity ring buffer. Conforming to RandomAccessCollection and RangeReplaceable would be a lot of work, so we choose just Collection with an Int index, which still unlocks the whole toolbox.

Swift A fixed-size window as a Collection

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Conforming to Collection took four tiny members. Everything else (count, max, sorted, contains, first) comes from the protocol extensions. This is the pattern professionals follow: store the data in a familiar type, forward the four requirements, and only add custom code for what is genuinely different. If you want more, add BidirectionalCollection by writing index(before:); RandomAccessCollection then only needs the Int-style index arithmetic you already have.

Mutating protocols, briefly

  • MutableCollection adds a settable subscript so elements can be replaced in place, never changing the size. It brings sort(), reverse(), shuffle(), swapAt(_:_:) and partition(by:). Array and ArraySlice conform; String, Set and Dictionary do not.
  • RangeReplaceableCollection adds an empty init() and replaceSubrange(_:with:). From that single method come append, insert, remove, removeAll, removeFirst and +. Array, String and Substring conform.

A generic function that sorts in place must ask for MutableCollection & RandomAccessCollection (or call the standard sort()), while one that removes elements needs RangeReplaceableCollection. If the compiler complains that a method "is not available" on your generic type, check that you asked for the right protocol.

Complexity cheat sheet

Operation Array String Set / Dictionary
count O(1) O(n) O(1)
first O(1) O(1) O(1)
last O(1) O(1) not available
index(offsetBy:) O(1) O(n) O(n)
contains(_:) O(n) O(n) O(1)
reversed() (lazy view) O(1) O(1) not available

The pattern is: algorithms written once on the protocol take the cost of whatever the conformer provides. When performance surprises you, look at which rung of the ladder the type sits on.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the one method a type must provide to conform to Sequence?

    A Sequence returns an iterator from makeIterator(). The iterator's own next() method hands out the elements, and for-in uses both.
  2. 2. Why can a generic function over C: Collection not write items[0]?

    Indices are an associated type. Sets, dictionaries and strings use their own index types. The compiler says it cannot convert Int to C.Index.
  3. 3. Which of these is NOT a BidirectionalCollection?

    A Set has no meaningful order, so there is no 'previous' element and no last.
  4. 4. What does reversed() return on an Array?

    Because Array is bidirectional, reversed() wraps it in a ReversedCollection. Wrap the result in Array(...) when you need a real copy.
  5. 5. What is the main benefit of RandomAccessCollection over Collection?

    That promise is what makes algorithms like binary search truly logarithmic. String lacks it, so string.count and offsetting indices are O(n).

Summary

  • Sequence means one-pass iteration through makeIterator(); for-in, map, filter, reduce and sorted are written once for every sequence.
  • Collection adds multi-pass traversal, indices (startIndex, endIndex, index(after:)), a subscript, count and slicing.
  • BidirectionalCollection adds index(before:) for last, suffix and the lazy reversed(); RandomAccessCollection makes index arithmetic O(1).
  • Indices are an associated type: String.Index and Set.Index are not integers, and an index belongs only to the collection that produced it.
  • Write generic code with some Collection<Element> and use any only when you need a heterogeneous box.
  • To create your own collection, forward startIndex, endIndex, index(after:) and the subscript to existing storage and enjoy the free methods.
  • MutableCollection and RangeReplaceableCollection describe in-place edits and insertion/removal.

Next: Lazy Sequences