If you’ve written code in languages other than Swift, you might have wondered why Swift doesn’t have ordered sets or dictionaries. Wonder no more! With the new open-source Swift Collections package by Apple, you now have the data structures for Swift you’ve been seeking.

In this tutorial, you’ll learn about:

• The three new data structures in the package: Deque, OrderedSet and OrderedDictionary.
• The differences and advantages of these new structures versus the built-in collection types in the Swift Standard Library.
• An alternative to ordered dictionaries that already exists in the Swift Standard Library.

OK. It’s time to get started!

Getting Started

Download the project materials by clicking the Download Materials button at the top or bottom of the tutorial. Open the starter project, which contains an Xcode workspace with a playground in it. The playground already includes the Swift Collections package as a dependency. You’ll need to wait for Xcode to download and build the package before you can start.

The playground contains three pages: one for Deque, one for OrderedSet and one for OrderedDictionary.

Each page already contains code to demonstrate how to use the closely-matching data structures that Swift already contains: Array, Set and Dictionary, as well as KeyValuePairs, which you may not have heard of before.

Run the code in each of the playground pages to check out the results. Each page creates one of the built-in data structures, then performs commonly-used operations on each. This will help set up a baseline of what the built-in types can do compared to the data structures available in the Swift Collections package.

Now that you’re familiar with the starter project, you’ll learn about the new data structures available in the Swift Collections package, starting with Deque.

Understanding Deque

Deque — pronounced “Deck”, derived from Double-Ended Queue — holds a sequence of values, just like an array. Unlike an array, a deque is super efficient at inserting or removing elements from its beginning or its end. An array is only optimized for adding or removing elements at its end.

You can think of the difference between the two queues by visualizing Array as a vertical stack of cubes and Deque as a horizontal row of cubes. It’s easy to add an element at the bottom of a stack of vertical cubes as long as there aren’t too many cubes. But as you add more cubes, adding a cube at the bottom of the stack becomes more difficult. It has a performance of O(n).

Adding cubes at the beginning or end of your row of cubes (Deque) is quick and easy. The performance of adding a cube at either end is O(1).

Deque vs. Array

Deque

Array

Now that you know what a deque is, you can jump straight into coding with it.

Working With Deque

Creating a deque is similar to creating an array. To try it, open the Deque page of MyPlayground and scroll to the bottom. Add the following code:

var deque = Deque<String>()

This creates a Deque ready to hold String elements. You can also create deque literals as you would with an array with the following code:

var anotherDeque: Deque = ["An Element"]

This creates a Deque with a single element.

Appending and Prepending With Deque

As you learned above, Deque efficiently inserts items both at the beginning and the end.

Deque offers the following ways to add items to a sequence:

• append(_:): Adds an item to the end of the sequence, exactly like Array.
• append(contentsOf:): Adds the contents of a collection to the end of the sequence, again exactly like Array.
• prepend(_:): Adds an item to the beginning of the sequence.
• prepend(contentsOf:): Adds the contents of a collection to the beginning of the sequence.

To add items to the start of an array, you’d have to use insert(_:at:) to specify not only the element you’re adding but also the index where you’re inserting it.

Add the following code at the end of your playground page to add some elements to your deque:

deque.append("Element 2")
deque.prepend("Element 1")
deque.append("Element 3")

Because Deque respects the order in which you added the elements, your playground will print out the following:

["Element 1", "Element 2", "Element 3"]

Your sequence’s contents are printed in the expected order given the order of your append and prepend calls.

Add the following code to your playground to test out adding the contents of a collection to your deque:

deque.append(contentsOf: ["Element 4", "Element 5"])
deque.prepend(contentsOf: ["Element 0"])

Run the playground and you’ll see the deque now contains elements 0 to 5, in order.

Removing Items From a Deque

Like Array, Deque also supports removing items from the beginning or end of a sequence. Add the following code to see this in action:

deque.removeFirst()
deque

removeFirst() acts like it would in an Array, removing the element at the beginning of the sequence. Your deque must not be empty when calling this.

You can use popLast() to remove items at the end of the sequence. It works the same as removeLast(), but it returns an optional value and is fine to use on a deque that may be empty. Add the following code to the playground to see how it works:

deque.popLast()
deque

Originally, your queue contained these elements:

["Element 1", "Element 2", "Element 3", "Element 4", "Element 5"]

Now, it looks like this:

["Element 1", "Element 2", "Element 3", "Element 4"]

The same concept applies to its counterpart, popFirst(), which removes elements at the beginning of the sequence.

Add the code below to the playground:

deque.popFirst()
deque

Before this call, your dequeue looked like:

["Element 1", "Element 2", "Element 3", "Element 4"]

Now, it looks like this:

["Element 2", "Element 3", "Element 4"]

