When is the standard library not enough, and what does swift-collections add?

2.1.3 · L3 · Interview

Predict first

Which of these removes the first element in O(1)?

// A: Array<Int>
// B: ContiguousArray<Int>
// C: Deque<Int>  (swift-collections)
  • A
  • B
  • C

Mental model. An array is a queue where everyone steps forward when the first person leaves. A deque lets the first person just walk out.

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 ends), OrderedSet and OrderedDictionary (insertion order kept), Heap (priority queue), and BitSet.

The classic case is a queue. Array.removeFirst() shifts every remaining element, O(n), so a loop that drains an array from the front is quadratic. A Deque removes from the front in O(1).

Both array types must shift every remaining element. A Deque keeps a ring buffer, so the front is as cheap as the back.

Common traps

  • Using an array as a queue. removeFirst in a loop is O(n²) overall.
  • Reaching for a dependency too early. Reversing an array and popping from the end is a free O(1) queue for one-shot draining.

They might follow up with

  • When would you want an OrderedDictionary? When you need stable iteration, such as a form’s fields or a cache that evicts in insertion order.
  • How do you build a priority queue without a Heap? Keep a sorted array and binary search the insert position, fine for small sizes.

Related questions

  • 2.1.1 Array, Set or Dictionary: how do you choose, and what does each operation cost?
  • 2.1.4 How does an Array grow, and when do reserveCapacity and ContiguousArray help?

← What must Hashable guarantee, and why does iteration order change…   How does an Array grow, and when do reserveCapacity and… →