Is it safe to remove values from a Dictionary while iterating over its keys?

Using Swift
1

Based on my experience in other languages, I had been assuming this was perfectly safe in Swift:

var dict = [ "a": true, "b": false, "c": true, "d": false, "e": true, "f": false ]

for key in dict.keys {
    if dict[key] ?? false {
        dict.removeValue(forKey: key) // modify dict while iterating over its keys
    }
}

But is it safe? Or do I need to do this instead?

let keys = Array(dict.keys) // make a copy of the keys first

for key in keys {
    if dict[key] ?? false {
        dict.removeValue(forKey: key)
    }
}

I tried looking in the docs, but couldn’t find an answer one way or the other. I did find the Dictionary.Keys docs that describe it as “A view of a dictionary’s keys.” The word “view” gave me some pause.

In all my experience and testing, the first example does seem safe in Swift. But it would be great to have confirmation one way or the other. (And it would also be great to update the docs with this information, if it’s not already there somewhere.)

1 Like
2

Interesting question.

SE-0154: Provide Custom Collections for Dictionary Keys and Values doesn't seem to make any guarantees about this, either.

I looked at how Dictionary.Keys is implemented: https://github.com/swiftlang/swift/blob/cab1d1525d2de722fb0c2293033e737a8ac40f4b/stdlib/public/core/Dictionary.swift#L1296-L1307 (this link points to the current tip of the release/6.2 branch):

  @frozen
  public struct Keys: Collection, Equatable {
    …
    @usableFromInline
    internal var _variant: Dictionary<Key, Value>._Variant

    @inlinable
    internal init(_dictionary: __owned Dictionary) {
      self._variant = _dictionary._variant
    }
    …

This tells us:

  • Dictionary.Keys stores the entire dictionary (Dictionary._Variant is effectively the entire dictionary). The assignment in the initializer is cheap because of copy-on-write (no actual copy of the dictionary storage at this point), but see below for a caveat.
  • Iterating over the keys then iterates over this stored dictionary.
  • Since the struct is @frozen, the implementation cannot be changed in the future without breaking ABI.

Conclusion: yes, mutating the dictionary while iterating over the keys is safe in practice, even if it may not be officially documented/guaranteed.

But: your second variant (creating a separate array from the keys) can be more efficient because it avoids a copy of the dictionary on mutation.

In your first variant, the keys collection maintains another reference to the underlying dictionary storage during iteration. The first mutation of the dictionary in the loop is then forced to make an independent copy of the dictionary's storage.

3 Likes
3

(post deleted by author)

4

Thank you!

If it really is safe, and changing it would require breaking the ABI, then it definitely seems like it should be documented somewhere. (The nuance about making a copy on modification due to the reference held by the keys struct is a subtlety that probably doesn’t need to be in the basic language docs, but it’s good to know.)

1 Like
5

"Views" over the standard library collections generally still have independent value semantics unless specified otherwise. (I agree that, especially with the advent of noncopyable types and dependent views, it'd be good to spell this out more consistently in documentation.) So the iterated value that for key in dict.keys operates on is guaranteed to remain the value of dict.keys as it appeared prior to beginning iteration, even if dict is later modified. This might trigger a COW on the dictionary, but your code is sound.

9 Likes