SortedDictionary

public struct SortedDictionary<Key, Value> : DictionaryCollection where Key : Comparable

A collection whose elements are key and value pairs, sorted by keys.

SortedDictionary is implemented using Red-Black Tree, so can perform insertion, search, deletion operations in logarithmic time.

Unlike Dictionary.Values, SortedDictionary.Values doesn’t conform to MutableCollection.

Example

let countries = ["Singapore", "Canada", "Sweden", "Egypt", "Croatia"]
var d1 = SortedDictionary(grouping: countries) {
    country in String(country.first!)
}
print(d1["C"]!) // ["Canada", "Croatia"]
print(d1) // ["C": ["Canada", "Croatia"], "E": ["Egypt"], "S": ["Singapore", "Sweden"]]

d1["G", default: []].append("Greece")
d1["E", default: []].append("Ecuador")
print(d1) // ["C": ["Canada", "Croatia"], "E": ["Egypt", "Ecuador"], "G": ["Greece"], "S": ["Singapore", "Sweden"]]

let d2 = d1.compactMapValues {
    v in v.count > 1 ? v.map { $0.uppercased() } : nil
}
print(d2) // ["C": ["CANADA", "CROATIA"], "E": ["EGYPT", "ECUADOR"], "S": ["SINGAPORE", "SWEDEN"]]

Element
The element type of a SortedDictionary: a tuple containing an individual key-value pair.
Declaration
Swift

public typealias Element = (key: Key, value: Value)
init()
Creates an empty SortedDictionary.
Declaration
Swift

@inlinable @inline(__always) public init()


                    
                    
                    init(uniqueKeysWithValues:)

Creates a new SortedDictionary, initializing its contents with the given key and value pairs keysAndvalues.

let keys_and_values = [("c", 3), ("b", 2), ("d", 4), ("a", 1)]
let d = SortedDictionary(uniqueKeysWithValues: keys_and_values)
// ["a": 1, "b": 2, "c": 3, "d": 4]

Precondition

Keys must be unique.

Declaration

Swift

@inlinable
public init<S: Sequence>(uniqueKeysWithValues keysAndValues: S)
    where S.Element == (Key, Value)

Parameters


                                keysAndValues

A sequence of key and value pairs.

Return Value

A new SortedDictionary initialized with the elements of keysAndValues.


                    
                    
                    init(_:uniquingKeysWith:)

Creates a new SortedDictionary, initializing its contents with the given key and value pairs keysAndValues, eliminating values that have duplicate key using closure combine.

let keys_and_values = [("b", 2), ("a", 1), ("a", 3), ("b", 4)]
let d1 = SortedDictionary(keys_and_values) { old, _ in old }
// ["a": 1, "b": 2]
let d2 = SortedDictionary(keys_and_values) { _, new in new }
// ["a": 3, "b": 4]

Declaration

Swift

@inlinable
public init<S: Sequence>(
    _ keysAndValues: S,
    uniquingKeysWith combine: (Value, Value) throws -> Value) rethrows
    where S.Element == (Key, Value)

Parameters

`keysAndValues`	A sequence of key and value pairs.
`combine`	A closure that is called with the old and new values for duplicate key.


                    
                    
                    init(grouping:by:)

Creates a new SortedDictionary, initializing its contents with the given values and its key retrieving from closure keyForValue.

let countries = ["Singapore", "Canada", "Sweden", "Egypt", "Croatia"]
let countries_by_first_letter =
    SortedDictionary(grouping: countries) {
        country in String(country.first!)
    }
// ["C": ["Canada", "Croatia"], "E": ["Egypt"],
//  "S": ["Singapore", "Sweden"]]

Declaration

Swift

@inlinable
public init<S: Sequence>(
    grouping values: S, by keyForValue: (S.Element) throws -> Key) rethrows
    where Value == [S.Element]

Parameters

`values`	A sequence of values.
`keyForValue`	A closure that is called with each element in `values` and returns its key.


                    
                    
                    updateValue(_:forKey:)

Updates the value associated with the key. If the SortedDictionary does not contain element whose key is equivalent to key, inserts key and value pair.

Complexity

O(log n), where n is the length of the SortedDictionary.

Declaration

Swift

@discardableResult
@inlinable
public mutating func updateValue(
    _ value: Value, forKey key: Key) -> Value?

Parameters

`value`	The new value for `key`.
`key`	The key for `value`.

Return Value

If the new element was inserted, nil, otherwise the old value.


                    
                    
                    merge(_:uniquingKeysWith:)

