34

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.

Improve this question
1

3 Answers 3

Reset to default
33

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.

Improve this answer
8
  • 20
    NSOrderedSet is for any platform that includes Foundation. It's not just iOS.
    – rmaddy
    Commented Oct 2, 2017 at 22:36
  • 2
    Thank you, Tom – I'm reading around the subject currently. Yoda says, "Much to know, there is."
    – Benjohn
    Commented Oct 3, 2017 at 8:03
  • 3
    While you can use NSOrderedSet in swift it will always have a type of Any as it does not support generics
    – Konrad Piascik
    Commented Jul 13, 2018 at 14:02
  • 1
    @Benjohn I guess you are looking for something similar to OrderedSet where the elements are comparable and the data structure sorts the elements as they are inserted. Which is different from an orderedSet. I think some ppl have called this a SortedSet. You can find one implementation of this the data structure here. I definitely think one could build a great implementation of a SortedSet using OrderedSet.
    – J.beenie
    Commented Mar 30, 2020 at 1:04
  • 1
    Here is another implementation of SortedSet
    – J.beenie
    Commented Mar 30, 2020 at 4:05
9

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

Improve this answer
3

At the time being there is no ordered set in Swift. Despite using NSOrderedSet on all Apple platforms, you can simply combine a Set with an Array to basically get the same effect. The Set is used to avoid duplicate entries, the Array is used to store the order. Before adding a new element to the Array, check if it is in the Set already. When removing an element from the Array, also remove it from the Set. To check if an element exists, ask the Set, it's faster. To retrieve an element by index, use the Array. You can change the order of elements in the Array (e.g. resort it) without having to touch the Set at all. To iterate over all elements, use the Array as that way the elements are iterated in order.

Improve this answer
3
  • I'd say an ordered set is more like a set of (double-linked) list nodes so you'd get the benefits of O(1) lookups and can append/insert anywhere without constantly enumerating your array; or how would you suggest you handle insert before/after? Array inserts are O(n) worst case while inserting in a list would be O(1).
    – Ron
    Commented Sep 2, 2020 at 22:57
  • @Ron A double linked list has O(n) lookups, not O(1). It has only O(1) insertion and delete but only if the place for the operation is already known. All indexed operations would such be O(n) on such a linked list just for finding the place where to perform the operation, including objectAt:. One could also implement NSArray as a linked list but that would have the same disadvantages, which is why it isn't implemented that way.
    – Mecki
    Commented Sep 3, 2020 at 8:27
  • Not when you make dictionary values (or keys, depends) list nodes. Sorry I forgot to mention that previously. LRU cache anyone?
    – Ron
    Commented Oct 3, 2020 at 5:46

Not the answer you're looking for? Browse other questions tagged or ask your own question.