Does anyone know what the data structure inside an IndexSet is?
The docs don't seem to say anything about it, or about performance bounds of basic ops like insert, remove, contains. Ie, are they O(1), O(log(n))?
If I'm going to use IndexSet in a performance critical place it would be nice to know.
I'm trying some performance tests and it seems like IndexSet and Set<Int> are about the same in Debug build, but in a Release build Set<Int> is doing much better.
While I'm not too familiar with the internals, my understanding is that it optimizes its contents into Ranges whenever possible to conserve memory. For example an IndexSet of [1, 2, 3, 4, 5, 7] will be represented under the hood as [1...5, 7...7].
Here’s the source: swift-corelibs-foundation/NSIndexSet.swift at main · apple/swift-corelibs-foundation · GitHub
It appears to use an Array of ranges. You might also consider using the standard library’s new RangeSet type.
If IndexSet saves memory but has lower performance than a plain Set<Int>, this should be noted in the documentation.