You might be thinking that slightly more convenient methods when dealing with items at the start of a collection are not worth including a whole dependency in your project for. The real benefit of using deques over arrays comes down to performance, which you’ll look at next.

Comparing the Performance of Deque Versus Array

Using Deque to add items to the beginning of a large sequence is more performant. To compare the performance of inserting an element at the beginning of an Array versus a Deque, add the following code to the playground:

for number in 1...2000 {
  array.append("\(number)")
  deque.append("\(number)")
}

var start = Date()
array.insert("0", at: 0)
print(Date().timeIntervalSince(start))

start = Date()
deque.prepend("0")
print(Date().timeIntervalSince(start))

This code takes your existing sequences and adds two thousand elements into each. From there, you add an element at the beginning of each sequence and measure the time it takes.

Run your playground a couple of times and pay attention to the results. Notice how Deque is consistently faster than Array for this operation.

Knowing When to Use Deque

As you have seen, deques are very similar to arrays. Their main advantage lies in the increased efficiency when adding or removing to the beginning of the collection. However, as you’ve seen, the performance difference may be very small for a lot of cases. The only way to be sure that it’s worth using deques is to run performance testing, using Instruments, on a device. See our Instruments tutorial for more details.

All things considered, it’s great that Deque and Array are so similar because it’s quicker for you to learn and use Deque. You now have the option to use Deque when you need a more traditional double-ended queue.

In the next section, you’ll learn about a new type where the decision to use it or not is much more obvious.

Introducing OrderedSet

Here’s the major reason to rejoice about the Swift Collections package: OrderedSet!

Before this, it was frustrating to keep a unique list of items in a specific order in Swift, especially because that’s a common scenario. Think of an app that processes a store’s preorders. There can only be one preorder per customer. If you, Ray and I all want to preorder the next iPhone, Apple needs to know who placed the order first, second and last. While a Swift Array could work for this, you’d need to write extra code to prevent the user from adding duplicate items to the collection.

Set, the old alternative to Array, could maintain each element’s uniqueness, but it doesn’t maintain or guarantee the order. You could use a tuple or custom type to track the position or order, but this would get cumbersome, add extra code to your project and result in reduced performance compared to a proper, native set that maintains order.

Now, there’s a data structure that fills in both of those gaps: OrderedSet. It not only guarantees the uniqueness of elements, but it also maintains their order!

Ordered Set vs. Set

Ordered Set

Working With OrderedSet

Open the Ordered Set page in the playground and add the following code at the very bottom:

var orderedSet = OrderedSet<String>()

Voilà! You’ll see an OrderedSet of Swift strings. Like other Swift Collections, you can create an ordered set using a literal like this:

var orderedSet: OrderedSet<String> = []

Now, to add items to your ordered set, add the following code to your playground:

orderedSet.append(customer2)
orderedSet.append(customer1)
orderedSet.append(customer3)
orderedSet

As with many other collections in Swift, append(_:) adds elements to the OrderedSet. The resulting ordered set looks like this:

["Andrea", "James", "Ray"]

Notice that the ordered set respects the order in which you added the elements.

Checking for Equality Using OrderedSet

With OrderedSet, checking for equality against another collection works differently than with a regular Set. Set checks to ensure that both collections contain the exact same elements regardless of the order, whereas OrderedSet checks that the elements are the same and appear in the same order.

Add the following code to your playground to test this:

orderedSet == [customer2, customer1, customer3]

Compare that to the example code applied to set:

set == [customer1, customer2, customer3]

Notice that Set‘s elements were a different order than the collection you compared, but it still returned true when checking for equality.

Next, you’ll learn how to add an object to an existing OrderedSet.

Adding Elements to an Existing OrderedSet

To add an object when working with Set, you only need to specify an element to add to the collection. But with OrderedSet, you also need to include an index because it keeps track of the order of elements. To do this, add the following code to your playground:

var result = orderedSet.insert(customer4, at: orderedSet.startIndex)
orderedSet

This is the resulting collection:

["Elena", "Andrea", "James", "Ray"]

This code adds Elena to the beginning of your ordered set.

Next, you’ll learn how to remove an element.

Removing Elements From an OrderedSet

You can also remove elements from an ordered set using remove(). Add the following code to your playground:

orderedSet.remove(customer1)
orderedSet

Here, you specified the element you want to remove and let OrderedSet take care of it. You don’t have to worry about figuring out the index of the element you want to remove.

Unlike Set, OrderedSet implements most of SetAlgebra, but not all of it. This can be important should your project require it for backward compatibility with your existing code.

To try using SetAlgebra with OrderedSet, add the following code to your playground:

orderedSet.isSubset(of: allCustomers)