Merges key and value pairs into the SortedDictionary, eliminating values that have duplicate key using closure combine.

Complexity

O(n * log(m + n)), where m is the length of the SortedDictionary and n is the length of the keysAndValues.

Declaration

Swift

@inlinable
public mutating func merge<S: Sequence>(
    _ keysAndValues: S,
    uniquingKeysWith combine: (Value, Value) throws -> Value) rethrows
    where S.Element == (Key, Value)

Parameters

`keysAndValues`	A sequence of key and value pairs.
`combine`	A closure that is called with the old and new values for duplicate key.


                    
                    
                    merge(_:uniquingKeysWith:)

Merges the other SortedDictionary into the SortedDictionary, eliminating values that have duplicate key using closure combine.

Complexity

O(m + n), where m is the length of this SortedDictionary and n is the length of the other SortedDictionary.

Declaration

Swift

@inlinable
public mutating func merge(
    _ other: SortedDictionary,
    uniquingKeysWith combine: (Value, Value) throws -> Value) rethrows

Parameters

`other`	An other SortedDictionary.
`combine`	A closure that is called with the old and new values for duplicate key.


                    
                    
                    merging(_:uniquingKeysWith:)

Creates a new SortedDictionary by merging this SortedDictionary and the given sequence, eliminating values that have dupliacte key using closure combine.

Complexity

O(n * log(n)), where n is the length of the resulting SortedDictionary.

Declaration

Swift

@inlinable
public func merging<S: Sequence>(
    _ other: S,
    uniquingKeysWith combine: (Value, Value) throws -> Value) rethrows
    -> SortedDictionary where S.Element == (Key, Value)

Parameters

`keysAndValues`	A sequence of key and value pairs.
`combine`	A closure that is called with the old and new values for duplicate key.


                    
                    
                    merging(_:uniquingKeysWith:)

Creates a new SortedDictionary by merging the SortedDictionary and the other SortedDictionary, eliminating values that have dupliacte key using closure combine.

Complexity

O(m + n), where m is the length of this SortedDictionary and n is the length of the other SortedDictionary.

Declaration

Swift

@inlinable
public func merging(
    _ other: SortedDictionary,
    uniquingKeysWith combine: (Value, Value) throws -> Value) rethrows
    -> SortedDictionary

Parameters

`other`	An other SortedDictionary.
`combine`	A closure that is called with the old and new values for duplicate key.


                    
                    
                    subscript(_:)

Accesses the value for the specified key.

If you assign nil to the value for the specified key, the element whose key is equivalent to key is deleted.

Complexity

O(log n), where n is the length of this SortedDictionary.

Declaration

Swift

@inlinable
public subscript(key: Key) -> Value? { get set }

Parameters

key

The key for the value.

Return Value

The value for the specified key if the element exists in this SortedDictionary, otherwise nil.


                    
                    
                    subscript(_:default:)

Accesses the value for the specified key.

If the SortedDictionary doesn’t contain the element whose key is equivalent to key, the key and defaultValue pair is inserted into the SortedDictionary.

Complexity

O(log n), where n is the length of this SortedDictionary.

Declaration

Swift

@inlinable
public subscript(
    key: Key,
    default defaultValue: @autoclosure () -> Value) -> Value

Parameters

`key`	The key for the value.
`default`	The default value for the key.

Return Value

The value for the specified key if the element exists in this SortedDictionary, or defaultValue.


                    
                    
                    mapValues(_:)

Creates a new SortedDictionary whose values are transformed by the given closure transform.

Complexity

O(n), where n is the length of the SortedDictionary.

Declaration

Swift

@inlinable
public func mapValues<T>(
    _ transform: (Value) throws -> T) rethrows
    -> SortedDictionary<Key, T>

Parameters


                                transform

A closure that is called with each value in this SortedDictionary and returns a transformed value.

Return Value

A SortedDictionary whose values are transformed.


                    
                    
                    compactMapValues(_:)

Creates a new SortedDictionary whose values are transformed by the given closure transform and the results aren’t nil.

Complexity

O(m + n), where m is the length of the original SortedDictionary and n is the length of the resulting SortedDictionary.

Declaration

Swift

@inlinable
public func compactMapValues<T>(
    _ transform: (Value) throws -> T?) rethrows
    -> SortedDictionary<Key, T>

Parameters


                                transform

A closure that is called with each value in this SortedDictionary and returns an optional transformed value.

