Swift Source Code: Sequence

Summary

Sequence provides iteration. It allows you to create an iterator, but there are no guarantees about whether the sequence is single-pass (e.g. reading from standard input) or multi-pass (iterating over an array).

Types

IteratorProtocol

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public protocol IteratorProtocol {
  /// The type of element traversed by the iterator.
  associatedtype Element

  /// Advances to the next element and returns it, or `nil` if no next element
  /// exists.
  ///
  /// Repeatedly calling this method returns, in order, all the elements of the
  /// underlying sequence. As soon as the sequence has run out of elements, all
  /// subsequent calls return `nil`.
  ///
  /// You must not call this method if any other copy of this iterator has been
  /// advanced with a call to its `next()` method.
  ///
  /// The following 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`.
  mutating func next() -> Element?
}

Sequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
public protocol Sequence {
  /// A type representing the sequence's elements.
  associatedtype Element

  /// A type that provides the sequence's iteration interface and
  /// encapsulates its iteration state.
  associatedtype Iterator: IteratorProtocol where Iterator.Element == 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(*, unavailable, renamed: "Iterator")
  typealias Generator = Iterator

  /// A type that represents a subsequence of some of the sequence's elements.
  // associatedtype SubSequence: Sequence = AnySequence<Element>
  //   where Element == SubSequence.Element,
  //         SubSequence.SubSequence == SubSequence
  // typealias SubSequence = AnySequence<Element>

  /// Returns an iterator over the elements of this sequence.
  __consuming func makeIterator() -> 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 }

  func _customContainsEquatableElement(
    _ element: Element
  ) -> Bool?

  /// Create a native array buffer containing the elements of `self`,
  /// in the same order.
  __consuming func _copyToContiguousArray() -> ContiguousArray<Element>

  /// Copy `self` into an unsafe buffer, initializing its memory.
  ///
  /// The default implementation simply iterates over the elements of the
  /// sequence, initializing the buffer one item at a time.
  ///
  /// For sequences whose elements are stored in contiguous chunks of memory,
  /// it may be more efficient to copy them in bulk, using the
  /// `UnsafeMutablePointer.initialize(from:count:)` method.
  ///
  /// - Parameter ptr: An unsafe buffer addressing uninitialized memory. The
  ///    buffer must be of sufficient size to accommodate
  ///    `source.underestimatedCount` elements. (Some implementations trap
  ///    if given a buffer that's smaller than this.)
  ///
  /// - Returns: `(it, c)`, where `c` is the number of elements copied into the
  ///    buffer, and `it` is a partially consumed iterator that can be used to
  ///    retrieve elements that did not fit into the buffer (if any). (This can
  ///    only happen if `underestimatedCount` turned out to be an actual
  ///    underestimate, and the buffer did not contain enough space to hold the
  ///    entire sequence.)
  ///
  ///    On return, the memory region in `buffer[0 ..< c]` is initialized to
  ///    the first `c` elements in the sequence.
  __consuming func _copyContents(
    initializing ptr: UnsafeMutableBufferPointer<Element>
  ) -> (Iterator,UnsafeMutableBufferPointer<Element>.Index)

  /// Executes a closure on the sequence’s contiguous storage.
  ///
  /// This method calls `body(buffer)`, where `buffer` is a pointer to the
  /// collection’s contiguous storage. If the contiguous storage doesn't exist,
  /// the collection creates it. If the collection doesn’t support an internal
  /// representation in a form of contiguous storage, the method doesn’t call
  /// `body` --- it immediately returns `nil`.
  ///
  /// The optimizer can often eliminate bounds- and uniqueness-checking
  /// within an algorithm. When that fails, however, invoking the same
  /// algorithm on the `buffer` argument may let you trade safety for speed.
  ///
  /// Successive calls to this method may provide a different pointer on each
  /// call. Don't store `buffer` outside of this method.
  ///
  /// A `Collection` that provides its own implementation of this method
  /// must provide contiguous storage to its elements in the same order
  /// as they appear in the collection. This guarantees that it's possible to
  /// generate contiguous mutable storage to any of its subsequences by slicing
  /// `buffer` with a range formed from the distances to the subsequence's
  /// `startIndex` and `endIndex`, respectively.
  ///
  /// - Parameters:
  ///   - body: A closure that receives an `UnsafeBufferPointer` to the
  ///     sequence's contiguous storage.
  /// - Returns: The value returned from `body`, unless the sequence doesn't
  ///   support contiguous storage, in which case the method ignores `body` and
  ///   returns `nil`.
  func withContiguousStorageIfAvailable<R>(
    _ body: (_ buffer: UnsafeBufferPointer<Element>) throws -> R
  ) rethrows -> R?
}

