Swift Source Code: Collection

Summary

Collection extends Sequence. It guarantees that the sequence is multi-pass, and it allows you to look up elements by their indices. It also adds slicing capabilities via its SubSequence type, which is a collection itself.

Types

IndexingIterator

• IndexingIterator 是collection类型默认的iterator实现
• 自定义Collection所需要的最小实现只需要startIndex, endIndex, subscript方法
• IndexingIterator实现了IteratorProtocol, Sequence, Sendable等protocol

/// A type that iterates over a collection using its indices.
///
/// The `IndexingIterator` type is the default iterator for any collection that
/// doesn't declare its own. It acts as an iterator by using a collection's
/// indices to step over each value in the collection. Most collections in the
/// standard library use `IndexingIterator` as their iterator.
///
/// By default, any custom collection type you create will inherit a
/// `makeIterator()` method that returns an `IndexingIterator` instance,
/// making it unnecessary to declare your own. When creating a custom
/// collection type, add the minimal requirements of the `Collection`
/// protocol: starting and ending indices and a subscript for accessing
/// elements. With those elements defined, the inherited `makeIterator()`
/// method satisfies the requirements of the `Sequence` protocol.
///
/// Here's an example of a type that declares the minimal requirements for a
/// collection. The `CollectionOfTwo` structure is a fixed-size collection
/// that always holds two elements of a specific type.
///
///     struct CollectionOfTwo<Element>: Collection {
///         let elements: (Element, Element)
///
///         init(_ first: Element, _ second: Element) {
///             self.elements = (first, second)
///         }
///
///         var startIndex: Int { return 0 }
///         var endIndex: Int   { return 2 }
///
///         subscript(index: Int) -> Element {
///             switch index {
///             case 0: return elements.0
///             case 1: return elements.1
///             default: fatalError("Index out of bounds.")
///             }
///         }
///         
///         func index(after i: Int) -> Int {
///             precondition(i < endIndex, "Can't advance beyond endIndex")
///             return i + 1
///         }
///     }
///
/// Because `CollectionOfTwo` doesn't define its own `makeIterator()`
/// method or `Iterator` associated type, it uses the default iterator type,
/// `IndexingIterator`. This example shows how a `CollectionOfTwo` instance
/// can be created holding the values of a point, and then iterated over
/// using a `for`-`in` loop.
///
///     let point = CollectionOfTwo(15.0, 20.0)
///     for element in point {
///         print(element)
///     }
///     // Prints "15.0"
///     // Prints "20.0"
@frozen
public struct IndexingIterator<Elements: Collection> {
  @usableFromInline
  internal let _elements: Elements
  @usableFromInline
  internal var _position: Elements.Index

  /// Creates an iterator over the given collection.
  @inlinable
  @inline(__always)
  public /// @testable
  init(_elements: Elements) {
    self._elements = _elements
    self._position = _elements.startIndex
  }

  /// Creates an iterator over the given collection.
  @inlinable
  @inline(__always)
  public /// @testable
  init(_elements: Elements, _position: Elements.Index) {
    self._elements = _elements
    self._position = _position
  }
}

extension IndexingIterator: IteratorProtocol, Sequence {
  public typealias Element = Elements.Element
  public typealias Iterator = IndexingIterator<Elements>
  public typealias SubSequence = AnySequence<Element>

  /// Advances to the next element and returns it, or `nil` if no next element
  /// exists.
  ///
  /// Repeatedly calling this method returns all the elements of the underlying
  /// sequence in order. As soon as the sequence has run out of elements, all
  /// subsequent calls return `nil`.
  ///
  /// This example shows how an iterator can be used explicitly to emulate a
  /// `for`-`in` loop. First, retrieve a sequence's iterator, and then call
  /// the iterator's `next()` method until it returns `nil`.
  ///
  ///     let numbers = [2, 3, 5, 7]
  ///     var numbersIterator = numbers.makeIterator()
  ///
  ///     while let num = numbersIterator.next() {
  ///         print(num)
  ///     }
  ///     // Prints "2"
  ///     // Prints "3"
  ///     // Prints "5"
  ///     // Prints "7"
  ///
  /// - Returns: The next element in the underlying sequence if a next element
  ///   exists; otherwise, `nil`.
  @inlinable
  @inline(__always)
  public mutating func next() -> Elements.Element? {
    if _position == _elements.endIndex { return nil }
    let element = _elements[_position]
    _elements.formIndex(after: &_position)
    return element
  }
}

extension IndexingIterator: Sendable  where Elements: Sendable, Elements.Index: Sendable { }
  where Elements: Sendable, Elements.Index: Sendable 

