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.