集合

这里的集合指的是建立在Sequence协议上的Collection协议。
集合是稳定的序列，可以重复遍历而不会发生变化，除了遍历还可以使用下标访问，swift的下标不一定是整数，但一定是一个有限的范围，因此集合不能是无限的，如此，集合也产生了长度的属性count。

通过定义一个集合类型来理解Collection如何工作。
首先设计一个队列协议：

protocol Queue{
    //声明类型
    associatedtype Element
    //入队
    mutating func enqueue(_ newElement:Element)
    //出队
    mutating func dequeue() -> Element?
}

从这里能够感受swift特性的冰山一角，这个协议就三行代码，协议越简单，工作范围越大，使用越不受约束，效率可能就越低，因此如何使用非常关键，Xcode documentation里，swift协议的文档有大量的注释，其中还有很多demo，为的就是给出使用建议。
比如这个Squeue协议，我们可以建议入队和出队的复杂度需要是O(1),这就限制了可以使用这个协议的数据结构。仅仅2个方法，能够表达的功能太少，比如它没有peek方法来获取某个元素，只能按顺序出队，也没有限制必须是Collection，甚至没有限制它是FIFO先进先出还是LIFO后进先出等等。

接下来实现队列

struct FIFOQueue<Element>:Queue{
    
    private var left:[Element] = []
    private var right:[Element] = []
 
    mutating func enqueue(_ newElement: Element) {
        right.append(newElement)
    }
    
    mutating func dequeue() -> Element? {
        if left.isEmpty{
            left = right.reversed()
            right.removeAll()
        }
        return left.popLast()
    }
}

这个实现使用两个栈 (两个常规的数组) 来模拟队列的行为。当元素入队时，它们被添加到 “右”
栈中。当元素出队时，它们从 “右” 栈的反序数组的 “左” 栈中被弹出。当左栈变为空时，再将右
栈反序后设置为左栈。

接下来实现Collection协议

protocol Collection: Sequence {
    associatedtype Element // inherited from Sequence
    associatedtype Index: Comparable
    associatedtype IndexDistance: SignedInteger = Int
    associatedtype Iterator: IteratorProtocol = IndexingIterator<Self>
where Iterator.Element == Element
    associatedtype SubSequence: Sequence /* ... */
    associatedtype Indices: Sequence = DefaultIndices<Self>
    /* ... */
    var frst: Element? { get }
    var indices: Indices { get }
    var isEmpty: Bool { get }
    var count: IndexDistance { get }
    func makeIterator() -> Iterator
    func prefx(through: Index) -> SubSequence
    func prefx(upTo: Index) -> SubSequence
    func suffx(from: Index) -> SubSequence
    func distance(from: Index, to: Index) -> IndexDistance
    func index(_: Index, offsetBy: IndexDistance) -> Index
    func index(_: Index, offsetBy: IndexDistance, limitedBy: Index) -> Index?
    subscript(position: Index) -> Element { get }
    subscript(bounds: Range<Index>) -> SubSequence { get }
}

Collection协议有这么多的内容，不过很多都在extension中有默认实现 ，最终只需要实现下面这些方法

extension FIFOQueue: Collection {
    /// ⼀个⾮空集合中⾸个元素的位置
    public var startIndex: Int { return 0 }
    /// 集合中超过末位的位置---也就是⽐最后⼀个有效下标值⼤ 1 的位置
    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) -> Element {
        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]
        }
    }
}

重点在于下标方法 ，left和right两个数组加起来保存这完整的队列元素，需要根据不同的情况考虑从哪个数组取数据，现在来验证一下

var q = FIFOQueue<String>()
        for x in ["a","b","c","d","e"]{
            q.enqueue(x)
        }
        q.forEach { s in
            print(s)
        }
        print("出队 \(q.dequeue()!)")
        q.forEach { s in
            print(s)
        }
        print("入队")
        q.enqueue("f")
        q.forEach { s in
            print(s)
        }
        print("出队 \(q.dequeue()!)")
        q.forEach { s in
            print(s)
        }

输出结果
a
b
c
d
e
出队 a
b
c
d
e
入队
b
c
d
e
f
出队 b
c
d
e
f

