Swift Ordered Set

Question

Does Swift have an ordered set type? And if not, what are my options if I want to use one?

The standard library's Set is unordered, as is made clear in the documentation:

Arrays are ordered collections of values. Sets are unordered collections of unique values. Dictionaries are unordered collections of key-value associations.

However, many data structures suitable for implementing ordered sets (and dictionaries) are known, in particular balanced binary trees such as Red-Black trees.

As an example of this, c++'s stl has ordered sets and maps, and allows range queries on them using lower and upper bounds.

I know that a set's members can be sorted in to an array, but I am after a data structure with O(log(n)) insertion, removal and query.

Answer 1

Swift does not have a native ordered set type. If you use Foundation, you can use NSOrderedSet in Swift. If not, you have the opportunity to write your own ordered set data structure.

Update: Swift Package Manager includes an OrderedSet implementation that may be useful. It wraps both an array and a set and manages access to get ordered set behavior.

Update #2: Apple's Swift Collections repository contains an ordered set implementation.

Answer 2

On April 6th, 2021, a new package of Swift was released: Swift-Collection where three more data structures have been implemented. (OrderedSet, OrderedDictionary, Deque)

However, this package is in its pre-1.0 release state. As a result, it might not be stable.

Swift blog: Release of Swift Collections