DropFirstSequence, PrefixSequence, DropWhileSequence

在dropFirst，prefix， drop(while:) 方法中，返回的并非为Array或者Sequence类型，而是返回了对应的XXSequence struct 类型。看注释上说时可以lazily consume. 这几类Sequence有些类似Box/Wrapper Sequence.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/// A sequence that lazily consumes and drops `n` elements from an underlying
/// `Base` iterator before possibly returning the first available element.
///
/// The underlying iterator's sequence may be infinite.
@frozen
public struct DropFirstSequence<Base: Sequence> {
  @usableFromInline
  internal let _base: Base
  @usableFromInline
  internal let _limit: Int
  
  @inlinable 
  public init(_ base: Base, dropping limit: Int) {
    _precondition(limit >= 0, 
      "Can't drop a negative number of elements from a sequence")
    _base = base
    _limit = limit
  }
}

extension DropFirstSequence: Sequence {
  public typealias Element = Base.Element
  public typealias Iterator = Base.Iterator
  public typealias SubSequence = AnySequence<Element>
  
  @inlinable
  public __consuming func makeIterator() -> Iterator {
    var it = _base.makeIterator()
    var dropped = 0
    while dropped < _limit, it.next() != nil { dropped &+= 1 }
    return it
  }

  @inlinable
  public __consuming func dropFirst(_ k: Int) -> DropFirstSequence<Base> {
    // If this is already a _DropFirstSequence, we need to fold in
    // the current drop count and drop limit so no data is lost.
    //
    // i.e. [1,2,3,4].dropFirst(1).dropFirst(1) should be equivalent to
    // [1,2,3,4].dropFirst(2).
    return DropFirstSequence(_base, dropping: _limit + k)
  }
}

/// A sequence that only consumes up to `n` elements from an underlying
/// `Base` iterator.
///
/// The underlying iterator's sequence may be infinite.
@frozen
public struct PrefixSequence<Base: Sequence> {
  @usableFromInline
  internal var _base: Base
  @usableFromInline
  internal let _maxLength: Int

  @inlinable
  public init(_ base: Base, maxLength: Int) {
    _precondition(maxLength >= 0, "Can't take a prefix of negative length")
    _base = base
    _maxLength = maxLength
  }
}

/// A sequence that lazily consumes and drops `n` elements from an underlying
/// `Base` iterator before possibly returning the first available element.
///
/// The underlying iterator's sequence may be infinite.
@frozen
public struct DropWhileSequence<Base: Sequence> {
  public typealias Element = Base.Element
  
  @usableFromInline
  internal var _iterator: Base.Iterator
  @usableFromInline
  internal var _nextElement: Element?
  
  @inlinable
  internal init(iterator: Base.Iterator, predicate: (Element) throws -> Bool) rethrows {
    _iterator = iterator
    _nextElement = _iterator.next()
    
    while let x = _nextElement, try predicate(x) {
      _nextElement = _iterator.next()
    }
  }
  
  @inlinable
  internal init(_ base: Base, predicate: (Element) throws -> Bool) rethrows {
    self = try DropWhileSequence(iterator: base.makeIterator(), predicate: predicate)
  }
}

Functions