Collection

A sequence whose elements can be traversed multiple times, nondestructively, and accessed by an indexed subscript.

• Accessing Individual Elements
• Accessing Slices of a Collection
• Traversing a Collection
• Conforming to the Collection Protocol
  • The startIndex and endIndex properties
  • A subscript
  • index(after:)
• Expected Performance
  • startIndex and endIndex and subscript access O(1)
  • forward or bidirectional collection accessing its count property is an O(n)

public protocol Collection: Sequence {
  // FIXME: ideally this would be in MigrationSupport.swift, but it needs
  // to be on the protocol instead of as an extension
  @available(*, deprecated/*, obsoleted: 5.0*/, message: "all index distances are now of type Int")
  typealias IndexDistance = Int  

  // FIXME: Associated type inference requires this.
  override associatedtype Element

  // FIXME: <rdar://problem/34142121>
  // This typealias should be removed as it predates the source compatibility
  // guarantees of Swift 3, but it cannot due to a bug.
  @available(swift, deprecated: 3.2, obsoleted: 5.0, renamed: "Element")
  typealias _Element = Element

  /// A type that represents a position in the collection.
  ///
  /// Valid indices consist of the position of every element and a
  /// "past the end" position that's not valid for use as a subscript
  /// argument.
  associatedtype Index: Comparable

  /// The position of the first element in a nonempty collection.
  ///
  /// If the collection is empty, `startIndex` is equal to `endIndex`.
  var startIndex: Index { get }
 
  /// The collection's "past the end" position---that is, the position one
  /// greater than the last valid subscript argument.
  ///
  /// When you need a range that includes the last element of a collection, use
  /// the half-open range operator (`..<`) with `endIndex`. The `..<` operator
  /// creates a range that doesn't include the upper bound, so it's always
  /// safe to use with `endIndex`. For example:
  ///
  ///     let numbers = [10, 20, 30, 40, 50]
  ///     if let index = numbers.firstIndex(of: 30) {
  ///         print(numbers[index ..< numbers.endIndex])
  ///     }
  ///     // Prints "[30, 40, 50]"
  ///
  /// If the collection is empty, `endIndex` is equal to `startIndex`.
  var endIndex: Index { get }

  /// A type that provides the collection's iteration interface and
  /// encapsulates its iteration state.
  ///
  /// By default, a collection conforms to the `Sequence` protocol by
  /// supplying `IndexingIterator` as its associated `Iterator`
  /// type.
  associatedtype Iterator = IndexingIterator<Self>

  // FIXME: Only needed for associated type inference. Otherwise,
  // we get an `IndexingIterator` rather than properly deducing the
  // Iterator type from makeIterator(). <rdar://problem/21539115>
  /// Returns an iterator over the elements of the collection.
  override __consuming func makeIterator() -> Iterator

  /// A collection representing a contiguous subrange of this collection's
  /// elements. The subsequence shares indices with the original collection.
  ///
  /// The default subsequence type for collections that don't define their own
  /// is `Slice`.
  associatedtype SubSequence: Collection = Slice<Self>
  where SubSequence.Index == Index,
        Element == SubSequence.Element,
        SubSequence.SubSequence == SubSequence

  /// Accesses the element at the specified position.
  ///
  /// The following example accesses an element of an array through its
  /// subscript to print its value:
  ///
  ///     var streets = ["Adams", "Bryant", "Channing", "Douglas", "Evarts"]
  ///     print(streets[1])
  ///     // Prints "Bryant"
  ///
  /// You can subscript a collection with any valid index other than the
  /// collection's end index. The end index refers to the position one past
  /// the last element of a collection, so it doesn't correspond with an
  /// element.
  ///
  /// - Parameter position: The position of the element to access. `position`
  ///   must be a valid index of the collection that is not equal to the
  ///   `endIndex` property.
  ///
  /// - Complexity: O(1)
  @_borrowed
  subscript(position: Index) -> Element { get }

