# Structs

The following structs are available globally.

• ``` SortedBag ```

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 `SortedBag`s may be cheaper than ordinary `Set`s, 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.

`SortedSet`
See more

#### Declaration

Swift

``public struct SortedBag<Element: Comparable>: SetAlgebra``
• ``` BTreeIterator ```

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

See more

#### Declaration

Swift

``public struct BTreeIterator<Key: Comparable, Value>: IteratorProtocol``
• ``` BTreeValueIterator ```

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

See more

#### Declaration

Swift

``public struct BTreeValueIterator<Value>: IteratorProtocol``
• ``` BTreeKeyIterator ```

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

See more

#### Declaration

Swift

``public struct BTreeKeyIterator<Key: Comparable>: IteratorProtocol``
• ``` BTree ```

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

See more

#### Declaration

Swift

``public struct BTree<Key: Comparable, Value>``
• ``` BTreeIndex ```

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.

`BTreeCursor` for an efficient way to modify a batch of values in a B-tree.
See more

#### Declaration

Swift

``public struct BTreeIndex<Key: Comparable, Value>``
• ``` List ```

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.

Note

`List` implements all formal requirements of `CollectionType`, but it violates the semantic requirement that indexing has O(1) complexity: subscripting a `List` costs `O(log(count))`, since it requires an offset lookup in the B-tree. However, B-trees for typical element sizes and counts are extremely shallow (less than 5 levels for a billion elements), so with practical element counts, offset lookup typically behaves more like `O(1)` than `O(log(count))`.
See more

#### Declaration

Swift

``public struct List<Element>``
• ``` SortedSet ```

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 `SortedSet`s may be cheaper than ordinary `Set`s, 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.

`SortedBag`
See more

#### Declaration

Swift

``public struct SortedSet<Element: Comparable>: SetAlgebra``
• ``` Map ```

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.

See more

#### Declaration

Swift

``public struct Map<Key: Comparable, Value>``