集合类型协议

3.2集合类型:Collection

---

这一节只要目的是通过自定义一个FIFO(First Input First Output)的集合去了解一些细节。

稳定的序列(可多次遍历且保持一致)，可通过下标获取其中的元素。

知识点1：Collection建立在Sequence协议之上

知识点2：String，Data，IndexSet也准守了Collection协议。

知识点3：swift数组可以当做栈 用append入栈，popLast出栈

注：数组是在连续的内存中持有元素，移除非末尾元素时，后面的元素都会移动填补空白，复杂度为O(n)。 做类似操作的时候可以从性能方面去考虑一下。

队列可以结合使用 push和remove(at:0)

为队列设计协议：Iterator

---

/// 自己写一个最简单的将元素入队和出队的类型
protocol Queue{
    ///self中所持有的元素类型
    associatedtype Element
    ///把newElement 加入队列
    mutating func enqueue(_ newElement: Element)
    ///从self出队一个元素
    /// 返回值是可选值? 队列为空时这样的做法是安全的
    mutating func dequeue() -> Element?
}

这就表述了队列的定义。

队列的实现

下面我们将准守上面的Queue协议，写一个FIFO( First Input First Output)队列

///FIFO( First Input First Output)
struct FIFOQueue:Queue {
    
    fileprivate var left: [Int] = []
    fileprivate var right: [Int] = []
    
    ///把元素添加到队尾
    /// 复杂度O(1)
    mutating func enqueue(_ newElement: Int) {
        right.append(newElement)
    }
    
    
    /// 从队列首部移除一个元素
    /// 队列为nil时候返回空
    /// - 复杂度： 平摊 O(1)
    mutating func dequeue() -> Int? {
        if left.isEmpty {
            left = right.reversed()
            right.removeAll()
        }
        return left.popLast()
    }
}

入队添加到"右",
出队从"右"的反序"左"中被弹出。 "左"为空时再将"右"反序设置为左(好绕，不太理解的同学可以自己看着代码把流程走走就很快能理解啦~)

准守Collection协议

---

前面我们已经有一个FIFO队列了，下面可以为它添加Collection协议啦~ 在swift2.0的时候Collection协议有
4个关联类型
4个属性
7个实例方法
2个下标方法

在swift4.2中有略微改进。。具体可参照Collection 苹果官方文档

是不是有点慌。一开始看到的时候我也慌😂，其实捏 所有的关联类型都有默认值 除非你有特殊需求，一般不用关心的。

下面我们就开始让我们的FIFO去遵守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 < endIndex)
        return i + 1
    }
    
    public subscript(position: Int) -> Int {
        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]
        }
    }
}

下面就可以愉快地使用我们创建的FIFOQueue啦~

遵守 ExpressibleByArrayLiteral协议

---

ExpressibleByArrayLiteral的主要作用是可以让对象支持字面量初始化
第一次看这个名词我也一脸懵。
其实就是让你的集合可以用[value1, value2, etc]的方式去创建。

extension FIFOQueue:ExpressibleByArrayLiteral{
    ///ExpressibleByArrayLiteral 的init方法去实现一下就ok~ 
    init(arrayLiteral elements: Int...) {
        self.init(left: elements.reversed(), right: [])
    }
}

关联类型

---

Iterator 是从Sequence 继承的关联类型。Iterator 是对集合的封装，用集合本身的索引去迭代每一个元素。 这里讲的比较简单，可百度，待补充。 (TO BE ENHANCEMENT)

文章源文件地址