深入理解数组：底层实现探究

数组的协议结构

数组的协议结构

序列 -> 集合 -> 可以做区间替换的集合 -> 数组

Sequence 序列

• 一个序列（Sequence）代表的是一系列具有相同类型的值，你可以对这些值进行迭代。

public protocol Sequence {

    /// A type representing the sequence's elements.
    associatedtype Element where Self.Element == Self.Iterator.Element

    /// A type that provides the sequence's iteration interface and
    /// encapsulates its iteration state.
    associatedtype Iterator : IteratorProtocol

    /// Returns an iterator over the elements of this sequence.
    func makeIterator() -> Self.Iterator

    /// A value less than or equal to the number of elements in the sequence,
    /// calculated nondestructively.
    ///
    /// The default implementation returns 0. If you provide your own
    /// implementation, make sure to compute the value nondestructively.
    ///
    /// - Complexity: O(1), except if the sequence also conforms to `Collection`.
    ///   In this case, see the documentation of `Collection.underestimatedCount`.
    var underestimatedCount: Int { get }

    (UnsafeBufferPointer<Self.Element>) throws -> R) rethrows -> R?
}

IteratorProtocol

• Sequence 通过创建一个迭代器来提供对元素的访问。迭代器每次产生一个序列的值，并且当便利序列时对遍历状态进行管理。
• 当序列被耗尽时，next() 应返回 nil。

IteratorProtocol

定义自己的 Sequence

定义自己的 Sequence

Collection

一个 Collection 是满足下面条件的 Sequence

• 稳定的 Sequence，能够被多次遍历且保持一致
• 除了线性遍历以外，集合中的元素也可以通过下标索引的方式被获取到
• 和 Sequence 不同，Collection 类型不能是无限的。

Collection

Array 的迭代器

Array 的迭代器

Array 的下标访问

Array 的下标访问

Array 的 buffer

Array 的 buffer

_ContiguousArrayBuffer

_ContiguousArrayBuffer

_ContiguousArrayBuffer 的 getElement

_ContiguousArrayBuffer 的 getElement

UnsafeMutablePointer 的下标操作

UnsafeMutablePointer 的下标操作

问题：endIndex vs count

endIndex vs count

索引

索引

对字符串，endIndex 复杂度为O(1)，count 为O(n)
对于数组，endIndex 和 count 都为O(n)，完全等效。