实现ExpressibleByArrayLiteral的方法 直接字面量初始化

extension FIFOQueue : ExpressibleByArrayLiteral{
    typealias ArrayLiteralElement = Element
    public init(arrayLiteral elements: ArrayLiteralElement...) {
        left = elements.reversed()
        right = []
    }
}

var q:FIFOQueue = ["a","b","c","d","e"]

索引

索引表示集合中的位置，从上面可以看到，集合有两个特殊索引，startIndex和endIndex，前者是第一个元素，后者是最后一个元素的下一个位置，也就是endIndex不是有效的下标。
索引一半都是整数，但这不是唯一的选择，只要具有一定顺序，遵循Comparable就可以。
字典也有索引，类型是DictionaryIndex，根据键访问字典，得到一个value，而通过索引访问字典，得到一个元组(key: Key, value: Value)
需要注意的是，Collection定义了索引访问的方法 ，它返回一个非可选的值，哪怕可能会引起crash，因为错误的使用索引值，被认为是程序员的错误。通过key访问字典获取的是一个可选值，而通过DictionaryIndex获得元组是非可选。
swift的安全检查选择了一个合适的范围，如果所有的API都要考虑失败，那就太折磨了

集合发生变化时，索引可能会失效，比如错位，或者crash，但是字典不太一样
字典的索引不会随着新的键值对的加入而失效，直到字典的尺寸增大到触发重新的内存分配。
这是因为一般情况下字典存储的缓冲区内的元素位置是不会改变的，而在元素超过缓冲区尺寸
时，缓冲区会被重新分配，其中的所有元素的哈希值也会被重新计算。从字典中移除元素总是
会使索引失效。

关联类型，SubSequence是继承自Sequence，Collection对SubSequence添加了更详细的扩展，一个集合类型的 SubSequence 本身也应该是一个 Collection,比如String的关联类型SubString

自定义集合索引
作为非整数索引集合的例子，我们将会构建一种在字符串中迭代单词的方式。当你想要将一个
字符串分割成一个个的单词，最简单的方法就是使用
split(separator:maxSplits:omittingEmptySubsequences:) (当然，这是对英文而言)，这个方
法将使用提供的分割元素进行分割，把一个集合转变为其 SubSequence 的数组，它有一个缺点：这个方法将会热心地为你计算出整个数组。如果你的字符串非常大，而且你只
需要前几个词的话，这么做是相当低效的。为了提高性能，我们要构建一个 Words 集合，它能
够让我们不一次性地计算出所有单词，而是可以用延迟加载的方式进行迭代。

实现方案
定义一个从文章中查找单词的索引方法，首先把开头的空格都去掉，然后寻找下一个空格作为结束，最后返回一个Range

extension Substring {
    var nextWordRange: Range<Index> {
        let start = drop(while: { $0 == " "})
        let end = start.firstIndex(where: { $0 == " "}) ?? endIndex
        return start.startIndex..<end
    }
}

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.Index) -> Bool {
        return lhs.range.lowerBound < rhs.range.lowerBound
    }
    static func ==(lhs: Words.Index, rhs: Words.Index) -> Bool {
        return lhs.range == rhs.range
    }
}

struct Words: Collection {
    let string: Substring
    let startIndex: WordsIndex
    init(_ s: String) {
        self.init(s[...])
    }
    private init(_ s: Substring) {
        self.string = s
        self.startIndex = WordsIndex(string.nextWordRange)
    }
    var endIndex: WordsIndex {
        let e = string.endIndex
        return WordsIndex(e..<e)
    }
    
    subscript(index: WordsIndex) -> Substring {
        return string[index.range]
    }
    
    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)
    }
}

collection要求索引访问元素应该是O(1)，如果使用整数的索引，在获取第i个的时候，我们需要把整个字符串都处理好，然后取出第i个。
将 Range<Substring.Index> 进行包装，然后用它来作为索引类型，另外由于Comparable基于Equatable，所以还需要实现==方法
现在使用单词的range来作为索引访问words集合，就是O(1)的复杂度，类似于String的索引。

切片

切片已经在字符串操作中频繁使用了，虽然语法有些啰嗦。
所有的集合类型都有切片操作的默认实现，并且有一个接受Range<Index> 作为参数的下标方法。