  /// Accesses a contiguous subrange of the collection's elements.
  ///
  /// For example, using a `PartialRangeFrom` range expression with an array
  /// accesses the subrange from the start of the range expression until the
  /// end of the array.
  ///
  ///     let streets = ["Adams", "Bryant", "Channing", "Douglas", "Evarts"]
  ///     let streetsSlice = streets[2..<5]
  ///     print(streetsSlice)
  ///     // ["Channing", "Douglas", "Evarts"]
  ///
  /// The accessed slice uses the same indices for the same elements as the
  /// original collection. This example searches `streetsSlice` for one of the
  /// strings in the slice, and then uses that index in the original array.
  ///
  ///     let index = streetsSlice.firstIndex(of: "Evarts")!    // 4
  ///     print(streets[index])
  ///     // "Evarts"
  ///
    /// Always use the slice's `startIndex` property instead of assuming that its
  /// indices start at a particular value. Attempting to access an element by
  /// using an index outside the bounds of the slice may result in a runtime
  /// error, even if that index is valid for the original collection.
  ///
  ///     print(streetsSlice.startIndex)
  ///     // 2
  ///     print(streetsSlice[2])
  ///     // "Channing"
  ///
  ///     print(streetsSlice[0])
  ///     // error: Index out of bounds
  ///
  /// - Parameter bounds: A range of the collection's indices. The bounds of
  ///   the range must be valid indices of the collection.
  ///
  /// - Complexity: O(1)
  subscript(bounds: Range<Index>) -> SubSequence { get }

  /// A type that represents the indices that are valid for subscripting the
  /// collection, in ascending order.
  associatedtype Indices: Collection = DefaultIndices<Self>
    where Indices.Element == Index, 
          Indices.Index == Index,
          Indices.SubSequence == Indices
        
  /// The indices that are valid for subscripting the collection, in ascending
  /// order.
  ///
  /// A collection's `indices` property can hold a strong reference to the
  /// collection itself, causing the collection to be nonuniquely referenced.
  /// If you mutate the collection while iterating over its indices, a strong
  /// reference can result in an unexpected copy of the collection. To avoid
  /// the unexpected copy, use the `index(after:)` method starting with
  /// `startIndex` to produce indices instead.
  ///
  ///     var c = MyFancyCollection([10, 20, 30, 40, 50])
  ///     var i = c.startIndex
  ///     while i != c.endIndex {
  ///         c[i] /= 5
  ///         i = c.index(after: i)
  ///     }
  ///     // c == MyFancyCollection([2, 4, 6, 8, 10])
  var indices: Indices { get }

  /// A Boolean value indicating whether the collection is empty.
  ///
  /// When you need to check whether your collection is empty, use the
  /// `isEmpty` property instead of checking that the `count` property is
  /// equal to zero. For collections that don't conform to
  /// `RandomAccessCollection`, accessing the `count` property iterates
  /// through the elements of the collection.
  ///
  ///     let horseName = "Silver"
  ///     if horseName.isEmpty {
  ///         print("My horse has no name.")
  ///     } else {
  ///         print("Hi ho, \(horseName)!")
  ///     }
  ///     // Prints "Hi ho, Silver!"
  ///
  /// - Complexity: O(1)
  var isEmpty: Bool { get }

  /// The number of elements in the collection.
  ///
  /// To check whether a collection is empty, use its `isEmpty` property
  /// instead of comparing `count` to zero. Unless the collection guarantees
  /// random-access performance, calculating `count` can be an O(*n*)
  /// operation.
  ///
  /// - Complexity: O(1) if the collection conforms to
  ///   `RandomAccessCollection`; otherwise, O(*n*), where *n* is the length
  ///   of the collection.
  var count: Int { get }
  
  // The following requirements enable dispatching for firstIndex(of:) and
  // lastIndex(of:) when the element type is Equatable.

  /// Returns `Optional(Optional(index))` if an element was found
  /// or `Optional(nil)` if an element was determined to be missing;
  /// otherwise, `nil`.
  ///
  /// - Complexity: O(*n*), where *n* is the length of the collection.
  func _customIndexOfEquatableElement(_ element: Element) -> Index??

  /// Customization point for `Collection.lastIndex(of:)`.
  ///
  /// Define this method if the collection can find an element in less than
  /// O(*n*) by exploiting collection-specific knowledge.
  ///
  /// - Returns: `nil` if a linear search should be attempted instead,
  ///   `Optional(nil)` if the element was not found, or
  ///   `Optional(Optional(index))` if an element was found.
  ///
  /// - Complexity: Hopefully less than O(`count`).
  func _customLastIndexOfEquatableElement(_ element: Element) -> Index??

