# Map

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

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.

• ``` init() ```

Initialize an empty map.

#### Declaration

Swift

``public init()``
• ``` init(_:) ```

Initialize a new map from an unsorted sequence of elements, using a stable sort algorithm.

If the sequence contains elements with duplicate keys, only the last element is kept in the map.

Complexity

O(n * log(n)) where n is the number of items in `elements`.

#### Declaration

Swift

``public init<S: Sequence>(_ elements: S) where S.Iterator.Element == Element``
• ``` init(sortedElements:) ```

Initialize a new map from a sorted sequence of elements.

If the sequence contains elements with duplicate keys, only the last element is kept in the map.

Complexity

O(n) where n is the number of items in `elements`.

#### Declaration

Swift

``public init<S: Sequence>(sortedElements elements: S) where S.Iterator.Element == Element``
• ``` init(dictionaryLiteral:) ```

Initialize a new map from the given elements.

#### Declaration

Swift

``public init(dictionaryLiteral elements: (Key, Value)...)``
• ``` description ```

A textual representation of this map.

#### Declaration

Swift

``public var description: String``
• ``` debugDescription ```

A textual representation of this map, suitable for debugging.

#### Declaration

Swift

``public var debugDescription: String``
• ``` subscript(_:) ```

Return a submap consisting of elements in the given range of indexes.

Requires

The indexes in `range` originated from an unmutated copy of this map.

Complexity

O(log(`count`))

#### Declaration

Swift

``public subscript(range: Range<Index>) -> Map<Key, Value>``
• ``` subscript(_:) ```

Returns the (key, value) pair at the given index.

Requires

`index` originated from an unmutated copy of this map.

Complexity

O(1)

#### Declaration

Swift

``public subscript(index: Index) -> Element``
• ``` startIndex ```

The index of the first element when non-empty. Otherwise the same as `endIndex`.

Complexity

O(log(`count`))

#### Declaration

Swift

``public var startIndex: Index``
• ``` endIndex ```

The past-the-end element index; the successor of the last valid subscript argument.

Complexity

O(1)

#### Declaration

Swift

``public var endIndex: Index``
• ``` count ```

The number of (key, value) pairs in this map.

#### Declaration

Swift

``public var count: Int``
• ``` isEmpty ```

True iff this collection has no elements.

#### Declaration

Swift

``public var isEmpty: Bool``
• ``` makeIterator() ```

Return an iterator over all (key, value) pairs in this map, in ascending key order.

#### Declaration

Swift

``public func makeIterator() -> Iterator``
• ``` index(after:) ```

Returns the successor of the given index.

Requires

`index` is a valid index of this map and it is not equal to `endIndex`.

Complexity

Amortized O(1).

#### Declaration

Swift

``public func index(after index: Index) -> Index``
• ``` formIndex(after:) ```

Replaces the given index with its successor.

Requires

`index` is a valid index of this map and it is not equal to `endIndex`.

Complexity

Amortized O(1).

#### Declaration

Swift

``public func formIndex(after index: inout Index)``
• ``` index(before:) ```

Returns the predecessor of the given index.

Requires

`index` is a valid index of this map and it is not equal to `startIndex`.

Complexity

Amortized O(1).

#### Declaration

Swift

``public func index(before index: Index) -> Index``
• ``` formIndex(before:) ```

Replaces the given index with its predecessor.

Requires

`index` is a valid index of this map and it is not equal to `startIndex`.

Complexity

Amortized O(1).

#### Declaration

Swift

``public func formIndex(before index: inout Index)``
• ``` index(_:offsetBy:) ```

Returns an index that is the specified distance from the given index.

Requires

`index` must be a valid index of this map. If `n` is positive, it must not exceed the distance from `index` to `endIndex`. If `n` is negative, it must not be less than the distance from `index` to `startIndex`.

Complexity

O(log(count)) where count is the number of elements in the map.

#### Declaration

Swift

``public func index(_ i: Index, offsetBy n: Int) -> Index``
• ``` formIndex(_:offsetBy:) ```

Offsets the given index by the specified distance.

Requires

`index` must be a valid index of this map. If `n` is positive, it must not exceed the distance from `index` to `endIndex`. If `n` is negative, it must not be less than the distance from `index` to `startIndex`.

Complexity

O(log(count)) where count is the number of elements in the map.

#### Declaration

Swift

``public func formIndex(_ i: inout Index, offsetBy n: Int)``
• ``` index(_:offsetBy:limitedBy:) ```

Returns an index that is the specified distance from the given index, unless that distance is beyond a given limiting index.

Requires

`index` and `limit` must be valid indices in this map. The operation must not advance the index beyond `endIndex` or before `startIndex`.

Complexity

O(log(count)) where count is the number of elements in the map.

#### Declaration

Swift

``public func index(_ i: Index, offsetBy n: Int, limitedBy limit: Index) -> Index?``
• ``` formIndex(_:offsetBy:limitedBy:) ```

