Read the guide

Foxfriend technical team

Swift is a protocol oriented language. The protocol can be extended to provide specific implementations such as methods for the types that follow the protocol. By extending the protocol, we can provide default implementations for the methods required by the protocol. Protocols have been important in iOS since before Swift. If you think about the UITableViewDataSource and UITableViewDelegate protocols, they come to mind every day. For example, Array is a Struct that inherits 10 protocols. Bool is a Struct that inherits 7 protocols.

This is the first in a series of articles on the Swift Collection Type protocol. In this article, we try to understand the internals and logic of some of the underlying protocols to show you what makes Swift so powerful.

Sequence

A Sequence is a list of values that provides sequential, iterative access to elements.

1protocol Sequence {2 associatedtype Iterator3 func makeIterator() -> Iterator4}5protocol IteratorProtocol {6 associatedtype Element7 mutating func next() -> Element? 8}Copy the code

Sequence protocol requires a method named makeIterator to retrieve the Iterator and return Iterator Iterator. Iterator follows the IteratorProtocol, which has a mutating next method. This method returns the next object in the Sequence until no nil is returned.

Here’s an example:

1struct InfiniteIterator: IteratorProtocol {2  let value: Int3  mutating func next() -> Int? {4    return value5  }6}
Copy the code

InfiniteIterator follows the IteratorProtocol protocol, so we need the next method. Let’s simplify this by making the return value of next always value:

1var iterator = InfiniteIterator(value: 24)2iterator.next()   //243iterator.next()   //24
Copy the code

You’ll notice that the output is always 24. Let’s continue implementing the Sequence protocol:

1struct InfiniteSequence: Sequence {2 let value: Int3 func makeIterator() -> InfiniteIterator {4 return InfiniteIterator(value: value)}Copy the code

Implement the makeIterator method and return the type of the IteratorProtocol object, InfiniteIterator, just implemented in the previous step. Thus a Sequence protocol object is formed. We can try using the Sequence protocol’s prefix method to test the first few objects:

1let infinite = InfiniteSequence(value: 20)2for value in infinite.prefix(5) {3  print(value)   //204}
Copy the code

Types that follow sequences can be traversed using for in, such as:

1let array = [1,2,3]2for item in array {3    print(item)4}
Copy the code

So why does it work this way? The internal implementation is similar to the following. With iterators and the next method to get the next element, we know what’s next, and what’s next, and what’s next.

1var iterator = someSequence.makeIterator()2while let element = iterator.next() {3   doSomething(with:element)4}
Copy the code

A quick summary:

(1) a Sequence can be either a finiteSequence or an InfiniteSequence, as in the preceding example InfiniteSequence is an InfiniteSequence;

(2) Sequence can be iterated only once, sometimes multiple times, but there is no guarantee that it can be iterated multiple times each time.

AnySequence

To simplify the protocol complexity of creating sequences, we found that the standard library provides us with a Sequence method:

1func sequence<T>(first: T, next: @escaping (T) -> T?) -> UnfoldFirstSequence<T>
Copy the code

This function takes two arguments. The first argument requires the first value returned by the Sequence. The second argument is a closure that takes the previous Sequence element and returns the next one:

1func infiniteBasic(value: Int) -> UnfoldSequence<Int, (Int? , Bool)> {2 return sequence(first: value) { _ in return value }3}Copy the code

The return type UnfoldSequence follows both the IteratorProtocol and Sequence. This simplifies the previous step by eliminating the need to write two classes that follow each of these protocols:

1for value in infiniteBasic(value: 24).prefix(5) {2  print(value)3}
Copy the code

The output is still 24, the same as the previous implementations;

Then we’ll look at AnySequence in this section, which is a type eraser, officially defined as:

An instance of AnySequence forwards its operations to an underlying base sequence having the same Element type, hiding the specifics of the underlying sequence.

It has nothing to do with the actual type, but is used to hide the actual type inside. It is similar to the id in OC. AnySequence follows the Sequence protocol, so infiniteBasic above can be modified as:

1func infinite(value: Int) -> AnySequence<Int> {2  return AnySequence {3    sequence(first: value) { _ in return value }4  }5}6for value in infinite(value: 24).prefix(5) {7  print(value)    //24  8}
Copy the code

AnyIterator

Type erasure sequence. AnyIterator is an instance of AnySequence that forwards its operations to the underlying base sequence with the same element type, thus hiding the details of the underlying sequence. The essence is to pass in a closure that generates the next Element, and internally iterate through the next Element type through the next method.

1func infinite(value: Int) -> AnySequence<Int> {2  return AnySequence<Int> {3    AnyIterator<Int> { value }4  }5}
Copy the code

The AnyIterator closure returns the next element, as as defer, which hides the implementation of the IteratorProtocol, as shown in the following example:

 1var x=0 2func infinite2(value: Int) -> AnySequence<Int> { 3    return AnySequence<Int> { 4        AnyIterator<Int> { 5            defer { 6                x+=1 7            } 8            return x<15 ? x : nil 9        }10    }11}



1for value in infinite2(value: 24) {2    print(value)3}
Copy the code

This code iterates through +1 returns every time until 15.

Sequence protocol has the Iterator attribute. This attribute follows the IteratorProtocol. UnfoldSequence protocol follows both Sequence and IteratorProtocol. AnySequence follows the Sequence protocol. AnySequence also has the same Iterator attribute. This attribute follows the AnyIterator protocol, and the AnyIterator protocol follows both the IteratorProtocol and Sequence. Therefore, we can form a Sequence by combining AnySequence and AnyIterator.

Collection

A collection is an indexed sequence that can be addressed many times (one way) from any index.

Implement a collection:

  • Define Comaprable index type.

  • Define startIndex;

  • Define endIndex, which is next to the last element;

  • Index (after:);

  • Define O(1) subscript operator get only to pass the given index and return element element.

Let’s take a specific example, called the Fizz Buzz Collection; We’re going to create a set from 1 to 100, print a range from 1 to 100, and if it’s divisible by 3, print Fizz; When divisible by 5, print Buzz; If it’s divisible by both 3 and 5, print FizzBuzz.

 1struct FizzBuzz: Collection { 2 3    typealias Index = Int 4 5    var startIndex: Index { 6        return 1 7    } 8 9    var endIndex: Index {10        return 10111    }1213    func index(after i: Index) -> Index {14        return i + 115    }1617    func index(_ i: Int, offsetBy distance: Int) -> Int {18        return i + distance19    }2021    subscript (index: Index) -> String {22        precondition(indices.contains(index), "out of 1-100")23        switch (index.isMultiple(of: 3), index.isMultiple(of: 5)) {24        case (false, false):25            return String(index)26        case (true, false):27            return "Fizz"28        case (false, true):29            return "Buzz"30        case (true, true):31            return "FizzBuzz"32        }33    }34}
Copy the code

A Collection inherits from a Sequence. Unlike a Sequence, a Collection can no longer be infinite. You always know how many elements there are in a Collection, so we can iterate over the Collection many times; For sequences, you can only iterate once; In addition, the main new element in the protocol is a new association type named Index. The scope of the Collection is from startIndex to endIndex. Note that endIndex refers to the position next to the last element, so 101. In addition, the Index association type must be Comparable; getting the next element increases Index until endIndex is reached, at which point the iteration terminates.

1for value in FizzBuzz() {2    print(value)3}
Copy the code

BidirectionalCollection

A bidirectional set is very similar to a set, except it has one more feature. In the same way that a Collection inherits from a Sequence, a BidirectionalCollection inherits from a Collection, but a BidirectionalCollection can move in either direction. In the collection, we already have indexAfter, so to add back functionality, we need to add a new function called indexBefore, which will let us traverse the collection in reverse order.

1protocol Collection {2 //... 3 func index(after index: Index) -> Index4}56protocol BidirectionalCollection: Collection {7 func index(before index: Index) -> Index8}9Copy the code

If you think about it if it’s a Collection normal Collection, what do you do if you want to get the last element?

Obviously you have to go through it one by one, until you get to the last element, which is obviously too slow, but we prefer to skip to the end and return the last value right away, and now with BidirectionalCollection, it’s a lot different, check if the collection is empty, and if it’s empty, then just return nil; If not, we need to take endIndex, and then use indexBefore to get the previous index of endIndex, which gives us the last element.

1var last: Iterator.Element? {2 guard ! self.isEmpty else { return nil }3 let indexOfLastItem = self.index(before: self.endIndex)4 return self[indexOfLastItem]5}Copy the code

RandomAccessCollection

Following this protocol allows faster access to values. You can jump directly to the element you want without having to step through it; RandomAccessCollection inherits from BidirectionalCollection and allows you to access any collection of elements in constant time. The common example is Array.

Following the RandomAccessCollection requires implementing the index(_:offsetBy:) and distance(from:to:) methods or the Index follows the Strideable protocol.

MutableCollection

Supports a collection to subscript its own elements, namely array[index] = newValue. The new API to this protocol over Collection is a setter method that subscript[5] must provide.

RangeReplaceableCollection

Supports insertion and deletion of arbitrary range of element sets; Follow RangeReplaceableCollection agreement need to implement:

(1) empty initialization set;

(2) implement replaceSubrange (_ : with:), RangeReplaceableCollection agreement provides a default implementation of this method, it is used to replace the current set of elements in the specified range. The target range and the length used to replace the set can differ.

We’ll look back at this article began in the types of relationship graph, you will find MutableCollection RangeReplaceableCollection and in the same level, and no inheritance relationships, Some types meet MutableCollection only (e.g. UnsafeMutableBufferPointer [6]), some only applies to RangeReplaceableCollection (such as a String. CharacterView), Only a portion of the Array is complied with, as shown in the figure below:

conclusion

Sequence and Collection form the foundation of Collection types in Swift. The specialized collection types are BidirectionalCollection, RandomAccessCollection, MutableCollection, and RandomAccessCollection Provides very fine-grained control over the functionality and performance features of your custom types and algorithms, making for a powerful combination of capabilities.

Reference: / Github /