This is the 9th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

The introduction

One area of Swift that I have been reluctant to learn is the collection types of the entire series. So why bother now, because the main reason is that the specific implementations provided in the standard library — arrays, collections, and dictionaries — cover 99 percent of everyday development. There is a more important reason —- too many protocols!

Not to mention the Swift 5.5. Introduces a new family of Protocols based on AsyncSequence, which will not be covered in this article.

Let’s try to figure out what each agreement does and why we need so many of them. The following figure shows the full set of collection protocols, which I’ll cover from top to bottom:

IteratorProtocol

Provides the type of a sequence value one at a time. This protocol is closely related to the Sequence protocol, as you’ll see later. A sequence provides access to its elements by creating iterators that track its iteration and return one element at a time as the sequence progresses. The definition of the agreement is as follows:

public protocol IteratorProtocol {
    associatedtype Element
    mutating func next(a) -> Element?
}
Copy the code

A method called next() that returns the next element or nil. It is marked mutating so that their internal state can be updated in preparation for the next call to next(). Iterators can generate values indefinitely if the implementation does not return nil. We rarely create iterators directly because there is a more common approach to ordering in Swift. However, let’s create a concrete iterator to see how it works.

struct DoublingIterator: IteratorProtocol {
    var value: Int
    var limit: Int? = nil

    mutating func next(a) -> Int? {
        if let l = limit, value > l {
            return nil
        } else {
            let current = value
            value * = 2
            return current
        }
    }
}

var doublingIterator = DoublingIterator(value: 1, limit: 1024)
while let value = doublingIterator.next() {
    print(value)
}
Copy the code

Call a simple iterator, doubling the value each time next() is called. If limit passes nil when we initialize DoublingIterator, the iterator will run forever until the value exceeds the maximum value.

Sequence

A type that can be used for sequential iterative access to its elements. A sequence is a series of values that we can access one at a time. Although seemingly simple, this capability allows us to perform a large number of operations, and we can perform these operations on any sequence. The Sequence protocol provides a default implementation for these common operations. Before exploring these operations, let’s take a look at the protocol definition ~

public protocol Sequence {
    associatedtype Element
    associatedtype Iterator: IteratorProtocol where Iterator.Element = = Element
    func makeIterator(a) -> some IteratorProtocol
}
Copy the code

The sequence ensures that the Element type of the iterator matches the sequence through its makeIterator() method and the associated type. Let’s create a concrete DoublingSequence using a DoublingIterator:

struct DoublingSequence: Sequence {
    var value: Int
    var limit: Int? = nil

    func makeIterator(a) -> DoublingIterator {
        DoublingIterator(value: value, limit: limit)
    }
}

let doubler = DoublingSequence(value: 1, limit: 1024)
for value in doubler {
    print(value)
}

print(doubler.contains { $0 = = 512 }) // true
print(doubler.reduce(0.+)) / / 2047
Copy the code

Just by following the Sequence, our concrete type gains the ability to for-in and some other operations, such as Map, filter, reduce, and so on. Sequence also provides methods such as dropFirst(_:) and dropLast(_:). However, at the sequence level, the implementation of these methods is constrained by iterating one element at a time. This reflects their time complexity — dropFirst(_:) is O(k), where k is the number of elements to delete, and dropLast(_:) is O(n), where n is the total number of elements in order. Unlike dropFirst(_:), dropLast(_:) requires that the sequence be finite.

There are a few things to be aware of when using Sequences

  • Sequences do not guarantee that multiple iterations will produce the desired result. How does the implementation type determine how to handle an iteration of a sequence that has already been iterated over once
  • The iterators provided by the sequence should ensure time complexity O(1). It has no additional requirements for element access. Therefore, unless otherwise documented, the method of traversing a sequence should be treated as O(n)

Given an element, Sequence allows us to move to the next element. In order to be able to move to any element (although there is no guarantee that the moving world is constant time), we need Collection.

Collection

A sequence whose elements can be accessed multiple times by subscript. When we use arrays, dictionaries, or collections, we benefit from the operations declared and implemented by the Collection protocol. In addition to the operations inherited from the Sequence protocol, we can also access the methods of elements at specific locations in the collection. The protocol for Collection is defined as follows:

protocol Collection: Sequence {
    associatedtype Index: Comparable

    var startIndex: Index { get }
    var endIndex: Index { get }
    subscript(position: Index) -> Element { get }
    func index(after i: Index) -> Index
}
Copy the code

Due to the need for multiple traversals and access through index subscripts, a collection cannot be evaluated lazily, nor can it be infinite. Unlike Sequences, Sequences can update their internal state with the current call to next() in preparation for the next call. Also note that associatedType Index is not an Int, but any type that complies with Comparable.

conclusion

In the next article, we’ll explore the rest