集合类型协议
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)
网友评论