Offsets the given index by the specified distance, or so that it equals the given limiting index.

Requires

`index` and `limit` must be valid indices in this map. The operation must not advance the index beyond `endIndex` or before `startIndex`.

Complexity

O(log(count)) where count is the number of elements in the map.

#### Declaration

Swift

``public func formIndex(_ i: inout Index, offsetBy n: Int, limitedBy limit: Index) -> Bool``
• ``` distance(from:to:) ```

Returns the distance between two indices.

Requires

`start` and `end` must be valid indices in this map.

Complexity

O(1)

#### Declaration

Swift

``public func distance(from start: Index, to end: Index) -> Int``
• ``` forEach(_:) ```

Call `body` on each element in `self` in ascending key order.

Complexity

O(`count`)

#### Declaration

Swift

``public func forEach(_ body: (Element) throws -> ()) rethrows``
• ``` map(_:) ```

Return an `Array` containing the results of mapping `transform` over all elements in `self`. The elements are transformed in ascending key order.

Complexity

O(`count`)

#### Declaration

Swift

``public func map<T>(_ transform: (Element) throws -> T) rethrows -> [T]``
• ``` flatMap(_:) ```

Return an `Array` containing the concatenated results of mapping `transform` over `self`.

Complexity

O(`count`)

#### Declaration

Swift

``public func flatMap<S: Sequence>(_ transform: (Element) throws -> S) rethrows -> [S.Iterator.Element]``
• ``` flatMap(_:) ```

Return an `Array` containing the non-`nil` results of mapping `transform` over `self`.

Complexity

O(`count`)

#### Declaration

Swift

``public func flatMap<T>(_ transform: (Element) throws -> T?) rethrows -> [T]``
• ``` reduce(_:_:) ```

Calculate the left fold of this map over `combine`: return the result of repeatedly calling `combine` with an accumulated value initialized to `initial` and each element of `self`, in turn.

I.e., return `combine(combine(...combine(combine(initial, self), self),...self[count-2]), self[count-1])`.

Complexity

O(`count`)

#### Declaration

Swift

``public func reduce<T>(_ initialResult: T, _ nextPartialResult: (T, Element) throws -> T) rethrows -> T``
• ``` subscript(_:) ```

Provides access to the value for a given key. Nonexistent values are represented as `nil`.

Complexity

O(log(`count`))

#### Declaration

Swift

``public subscript(key: Key) -> Value?``
• ``` keys ```

A collection containing just the keys in this map, in ascending order.

#### Declaration

Swift

``public var keys: LazyMapCollection<Map<Key, Value>, Key>``
• ``` values ```

A collection containing just the values in this map, in order of ascending keys.

#### Declaration

Swift

``public var values: LazyMapCollection<Map<Key, Value>, Value>``
• ``` index(forKey:) ```

Returns the index for the given key, or `nil` if the key is not present in this map.

Complexity

O(log(`count`))

#### Declaration

Swift

``public func index(forKey key: Key) -> Index?``
• ``` updateValue(_:forKey:) ```

Update the value stored in the map for the given key, or, if they key does not exist, add a new key-value pair to the map. Returns the value that was replaced, or `nil` if a new key-value pair was added.

This method invalidates all existing indexes into `self`.

Complexity

O(log(`count`))

#### Declaration

Swift

``public mutating func updateValue(_ value: Value, forKey key: Key) -> Value?``
• ``` remove(at:) ```

Remove the key-value pair at `index` from this map.

This method invalidates all existing indexes into `self`.

Complexity

O(log(`count`))

#### Declaration

Swift

``public mutating func remove(at index: Index) -> (key: Key, value: Value)``
• ``` removeValue(forKey:) ```

Remove a given key and the associated value from this map. Returns the value that was removed, or `nil` if the key was not present in the map.

This method invalidates all existing indexes into `self`.

Complexity

O(log(`count`))

#### Declaration

Swift

``public mutating func removeValue(forKey key: Key) -> Value?``
• ``` removeAll() ```

Remove all elements from this map.

This method invalidates all existing indexes into `self`.

Complexity

O(`count`)

#### Declaration

Swift

``public mutating func removeAll()``
• ``` index(ofOffset:) ```

Returns the index of the element at `offset`.

Requires

`offset >= 0 && offset < count`

Complexity

O(log(`count`))

#### Declaration

Swift

``public func index(ofOffset offset: Int) -> Index``
• ``` offset(of:) ```

Returns the offset of the element at `index`.

Complexity

O(log(`count`))

#### Declaration

Swift

``public func offset(of index: Index) -> Int``
• ``` offset(of:) ```

Returns the offset of the element with the given key, or `nil` if there is no such element.

Complexity

O(log(`count`))

#### Declaration

Swift

``public func offset(of key: Key) -> Int?``
• ``` element(atOffset:) ```

Return the element stored at `offset` in this map.

