BT

Facilitating the Spread of Knowledge and Innovation in Professional Software Development

Write for InfoQ

Topics

Choose your language

InfoQ Homepage News Swift Collections Brings New Data Structures to Swift

Swift Collections Brings New Data Structures to Swift

This item in japanese

Swift Collections is a new open-source package that aims to extend the choice of data structures available to Swift programmers beyond those provided in the standard library. In its initial version, it offers deques, ordered sets, and ordered dictionaries.

Deques, short for double-ended queues, are similar to arrays but support efficient insertion and removal at both the beginning and the end, like in a FIFO queue. In particular, according to Swift engineer Karoy Lorentey's benchmarks, prepending an element is a constant-time operation for Deque and shows significant performance advantage over the same operation for Array starting with a collection size of 32 elements. This is accomplished by allocating deque elements in non-contiguous buffers, which makes them slightly slower than arrays for normal operations, though.

You can use the prepend method to insert a new element at the beginning of a deque and append to insert an element at the end. Similarly, you can use popFirst and popLast to pop elements from the deque ends.

var elements = Deque["e1", "e2"]

elements.prepend("e0")  // -> ["e0", "e1", "e2"]
elements.append("e3")  // -> ["e0", "e1", "e2", "e3"]

let e0 = elements.popFirst()
let e3 = elements.popLast()

OrderedSets ensure that each of their elements is unique and provide efficient membership tests with contains, while preserving the same order as they were appended to the set. Lorentey's benchmarks show a significant performance advantage over an unordered Set starting at approximately 64 elements when using contains. OrderedSets can be easily passed to functions expecting an Array argument using their .elements property. When SetAlgebra conformance is required, the .unordered property provides an unordered view of the set elements.

The third collection present in Swift Collections is OrderedDictionary, which preserves all desirable properties of dictionaries, like constant-time insert and access, while ensuring its elements remain in user-defined order. Again, while constant-time operation is granted, the constant for OrderedDictionary is slightly higher than for an unordered Dictionary. An OrderedDictionary consists of an OrderedSet of keys and a regular Array of elements, and both can be efficiently accessed using the .keys and .elements properties.

Swift Collections is similar in nature and intent to the Swift Numerics and Swift Algorithms packages, in that all of them attempt to provide data structures not available in the Standard Library in a way that may lead to their eventual inclusion in it through the official Swift evolution process.

Swift Collections is available on GitHub, and contributions are welcome, although they should meet stringent criteria as to reliability, performance, and memory usage, says Lorentey.

Rate this Article

Adoption
Style

BT