Swift Set operation time complexity is not documented, and where to report this?

Using Swift
1

Hi there,

I'm looking at Swift Set operations, and notice the time complexity is not ducmented, e.g. for insert(), remove(), and contains()

I see Set adopts Hashable, which means I could assume Set.contains() is O(1), but for remove() and insert(), I'm not quite sure whether it's O(1) or could be O(n).

The soucre code of Set is also hard to tell: swift/Set.swift at main · apple/swift · GitHub

_variant.remove(member) is hard to tell what is _variant implementation.

Could someone help to clarify the time complexity, as well as where is the proper place to report this so Apple could add the doc?

Thanks.

1 Like
2

Should be this one, which is just a pair of find and remove. Looks like it's a regular hash table with some probing, so you could say that these operations are O(1) on average.

1 Like
3

Thanks @Lantua ! btw, how do you find the variant imp so fast? Any pattern I could learn?

4

The filename is usually quite telling. If you narrow down to files with Set in their names, it's not hard to spot SetVariant.swift. Even if not, it'd help reducing the number of files by a lot.