Structs

A sorted collection of comparable elements; also known as a multiset. SortedBag is like a SortedSet except it can contain multiple members that are equal to each other. Lookup, insertion and removal of any element has logarithmic complexity.

SortedBag stores duplicate elements in their entirety; it doesn’t just count multiplicities. This is an important feature when equal elements can be distinguished by identity comparison or some other means. (If you’re OK with just counting duplicates, use a Map or a Dictionary with the multiplicity as the value.)

SortedBag is a struct with copy-on-write value semantics, like Swift’s standard collection types. It uses an in-memory b-tree for element storage, whose individual nodes may be shared with other sorted sets or bags. Mutating a bag whose storage is (partially or completely) shared requires copying of only O(log(count)) elements. (Thus, mutation of shared SortedBags may be cheaper than ordinary Sets, which need to copy all elements.)

Set operations on sorted bags (such as taking the union, intersection or difference) can take as little as O(log(n)) time if the elements in the input bags aren’t too interleaved.

An iterator for all elements stored in a B-tree, in ascending key order.

An iterator for the values stored in a B-tree with an empty key.

An iterator for the keys stored in a B-tree without a value.

B-trees are search trees that provide an ordered key-value store with excellent performance characteristics.

An index into a collection that uses a B-tree for storage.

BTree indices belong to a specific tree instance. Trying to use them with any other tree instance (including one holding the exact same elements, or one derived from a mutated version of the original instance) will cause a runtime error.

This index satisfies Collection’s requirement for O(1) access, but it is only suitable for read-only processing – most tree mutations will invalidate all existing indexes.

A random-access collection of arbitrary elements. List works like an Array, but lookup, insertion and removal of elements at any index have logarithmic complexity. (Array has O(1) lookup, but removal/insertion at an arbitrary index costs O(count).)

List is a struct with copy-on-write value semantics, like Swift’s standard collection types. It uses an in-memory B-tree for element storage, whose individual nodes may be shared with other lists. Mutating a list whose storage is (partially or completely) shared requires copying of only O(log(count)) elements. (Thus, mutation of shared lists may be relatively cheaper than arrays, which need to copy all elements.)

Lookup, insertion and removal of individual elements anywhere in a list have logarithmic complexity. Using the batch operations provided by List can often be much faster than processing individual elements one by one. For example, splitting a list or concatenating two lists can be done in O(log(n)) time.

A sorted collection of unique comparable elements. SortedSet is like Set in the standard library, but it always keeps its elements in ascending order. Lookup, insertion and removal of any element has logarithmic complexity.

SortedSet is a struct with copy-on-write value semantics, like Swift’s standard collection types. It uses an in-memory b-tree for element storage, whose individual nodes may be shared with other sorted sets. Mutating a set whose storage is (partially or completely) shared requires copying of only O(log(count)) elements. (Thus, mutation of shared SortedSets may be cheaper than ordinary Sets, which need to copy all elements.)

Set operations on sorted sets (such as taking the union, intersection or difference) can take as little as O(log(n)) time if the elements in the input sets aren’t too interleaved.

An ordered mapping from comparable keys to arbitrary values. Works like Dictionary, but provides a well-defined ordering for its elements.

Map is a struct with copy-on-write value semantics, like Swift’s standard collection types. It uses an in-memory B-tree for element storage, whose individual nodes may be shared with other maps. Modifying an element of a map whose storage is (partially or completely) shared requires copying of only O(log(count)) elements. (Thus, mutation of shared maps may be relatively cheaper than dictionaries, which need to clone all elements.)

Lookup, insertion and removal of individual key-value pairs in a map have logarithmic complexity. This is in contrast to Dictionary’s best-case O(1) (worst-case O(n)) implementations for the same operations. To make up for being typically slower, Map always keeps its elements in a well-defined order.

While independently looking up individual elements takes O(log(n)) time, batch operations on lots of elements often complete faster than you might expect. For example, iterating over a Map using the generator API requires O(n) time, just like a dictionary.

Due to its tree-based structure, Map is able to provide efficient implementations for several operations that would be slower with dictionaries.