Sequence, Collection, BidirectionalCollection, RandomAccessCollection: what does each add?

2.1.9 · L2 · Interview

Predict first

What does this print?

var it = [1, 2, 3].makeIterator()
_ = it.next()
print(Array(IteratorSequence(it)))
  • [1, 2, 3]
  • [2, 3]

Predict first

What type is r?

let r = [1, 2, 3].reversed()
print(type(of: r))
  • Array<Int>
  • ReversedCollection<Array<Int>>

Mental model. A sequence is a conveyor belt. A collection is a shelf you can walk along repeatedly. Random access is a shelf with numbered slots you can jump to.

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 traversal and indices: startIndex, endIndex, a subscript, and index(after:). BidirectionalCollection adds stepping backwards, so you get last and reversed(). RandomAccessCollection adds O(1) jumps, which makes count and offset indexing O(1).

The ladder matters for cost. On a plain Collection, count walks the elements. reversed() on a bidirectional collection is an O(1) wrapper, not a copy. Array is random access; String is only bidirectional, which is the real reason s[i + 1] is not O(1).

An iterator is stateful. Having already produced 1, it continues from 2.

reversed() on a bidirectional collection returns a cheap view that walks backwards. Wrap it in Array(...) if you need a real array.

SequenceCollectionBidirectionalRandomAccess
Walk it againmaybe notyesyesyes
Index and subscriptnoyesyesyes
Walk backwardsnonoyesyes
O(1) jump and countnononoyes
ExampleAnySequenceSetStringArray

Common traps

  • Iterating a sequence twice. A single-pass sequence is consumed by the first loop.
  • “reversed() makes a copy.” On a bidirectional collection it returns a lazy ReversedCollection wrapper.

They might follow up with

  • Why does String not conform to RandomAccessCollection? Characters have variable width, so finding the nth one means walking. See the Strings section.
  • What are MutableCollection and RangeReplaceableCollection? The ability to assign by index, and to insert and remove elements. Array has both.

Related questions

  • 2.1.11 How do you write your own Collection, and what do you get for free?
  • 2.1.10 What does .lazy do, and what does it cost?
  • 1.9.1 Why is String not a RandomAccessCollection of Character? Why is string[i + 1] not O(1)?

← How does sorting work in Swift, and what do you need to watch out for?   What does .lazy do, and what does it cost? →