The result will be true, because this method checks to see if OrderedSet is a subset of allCustomers, not if the order of the elements is the same.

Knowing When to Use OrderedSet

Use your newfound best friend, OrderedSet, when you need to maintain both the uniqueness and the order of the elements in your collection. Otherwise, you can continue to use Set. This is especially true if you:

• Rely on SetAlgebra‘s’ operations and compliance
• Need to use elements to work with existing functions that don’t support OrderedSet.

Now, you’ll learn about how OrderedSet works to further help in your decision-making process.

Equality between two ordered sets happens when both the elements and their order are the same. In contrast, a Set only needs both sets to contain the same elements to have equality.

At the end of the previous section, you saw that OrderedSet implements most of SetAlgebra, but doesn’t conform to it. The documentation for Swift Collections mentions that OrderedSet is “incompatible with SetAlgebra’s documented semantic requirements” due to the way it checks the order of the elements when it compares for equality.

Operations that return an ordered set will usually take into account the original order of the elements. However, some, like isSubset(of:), do not.

If your code needs SetAlgebra, you could still potentially work with OrderedSet because it does have an unordered property that returns an unordered collection of your elements. The unordered collection it returns is of type UnorderedView.

Now, it’s time to move on to the performance side of OrderedSet.

As with with Set, the performance of your code will depend on the quality of hashing that the elements of your OrderedSet implement. This is great news because you don’t have to pay a performance penalty for using OrderedSet instead of Set. This differs from the penalty you pay for using Deque instead of Array in scenarios that the latter could handle gracefully.

Ordered Set vs. Set

Next, you’ll learn about the third new data structure in Swift Collections: OrderedDictionary.

Introducing OrderedDictionary

Your third new data structure friend is OrderedDictionary, which is to Dictionary what OrderedSet is to Set.

Like the regular Dictionary, OrderedDictionary works by using hash tables to ensure that two elements don’t share the same key. The advantage of OrderedDictionary, however, is that it keeps the elements in an order that you specify.

The iPhone preorder system from the OrderedSet section is also a good example of how an OrderedDictionary is useful.

In that system, you used OrderedSet to keep track of the order in which customers placed the preorders as well as which customer placed the order. Its limitation is that the only information associated with a customer is the name you stored in the ordered set.

With OrderedDictionary, you can keep track of your customers and the order in which the preorders were placed — stored as keys in the ordered dictionary. You can also have values for the order details for each customer.

A regular Swift Dictionary offers uniqueness for each customer, but doesn’t guarantee the order of the elements.

Ordered Dictionary vs. Dictionary

Dictionary

Ordered Dictionary

Working With OrderedDictionary

Open the OrderedDictionary playground page and scroll to the bottom. Add the following code to create your very own OrderedDictionary:

var orderedDictionary = OrderedDictionary<String, String>()

This creates an empty, mutable OrderedDictionary containing keys and values of type String.

Next, add the code below to populate your ordered dictionary with some elements:

orderedDictionary["Order 1"] = "Ray"
orderedDictionary["Order 2"] = "James"
orderedDictionary["Order 3"] = "Andrea"
orderedDictionary["Order 4"] = "Elena"
orderedDictionary

Hmmm. This looks similar, if not identical, to working with a regular Dictionary, right? Not quite. Find the line commented // Check the order of the output and look at the values exported from the regular dictionary. You’ll see the elements in a random order, completely different from the order in which you added them to the dictionary. The output of orderedDictionary will always be the same.

With an ordered dictionary, you are guaranteed that the keys and elements are in a consistent order. Add the following code to your playground:

orderedDictionary.keys
orderedDictionary.values.elements

Check the sidebar’s keys and elements after adding this code to verify their order.

If the order of keys and values is guaranteed, that means you can refer to items in the dictionary using indices. You’ll learn about that next.

Swapping Elements Using OrderedDictionary

Because OrderedDictionary maintains the elements’ order, you can use swapAt(_:_:), which allows you to exchange the position of two elements. With this, you don’t need to remove the elements and manually reinsert them in the correct location.

To see how you can swap elements, add the code below to your playground:

orderedDictionary.swapAt(1, 3)

Before, your elements were in the following order:

[
  "Order 1": "Ray", 
  "Order 2": "James", 
  "Order 3": "Andrea", 
  "Order 4": "Elena"
]

Now, they’re like this:

[
  "Order 1": "Ray",
  "Order 4": "Elena",
  "Order 3": "Andrea",
  "Order 2": "James"
]

Just as before, you can check your playground’s sidebar to see these elements.

You learned that ordered sets have different definitions of equality to sets. The same applies to ordered dictionaries and dictionaries.

Checking Equality With OrderedDictionary

As with OrderedSet, two ordered dictionaries must have the same elements in the same order to be considered equal.

