List

public struct List<Element>

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)).

  • Return a view of this list as an immutable NSArray, without copying elements. This is useful when you want to use List values in Objective-C APIs.

    Complexity

    O(1)

    Declaration

    Swift

    public var arrayView: NSArray
    Show on GitHub

Initializers

  • Initialize a new list from the given elements.

    Complexity

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

    Declaration

    Swift

    public init<S: Sequence>(_ elements: S) where S.Iterator.Element == Element
    Show on GitHub

Conversion from an array literal

String conversion

  • A textual representation of this list, suitable for debugging.

    Declaration

    Swift

    public var debugDescription: String
    Show on GitHub

CollectionType

  • Return a sublist of this list, or replace a sublist with another list (possibly of a different size).

    Complexity

    O(log(count)) for the getter, and O(log(count) + range.count) for the setter.

    Declaration

    Swift

    public subscript(range: Range<Int>) -> List<Element>
    Show on GitHub

  • Get or set the element at the given index.

    Complexity

    O(log(count))

    Declaration

    Swift

    public subscript(index: Int) -> Element
    Show on GitHub

  • Always zero, which is the index of the first element when non-empty.

    Declaration

    Swift

    public var startIndex: Int
    Show on GitHub

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

    Declaration

    Swift

    public var endIndex: Int
    Show on GitHub

  • The number of elements in this list.

    Declaration

    Swift

    public var count: Int
    Show on GitHub

  • True iff this list has no elements.

    Declaration

    Swift

    public var isEmpty: Bool
    Show on GitHub

  • Return an iterator over all elements in this list.

    Declaration

    Swift

    public func makeIterator() -> Iterator
    Show on GitHub

  • Return the successor value of index. This method does not verify that the given index or the result are valid in this list.

    Declaration

    Swift

    public func index(after index: Index) -> Index
    Show on GitHub

  • Replace index by its successor. This method does not verify that the given index or the result are valid in this list.

    Declaration

    Swift

    public func formIndex(after index: inout Index)
    Show on GitHub

  • Return the predecessor value of index. This method does not verify that the given index or the result are valid in this list.

    Declaration

    Swift

    public func index(before index: Index) -> Index
    Show on GitHub

  • Replace index by its predecessor. This method does not verify that the given index or the result are valid in this list.

    Declaration

    Swift

    public func formIndex(before index: inout Index)
    Show on GitHub

  • Add n to i and return the result. This method does not verify that the given index or the result are valid in this list.

    Declaration

    Swift

    public func index(_ i: Index, offsetBy n: Int) -> Index
    Show on GitHub

  • Add n to i in place. This method does not verify that the given index or the result are valid in this list.

    Declaration

    Swift

    public func formIndex(_ i: inout Index, offsetBy n: Int)
    Show on GitHub

  • Add n to i and return the result, unless the result would exceed (or, in case of negative n, go under) limit, in which case return nil. This method does not verify that the given indices (or the resulting value) are valid in this list.

    Declaration

    Swift

    public func index(_ i: Index, offsetBy n: Int, limitedBy limit: Index) -> Index?
    Show on GitHub

  • Add n to i in place, unless the result would exceed (or, in case of negative n, go under) limit, in which case set i to limit. This method does not verify that the given indices (or the resulting value) are valid in this list.

    Declaration

    Swift

    public func formIndex(_ i: inout Index, offsetBy n: Int, limitedBy limit: Index) -> Bool
    Show on GitHub

  • Return the difference between end and start. This method does not verify that the given indices are valid in this list.

    Declaration

    Swift

    public func distance(from start: Index, to end: Index) -> Int
    Show on GitHub

  • Return the first element in this list, or nil if the list is empty.

    Declaration

    Swift

    public var first: Element?
    Show on GitHub

  • Return the last element in this list, or nil if the list is empty.

    Declaration

    Swift

    public var last: Element?
    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(result.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 list 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

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

    Complexity

    O(count)

    Declaration

    Swift

    public func filter(_ includeElement: (Element) throws -> Bool) rethrows -> [Element]
    Show on GitHub

Queries

  • 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 lists are divergent mutations originating from the same value.

    Requires

    isEquivalent is an equivalence relation.

    Complexity

    O(count)

    Declaration

    Swift

    public func elementsEqual(_ other: List<Element>, by isEquivalent: (Element, Element) throws -> Bool) rethrows -> Bool
    Show on GitHub

  • Returns the first index where predicate returns true for the corresponding value, or nil if such value is not found.

    Complexity

    O(count)

    Declaration

    Swift

    public func index(where predicate: (Element) throws -> Bool) rethrows -> Index?
    Show on GitHub

  • Return true iff self and other contain equal elements.

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

    Requires

    isEquivalent is an equivalence relation.

    Complexity

    O(count)

    Declaration

    Swift

    public func elementsEqual(_ other: List<Element>) -> Bool
    Show on GitHub

  • Returns the first index where the given element appears in self or nil if the element is not found.

    Complexity

    O(count)

    Declaration

    Swift

    public func index(of element: Element) -> Index?
    Show on GitHub

  • Return true iff element is in self.

    Declaration

    Swift

    public func contains(_ element: Element) -> Bool
    Show on GitHub

  • Returns true iff the two lists have the same elements in the same order.

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

    Complexity

    O(count)

    Declaration

    Swift

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

  • Returns false iff the two lists do not have the same elements in the same order.

    Declaration

    Swift

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

Insertion

  • Append element to the end of this list.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func append(_ element: Element)
    Show on GitHub

  • Insert element into this list at index.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func insert(_ element: Element, at index: Int)
    Show on GitHub

  • Append list to the end of this list.

    Complexity

    O(log(self.count + list.count))

    Declaration

    Swift

    public mutating func append(contentsOf list: List<Element>)
    Show on GitHub

  • Append the contents of elements to the end of this list.

    Complexity

    O(log(count) + n) where n is the number of elements in the sequence.

    Declaration

    Swift

    public mutating func append<S: Sequence>(contentsOf elements: S) where S.Iterator.Element == Element
    Show on GitHub

  • Insert list as a sublist of this list starting at index.

    Complexity

    O(log(self.count + list.count))

    Declaration

    Swift

    public mutating func insert(contentsOf list: List<Element>, at index: Int)
    Show on GitHub

  • Insert the contents of elements into this list starting at index.

    Complexity

    O(log(self.count) + n) where n is the number of elements inserted.

    Declaration

    Swift

    public mutating func insert<S: Sequence>(contentsOf elements: S, at index: Int) where S.Iterator.Element == Element
    Show on GitHub

Removal

  • Remove and return the element at index.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func remove(at index: Int) -> Element
    Show on GitHub

  • Remove and return the first element.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func removeFirst() -> Element
    Show on GitHub

  • Remove the first n elements.

    Complexity

    O(log(count) + n)

    Declaration

    Swift

    public mutating func removeFirst(_ n: Int)
    Show on GitHub

  • Remove and return the last element.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func removeLast() -> Element
    Show on GitHub

  • Remove and return the last n elements.

    Complexity

    O(log(count) + n)

    Declaration

    Swift

    public mutating func removeLast(_ n: Int)
    Show on GitHub

  • If the list is not empty, remove and return the last element. Otherwise return nil.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func popLast() -> Element?
    Show on GitHub

  • If the list is not empty, remove and return the first element. Otherwise return nil.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func popFirst() -> Element?
    Show on GitHub

  • Remove elements in the specified range of indexes.

    Complexity

    O(log(self.count) + range.count)

    Declaration

    Swift

    public mutating func removeSubrange(_ range: Range<Int>)
    Show on GitHub

  • Remove all elements.

    Complexity

    O(count)

    Declaration

    Swift

    public mutating func removeAll()
    Show on GitHub

Range replacement

  • Replace elements in range with elements.

    Complexity

    O(log(count) + range.count)

    Declaration

    Swift

    public mutating func replaceSubrange(_ range: Range<Int>, with elements: List<Element>)
    Show on GitHub

  • Replace elements in range with elements.

    Complexity

    O(log(count) + max(range.count, elements.count))

    Declaration

    Swift

    public mutating func replaceSubrange<C: Collection>(_ range: Range<Int>, with elements: C) where C.Iterator.Element == Element
    Show on GitHub

  • Concatenate a with b and return the resulting List.

    Declaration

    Swift

    public static func +(a: List, b: List) -> List
    Show on GitHub