Return Value

A SortedDictionary whose values are non-nil transformed.


                    
                    
                    filter(_:)

Creates a new SortedDictionary whose only elements for which the given closure isIncluded returns true.

Complexity

O(m + n), where m is the length of the original SortedDictionary and n is the length of the resulting SortedDictionary.

Declaration

Swift

@inlinable
public func filter(_ isIncluded: (Element) throws -> Bool) rethrows
    -> SortedDictionary

Parameters


                                isIncluded

A closure that is called with each element in this SortedDictionary and returns whether the element should be included in the result.

Return Value

A SortedDictionary whose elements for which the given closure isIncluded returns true.


                    
                    
                    removeValue(forKey:)

Removes the element for the specified key.

Complexity

O(log n), where n is the length of this SortedDictionary.

Declaration

Swift

@discardableResult
@inlinable
@inline(__always)
public mutating func removeValue(forKey key: Key) -> Value?

Parameters

key

The key for the element to remove.

Return Value

If the element for the specified key was removed, returns the value of the element, otherwise nil.


                    
                    
                    remove(at:)

Removes the element for the specified index.

Complexity

Amortized O(1).

Declaration

Swift

@discardableResult
@inlinable
@inline(__always)
public mutating func remove(at position: Index) -> Element

Parameters


                                position

The index for the element to remove.

Return Value

If the element for the specified key was removed, returns the value of the element, otherwise nil.


                    
                    
                    removeAll(keepingCapacity:)

Removes all elements in the SortedDictionary.

Complexity

O(n), where n is the length of this SortedDictionary.

Note

keepingCapacity is always ignored.

Declaration

Swift

@inlinable
@inline(__always)
public mutating func removeAll(
    keepingCapacity keepCapacity: Bool = false)

Parameters


                                keepCapacity

The value is always ignored.


                    
                    
                    lowerBound(of:)

Returns an index to the element with key not less than key in the SortedDictionary.

Complexity

O(log n), where n is the length of this SortedDictionary.

Declaration

Swift

@inlinable
@inline(__always)
public func lowerBound(of key: Key) -> Index

Parameters

key

the key for the element.

Return Value

The index to the element if it exists in the sorted dictionary, otherwise endIndex.


                    
                    
                    upperBound(of:)

Returns an index to the element with key greater than key in the SortedDictionary.

Complexity

O(log n), where n is the length of this SortedDictionary.

Declaration

Swift

@inlinable
@inline(__always)
public func upperBound(of key: Key) -> Index

Parameters

key

the key for the element.

Return Value

The index to the element if it exists in this SortedDictionary, otherwise endIndex.


                    
                    
                    updateValue(_:at:)

Updates the value of the element for the specified index.

Complexity

O(1).

Declaration

Swift

@discardableResult
@inlinable
@inline(__always)
public mutating func updateValue(_ value: Value, at position: Index)
    -> Value

Parameters

`value`	The new value for `key`.
`position`	The index for the element to update.

Return Value

The old value for key.


                    
                    
                    subscript(_:hint:)

Accesses the value for the specified key.

If you assign nil to the value for the specified key, the element whose key is equivalent to key is deleted.

Complexity

O(log n), where n is the length of this SortedDictionary. If the new element for key is located either at, or just before, or just after hint, amortized O(1).

Declaration

Swift

@inlinable
public subscript(key: Key, hint hint: Index) -> Value? { get set }

Parameters

`key`	The key for the value.
`hint`	The closest position where the element for `key` is located.

Return Value

The value for the specified key if the element exists in this SortedDictionary, otherwise nil.


                    
                    
                    subscript(_:hint:default:)

Accesses the value for the specified key.

If the SortedDictionary doesn’t contain the element whose key is equivalent to key, the key and defaultValue pair is inserted into the SortedDictionary.

Complexity

O(log n), where n is the length of this SortedDictionary. If the new element for key is located either at, or just before, or just after hint, amortized O(1).

Declaration

Swift

@inlinable
public subscript(
    key: Key, hint hint: Index,
    default defaultValue: @autoclosure () -> Value) -> Value

Parameters

`key`	The key for the value.
`hint`	The closest position where the element for `key` is located.
`default`	The default value for the key.

Return Value

The value for the specified key if the element exists in this SortedDictionary, or defaultValue.


                    
                    
                    init(_:)

Creates a new SortedDictionary, initializing its contents with the given Dictionary.

Declaration

Swift

