Swift进阶二:序列

1. 序列
   Array,Dictionary,Set都是建立在Sequence 和Collection 协议上的;
   Sequence协议就是抽象了序列的概念.最基本的就是一个序列需要由同样类型的数据组成,可以迭代这个序列
   满足Sequence协议只需要实现一个迭代器

protocol Sequence { 
  associatedtype Iterator: IteratorProtocol 
  func makeIterator() -> Iterator 
  // ... 
}

2.IteratorProtocol是实现迭代器的协议,它只有一个方法next(),返回序列下一个元素

protocol IteratorProtocol { 
  associatedtype Element 
  mutating func next() -> Element? 
}

事实上for循环就是实现迭代器并且不停的调用next()的简化过程

var iterator = someSequence.makeIterator() 
  while let element = iterator.next() { 
  doSomething(with: element)
 }

自定义一个迭代器可以实现一些特别的需求, 比如一般来说迭代器是用来查看序列的,但是即使没有序列迭代器也是一样的工作,比如实现一个输出斐波那契数列的迭代器,这个例子没有结束,会一直输出到Int类型溢出.

struct FibsIterator: IteratorProtocol { 
    var state = (0, 1)
     mutating func next() -> Int? { 
        let upcomingNumber = state.0
        state = (state.1, state.0 + state.1)
         return upcomingNumber 
      } 
  }

 var iterator = FibsIterator() 
 while let x = iterator.next() { 
      print(x) 
  }

3.现在开始遵循Sequence协议,给斐波那契迭代器增加一个上限,然后声明一个斐波那契序列,实现迭代器方法.

struct FibsIterator: IteratorProtocol {
    var state = (0, 1)
    var max : Int
    init(max:Int){
        self.max = max
    }
    mutating func next() -> Int? {
        let upcomingNumber = state.0
        state = (state.1, state.0 + state.1)
        if upcomingNumber >= max{
            return nil
        }
        return upcomingNumber
    }
}

struct FibsSequence: Sequence {
    var max : Int
    func makeIterator() -> FibsIterator {
        return FibsIterator.init(max: max)
    }
}

现在可以使用for in来迭代了,当然还有其他Sequence协议的方法.

        let fibList = FibsSequence.init(max: 100)
        for v in fibList{
            print(v)
        }
//        fibList.map(<#T##transform: (Int) throws -> T##(Int) throws -> T#>)
//        fibList.filter(<#T##isIncluded: (Int) throws -> Bool##(Int) throws -> Bool#>)

这里FibsSequence结构体其实没什么实质作用,直接声明一个Fibs,同时遵循IteratorProtocol, Sequence,然后实现next()即可

struct Fibs: IteratorProtocol, Sequence {
    var state = (0, 1)
    var max : Int
    init(max:Int){
        self.max = max
    }
    mutating func next() -> Int? {
        let upcomingNumber = state.0
        state = (state.1, state.0 + state.1)
        if upcomingNumber >= max{
            return nil
        }
        return upcomingNumber
    }
}

         let fiblist = Fibs.init(max: 100)
        fiblist.forEach { v in
            print(v)
        }

4.迭代器是值类型,如果赋值,会被复制一份,同时状态也会被复制,并且之后两个迭代器就不再相关了.

var it = FibsIterator.init(max: 100)
        print("it1 = \(it.next() ?? 0)")
        print("it1 = \(it.next() ?? 0)")
        print("it1 = \(it.next() ?? 0)")
        print("it1 = \(it.next() ?? 0)")
        print("it1 = \(it.next() ?? 0)")
        var it2 = it
        print("it1 = \(it.next() ?? 0)")
        print("it1 = \(it.next() ?? 0)")
        print("it2 = \(it2.next() ?? 0)")
        print("it2 = \(it2.next() ?? 0)")
/*
it1 = 0
it1 = 1
it1 = 1
it1 = 2
it1 = 3
it1 = 5
it1 = 8
it2 = 5
it2 = 8
*/

5.序列与集合的区别,序列是一种结构描述,集合就是一组元素,集合(无序的)可以转换为序列,或者集合(有序的)就是序列,但是集合是有限的,序列可以是无限的,就比如上面的斐波那契序列.
序列不能保证多次迭代产生的结果是一样的,因为它的元素可能是延迟产生的,还是斐波那契序列的例子,每个值都是被计算出来的,增加一些其他代码,可以使第二次迭代和第一次结果不一样;而集合(Collection协议)可以保证迭代是可以安全重复的.

6. SubSequence是子序列,提供了一些便利的方法:

   
   image.png

7.实现一个单链表
首先用递归枚举indirect关键字实现节点,节点有两种,一是需要存放数据和持有下一个节点,另一种是表示链表的结尾,当然持有下一个为空也可以表示结尾.

enum List<Element> { 
  case end
  indirect case node(Element, next: List<Element>) 
}

接下来定义一个空链表,然后向头部添加节点,就像下面这样

        let empty = List<Int>.end
        let one = List<Int>.node(1, next: empty)

因此可以封装成insert()方法,现在创建并添加节点

    extension List{
        func insert(x:Element) -> List{
            return .node(x, next: self)
         }
     }
     let list = List<Int>.end.insert(x: 1).insert(x: 2).insert(x: 3)

看起来还行,但是它是倒序的,而且有点长,可以通过ExpressibleByArrayLiteral来实现数组字面量初始化链表;

extension List : ExpressibleByArrayLiteral{
    init(arrayLiteral elements: Element...) {
        self = elements.reduce(.end) { partialList, element in
            partialList.insert(x: element)
        }
    }
}

let list2 : List<Int> = [1,2,3]

链表的内容

这个链表的节点是死的,枚举是值类型,一旦创建这里的节点就不能修改了,也就是只能增加不能删除,而且增加也不会复制链表本身,只是相当于给链表换一个头,它可以有多个头,或者多个头加上身子,总之可以共用尾部;

共同的尾部

我们还可以在 List 上定义一些可变方法，来让我们能够将元素推入和推出 ,因为链表其实也是
一个栈，end在最下面,第一个元素在最上面,因此构造相当于 push，获取 next 元素相当于 pop;
push是insert,self相当于head,指向了新的节点,
当调用pop时,如果self是end,那么就是栈底;
如果self是一个节点,pop时要丢弃最外面的一个节点,也就是self,指向了后面的节点,head节点被释放,
pop方法是可以设置为返回节点的值,栈底返回nil

extension List {
    mutating func push(_ x: Element) {
        self = self.insert(x: x)
    }
    mutating func pop() -> Element? {
        switch self {
        case .end: return nil
        case let .node(x, next: tail):
            self = tail
            return x
        }
    }
}

        var stack: List<Int> = [3,2,1]
        var a = stack
        var b = stack
        a.pop() // Optional(3)
        a.pop() // Optional(2)
        a.pop() // Optional(1)
        stack.pop() // Optional(3)
        stack.push(4)
        b.pop() // Optional(3)
        b.pop() // Optional(2)
        b.pop() // Optional(1)
        stack.pop() // Optional(4)
        stack.pop() // Optional(2)
        stack.pop() // Optional(1)

可以看到,a和b变成了List的迭代器,修改变量a和b并不会修改节点,因为list是一个值类型.

现在让List遵循Sequence协议,用pop来实现next(),现在List就是一个序列了.

extension List: IteratorProtocol, Sequence {
    mutating func next() -> Element? {
        return pop()
    }
}

        let list : List = ["1","2","3"]
        print(list.joined(separator: ",")) // 3,2,1