OrderedSet In Swift

Many iOS and macOS applications use Set for internal logic. A new Swift package called swift-collections introduces OrderedSet, a set which keeps track of insertion order. This post presents an overview of OrderedSet and usage examples:

  1. OrderedSet Examples
    a. Insert Element
    b. Get Element
    c. Remove Element
    d. Union
    e. Intersection
  2. Set vs OrderedSet
    a. OrderedSet Maintains Insert Order
    b. OrderedSet Insert Performance Differs
  3. When To Use OrderedSet
    a. Time-Series Deduplication

Note: To use OrderedSet, first add the swift-collections Swift package to your project. Then, import the OrderedCollections module:

import OrderedCollections

OrderedSet Examples

Insert Element

var orderedSet = OrderedSet(["id0", "id1"])
orderedSet.append("id2")

// OrderedSet now contains, in order,
// "id0", "id1", "id2"

Get Element

A traditional Set does not have an interface to "get" an element, only contains(_:) -> Bool to determine if the Set includes a specific element. OrderedSet implements contains(_:) -> Bool as well, and also allows elements to be retrieved by the position of the element in the order:

var orderedSet = OrderedSet(["id0", "id1", “id2”])

// orderedSet contains, in order, 
// "id0", "id1", "id2". Getting the element
// at index 1 returns “id1”

// Get the element at index 1
orderedSet[1] // "id1"

Remove Element

There are multiple ways to remove elements from an OrderedSet. One way is to remove an element explicitly, either specifying the element directly or the index the element is at:

// Remove a specific element
orderedSet.remove("id2")

// Remove an element at a specific index
orderedSet.remove(at: 2)

Another method is to remove elements relative to the front and back of the OrderedSet:

// Remove elements from the front
orderedSet.removeFirst()
orderedSet.removeFirst(2)

// Remove elements from the back
orderedSet.removeLast()
orderedSet.removeLast(2)

OrderedSet also includes methods for removing all elements, and removing all elements that meet some filter criteria:

// Remove all elements
orderedSet.removeAll()

// Filter elements
orderedSet.removeAll { (element) -> Bool in
    // Filter criteria
}

Union

A union between a Set and another Set returns a new Set with elements of both source sets. Similarly, a union between an OrderedSet and another OrderedSet (or sequence) returns a new OrderedSet with elements of both sources. In an OrderedSet union, new elements are appended to the back of the OrderedSet.

let orderedSet = OrderedSet(["id0", "id1"])
var newOrderedSet = orderedSet.union([
    "id1", "newId", "id0"
])

// newOrderedSet now contains, in order,
// "id0", "id1", "newId"

Intersection

An intersection between a Set and another Set returns a new Set with only common elements of both source sets. Similarly, an intersection between an OrderedSet and another OrderedSet (or sequence) returns a new OrderedSet with only common elements of both sources. In an OrderedSet intersection, elements are ordered according to the OrderedSet on which union(_:) was called:

let orderedSet = OrderedSet([
    "id0", "id1", "id2", "id3", "id4"
])

var newOrderedSet = orderedSet.intersection([
    "id3", "id2", "id0"
])

// newOrderedSet now contains, in order,
// "id0", "id2", "id3"

Set vs OrderedSet

Set is an unordered collection of unique elements, often used to test if an element belongs to a set. Like Set, OrderedSet contains unique elements and can be used to test if an element belongs to a set. Unlike Set:

OrderedSet Maintains Insert Order

As the name indicates, OrderedSet maintains element order. This means an OrderedSet can efficiently check if an element is within the OrderedSet, like a traditional Set, and also retrieve elements at a specific position, like a traditional Array.

To maintain element order, OrderedSet has a different interface than Set. Instead of implementing add(_:) to add elements, OrderedSet implements append(_:) and insert(_:, at:) for greater clarity on how the order is modified. OrderedSet.append(_:) adds an element to the back of an OrderedSet (if the element is not already in the OrderedSet), and insert(_:, at:) adds an element at a specific index in the OrderedSet.

OrderedSet Insert Performance Differs

An OrderedSet implementation requires additional logic for insertions and removals to maintain element order. The swift-collections README details the performance impact:

"these operations are expected to have performance characteristics similar to an Array: inserting or removing an element to the end of an ordered set is expected to execute in O(1) operations, while they are expected to take linear time at the front (or in the middle) of the set"

This means that repeated calls to insert(_:, at:) or remove(at:) at the front or the middle of an OrderedSet will take longer than repeated append(_:) or removeLast() calls.

When To Use OrderedSet

Time-Series Deduplication

In some cases, for example a time series of data points, deduplication requires order to be perseved. An OrderedSet can deduplicate ordered elements while preserving the original element order:

var timeSeries = [
    ["id": "0", "value": "0"],
    ["id": "1", "value": "1"],
    ["id": "0", "value": "0"],
    ["id": "2", "value": "2"],
    ["id": "1", "value": "1"]
]

var orderedUniqueSeries = OrderedSet(timeSeries)
// orderedUniqueSeries contains, in order,
//    ["id": "0", "value": "0"],
//    ["id": "1", "value": "1"],
//    ["id": "2", "value": "2"]

// Iterating over an OrderdSet always
// yields elements in order
for item in orderedUniqueSeries {
    print("\(item["id"]!)")
}

// Expected console output:
// "0"
// "1"
// "2"

FREE all Swift loading animations.

Loading Animation Example

Follow AdvancedSwift and immediately get access to commented code for these animations that you can use in your projects.

Swift OrderedSet

That’s it! By using the swift-collections package and OrderedSet, you can take advantage of both Set properties and element ordering in Swift.