Complexity

O(log(`count`))

#### Declaration

Swift

``public func element(atOffset offset: Int) -> Element``
• ``` updateValue(_:atOffset:) ```

Set the value of the element stored at `offset` in this map.

Complexity

O(log(`count`))

#### Declaration

Swift

``public mutating func updateValue(_ value: Value, atOffset offset: Int) -> Value``
• ``` remove(atOffset:) ```

Remove and return the (key, value) pair at the specified offset from the start of the map.

Complexity

O(log(`count`))

#### Declaration

Swift

``public mutating func remove(atOffset offset: Int) -> Element``
• ``` remove(atOffsets:) ```

Remove all (key, value) pairs in the specified offset range.

Complexity

O(log(`count`))

#### Declaration

Swift

``public mutating func remove(atOffsets offsets: Range<Int>)``
• ``` submap(with:) ```

Return a submap consisting of elements in the specified range of indexes.

Complexity

O(log(`count`))

#### Declaration

Swift

``public func submap(with range: Range<Index>) -> Map``
• ``` submap(withOffsets:) ```

Return a submap consisting of elements in the specified range of offsets.

Complexity

O(log(`count`))

#### Declaration

Swift

``public func submap(withOffsets offsets: Range<Int>) -> Map``
• ``` submap(from:to:) ```

Return a submap consisting of all elements with keys greater than or equal to `start` but less than `end`.

Complexity

O(log(`count`))

#### Declaration

Swift

``public func submap(from start: Key, to end: Key) -> Map``
• ``` submap(from:through:) ```

Return a submap consisting of all elements with keys greater than or equal to `start` but less than or equal to `end`.

Complexity

O(log(`count`))

#### Declaration

Swift

``public func submap(from start: Key, through end: Key) -> Map``
• ``` elementsEqual(_:by:) ```

Return `true` iff `self` and `other` contain equivalent elements, using `isEquivalent` as the equivalence test.

This method skips over shared subtrees when possible; this can drastically improve performance when the two maps are divergent mutations originating from the same value.

Requires

`isEquivalent` is an equivalence relation.

Complexity

O(`count`)

#### Declaration

Swift

``public func elementsEqual(_ other: Map, by isEquivalent: (Element, Element) throws -> Bool) rethrows -> Bool``
• ``` elementsEqual(_:) ```

Return `true` iff `self` and `other` contain equivalent elements.

This method skips over shared subtrees when possible; this can drastically improve performance when the two maps are divergent mutations originating from the same value.

Complexity

O(`count`)

#### Declaration

Swift

``public func elementsEqual(_ other: Map) -> Bool``
• ``` ==(_:_:) ```

Return true iff `a` is equal to `b`.

This function skips over shared subtrees when possible; this can drastically improve performance when the two maps are divergent mutations originating from the same value.

#### Declaration

Swift

``public static func ==(a: Map, b: Map) -> Bool``
• ``` !=(_:_:) ```

Return true iff `a` is not equal to `b`.

#### Declaration

Swift

``public static func !=(a: Map, b: Map) -> Bool``
• ``` merging(_:) ```

Return a map that combines elements from `self` with those in `other`. If a key is included in both maps, the value from `other` is used.

This function links subtrees containing elements with distinct keys when possible; this can drastically improve performance when the keys of the two maps aren’t too interleaved.

Complexity

O(`count`)

#### Declaration

Swift

``public func merging(_ other: Map) -> Map``
• ``` +(_:_:) ```

Return a map that combines elements from `a` with those in `b`. If a key is included in both maps, the value from `b` is used.

This function links subtrees containing elements with distinct keys when possible; this can drastically improve performance when the keys of the two maps aren’t too interleaved.

Complexity

O(`count`)

#### Declaration

Swift

``public static func +(a: Map, b: Map) -> Map``
• ``` including(_:) ```

Return a map that contains all elements in `self` whose keys are in `keys`.

Complexity

O(`keys.count` * log(`count`))

#### Declaration

Swift

``public func including(_ keys: SortedSet<Key>) -> Map``
• ``` including(_:) ```

Return a map that contains all elements in `self` whose keys are in `keys`.

Complexity

O(n * log(`count`)) where n is the number of keys in `keys`.

#### Declaration

Swift

``public func including<S: Sequence>(_ keys: S) -> Map where S.Iterator.Element == Key``
• ``` excluding(_:) ```

Return a map that contains all elements in `self` whose keys are not in `keys`.

Complexity

O(`keys.count` * log(`count`))

#### Declaration

Swift

``public func excluding(_ keys: SortedSet<Key>) -> Map``
• ``` excluding(_:) ```

Return a map that contains all elements in `self` whose keys are not in `keys`.

Complexity

O(n * log(`count`)) where n is the number of keys in `keys`.

#### Declaration

Swift

``public func excluding<S: Sequence>(_ keys: S) -> Map where S.Iterator.Element == Key``