suffix(_ maxLength: Int)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/// Returns a subsequence, up to the given maximum length, containing the
/// final elements of the sequence.
///
/// The sequence must be finite. If the maximum length exceeds the number of
/// elements in the sequence, the result contains all the elements in the
/// sequence.
///
///     let numbers = [1, 2, 3, 4, 5]
///     print(numbers.suffix(2))
///     // Prints "[4, 5]"
///     print(numbers.suffix(10))
///     // Prints "[1, 2, 3, 4, 5]"
///
/// - Parameter maxLength: The maximum number of elements to return. The
///   value of `maxLength` must be greater than or equal to zero.
///
/// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public __consuming func suffix(_ maxLength: Int) -> [Element] {
  _Precondition(maxLength >= 0, "Can't take a suffix of negative length from a sequence")
  guard maxLength != 0 else { return [] }

  // FIXME: <rdar://problem/21885650> Create reusable RingBuffer<T>
  // Put incoming elements into a ring buffer to save space. Once all
  // elements are consumed, reorder the ring buffer into a copy and return it.
  // This saves memory for sequences particularly longer than `maxLength`.
  // 这里提到[RingBuffer](https://en.wikipedia.org/wiki/Circular_buffer)这个数据结构用于节省空间，这块还是值得注意的。因为如果使用正常的Array或者ContiguousArray，会创建一个和self本身同等大小的array，而使用RingBuffer则只会使用maxLength大小的空间.
  // 已经有相关RingBuffer(CircularBuffer)实现的[PR](https://github.com/apple/swift/pull/30242/files)，最终没有merge到main
  var ringBuffer = ContiguousArray<Element>()
  ringBuffer.reserveCapacity(Swift.min(maxLength, underestimatedCount))

  var i = 0

  for element in self {
    if ringBuffer.count < maxLength {
      ringBuffer.append(element)
    } else {
      // RingBuffer相关操作，只保留buffer大小的数据，其他数据进行覆盖
      ringBuffer[i] = element
      i = (i + 1) % maxLength
    }
  }

  if i != ringBuffer.startIndex {
    // Rotate RingBuffer
    var rotated = ContiguousArray<Element>()
    rotated.reserveCapacity(ringBuffer.count)
    rotated += ringBuffer[i..<ringBuffer.endIndex]
    rotated += ringBuffer[0..<i]
    return Array(rotated)
  } else {
    return Array(ringBuffer)
  }
}

dropLast(_ k: Int = 1) -> [Element]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/// Returns a sequence containing all but the given number of final
/// elements.
///
/// The sequence must be finite. If the number of elements to drop exceeds
/// the number of elements in the sequence, the result is an empty
/// sequence.
///
///     let numbers = [1, 2, 3, 4, 5]
///     print(numbers.dropLast(2))
///     // Prints "[1, 2, 3]"
///     print(numbers.dropLast(10))
///     // Prints "[]"
///
/// - Parameter n: The number of elements to drop off the end of the
///   sequence. `n` must be greater than or equal to zero.
/// - Returns: A sequence leaving off the specified number of elements.
///
/// - Complexity: O(*n*), where *n* is the length of the sequence.
@inlinable
public __consuming func dropLast(_ k: Int = 1) -> [Element] {
  _precondition(k >= 0, "Can't drop a negative number of elements from a sequence")
  guard k != 0 else { return Array(self) }

  // FIXME: <rdar://problem/21885650> Create reusable RingBuffer<T>
  // Put incoming elements from this sequence in a holding tank, a ring buffer
  // of size <= k. If more elements keep coming in, pull them out of the
  // holding tank into the result, an `Array`. This saves
  // `k` * sizeof(Element) of memory, because slices keep the entire
  // memory of an `Array` alive.
  var result = ContiguousArray<Element>()
  // ringBuffer的大小同k相同，最后会保存被drop的元素
  var ringBuffer = ContiguousArray<Element>()
  var i = ringBuffer.startIndex

  for element in self {
    // 当ringbuffer小于k时，将元素放入ringbuffer中(holding tank)
    if ringBuffer.count < k {
      ringBuffer.append(element)
    } else {
      // pull them out of the holding tank into the result
      result.append(ringBuffer[i])
      // 更新ringbuffer与index
      ringBuffer[i] = element
      i = (i + 1) % k
    }
  }
  return Array(result)
}