@inlinable
@inline(__always)
public init(_ dictionary: Dictionary<Key, Value>)

Parameters


                                dictionary

A Dictionary.

Return Value

A new dictionary initialized with the elements of dictionary.


                    
                    
                    ==(_:_:)

Declaration

Swift

@inlinable
@inline(__always)
public static func == (
    lhs: SortedDictionary<Key, Value>, rhs: SortedDictionary<Key, Value>)
    -> Bool


                    
                    
                    <(_:_:)

Declaration

Swift

@inlinable
@inline(__always)
public static func < (
    lhs: SortedDictionary, rhs: SortedDictionary) -> Bool


                    
                    
                    hash(into:)

Declaration

Swift

@inlinable
@inline(__always)
public func hash(into hasher: inout Hasher)

Keys
A view of keys in a SortedDictionary.
See more
Declaration
Swift

public struct Keys
keys
A collection whose keys in the SortedDictionary.
Declaration
Swift

@inlinable public var keys: Keys { get }

Values
A view of values in a SortedDictionary.
See more
Declaration
Swift

public struct Values
values
A collection whose values in the SortedDictionary.
Declaration
Swift

@inlinable public var values: Values { get }


                    
                    
                    Iterator

Declaration

Swift

public struct Iterator : IteratorProtocol


                    
                    
                    makeIterator()

Declaration

Swift

@inlinable
@inline(__always)
public func makeIterator() -> Iterator

min()
Returns the element whose key is the minimum in the SortedDictionary.

Complexity
O(1).
Declaration
Swift

@warn_unqualified_access @inlinable @inline(__always) public func min() -> Element?
Return Value

The element whose key is the minimum in the sorted dictionary. If the SortedDictionary has no elements, returns nil.
max()
Returns the element whose key is the maximum in the SortedDictionary.

Complexity
O(1).
Declaration
Swift

@warn_unqualified_access @inlinable @inline(__always) public func max() -> Element?
Return Value

The element that key is the maximum in the sorted dictionary. If the SortedDictionary has no elements, returns nil.
sorted()
Returns the sorted elements of the SortedDictionary.

Complexity
O(n), where n is the length of this SortedDictionary.
Declaration
Swift

@inlinable @inline(__always) public func sorted() -> [Element]
Return Value

The sorted elements of the SortedDictionary.


                    
                    
                    Index

Declaration

Swift

public struct Index : Comparable, Hashable


                    
                    
                    startIndex

Declaration

Swift

@inlinable
public var startIndex: Index { get }


                    
                    
                    endIndex

Declaration

Swift

@inlinable
public var endIndex: Index { get }


                    
                    
                    subscript(_:)

Declaration

Swift

@inlinable
public subscript(position: Index) -> Element { get }


                    
                    
                    index(after:)

Declaration

Swift

@inlinable
@inline(__always)
public func index(after index: Index) -> Index


                    
                    
                    index(forKey:)

Undocumented

Declaration

Swift

@inlinable
@inline(__always)
public func index(forKey key: Key) -> Index?

popFirst()
Removes the element whose key is minimum, and returns the element.

Complexity
Amortized O(1).
Declaration
Swift

@inlinable @inline(__always) public mutating func popFirst() -> Element?
Return Value

If this SortedDictionary isn’t empty, the element whose key is minimum, otherwise nil.


                    
                    
                    count

Declaration

Swift

@inlinable
public var count: Int { get }


                    
                    
                    isEmpty

Declaration

Swift

@inlinable
public var isEmpty: Bool { get }


                    
                    
                    index(before:)

Declaration

Swift

@inlinable
@inline(__always)
public func index(before index: Index) -> Index

popLast()
Removes the element whose key is maximum, and returns the element.

Complexity
Amortized O(1).
Declaration
Swift

@inlinable @inline(__always) public mutating func popLast() -> Element?
Return Value

If this SortedDictionary isn’t empty, the element whose key is maximum, otherwise nil.


                    
                    
                    init(dictionaryLiteral:)

Declaration

Swift

@inlinable
public init(dictionaryLiteral elements: (Key, Value)...)


                    
                    
                    encode(to:)

Declaration

Swift

public func encode(to encoder: Encoder) throws


                    
                    
                    init(from:)

Declaration

Swift

public init(from decoder: Decoder) throws

description
Declaration
Swift

public var description: String { get }


                    
                    
                    debugDescription

Declaration

Swift

public var debugDescription: String { get }

customMirror
Declaration
Swift

public var customMirror: Mirror { get }