Does `Dictionary.Keys.contains(_:)` have `O(1)` time complexity?

(Alexander Momchilov) #1

This question stemmed from this StackOverflow post, in which it was called into question whether Dictionary.Keys.contains(_:) has linear or constant time complexity.

I saw this Swift evolution proposal, Provide Custom Collections for Dictionary Keys and Values, which was implemented for Swift 4, and specifically calls out this issue as something it aims to improve.

Yet, when I look at the implementation of Dictionary.Keys, I don't see anything that would suggest that it has hash-based, O(1) behavior for .contains(_:) calls. I was expecting to find an overload of contains(_:) that forwards to self._variant, but that's not the case.

So what's going on here?

(Hamish Knight) #2

Dictionary.Keys implements _customContainsEquatableElement, which is a customisation point of Sequence that's called from contains(_ element:).

Dictionary.Key's implementation of this customisation point forwards the call onto the underlying variant buffer which indeed performs the lookup in O(1) time. So yes, dict.key.contains(key) is an O(1) operation.

(Alexander Momchilov) #3

Hey Hamish. Great find!

Do you know why this was implemented in this way? What's the advantage over having types merely provide their own contains(_:) function?

(Hamish Knight) #4

The problem with making contains(_:) itself a customisation point is the fact that it requires Element to conform to Equatable, which cannot be expressed on a customisation point, e.g we cannot say:

protocol Sequence {
  associatedtype Element

  // ...
  func contains(_ element: Element) -> Bool where Element : Equatable

and there's no sensible default implementation for the case where the Element isn't Equatable.

_customContainsEquatableElement solves this problem by returning a Bool?, allowing the default implementation to return nil, which covers both the case where Element isn't Equatable and the type doesn't provide a custom implementation. The reason why it's underscored is due to the fact that it's an implementation detail of the conforming type.

The importance of being a customisation point is the fact that customisation points are dynamically dispatched, allowing them to be called from a generic context. If Dictionary.Key had just defined its own contains(_:) method, while it would get called for a direct call to dict.keys.contains(key), it would not get called from a generic context such as:

func foo<S : Sequence>(_ sequence: S, element: S.Element) -> Bool where S.Element : Equatable {
  return sequence.contains(element)

let dict = ["": 0]
print(foo(dict.keys, element: ""))

(Slava Pestov) #5

We have in the past discussed allowing 'where' clauses for non-generic declarations too, as long as they're nested inside a generic context (however there might be other reasons to implement contains(_:) the way its implemented today).