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

Using Swift
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: ""))
6 Likes