  /// Returns an index that is the specified distance from the given index.
  ///
  /// The following example obtains an index advanced four positions from a
  /// string's starting index and then prints the character at that position.
  ///
  ///     let s = "Swift"
  ///     let i = s.index(s.startIndex, offsetBy: 4)
  ///     print(s[i])
  ///     // Prints "t"
  ///
  /// The value passed as `distance` must not offset `i` beyond the bounds of
  /// the collection.
  ///
  /// - Parameters:
  ///   - i: A valid index of the collection.
  ///   - distance: The distance to offset `i`. `distance` must not be negative
  ///     unless the collection conforms to the `BidirectionalCollection`
  ///     protocol.
  /// - Returns: An index offset by `distance` from the index `i`. If
  ///   `distance` is positive, this is the same value as the result of
  ///   `distance` calls to `index(after:)`. If `distance` is negative, this
  ///   is the same value as the result of `abs(distance)` calls to
  ///   `index(before:)`.
  ///
  /// - Complexity: O(1) if the collection conforms to
  ///   `RandomAccessCollection`; otherwise, O(*k*), where *k* is the absolute
  ///   value of `distance`.
  func index(_ i: Index, offsetBy distance: Int) -> Index

  /// Returns an index that is the specified distance from the given index,
  /// unless that distance is beyond a given limiting index.
  ///
  /// The following example obtains an index advanced four positions from a
  /// string's starting index and then prints the character at that position.
  /// The operation doesn't require going beyond the limiting `s.endIndex`
  /// value, so it succeeds.
  ///
  ///     let s = "Swift"
  ///     if let i = s.index(s.startIndex, offsetBy: 4, limitedBy: s.endIndex) {
  ///         print(s[i])
  ///     }
  ///     // Prints "t"
  ///
  /// The next example attempts to retrieve an index six positions from
  /// `s.startIndex` but fails, because that distance is beyond the index
  /// passed as `limit`.
  ///
  ///     let j = s.index(s.startIndex, offsetBy: 6, limitedBy: s.endIndex)
  ///     print(j)
  ///     // Prints "nil"
  ///
  /// The value passed as `distance` must not offset `i` beyond the bounds of
  /// the collection, unless the index passed as `limit` prevents offsetting
  /// beyond those bounds.
  ///
  /// - Parameters:
  ///   - i: A valid index of the collection.
  ///   - distance: The distance to offset `i`. `distance` must not be negative
  ///     unless the collection conforms to the `BidirectionalCollection`
  ///     protocol.
  ///   - limit: A valid index of the collection to use as a limit. If
  ///     `distance > 0`, a limit that is less than `i` has no effect.
  ///     Likewise, if `distance < 0`, a limit that is greater than `i` has no
  ///     effect.
  /// - Returns: An index offset by `distance` from the index `i`, unless that
  ///   index would be beyond `limit` in the direction of movement. In that
  ///   case, the method returns `nil`.
  ///
  /// - Complexity: O(1) if the collection conforms to
  ///   `RandomAccessCollection`; otherwise, O(*k*), where *k* is the absolute
  ///   value of `distance`.
  func index(    _ i: Index, offsetBy distance: Int, limitedBy limit: Index  ) -> Index?
    _ i: Index, offsetBy distance: Int, limitedBy limit: Index
  )

  /// Returns the distance between two indices.
  ///
  /// Unless the collection conforms to the `BidirectionalCollection` protocol,
  /// `start` must be less than or equal to `end`.
  ///
  /// - Parameters:
  ///   - start: A valid index of the collection.
  ///   - end: Another valid index of the collection. If `end` is equal to
  ///     `start`, the result is zero.
  /// - Returns: The distance between `start` and `end`. The result can be
  ///   negative only if the collection conforms to the
  ///   `BidirectionalCollection` protocol.
  ///
  /// - Complexity: O(1) if the collection conforms to
  ///   `RandomAccessCollection`; otherwise, O(*k*), where *k* is the
  ///   resulting distance.
  func distance(from start: Index, to end: Index) -> Int

  /// Performs a range check in O(1), or a no-op when a range check is not
  /// implementable in O(1).
  ///
  /// The range check, if performed, is equivalent to:
  ///
  ///     precondition(bounds.contains(index))
  ///
  /// Use this function to perform a cheap range check for QoI purposes when
  /// memory safety is not a concern.  Do not rely on this range check for
  /// memory safety.
  ///
  /// The default implementation for forward and bidirectional indices is a
  /// no-op.  The default implementation for random access indices performs a
  /// range check.
  ///
  /// - Complexity: O(1).
  func _failEarlyRangeCheck(_ index: Index, bounds: Range<Index>)

  func _failEarlyRangeCheck(_ index: Index, bounds: ClosedRange<Index>)

  /// Performs a range check in O(1), or a no-op when a range check is not
  /// implementable in O(1).
  ///
  /// The range check, if performed, is equivalent to:
  ///
  ///     precondition(
  ///       bounds.contains(range.lowerBound) ||
  ///       range.lowerBound == bounds.upperBound)
  ///     precondition(
  ///       bounds.contains(range.upperBound) ||
  ///       range.upperBound == bounds.upperBound)
  ///
  /// Use this function to perform a cheap range check for QoI purposes when
  /// memory safety is not a concern.  Do not rely on this range check for
  /// memory safety.
  ///
  /// The default implementation for forward and bidirectional indices is a
  /// no-op.  The default implementation for random access indices performs a
  /// range check.
  ///
  /// - Complexity: O(1).
  func _failEarlyRangeCheck(_ range: Range<Index>, bounds: Range<Index>)

  /// Returns the position immediately after the given index.
  ///
  /// The successor of an index must be well defined. For an index `i` into a
  /// collection `c`, calling `c.index(after: i)` returns the same index every
  /// time.
  ///
  /// - Parameter i: A valid index of the collection. `i` must be less than
  ///   `endIndex`.
  /// - Returns: The index value immediately after `i`.
  func index(after i: Index) -> Index

  /// Replaces the given index with its successor.
  ///
  /// - Parameter i: A valid index of the collection. `i` must be less than
  ///   `endIndex`.
  func formIndex(after i: inout Index)
}