elementsEqual

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
extension Sequence where Element: Equatable {
  /// 直接比较两个两个类型的Sequence元素是否相同，可以省去转换成相同type的步骤
  /// Returns a Boolean value indicating whether this sequence and another
  /// sequence contain the same elements in the same order.
  ///
  /// At least one of the sequences must be finite.
  ///
  /// This example tests whether one countable range shares the same elements
  /// as another countable range and an array.
  ///
  ///     let a = 1...3
  ///     let b = 1...10
  ///
  ///     print(a.elementsEqual(b))
  ///     // Prints "false"
  ///     print(a.elementsEqual([1, 2, 3]))
  ///     // Prints "true"
  ///
  /// - Parameter other: A sequence to compare to this sequence.
  /// - Returns: `true` if this sequence and `other` contain the same elements
  ///   in the same order.
  ///
  /// - Complexity: O(*m*), where *m* is the lesser of the length of the
  ///   sequence and the length of `other`.
  @inlinable
  public func elementsEqual<OtherSequence: Sequence>(
    _ other: OtherSequence
  ) -> Bool where OtherSequence.Element == Element {
    return self.elementsEqual(other, by: ==)
  }
}

flatMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
extension Sequence {
  /// Returns an array containing the concatenated results of calling the
  /// given transformation with each element of this sequence.
  ///
  /// Use this method to receive a single-level collection when your
  /// transformation produces a sequence or collection for each element.
  ///
  /// In this example, note the difference in the result of using `map` and
  /// `flatMap` with a transformation that returns an array.
  ///
  ///     let numbers = [1, 2, 3, 4]
  ///
  ///     let mapped = numbers.map { Array(repeating: $0, count: $0) }
  ///     // [[1], [2, 2], [3, 3, 3], [4, 4, 4, 4]]
  ///
  ///     let flatMapped = numbers.flatMap { Array(repeating: $0, count: $0) }
  ///     // [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
  ///
  /// In fact, `s.flatMap(transform)`  is equivalent to
  /// `Array(s.map(transform).joined())`.
  ///
  /// - Parameter transform: A closure that accepts an element of this
  ///   sequence as its argument and returns a sequence or collection.
  /// - Returns: The resulting flattened array.
  ///
  /// - Complexity: O(*m* + *n*), where *n* is the length of this sequence
  ///   and *m* is the length of the result.
  @inlinable
  public func flatMap<SegmentOfResult: Sequence>(
    _ transform: (Element) throws -> SegmentOfResult
  ) rethrows -> [SegmentOfResult.Element] {
    var result: [SegmentOfResult.Element] = []
    for element in self {
      /// 有别于map的地方
      result.append(contentsOf: try transform(element))
    }
    return result
  }
}

compactMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
extension Sequence {
  /// Returns an array containing the non-`nil` results of calling the given
  /// transformation with each element of this sequence.
  ///
  /// Use this method to receive an array of non-optional values when your
  /// transformation produces an optional value.
  ///
  /// In this example, note the difference in the result of using `map` and
  /// `compactMap` with a transformation that returns an optional `Int` value.
  ///
  ///     let possibleNumbers = ["1", "2", "three", "///4///", "5"]
  ///
  ///     let mapped: [Int?] = possibleNumbers.map { str in Int(str) }
  ///     // [1, 2, nil, nil, 5]
  ///
  ///     let compactMapped: [Int] = possibleNumbers.compactMap { str in Int(str) }
  ///     // [1, 2, 5]
  ///
  /// - Parameter transform: A closure that accepts an element of this
  ///   sequence as its argument and returns an optional value.
  /// - Returns: An array of the non-`nil` results of calling `transform`
  ///   with each element of the sequence.
  ///
  /// - Complexity: O(*m* + *n*), where *n* is the length of this sequence
  ///   and *m* is the length of the result.
  @inlinable // protocol-only
  public func compactMap<ElementOfResult>(
    _ transform: (Element) throws -> ElementOfResult?
  ) rethrows -> [ElementOfResult] {
    return try _compactMap(transform)
  }

  // The implementation of compactMap accepting a closure with an optional result.
  // Factored out into a separate function in order to be used in multiple
  // overloads.
  @inlinable // protocol-only
  @inline(__always)
  public func _compactMap<ElementOfResult>(
    _ transform: (Element) throws -> ElementOfResult?
  ) rethrows -> [ElementOfResult] {
    var result: [ElementOfResult] = []
    for element in self {
      /// 与map的区别
      if let newElement = try transform(element) {
        result.append(newElement)
      }
    }
    return result
  }
}