Add the code below to check your dictionary’s equality against a second OrderedDictionary:

var secondDictionary = OrderedDictionary<String, String>()
secondDictionary["Order 1"] = "Ray"
secondDictionary["Order 2"] = "James"
secondDictionary["Order 3"] = "Andrea"
secondDictionary["Order 4"] = "Elena"
secondDictionary
orderedDictionary == secondDictionary

You’ll see they aren’t equal. Why? Because you swapped elements earlier. To fix this inequality, add the code below to the end of the file:

secondDictionary.swapAt(1, 3)
orderedDictionary == secondDictionary

The code above swaps the position of the two named elements. Now, the two dictionaries are equal.

Subscripting for OrderedDictionary

As with a regular Swift Dictionary, you can look up, add and remove values via subscripting. Add the following code to try it out:

orderedDictionary["Order 2"] = "Mary"
orderedDictionary

Here, you use subscripting to add the string Mary to your ordered dictionary for the key Order 2.

Make one last comparison between your two OrderedDictionaries to see if they’re equal:

orderedDictionary == secondDictionary

Because you’ve used subscripting to assign order 2 to Mary, the two dictionaries are no longer equal. Thus, the code above returns false.

One final thing that becomes relevant when you have a collection in a specified order is sorting.

Sorting an Ordered Dictionary

If the keys to your dictionary are Comparable, OrderedDictionary gives you access to another useful tool: sort(). As the name implies, it will sort your dictionary by comparing the keys. To see sorting in action, add the following snippet of code at the bottom of your playground:

orderedDictionary.sort()

The dictionary will now be sorted by key value:

[
  "Order 1": "Ray", 
  "Order 2": "Mary", 
  "Order 3": "Andrea", 
  "Order 4": "Elena"
]

To sort by the values instead of the keys, add the following code:

orderedDictionary.sort {
  $0.value < $1.value
}

Now the dictionary is ordered by value:

[
  "Order 3": "Andrea", 
  "Order 4": "Elena",
  "Order 2": "Mary",
  "Order 1": "Ray"
]

Ray is now at the back of the queue for a new iPhone!

You now know the basics about working with OrderedDictionary. But, there's an alternative you might not have heard of which could do the job for you, without having to include use the Collections package.

Understanding KeyValuePairs

In the OrderedDictionary playground page, you'll notice a section called KeyValuePairs.

As the name implies, KeyValuePairs is an ordered collection of key-value pairs. This collection is built-in as part of the Swift language; it's not part of the Swift Collections package. It acts like Dictionary but doesn't have fast key lookup.

There are three main advantages of KeyValuePairs:

• It's built in.
• It allows you to store an ordered collection of key-value pairs.
• Keys don't need to conform to Hashable protocol.

This data structure provides you with more flexibility, but searching for a value is slower because it must search through every element before returning a match. If you're dealing with a small collection of data and conforming to Hashable for the key types is an issue for you, it could be worth considering KeyValuePairs.

Knowing When to Use OrderedDictionary

Use OrderedDictionary when it's imperative to maintain the order of elements in your dictionary. But remember, even though OrderedDictionary is powerful, it has limitations.

Because OrderedDictionary has to maintain unique keys, the elements of the dictionary don't conform to MutableCollection or RangeReplaceableCollection. If your code relies on conforming to either of those protocols, you'll need to find an alternative.

Although OrderedDictionary doesn't conform to these protocols, it still supports mutations, or modifications, that change the order of its elements or remove a subset of its existing elements.

To insert elements efficiently, OrderedDictionary implements reserveCapacity(_:).

The performance of your OrderedDictionary, like Dictionary, depends on your key's implementation of Hashable.

Finally, Swift Dictionary literals are also ordered. As they are built into the language, like KeyValuePairs, they offer a good alternative to OrderedDictionary that doesn't require importing the Swift Collections package.

Ordered Dictionary vs. Dictionary

And that's it! Congratulations on finishing the tutorial. You should now have a clear understanding of three new tools from the Swift Collections package.

Where to Go From Here?

Download the final project by clicking the Download Materials button at the top or bottom of this tutorial.

You can expand your knowledge by working with collections in your own apps and by checking out the following resources:

• You can find the entire Swift Collections GitHub repository and documentation here.
• Read the Data Structures and Algorithms in Swift book. You'll not only learn how a lot of common data structures and algorithms work, but also how to write your own.
• You can also peruse the Swift Algorithms Club web page. It will teach you how to implement popular algorithms and data structures in Swift

This tutorial was a mere glimpse into Apple's new Swift Collections package. You can expect this package to expand in the future as more specialized collection types are added.

Thanks for reading this tutorial. We hope you enjoyed it. If you have any questions or comments, please leave a comment in our forums. Till next time!