切片与原集合共享索引，这一点比较违反直觉，但是又觉着合理

let cities = ["New York", "Rio", "London", "Berlin", "Rome", "Beijing", "Tokyo", "Sydney"]
let slice = cities[2...4]
cities.startIndex // 0 
cities.endIndex // 8 
slice.startIndex // 2 
slice.endIndex // 5

如果访问slice[0],就会crash，因为slice的startIndex是2，没有0，因此swift不建议使用索引的值（for index in collection.indices）来作为访问依据，应当尽可能始终选择for x in collection 的形式。另外如果需要在迭代的时候修改集合的内容，可以选择使用while循环，然后手动在每次迭代的时候增加索引值，这样你就不会用到 indices 属性。当你这么做的时候，要记住一定要从collection.startIndex 开始进行循环，而不要把 0 作为开始。

专门的集合类型

1.双向索引
BidirectionalCollection 在前向索引的基础上只增加了一个方法，但是它非常关键，那就是获取上一个索引值的 index(before:)，用它可以获取last元素，

extension BidirectionalCollection { 
/// 集合中的最后⼀个元素。
 public var last: Element? { 
        return isEmpty ? nil : self[index(before: endIndex)] 
    }
 }

BidirectionalCollection 还添加了一些高效的实现，比如 sufĩx，removeLast 和 reversed。这里的 reversed 方不会直接将集合反转，而是返回一个延时加载的表示方式

extension BidirectionalCollection { 
    /// 返回集合中元素的逆序表示⽅式似乎数组 
    /// - 复杂度: O(1) 
    public func reversed() -> ReversedCollection<Self> {
         return ReversedCollection(_base: self)
     }
 }

和上面 Sequence 的 enumerated 封装一样，它不会真的去将元素做逆序操作。ReverseCollection 会持有原来的集合，并且使用逆向的索引。集合会将所有索引遍历方法逆序，这样一来就可以通过前向遍历来在原来的集合中进行后向遍历了，相反也一样。

2.随机存取的集合类型
RandomAccessCollection 提供了最高效的元素存取方式，它能够在常数时间内跳转到任意索
引。要做到这一点，满足该协议的类型必须能够 (a) 以任意距离移动一个索引，以及 (b) 测量任
意两个索引之间的距离，两者都需要是 O(1) 时间常数的操作。

3.可变集合支持原地的元素更改
MutableCollection 增加了一个要求，单个元素的下标访问方法 subscript 现在必须提供一个 setter。
标准库中很少有满足 MutableCollection 的类型。在三个主要的集合类型中，只有Array 满足这个协议。MutableCollection 允许改变集合中的元素值，但是它不允许改变集合的⻓度或者元素的顺序。后面一点解释了为什么 Dictionary 和 Set 虽然本身当然是可变的数据结构，却不满足 MutableCollection 的原因。

乍一看读不懂，实际上就是list[0] = 1这种赋值方法。
给下标访问添加setter和getter

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 
        }
   }
}

4.添加或者移除元素
对于需要添加或者移除元素的操作，可以使用 RangeReplaceableCollection 协议。这个协议有两个要求：
1.一个空的初始化方法 — 在泛型函数中这很有用，因为它允许一个函数创建相同类型的新的空集合。 2.replaceSubrange(_:with:) 方法 — 它接受一个要替换的范围以及一个用来进行替换的
集合。

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)
    }
 }

这个协议添加了这些方法
→ append(:) 和 append(contentsOf:) — 将 endIndex..<endIndex (也就是说末尾的空范围) 替换为单个或多个新的元素。
→ remove(at:) 和 removeSubrange(:) — 将 i...i 或者 subrange 替换为空集合。
→ insert(at:) 和 insert(contentsOf:at:) — 将 i..<i (或者说在数组中某个位置的空范围) 替换为单个或多个新的元素。
→ removeAll — 将 startIndex..<endIndex 替换为空集合

Sequence 和 Collection 协议构成了 Swift 集合类型的基础,从中理解了所谓面向协议的冰山一角，高层级的抽象会使模型变得复杂，很多东西不容易看明白，但是越看越觉着很🐮🍺。