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.

Initializers

  • 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
    Show on GitHub

  • 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
    Show on GitHub

Conversion to string

CollectionType

  • 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>
    Show on GitHub

  • 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
    Show on GitHub

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

    Complexity

    O(log(count))

    Declaration

    Swift

    public var startIndex: Index
    Show on GitHub

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

    Complexity

    O(1)

    Declaration

    Swift

    public var endIndex: Index
    Show on GitHub

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

    Declaration

    Swift

    public var count: Int
    Show on GitHub

  • True iff this collection has no elements.

    Declaration

    Swift

    public var isEmpty: Bool
    Show on GitHub

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

    Declaration

    Swift

    public func makeIterator() -> Iterator
    Show on GitHub

  • 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
    Show on GitHub

  • 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)
    Show on GitHub

  • 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
    Show on GitHub

  • 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)
    Show on GitHub

  • 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
    Show on GitHub

  • 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)
    Show on GitHub

  • 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?
    Show on GitHub

  • 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
    Show on GitHub

  • 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
    Show on GitHub

Algorithms

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

    Complexity

    O(count)

    Declaration

    Swift

    public func forEach(_ body: (Element) throws -> ()) rethrows
    Show on GitHub

  • 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]
    Show on GitHub

  • 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]
    Show on GitHub

  • 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]
    Show on GitHub

  • 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[0]), self[1]),...self[count-2]), self[count-1]).

    Complexity

    O(count)

    Declaration

    Swift

    public func reduce<T>(_ initialResult: T, _ nextPartialResult: (T, Element) throws -> T) rethrows -> T
    Show on GitHub

Dictionary-like methods

  • 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?
    Show on GitHub

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

    Declaration

    Swift

    public var keys: LazyMapCollection<Map<Key, Value>, Key>
    Show on GitHub

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

    Declaration

    Swift

    public var values: LazyMapCollection<Map<Key, Value>, Value>
    Show on GitHub

  • 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?
    Show on GitHub

  • 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?
    Show on GitHub

  • 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)
    Show on GitHub

  • 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?
    Show on GitHub

  • Remove all elements from this map.

    This method invalidates all existing indexes into self.

    Complexity

    O(count)

    Declaration

    Swift

    public mutating func removeAll()
    Show on GitHub

Offset-based access

  • 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
    Show on GitHub

  • Returns the offset of the element at index.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func offset(of index: Index) -> Int
    Show on GitHub

  • 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?
    Show on GitHub

  • Return the element stored at offset in this map.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func element(atOffset offset: Int) -> Element
    Show on GitHub

  • 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
    Show on GitHub

  • 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
    Show on GitHub

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

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func remove(atOffsets offsets: Range<Int>)
    Show on GitHub

Submaps

  • 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
    Show on GitHub

  • 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
    Show on GitHub

  • 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
    Show on GitHub

  • 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
    Show on GitHub

Equivalence

  • 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
    Show on GitHub

  • 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
    Show on GitHub

  • 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
    Show on GitHub

  • Return true iff a is not equal to b.

    Declaration

    Swift

    public static func !=(a: Map, b: Map) -> Bool
    Show on GitHub

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
    Show on GitHub

  • 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
    Show on GitHub

Including and excluding keys

  • 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
    Show on GitHub

  • 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
    Show on GitHub

  • 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
    Show on GitHub

  • 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
    Show on GitHub