简单 Swift 数组扩展

Question

正在尝试扩展 Array 类型以使用二进制排序按顺序插入元素。这是我的游乐场代码：

  extension Array  {

      func insertionIndexOf(elem: T , isOrderedBefore: (T, T) -> Bool) -> Int {
       var lo = 0
       var hi = self.count - 1
       while lo <= hi {
        let mid = (lo + hi)/2
        if isOrderedBefore(self[mid], elem) {
            lo = mid + 1
        } else if isOrderedBefore(elem, self[mid]) {
            hi = mid - 1
        } else {
            return mid
        }
    }
        return 0 
 }


  mutating func insertOrdered(elem: T){
     let index = self.insertionIndexOf(elem, isOrderedBefore: { (a , b)     in return (a > b) } )
     return insert(elem, atIndex: index)
}

}

我收到一个编译器错误："cannot invoke insertionIndexOf with argument list of type ( T , isOrderedBefore: (_, _) -> _) "

奇怪的是，如果我改用：

    mutating func insertOrdered(elem: T){
         let index = self.insertionIndexOf(elem, isOrderedBefore: { (a , b) in return false } )
         return insert(elem, atIndex: index)
        }

编译器冷静下来，但数组插入不会有序，:(当然。请有什么想法？？谢谢。

（使用 Xcode 6.3 测试版 2 - Swift 1.2）

Answer 1

您正在尝试评估 a > b，但 T 可能不是 Comparable。今天不可能写这样的扩展。你想说的是：

extension Array where T: Comparable {

但目前 Swift 无法做到这一点。编译器团队已经表明这是一个优先事项，但我们不知道什么时候可能会到Swift。

您最好的方法是将其设为函数：

func insertOrdered<T: Comparable>(inout xs: [T], x: T)

或者创建一个具有数组的新对象：

struct OrderedArray<T: Comparable> : ... {
    var values: [T]
    func insertionIndexOf(elem: T , isOrderedBefore: (T, T) -> Bool) -> Int
    mutating func inserOrdered(elem: T)
    ...
}

Answer 2

从 Swift 2 开始，这可以通过 协议扩展方法来实现 :

extension CollectionType where Generator.Element : Comparable, Index == Int {

    func insertionIndexOf(elem: Generator.Element) -> Int {
        var lo = 0
        var hi = self.count - 1
        while lo <= hi {
            let mid = (lo + hi)/2
            if self[mid] < elem {
                lo = mid + 1
            } else if elem < self[mid] {
                hi = mid - 1
            } else {
                return mid // found at position mid
            }
        }
        return lo // not found, would be inserted at position lo
    }
}

extension RangeReplaceableCollectionType where Generator.Element : Comparable, Index == Int {

    mutating func insertOrdered(elem: Generator.Element) {
        let index = self.insertionIndexOf(elem)
        self.insert(elem, atIndex: index)
    }
}

示例：

var ar = [1, 3, 5, 7]
ar.insertOrdered(6)
print(ar) // [1, 3, 5, 6, 7]

这些方法没有直接为 struct Array 定义，但是对于一些 Array 遵守的协议，并提供必要的方法。

对于第一种方法，即CollectionType，因为提供（读取）下标访问，以及集合元素类型必须是 Comparable.

第二种方法变异集合，这里是更严格的协议 RangeReplaceableCollectionType 为必填项。

简单 Swift 数组扩展

Simple Swift Array Extension

arrays

swift

swift-playground