Functions

randomeElement

  /// 这两个方法我觉得可以用在测试代码中，如可以方便的随机选取登陆用户账号密码用于测试，或者随机一个dataset传入要测试的方法中
  @inlinable
  public func randomElement<T: RandomNumberGenerator>(    using generator: inout T  ) -> Element? {
    using generator: inout T
  )
    guard !isEmpty else { return nil }
    let random = Int.random(in: 0 ..< count, using: &generator)
    let idx = index(startIndex, offsetBy: random)
    return self[idx]
  }
  @inlinable
  public func randomElement() -> Element? {
    var g = SystemRandomNumberGenerator()
    return randomElement(using: &g)
  }


/// The system's default source of random data.
///
/// When you generate random values, shuffle a collection, or perform another
/// operation that depends on random data, this type is the generator used by
/// default. For example, the two method calls in this example are equivalent:
///
///     let x = Int.random(in: 1...100)
///     var g = SystemRandomNumberGenerator()
///     let y = Int.random(in: 1...100, using: &g)
///
/// `SystemRandomNumberGenerator` is automatically seeded, is safe to use in
/// multiple threads, and uses a cryptographically secure algorithm whenever
/// possible.
///
/// Platform Implementation of `SystemRandomNumberGenerator`
/// ========================================================
///
/// While the system generator is automatically seeded and thread-safe on every
/// platform, the cryptographic quality of the stream of random data produced by
/// the generator may vary. For more detail, see the documentation for the APIs
/// used by each platform.
///
/// - Apple platforms use `arc4random_buf(3)`.
/// - Linux platforms use `getrandom(2)` when available; otherwise, they read
///   from `/dev/urandom`.
/// - Windows uses `BCryptGenRandom`
  @frozen
public struct SystemRandomNumberGenerator: RandomNumberGenerator, Sendable {
  /// Creates a new instance of the system's default random number generator.
  @inlinable
  public init() { }

  /// Returns a value from a uniform, independent distribution of binary data.
  ///
  /// - Returns: An unsigned 64-bit random value.
  @inlinable
  public mutating func next() -> UInt64 {
    var random: UInt64 = 0
    swift_stdlib_random(&random, MemoryLayout<UInt64>.size)
    return random
  }
}

popFirst

/// Removes and returns the first element of the collection.
///
/// - Returns: The first element of the collection if the collection is
///   not empty; otherwise, `nil`.
///
/// - Complexity: O(1)
@inlinable
public mutating func popFirst() -> Element? {
  // TODO: swift-3-indexing-model - review the following
  guard !isEmpty else { return nil }
  /// 一定有倔种来告诉我，我们在swift不推荐使用“!”
  let element = first!
  /// 你删除first这么带劲吗？
  self = self[index(after: startIndex)..<endIndex]
  return element
}

isEmpty

/// isEmpty 有什么值得写的？请认真看看下面的注视
/// A Boolean value indicating whether the collection is empty.
///
/// When you need to check whether your collection is empty, use the
/// `isEmpty` property instead of checking that the `count` property is
/// equal to zero. For collections that don't conform to
/// `RandomAccessCollection`, accessing the `count` property iterates
/// through the elements of the collection.
///
///     let horseName = "Silver"
///     if horseName.isEmpty {
///         print("My horse has no name.")
///     } else {
///         print("Hi ho, \(horseName)!")
///     }
///     // Prints "Hi ho, Silver!")
///
/// - Complexity: O(1)
@inlinable
public var isEmpty: Bool {
  return startIndex == endIndex
}