32

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.

Benjohn
  • 13,228
  • 9
  • 65
  • 127
  • You will need to use an array to keep the elements order. You can use this answer to filter the duplicates from your array https://stackoverflow.com/a/34712330/2303865 or make sure you only append to your array if it does not contain the element thats being appended https://stackoverflow.com/questions/46519004/can-somebody-give-a-snippet-of-append-if-not-exists-method-in-swift-array/46519116#46519116 – Leo Dabus Oct 02 '17 at 22:22

3 Answers3

31

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.

Tom Harrington
  • 69,312
  • 10
  • 146
  • 170
  • 19
    `NSOrderedSet` is for any platform that includes Foundation. It's not just iOS. – rmaddy Oct 02 '17 at 22:36
  • 2
    Thank you, Tom – I'm reading around the subject currently. Yoda says, "Much to know, there is." – Benjohn Oct 03 '17 at 08: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 Jul 13 '18 at 14:02
  • [A post here](https://airspeedvelocity.net/2015/07/22/a-persistent-tree-using-indirect-enums-in-swift/) implements a [persistent](https://en.wikipedia.org/wiki/Persistent_data_structure) [red black tree](https://en.wikipedia.org/wiki/Red–black_tree) in Swift. The post doesn't implement deletes as [shown here for Haskel](https://abhiroop.github.io/Haskell-Red-Black-Tree/). An apparently simpler approach is described [here](http://matt.might.net/articles/red-black-delete/) for [Racket](https://racket-lang.org) (a [Scheme](https://en.wikipedia.org/wiki/Scheme_(programming_language)) dialect). – Benjohn Dec 09 '18 at 22:50
  • Hey Tom – thanks for the diligent update! I just had a look at the `OrderedSet`. It has interesting semantics, but not what I'm looking for. It remembers the insertion order in to the `OrderedSet`, rather than maintaining the set's members with a total order as something like a red-black tree would. – Benjohn Apr 15 '19 at 15:17
  • 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](https://github.com/raywenderlich/swift-algorithm-club/blob/master/Sorted%20Set/SortedSet.swift). I definitely think one could build a great implementation of a SortedSet using `OrderedSet`. – J.beenie Mar 30 '20 at 01:04
  • 1
    Here is another implementation of [SortedSet](https://github.com/attaswift/BTree/blob/master/Sources/SortedSet.swift) – J.beenie Mar 30 '20 at 04:05
  • Hi again Tom – yes, the [SortedSet](https://github.com/attaswift/BTree/blob/master/Sources/SortedSet.swift) you point to is exactly the kind of thing I'm looking for. Thank you. – Benjohn Mar 31 '20 at 05:36
7

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

Yan Zhuang
  • 436
  • 3
  • 10
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.

Mecki
  • 125,244
  • 33
  • 244
  • 253
  • 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 Sep 02 '20 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 Sep 03 '20 at 08:27
  • Not when you make dictionary values (or keys, depends) list nodes. Sorry I forgot to mention that previously. LRU cache anyone? – Ron Oct 03 '20 at 05:46