2.1 · Collections, indexing, Sequence and lazy

Array, Set and Dictionary cover most code. The interesting questions are what they cost, what their indices mean, and how the Sequence and Collection protocols let you build on top of them.

Mental model. A Sequence can be walked. A Collection can be walked again and indexed. Every performance and bug question here is about which of those two promises you are leaning on.

Choosing a collection

Pick by the operation you do most, then know what you give up.

  1. Array, Set or Dictionary: how do you choose, and what does each operation cost? 2.1.1 · L1
    Choose by the operation you do most. Array keeps order and gives O(1) access by position, but finding a value with contains is O(n). Set answers “is it in…
  2. What must Hashable guarantee, and why does iteration order change between launches? 2.1.2 · L2
    The contract is one rule: equal values must produce the same hash. The reverse is allowed (different values can collide). If == and hash(into:) disagree, a…
  3. When is the standard library not enough, and what does swift-collections add? 2.1.3 · L3
    The stdlib collections are general purpose. Where one of their costs hurts, the Apple-maintained swift-collections package fills the gap: Deque (O(1) at both…

Array in practice

Growth, iteration, and slices that are not what they look like.

  1. How does an Array grow, and when do reserveCapacity and ContiguousArray help? 2.1.4 · L2
    An array stores elements in one heap buffer. When an append would overflow it, the array allocates a larger buffer (roughly doubling) and moves the elements…
  2. What happens if you mutate an array while you loop over it? 2.1.5 · L2
    The loop works on a snapshot. for x in a copies the array value when the loop starts. Because of copy-on-write that copy is just a reference, until you mutate…
  3. What is an ArraySlice, and why does slice[0] crash? 2.1.6 · L3
    A slice is a view into its parent array. Creating one is O(1) because it shares the parent’s buffer, and it keeps the whole parent alive for as long as the…

Transforming and searching

The everyday higher-order functions, and their traps.

  1. map, filter, compactMap, flatMap, reduce, forEach: when do you use each, and what bites? 2.1.7 · L1
    map transforms every element. filter keeps some. compactMap transforms and drops nils. flatMap transforms to a sequence and joins the results into one array.…
  2. How does sorting work in Swift, and what do you need to watch out for? 2.1.8 · L2
    sort() sorts in place and returns nothing; sorted() returns a new array. Both are O(n log n) and take an areInIncreasingOrder closure that must be a strict…

Sequence, Collection and lazy

The protocol ladder, deferred work, and writing your own collection.

  1. Sequence, Collection, BidirectionalCollection, RandomAccessCollection: what does each add? 2.1.9 · L2
    Sequence promises only that you can iterate once; the iterator is stateful and may be consumed (think of a network stream). Collection adds multi-pass…
  2. What does .lazy do, and what does it cost? 2.1.10 · L2
    .lazy returns a wrapper whose map, filter and friends do not run immediately. They record the pipeline and compute elements on demand, one at a time, with no…
  3. How do you write your own Collection, and what do you get for free? 2.1.11 · L5
    The minimum is four requirements: startIndex, endIndex, a read-only subscript(position), and index(after:). From those you get iteration, map, filter, first…

More in Foundation & stdlib