Set type protocol
Collection types in Swift, including Array, Dictionary, and Set. Sequence and Collection protocols form the cornerstone of this set of Collection types.
graph TD A[Sequence] --> B[LazySequenceProtocol] A[Sequence] --> C[Collection] B --> D[LazyCollectionProtocol] C --> D C --> E[RangeReplaceableCollection] C --> F[BidirectionalCollection] C --> G[MutableCollection] F --> H[RandomAccessCollection]- Sequence provides the ability to iterate. It allows you to create an iterator, but provides no guarantee that the sequence can only be traversed once (reading the contents of standard input, for example) or supports multiple traversals (traversing an array, for example).
- Collection extends the Sequence. Not only is it a sequence that can be traversed multiple times, but it also allows you to access elements through indexes. Moreover, Collection also provides the ability to slice a Collection through SubSequence, which is itself a Collection.
- MutableCollection provides the ability to modify collection elements with subscripts in constant time. But it does not allow you to add or delete elements to the collection.
- RangeReplaceableCollectionProvides the ability to replace elements of a contiguous interval in a collection. By extension, this capability has spawned methods such as Append and Remove. Interval content substitution is possible for many mutable collections, but there are exceptions. For example, the most commonly used
Set和DictionaryThis operation is not supported, andArray和StringNo problem. - BidirectionalCollectionAdded the ability to traverse from the tail of a collection to the head of a collection. Obviously, we can’t go through one like this
Dictionary“, but iterating through a string “backwards” is perfectly fine. For some algorithms, reverse traversal is a critical operation. - RandomAccessCollectionExtend the
BidirectionalCollection, adds more efficient index computing power: it requires that calculating distances between indexes or moving index positions are constant time operations. Such as:ArrayIs a random access set, but a string is not, because calculating the distance between two characters is a linear time operation. - LazySequenceProtocol defines a sequence in which elements are evaluated only at the beginning of the iteration. It is common in algorithms written in a functional style: you can take an infinite sequence, filter the elements, and then read the first few records in the result. This process does not exhaust resources by needing to compute infinitely many elements outside of the result set.
- LazyCollectionProtocol 和
LazySequenceProtocolIs similar, except that it is used to define collection types that have the same behavior characteristics.
The sequence
The Sequence protocol is fundamental in the structure of collection types. A sequence represents a series of values of the same type that can be iterated over.
for element in someSequence {
doSomething(with: element)
}
Copy the codeSatisfying the Sequence protocol is simple. All you have to do is provide a makeIterator() method that returns an iterator:
protocol Sequence {
associatedtype Element
associatedtype Iterator: IteratorProtocol
func makeIterator(a) -> Iterator
// ...
}
Copy the codeThe iterator
Sequences provide access to elements by creating an iterator. Iterators produce one value in the sequence at a time and manage the traversal state. In IteratorProtocol, the only method is next(), which needs to return the next value in the sequence each time it is called. When the sequence is exhausted, next() should return nil:
protocol IteratorProtocol {
associatedtype Element
mutating func next(a) -> Element?
}
Copy the codeThe API design guide recommends that the protocol name be a noun, with the suffix -able, -ible, or -ing ‘, depending on the role the protocol plays.
The association type Element specifies the type of value produced by the iterator. For example, the iterator for String has an element type of Character. By extension, the iterator also defines the element type of its corresponding sequence. This is done by defining a type constraint for the Sequence’s associated type Iterator: iterator.element == Element, which ensures that the elements in the Sequence and Iterator are of the same type: iterator.element == Element
protocol Sequence {
associatedtype Element
associatedtype Iterator: IteratorProtocol
where Iterator.Element = = Element
// ...
}
Copy the codeThe for loop is a short form of this code:
var iterator = someSequence.makeIterator()
while let element = iterator.next() {
doSomething(with: element)
}
Copy the codeCompliance with sequence protocol
For example, the following PrefixGenerator generates all non-empty prefixes of a string (including the string itself) in sequence.
struct PrefixIterator: IteratorProtocol {
let string: String
var offset: String.Index
init(string: String) {
self.string = string
offset = string.startIndex
}
mutating func next(a) -> Substring? {
guard offset < string.endIndex else { return nil }
offset = string.index(after: offset)
return string[..<offset]
}
}
Copy the codestruct PrefixSequence: Sequence {
let string: String
func makeIterator(a) -> PrefixIterator {
return PrefixIterator(string: string)
}
}
Copy the codefor prefix in PrefixSequence(string: "Hello") {
print(prefix)}/*
H
He
Hel
Hell
Hello
*/
Copy the codePrefixSequence(string: "Hello").map { $0.uppercased() }
// ["H", "HE", "HEL", "HELL", "HELLO"]
Copy the codeIterator and value semantics
Most iterators in the library have value semantics, but there are exceptions. AnyIterator is an iterator that encapsulates another iterator by wrapping it in an inner box object that is a reference type. Therefore, AnyIterator does not have value semantics.
Iterators and sequences based on functions
AnyIteratorThere is another acceptancenextFunction as an initialization method for parameters. And I’m going to take that and I’m going to take thatAnySequenceWhen used together, types allow us to create iterators and sequences without defining any new types.
func fibsIterator(a) -> AnyIterator<Int> {
var state = (0.1)
return AnyIterator {
let upcomingNumber = state.0
state = (state.1, state.0 + state.1)
return upcomingNumber
}
}
Copy the codelet fibsSequence = AnySequence(fibsIterator)
Array(fibsSequence.prefix(10)) / /,1,1,2,3,5,8,13,21,34 [0]
Copy the code- Another way is to use
Sequencefunction
let fibsSequence2 = sequence(state: (0.1)) { state -> Int? in
let upcomingNumber = state.0
state = (state.1, state.0 + state.1)
return upcomingNumber
}
Array(fibsSequence2.prefix(10)) / /,1,1,2,3,5,8,13,21,34 [0]
Copy the codeThe return value type for sequence(first: Next 🙂 and sequence(state:next:) is UnfoldSequence. The name for this type comes from functional programming, where this operation is called unfold. Sequence corresponds to reduce, which is often called a fold in functional programming. Reduce reduces (or collapses) a sequence into a single return value, while sequence expands a single value into a sequence.
Traverse the sequence once
Sequences are not limited to traditional collection data types such as arrays or lists. Network flows, files on disk, flows of UI events, and many other types of data can be modeled using sequences. But not all types of sequences are like arrays, allowing you to iterate over their elements. Sequences such as network packet streams can only be traversed once. If you iterate over it again, it won’t produce the same value. But Both Fibonacci sequences and network packet flows are valid sequences, so the documentation for Sequence makes it very clear that sequences are not guaranteed to be traversed more than once:
The Sequence protocol does not care if the type that follows the protocol destroys the elements of the Sequence after iteration. That is, do not assume that multiple for-ins to a sequence will continue the previous iteration or start from scratch.
If a sequence obeys the Collection protocol, it must be iterated over again, because Collection guarantees that. The opposite is not necessarily true. There are sequences in the library that can be safely iterated over multiple times, but they are not collection types. For example, stride(from:to:by:) returns a StrideTo, and stride(from:through:by) returns a StrideThrough.
The relationship between sequences and iterators
A sequence that is traversed once holds an iterative state of its own and changes as it traverses. However, for multiple traversable sequences, their values cannot change with the for loop; they require independent traversal states, which is why iterators exist. The purpose of the makeIterator method is to create such a traversal state.
Let the List obey the Sequence
enum List<Element> {
case end
indirect case node(Element, next: List<Element>)}extension List {
mutating func push(_ x: Element) {
self = .node(x, next:self)}mutating func pop(a) -> Element? {
switch self {
case .end: return nil
case let .node(x, next: tail):
self = tail
return x
}
}
}
Copy the codeextension List: ExpressibleByArrayLiteral {
public init(arrayLiteral elements: Element...). {
self = elements.reversed().reduce(into: .end) { partialList, element in partialList.push(element)
}
}
}
let list: List = [3.2.1]
/*node(3, next: List<Swift.Int>.node(2,next:
List<Swift.Int>.node(1,
next: List<Swift.Int>.end)))
*/
Copy the codeextension List: IteratorProtocol.Sequence {
public mutating func next(a) -> Element? {
return pop()
}
}
Copy the codeThere is no need to implement the makeIterator method: Swift provides a default implementation for sequences whose iterator type is itself. In this way, you can pass for… In traverses the List object:
let list2: List = ["1"."2"."3"]
for x in list2 {
print("\(x) ", terminator: "")}/ / 1 2 3
Copy the codeCollection types
Collection types refer to sequences that can be iterated over many times and remain consistent.
Custom collection type
A very simple fifO queue:
/// an efficient FIFO queue with Element type 'Element'
struct FIFOQueue<Element> {
private var left: [Element] = []
private var right: [Element] = []
/// Add the element to the end of the queue
// - complexity: O(1)
mutating func enqueue(_ newElement: Element) {
right.append(newElement)
}
/// Remove an element from the front of the queue
/// Returns nil when the queue is empty
/// - complexity: amortized O(1)
mutating func dequence(a) -> Element? {
if left.isEmpty {
left = right.reversed()
right.removeAll()
}
return left.popLast()
}
}
Copy the codeNotes in the document:
. To implement Collection for an amount type, you must declare the contents:
- StartIndex and endIndex properties.
- Subscript operators that have at least read-only access to collection elements.
- The index(after:) method used to step between collection indexes.
Therefore, we need to achieve:
protocol Collection: Sequence {
/// a type that represents the element in the sequence
associatedtype Element
/// a type that represents a location in a collection
associatedtype Index: Comparable
/// The position of the first element in a non-empty set
var startIndex: Index { get }
/// The position in the set that exceeds the last significant subscript value -- that is, the position that is 1 greater than the last valid subscript value
var endIndex: Index { get }
/// returns the position after the given index
func index(after i: Index) -> Index
/// access the element at a specific location
subscript(position: Index) -> Element { get}}Copy the codeLet FIFOQueue satisfy Collection:
extension FIFOQueue: Collection {
public var startIndex: Int { return 0 }
public var endIndex: Int { return left.count + right.count }
public func index(after i: Int) -> Int {
precondition(i > = startindex && i < endIndex, "Index out of bounds")
return i + 1
}
public subscript(position: Int) -> Element {
precondition((startIndex..<endIndex).contains(position), "Index out of bounds")
if position < left.endIndex {
return left[left.count - position - 1]}else {
return right[position - left.count]
}
}
}
Copy the codeArray literals
When implementing a similar FIFOQueue such collection types, also to achieve the best ExpressibleByArrayLiteral. This allows users to create a queue with the well-known [value1,value2,etc] syntax. The protocol only requires us to implement an initialization method that looks like this:
extension FIFOQueue: ExpressibleByArrayLiteral {
public init(arrayLiteral elements: Element...). {
self.init(left: elements.reversed(), right: [])
}
}
Copy the codeAssociation types
Collection provides default values for all association types except Index and Element. Anyway, let’s go through them one by one.
Iterator – This is an association type inherited from Sequence. The default iterator type in a collection type is IndexingIterator
, which is a simple structure that wraps the collection and iterates over each element with the index of the collection itself.
SubSequence – Is a type that represents a contiguous slice of content in a collection. SubSequence is itself a collection type. The default is Slice
, which encapsulates the original collection and stores the Slice’s start and end indexes relative to the original collection.
Indices – The type of the Indices property for the collection. It is the collection of all valid indexes in the collection in ascending order. Note that endIndex is not included because it represents the index after the last valid index and is not a valid subscript parameter.
extension FIFOQueue: Collection {
// ...
typealias Indices = Range<Int>
var indices: Range<Int> {
return startIndex..<endIndex
}
}
Copy the codeThe index
The index represents the location in the collection. Each collection has two special index values: startIndex and endIndex. StartIndex specifies the first element in the set, and endIndex is the position next to the last element in the set.
Integer indexing is straightforward, but it’s not the only option. The only requirement for an Index of a collection type is that it must implement Comparable; in other words, the indexes must have a definite order.
The dictionary’s index is of type DictionaryIndex, which is an opaque value pointing to the dictionary’s internal stored buffer.
The subscript(_ key: key) method we normally access with keys is an overloading of the subscript method defined directly on the Dictionary, which returns an optional Value:
struct Dictionary {
.
subscript(key: Key) -> Value?
}
Copy the codeThe method of accessing by index is defined by the Collection protocol, which always returns a non-optional value.
protocol Collection { subscript(position: Index) -> Element { get }}
Copy the codeIndex of the failure
- When the collection changes, the index may be invalidated.
- Removing an element from a dictionary always invalidates the index.
- An index should be a simple value that contains only the minimum information needed to describe the location of an element.
Indexes step by step
collection.index(after: someIndex)
Copy the codeCustom collection index
Start by looking for the range of the first word in SubString.
extension Substring {
var nextWordRange: Range<Index> {
let start = drop(while: { $0 = = "" })
let end = start.firstIndex(where: { $0 = = ""}) ?? endIndex
return start.startIndex..<end
}
}
Copy the codeWrap Range< subString. Index> and use it as the Index type.
struct WordsIndex: Comparable {
fileprivate let range: Range<Substring.Index>
fileprivate init(_ value: Range<Substring.Index>) {
self.range = value
}
static func <(lhs:Words.Index.rhs: Words.Indx) -> Bool {
return lhs.range.lowerBound < rhs.range.lowerBound
}
static func = =(lhs: Words.Index.rhs: Words.Index) -> Bool {
return lhs.range = = rhs.range
}
}
Copy the codeThe startIndex complexity of the Collection protocol is O(1).
struct Words {
let string: Substring
let startIndex: WordsIndex
init(_ s: String) {
self.init(s[.])}private init(_ s: Substring) {
self.string = s
self.startIndex = WordsIndex(string.nextWordRange)
}
public var endIndex: WordsIndex {
let e = string.endIndex
return WordsIndex(e..<e)
}
}
Copy the codeCollection types require us to provide subscript methods to retrieve elements.
extension Words {
subscript(index: WordsIndex) -> Substring {
return string[index.range]
}
}
Copy the codeThe final requirement for Collection is to be able to calculate the next index given an index.
extension Words: Collection {
public func index(after i: WordsIndex) -> WordsIndex {
guard i.range.upperBound < string.endIndex else {
return endIndex
}
let remainder = string[i.range.upperBound.]
return WordsIndex(remainder.nextWordRange)
}
}
Array(Words(" hello world test ").prefix(2)) // ["hello","world"]
Copy the codesubsequence
The Collection protocol also has an association type called SubSequence. It represents a continuous self interval in a set:
extension Collection {
associatedtype Subsequence: Collection = Slice<Self>
where Element = = SubSequence.Element.SubSequence = = SubSequence.SubSequence
}
Copy the codeSubSequence is used for those operations that return slices of the original combined type:
- Prefix and suffix – Gets n elements at the beginning or end.
- Prefix (while:) – starting with the collection, gets the operations that satisfy the conditions specified by while.
- DropFirst and dropLast – return subsequences that remove the first or last n elements.
- Drop (while:) – removes elements until the condition is no longer true, and then returns the remaining elements.
- Split – Splits a sequence with the specified split element, returning an array of subsequences.
In addition, range-based subscripting also returns the range marked in the original collection by the index within the range as a slice.
slice
Slice is a lightweight wrapper based on any collection type and is ideal for using as a default SubSequence type, but when creating a custom collection type, it is best to consider whether the collection type itself can be used as its SubSequence.
On the other hand, having a different type for the original collection and its slices helps avoid unexpected memory “leaks,” which is why the standard library uses ArraySlice and Substring as subsequences of arrays and Strings.
Slices share indexes with the original collection
Another formal requirement of the Collection protocol is that the index of a slice be used interchangeably with the index of the original Collection.
Specialized collection type
- As with all well-designed protocols, Collection strives to keep its requirements to a minimum.
- The library provides four specialized Collection types, each of which adds new functionality to a Collection in a specific way:
- BidirectionalCollection – “A collection that supports both forward and backward traversal”
- RandomAccessCollection – “A collection that allows efficient traversal of random access indexes”
- MutableCollection – “A collection that supports subscript assignments”
- RangeReplaceableCollection – “a support to anyon range of elements are replaced with other elements of the set of collections”
BidirectionalCollection
BidirectionalCollection adds a key capability to the collection, which is to move the index back one place through the index(before:) method. With this method, we can give an implementation of the default last attribute for first:
extension BidirectionalCollection {
/// The last element in the collection
public var last: Element? {
return isEmpty ? nil : self[index(before: endIndex)]
}
}
Copy the codeOf course, Collection itself can also provide the last attribute, but this is not a good idea. In a forward-only indexed collection type, fetching the last element requires iterating all the way to the end, which is an O(n) operation.
Benefiting from this ability to traverse collections forward, BidirectionalCollection also implements methods such as suffix, removeLast, and Reversed that can be executed efficiently.
Most types in the library implement BidirectionalCollection along with Collection.
RandomAccessCollection
RandomAccessCollection provides the most efficient way to access elements by jumping to any index in constant time. To do this, the type satisfying the protocol must be able to (a) move an index by any distance, and (b) measure the distance between any two indexes, both of which need to be O(1) time constant operations. RandomAccessCollection redeclares the associated Indices and SubSequence types with tighter constraints, which must themselves be randomly accessible. You can do this by providing the index(_:offsetBy:) and distance(from:to:) methods, or by using a Strideable index type (like Int).
MutableCollection
Mutable collections support in-place element changes. MutableCollection adds only one additional requirement compared to Collection, that the subscript access method of a single element must now provide a setter:
extension FIFOQueue: MutableCollection {
public var startIndex: Int { return 0 }
public var endIndex: Int { return left.count + right.count }
public func index(after i: Int) -> Int {
return i + 1
}
public subscript(position: Int) -> Element {
get {
precondition((0..<endIndex).contains(position), "Index out of bounds")
if position < left.endIndex {
return left[left.count - position - 1]}else {
return right[position - left.count]
}
}
set {
precondition((0..<endIndex).contains(position), "Index out of bounds")
if position < left.endIndex {
left[left.count - position - 1] = newValue
} else {
return right[position - left.count] = newValue
}
}
}
}
Copy the codevar playlist: FIFOQueue = ["Shake It Off"."Blank Space"."Style"]
playlist.first // Optional("Shake It Off")
playlist[0] = "You Belong With Me"
playlist.first // Optional("You Belong With Me")
Copy the codeMany algorithms for in-place modification of collections require that the corresponding collection type meet the MutableCollection protocol. Examples include in situ sort, reverse order, and swapAt methods in the standard library. Relatively few types in the standard library satisfy MutableCollection. Of the three main collection types, only Array satisfies this protocol.
RangeReplaceableCollection
For the operation of the need to add or remove elements, can use RangeReplaceableCollection agreement. This agreement has two requirements:
- An empty initialization method – this is useful in generic functions because it allows a function to create an empty collection of the same type.
- a
replaceSubrange(_:with:)Method – it takes a range to replace and a collection to replace.
A perfect example of power RangeReplaceableCollection is to show agreement. If you implement a flexible replaceSubrange method, protocol extensions can provide you with a range of useful methods:
- append(_:) 和 apend(contentsOf:)–
endIndex.. <endIndex(that is, the empty range at the end) is replaced with a single or multiple new elements. - remove(at:) 和 removeSubrange(_:)–
i... iorsubrangeReplace it with an empty set. - insert(at:) 和 insert(contentsOf:at:)–
i.. <i(or an empty range at a location in the array) is replaced by a single or multiple new elements. - removeAll–
startIndex.. <endIndexReplace it with an empty set.
This method is also part of the protocol requirements. Of course, you can, depending on the situation, provide a more efficient implementation of your own, overriding the default implementation.
extension FIFOQueue: RangeReplaceableCollection {
mutating func replaceSubrange<C: Collection> (_ subrange: Range<Int>, with newElements: C)
where C.Element = = Element {
right = left.reversed() + right
left.removeAll()
right.replaceSubrange(subrange,with: newElements)
}
}
Copy the codeUnlike RandomAccessCollection expanded the BidirectionalCollection, RangeReplaceableCollection not to MutableCollection extension, They have their own independent inheritance relationship. In the standard library, the String is an implementation of a RangeReplaceableCollection but did not achieve MutableCollection example.
Combination ability
For example, the sort method in the standard library.
extension MutableCollection where Self: RandomAccessCollection.Element: Comparable {
// sort the collection in place
public mutating func sort(a) { .}}Copy the codeDelay sequence
The library provides two protocols for supporting lazy programming: LazySequenceProtocol and LazyCollectionProtocol. Deferred programming means that results are computed only when they are really needed, which is a concept compared to eager programming.
The library provides a.lazy attribute for Sequence to help us implement a delayed Sequence.
Deferred processing of collections
Deferred processing sequences are more efficient when multiple operations are concatenated on a common collection type (for example, Array).
(1..<100).map { $0 * $0 }.filter { $0 > 10 }.map { "\ [$0)" }
(1..<100).lazy.map {$0 * $0 }.filter { $0 > 10 }.map { "\ [$0)" }
Copy the codeIn Swift5.0, code that uses.lazy can be up to three times faster than previous IBIS versions without compiler optimizations enabled, and up to eight times faster when optimizations are enabled with -o.