2017-04-17 17:43:05 we7ss 阅读数 2454

在使用Swift的Array的时候发现没有removeObject方法,出于使用原生类型的考虑不打算换成NSMutableArray,于是在网上找到解决方式如下:

为Array类添加扩展

extension Array where Element: Equatable {
    
    // Remove first collection element that is equal to the given `object`:
    mutating func remove(_ object: Element) {
        if let index = index(of: object) {
            remove(at: index)
        }
    }
}

代码摘自:http://stackoverflow.com/questions/24938948/array-extension-to-remove-object-by-value


如此则可如

var a = [1,2,2,3]
a.remove(2)
一般流畅使用。

在Playground中测试以上例子确实无比顺利,但是具体项目编写的时候一直提示问题,

提示为:incorrect argument label in call (have 'object:', expected 'at:')


而且在我尝试使用index(of: object)方法的时候会提示:

Cannot invoke 'index' with an argument list of type '(of: AnyObject)'


经过反复研究,发现这是我的疏忽。

由于对于Swift的类型严格的不熟悉,我在声明Array的时候使用了

var finishedLines = Array<Any>()
的方式,但是Any并不是一个遵守Equatable协议的表示,即便我存入数组里的都是继承自NSObject的对象,而NSObject原生遵守Equatable协议,但是在类型严格的语言情况下这会被否定。而事实上我存在里面的全都是Line类型实例,一个继承自遵守Equatable协议的NSObject的类。

在把声明换成以下写法之后一切终于正常进行。

var finishedLines = Array<Line>()

这一次问题的主要原因在于我对类型严格和类型检查的不了解和不熟悉,查找问题源头的时候也有验证过自己的类是否遵循了协议,但是却忽视了数组的声明,所以才会冒出明明所有对象都遵循协议却偏偏不能正常识别和调用的问题。



2018-06-27 09:13:31 weixin_33763244 阅读数 242

关于 ContiguousArray ,这边有喵神的文章介绍的很详细了,可以先看看这个文章。

Array

接着喵神的思路,看一下 Array 以下是从源码中截取的代码片段。

public struct Array<Element>: _DestructorSafeContainer {
  #if _runtime(_ObjC)
    internal typealias _Buffer = _ArrayBuffer<Element>
  #else
    internal typealias _Buffer = _ContiguousArrayBuffer<Element>
  #endif

  internal var _buffer: _Buffer
  
  internal init(_buffer: _Buffer) {
    self._buffer = _buffer
  }
}
复制代码

if _runtime(_ObjC) 等价于 #if os(iOS) || os(macOS) || os(tvOS) || os(watchOS),从这个操作也可以看出 Swift 的野心不仅仅只是替换 Objective-C那么简单,而是往更加宽泛的方向发展。由于本次主要是研究在 iOS下的开发,所以主要看一下 _ArrayBuffer

_ArrayBuffer

去掉了注释和与类型检查相关的属性和方法。

internal typealias _ArrayBridgeStorage
  = _BridgeStorage<_ContiguousArrayStorageBase, _NSArrayCore>

internal struct _ArrayBuffer<Element> : _ArrayBufferProtocol {

  internal init() {
    _storage = _ArrayBridgeStorage(native: _emptyArrayStorage)
  }
  
  internal var _storage: _ArrayBridgeStorage
}
复制代码

可见 _ArrayBuffer 仅有一个存储属性 _storage ,它的类型 _ArrayBridgeStorage,本质上是 _BridgeStorage
_NSArrayCore 其实是一个协议,定义了一些 NSArray 的方法,主要是为了桥接 Objective-CNSArray
最主要的初始化函数,是通过 _emptyArrayStorage 来初始化 _storage

实际上 _emptyArrayStorage_EmptyArrayStorage 的实例,主要作用是初始化一个空的数组,并且将内存指定在堆上。

internal var _emptyArrayStorage : _EmptyArrayStorage {
  return Builtin.bridgeFromRawPointer(
    Builtin.addressof(&_swiftEmptyArrayStorage))
}
复制代码

_BridgeStorage

struct _BridgeStorage<NativeClass: AnyObject, ObjCClass: AnyObject> {
  
  typealias Native = NativeClass
  typealias ObjC = ObjCClass
  
  init(native: Native, bits: Int) {
    rawValue = _makeNativeBridgeObject(
      native, UInt(bits) << _objectPointerLowSpareBitShift)
  }
  
  init(objC: ObjC) {
    rawValue = _makeObjCBridgeObject(objC)
  }
  
  init(native: Native) {
    rawValue = Builtin.reinterpretCast(native)
  }
  
  internal var rawValue: Builtin.BridgeObject
复制代码

_BridgeStorage 实际上区分 是否是 class、@objc ,进而提供不同的存储策略,为上层调用提供了不同的接口,以及类型判断,通过 Builtin.BridgeObject 这个中间参数,实现不同的储存策略。

The ContiguousArray type is a specialized array that always stores its elements in a contiguous region of memory. This contrasts with Array, which can store its elements in either a contiguous region of memory or an NSArray instance if its Element type is a class or @objc protocol.

If your array’s Element type is a class or @objc protocol and you do not need to bridge the array to NSArray or pass the array to Objective-C APIs, using ContiguousArray may be more efficient and have more predictable performance than Array. If the array’s Element type is a struct or enumeration, Array and ContiguousArray should have similar efficiency.

正因为储存策略的不同,特别是在class 或者 @objc,如果不考虑桥接到 NSArray 或者调用 Objective-C,苹果建议我们使用 ContiguousArray,会更有效率。

Array 和 ContiguousArray 区别

通过一些常用的数组操作,来看看两者之间的区别。

append

ContiguousArray

public mutating func append(_ newElement: Element) {
    _makeUniqueAndReserveCapacityIfNotUnique()
    let oldCount = _getCount()
    _reserveCapacityAssumingUniqueBuffer(oldCount: oldCount)
    _appendElementAssumeUniqueAndCapacity(oldCount, newElement: newElement)
  }
 
 internal mutating func _makeUniqueAndReserveCapacityIfNotUnique() {
    if _slowPath(!_buffer.isMutableAndUniquelyReferenced()) {
      _copyToNewBuffer(oldCount: _buffer.count)
    }
  }
  
  internal mutating func _reserveCapacityAssumingUniqueBuffer(oldCount: Int) {
    let capacity = _buffer.capacity == 0

    if _slowPath(oldCount + 1 > _buffer.capacity) {
      _copyToNewBuffer(oldCount: oldCount)
    }
  }
  
  internal mutating func _copyToNewBuffer(oldCount: Int) {
    let newCount = oldCount + 1
    var newBuffer = _buffer._forceCreateUniqueMutableBuffer(
      countForNewBuffer: oldCount, minNewCapacity: newCount)
    _buffer._arrayOutOfPlaceUpdate(
      &newBuffer, oldCount, 0, _IgnorePointer())
  }
  
  internal mutating func _appendElementAssumeUniqueAndCapacity(
    _ oldCount: Int,
    newElement: Element
  ) {
    _buffer.count = oldCount + 1
    (_buffer.firstElementAddress + oldCount).initialize(to: newElement)
  }
复制代码

_makeUniqueAndReserveCapacityIfNotUnique() 检查数组是否是唯一持有者,以及是否是可变数组。
_reserveCapacityAssumingUniqueBuffer(oldCount: oldCount)检查数组内的元素个数加一后,是否超出超过所分配的空间。
前两个方法在检查之后都调用了 _copyToNewBuffer ,主要操作是如果当前数组需要申请空间,则申请空间,然后再复制 buffer
_appendElementAssumeUniqueAndCapacity(oldCount, newElement: newElement) 从首地址后的第 oldCount 个存储空间内,初始化 newElement

Array

Array 实现的过程与 ContiguousArray 差不多,但是还是有一些区别,具体看看,主要的区别存在于_ContiguousArrayBuffer_ArrayBuffer

_ContiguousArrayBuffer

internal var firstElementAddress: UnsafeMutablePointer<Element> {
  return UnsafeMutablePointer(Builtin.projectTailElems(_storage,
                                                       Element.self))
}
复制代码

直接返回了内存地址。

_ArrayBuffer

internal var firstElementAddress: UnsafeMutablePointer<Element> {
   _sanityCheck(_isNative, "must be a native buffer")
   return _native.firstElementAddress
 }

 internal var _native: NativeBuffer {
   return NativeBuffer(
     _isClassOrObjCExistential(Element.self)
     ? _storage.nativeInstance : _storage.nativeInstance_noSpareBits)
 }
 
internal typealias NativeBuffer = _ContiguousArrayBuffer<Element>
复制代码

从调用的情况来看,本质上还是调用了 _ContiguousArrayBufferfirstElementAddress

但是在创建时,会有类型检查。

_isClassOrObjCExistential(Element.self)检查是否是类或者@objc修饰的。

在上述中检查持有者是否唯一和数组是否可变的函数中, 其实是调用了 _buffer内部的 isMutableAndUniquelyReferenced()

_ContiguousArrayBuffer

 @inlinable
  internal mutating func isUniquelyReferenced() -> Bool {
    return _isUnique(&_storage)
  }
复制代码
internal func _isUnique<T>(_ object: inout T) -> Bool {
  return Bool(Builtin.isUnique(&object))
}
复制代码

最后调用的 Builtin 中的 isUnique

_ArrayBuffer

internal mutating func isUniquelyReferenced() -> Bool {
   if !_isClassOrObjCExistential(Element.self) {
     return _storage.isUniquelyReferenced_native_noSpareBits()
   }
   
   if !_storage.isUniquelyReferencedNative() {
     return false
   }
   return _isNative
 }
 
 mutating func isUniquelyReferencedNative() -> Bool {
   return _isUnique(&rawValue)
 }

 mutating func isUniquelyReferenced_native_noSpareBits() -> Bool {
   _sanityCheck(isNative)
   return _isUnique_native(&rawValue)
 }

func _isUnique_native<T>(_ object: inout T) -> Bool {
  _sanityCheck(
    (_bitPattern(Builtin.reinterpretCast(object)) &  _objectPointerSpareBits)
    == 0)
  _sanityCheck(_usesNativeSwiftReferenceCounting(
      type(of: Builtin.reinterpretCast(object) as AnyObject)))
 return Bool(Builtin.isUnique_native(&object))
}
复制代码

如果是 class 或者 @objc_ContiguousBuffer 一样。如果不是则需要调用 Builtin 中的 _isUnique_native,即要检查是否唯一,还要检查是否是 Swift 原生 而不是 NSArray。 相对于 _ContiguousArrayBuffer 由于 _ArrayBuffer 承载了需要桥接到 NSArray 的功能,所以多了一些类型检查的操作。

insert

ContiguousArray

//ContiguousArray
 public mutating func insert(_ newElement: Element, at i: Int) {
   _checkIndex(i)
   self.replaceSubrange(i..<i, with: CollectionOfOne(newElement))
 }
  
 public mutating func replaceSubrange<C>(
    _ subrange: Range<Int>,
    with newElements: C
  ) where C : Collection, C.Element == Element {
    let oldCount = _buffer.count
    let eraseCount = subrange.count
    let insertCount = newElements.count
    let growth = insertCount - eraseCount

    if _buffer.requestUniqueMutableBackingBuffer(
      minimumCapacity: oldCount + growth) != nil {

      _buffer.replaceSubrange(
        subrange, with: insertCount, elementsOf: newElements)
    } else {
      _buffer._arrayOutOfPlaceReplace(subrange, with: newElements, count: insertCount)
    }
  }
  
  internal mutating func requestUniqueMutableBackingBuffer(
    minimumCapacity: Int
  ) -> _ContiguousArrayBuffer<Element>? {
    if _fastPath(isUniquelyReferenced() && capacity >= minimumCapacity) {
      return self
    }
    return nil
  }
  
  //extension ArrayProtocol
  internal mutating func replaceSubrange<C>(
    _ subrange: Range<Int>,
    with newCount: Int,
    elementsOf newValues: C
  ) where C : Collection, C.Element == Element {
    _sanityCheck(startIndex == 0, "_SliceBuffer should override this function.")
    let oldCount = self.count //现有数组大小
    let eraseCount = subrange.count //需要替换大小

    let growth = newCount - eraseCount //目标大小 和 需要替换大小 的差值
    self.count = oldCount + growth  //替换后的数组大小

    let elements = self.subscriptBaseAddress //数组首地址。
    let oldTailIndex = subrange.upperBound 
    let oldTailStart = elements + oldTailIndex //需要替换的尾地址。
    let newTailIndex = oldTailIndex + growth //需要增加的空间的尾下标
    let newTailStart = oldTailStart + growth //需要增加的空间的尾地址
    let tailCount = oldCount - subrange.upperBound //需要移动的内存空间大小

    if growth > 0 {
      var i = newValues.startIndex
      for j in subrange {
        elements[j] = newValues[i]
        newValues.formIndex(after: &i)
      }
      for j in oldTailIndex..<newTailIndex {
        (elements + j).initialize(to: newValues[i])
        newValues.formIndex(after: &i)
      }
      _expectEnd(of: newValues, is: i)
    }
    else { 
      var i = subrange.lowerBound
      var j = newValues.startIndex
      for _ in 0..<newCount {
        elements[i] = newValues[j]
        i += 1
        newValues.formIndex(after: &j)
      }
      _expectEnd(of: newValues, is: j)

      if growth == 0 {
        return
      }

      let shrinkage = -growth
      if tailCount > shrinkage {   

        newTailStart.moveAssign(from: oldTailStart, count: shrinkage)

        oldTailStart.moveInitialize(
          from: oldTailStart + shrinkage, count: tailCount - shrinkage)
      }
      else {                      
        newTailStart.moveAssign(from: oldTailStart, count: tailCount)

        (newTailStart + tailCount).deinitialize(
          count: shrinkage - tailCount)
      }
    }
  }

复制代码

insert 内部实际是 调用了 replaceSubrange。 而在 replaceSubrange 的操作是,判断内存空间是否够用,和持有者是否唯一,如果有一个不满足条件则复制 buffer 到新的内存空间,并且根据需求分配好内存空间大小。

_buffer 内部的 replaceSubrange

  • 计算 growth 值看所替换的大小和目标大小差值是多少。
  • 如果 growth > 0 ,则需要将现有的内存空间向后移动 growth 位。
  • 替换所需要替换的值。
  • 超出的部分重新分配内存并初始化值。
  • 如果 growth <= 0,则将现有的值替换成新的值即可。
  • 如果 growth < 0,则将不需要的内存空间回收即可。(ps:删除多个元素或者需要替换的大小大于目标大小)。

Array insert 两者基本一致,唯一的区别和 append 一样在 在buffer的内部方法,isUniquelyReferenced() 中,多了一些类型检查。

remove

ContiguousArray

public mutating func remove(at index: Int) -> Element {
    _makeUniqueAndReserveCapacityIfNotUnique()
    let newCount = _getCount() - 1
    let pointer = (_buffer.firstElementAddress + index)
    let result = pointer.move()
    pointer.moveInitialize(from: pointer + 1, count: newCount - index)
    _buffer.count = newCount
    return result
  }
复制代码

检查数组持有者是否唯一,取出所要删除的内存地址,通过将当前的内存区域覆盖为一个未初始化的内存空间,以达到回收内存空间的作用,进而达到删除数组元素的作用。

Array

ContiguousArray 的区别就在于 _makeUniqueAndReserveCapacityIfNotUnique() 前面已经提到过,仍然是多了一些类型检查。

subscript

ContiguousArray

//ContiguousArray
public subscript(index: Int) -> Element {
    get {
      let wasNativeTypeChecked = _hoistableIsNativeTypeChecked()

      let token = _checkSubscript(
        index, wasNativeTypeChecked: wasNativeTypeChecked)

      return _getElement(
        index, wasNativeTypeChecked: wasNativeTypeChecked,
        matchingSubscriptCheck: token)
    }
  }
  
  public
  func _getElement(
    _ index: Int,
    wasNativeTypeChecked : Bool,
    matchingSubscriptCheck: _DependenceToken
  ) -> Element {
  #if false
    return _buffer.getElement(index, wasNativeTypeChecked: wasNativeTypeChecked)
  #else
    return _buffer.getElement(index)
  #endif
  }

  //ContiguousArrayBuffer
  internal func getElement(_ i: Int) -> Element {
    return firstElementAddress[i]
  }
复制代码

_hoistableIsNativeTypeChecked() 不做任何检查,直接返回 true_checkSubscript(index, wasNativeTypeChecked: wasNativeTypeChecked) 检查 index 是否越界。 _getElement 最终还是操作内存,通过 firstElementAddress 偏移量取出值。

Array

  //Array
  public
  func _checkSubscript(
    _ index: Int, wasNativeTypeChecked: Bool
  ) -> _DependenceToken {
#if _runtime(_ObjC)
    _buffer._checkInoutAndNativeTypeCheckedBounds(
      index, wasNativeTypeChecked: wasNativeTypeChecked)
#else
    _buffer._checkValidSubscript(index)
#endif
    return _DependenceToken()
  }
  
  func _hoistableIsNativeTypeChecked() -> Bool {
   return _buffer.arrayPropertyIsNativeTypeChecked
  }
  
  //ArrayBuffer
  internal var arrayPropertyIsNativeTypeChecked: Bool {
    return _hasNativeBuffer
  }
  
  internal var _isNativeTypeChecked: Bool {
    if !_isClassOrObjCExistential(Element.self) {
      return true
    } else {
      return _storage.isNativeWithClearedSpareBits(deferredTypeCheckMask)
    }
  }
复制代码

ContiguousArray_hoistableIsNativeTypeChecked() 直接返回 true, 而 Array 中如果不是 class 或者 @objc 会返回 ture,否则会检查是否可以桥接到 Swift

而在 Array_checkSubscript 调用的 _buffer 内部函数也不一样,下面来具体看一看内部实现。

  //ArrayBuffer
  internal func _checkInoutAndNativeTypeCheckedBounds(
    _ index: Int, wasNativeTypeChecked: Bool
  ) {
    _precondition(
      _isNativeTypeChecked == wasNativeTypeChecked,
      "inout rules were violated: the array was overwritten")

    if _fastPath(wasNativeTypeChecked) {
      _native._checkValidSubscript(index)
    }
  }
  
  //ContiguousArrayBuffer
  internal func _checkValidSubscript(_ index : Int) {
    _precondition(
      (index >= 0) && (index < count),
      "Index out of range"
    )
  }
复制代码

本质上就是多了一些是否是类型检查。

//Array
func _getElement(
    _ index: Int,
    wasNativeTypeChecked : Bool,
    matchingSubscriptCheck: _DependenceToken
  ) -> Element {
#if _runtime(_ObjC)
    return _buffer.getElement(index, wasNativeTypeChecked: wasNativeTypeChecked)
#else
    return _buffer.getElement(index)
#endif
  }

//ArrayBuffer
internal func getElement(_ i: Int, wasNativeTypeChecked: Bool) -> Element {
    if _fastPath(wasNativeTypeChecked) {
      return _nativeTypeChecked[i]
    }
    return unsafeBitCast(_getElementSlowPath(i), to: Element.self)
  }
  
internal func _getElementSlowPath(_ i: Int) -> AnyObject {
    let element: AnyObject
    if _isNative {
      _native._checkValidSubscript(i)
      
      element = cast(toBufferOf: AnyObject.self)._native[i]
    } else {
      element = _nonNative.objectAt(i)
    }
    return element
  }
  
  //ContiguousArrayBuffer
  internal subscript(i: Int) -> Element {
    get {
      return getElement(i)
    }
  }
复制代码

_buffer 内部的 getElement , 与 ContiguousArray 不同的是需要适配桥接到 NSArray 的情况,如果是 非NSArray 的情况调用的是 ContiguousArrayBuffer 内部的 subscript ,和 ContiguousArray 相同。

总结

从增删改查来看,不管是 ContiguousArray 还是 Array 最终都是操作内存,稍显区别的就是 Array 需要更多的类型检查。所以当不需要 Objective-C,还是尽量使用 ContiguousArray 。 下面是对数组中一些批量操作的总结:

  • removeAllinsert<C>(contentsOf: C, at: Int)removeSubrange:最终调用的是 replaceSubrange
  • append<S : Sequence>(contentsOf newElements: S)init(repeating repeatedValue: Element, count: Int):最终都是操作内存,循环初始化新的内存空间和值。

有什么不正确的地方,欢迎指出。

2018-05-28 18:39:21 qq_30932479 阅读数 0

协议的命名遵循Swift的标准库,即协议名以“Type”,"-able","-ible"结尾。

例如 SequenceType,GeneratorType,CustomStringCoveeertible,  -type定义行为,-able定义元素怎样做事。

Swift 能扩展协议

协议可以添加方法和属性

协议扩展能添加协议中已有属性和方法的实现

如果一个类遵循了协议,那么协议中的方法必须被这个类来实现或者在协议的扩展中被实现

上面是项目中遇到的协议中添加了3个方法,只在协议扩展中实现了一个,报错信息提示其他两个也得实现。

2015-12-15 20:20:37 abc649395594 阅读数 0

Swift中的集合

最近翻译完了《Advanced Swift》中文版的“集合”章节。书的质量非常高,讲解非常细致。但不可避免的导致篇幅有点长,有些前面的知识点看到后面无法串联起来。同时由于偏重于讲解,所以个人感觉总结还不够,比如我们可以考虑这几个问题:

  • 数组类型(_ArrayType)、集合(Collection)、序列(Sequence)、生成器(Generator)、元素(Element)、下标(Index),这些类型(协议)各自的作用。
  • 数组是如何利用上面这些类实现各种方法的。
  • mapreducefilter等方法的作用是什么,他们是怎么实现的。
  • 只有数组有上面这些方法么,如果不是,什么样的类型才有这些方法。
  • 如果实现一个自定义的集合类型,应该怎么做。

而这些问题恰恰是过去我们没有重视或根本无法找到答案的问题。因为在OC中,由于NSArray封装的非常好,而且在单纯的iOS开发中对数组的理解不用非常深入,所以我们很少深究数组背后的实现原理。

其实答案就遍布在《Advanced Swift》中文版的“集合”章节的各篇文章中。本文会通过分析Swift中数组的实现,回答上述问题并尝试着建立完整的知识体系。由于篇幅所限,本文不会给出非常详细的源码,而是做总结性的提炼。

参考文章

相关类型简介

我们从零开始,根据集合最本质的特点开始思考,逐步抽象。

元素(Element)

对于任何一种集合来说,它本质上是一种数据结构,也就是用来存放数据的。我们在各种代码中见到的Element表示的就是最底层数据的类型别名。因为对于集合这种范型类型来说,它不关心具体存放的数据的类型,所以就用通用的Element来代替,比如我们写这样的代码:

let array: Array<Int> = [1,2,3]

这就相当于告诉数组,Element现在具体变为Int类型了。

生成器(Generator)

对于集合来说,它往往还需要提供遍历的功能。那怎么把它设计为可遍历的呢?不要指望for循环,要知道目前我们什么都没有,没有数组的概念,更没有下标的概念。有一句名言说:“任何编程问题都可以通过增加一个中间层来解决”。于是,我们抽象出一个Generator(生成器)的概念。我们把它声明成一个协议,任何实现这个协议的类都要提供一个next方法,返回集合中的下一个元素:

protocol GeneratorType {
    typealias Element
    mutating func next() -> Element?
}

可以想象的是这样一来,实现了GeneratorType协议的类,就可以隐藏具体元素的信息,通过不断调用next方法就可以获得所有元素了。比如你可以用一个生成器,不断生成斐波那契数列的下一个数字。

总的来说,生成器(Generator)允许我们遍历所有的元素。

序列(Sequence)

生成器不断生成下一个元素,但是已经生成过的元素就无法再获取到了。比如在斐波那契数列中通过3和5得到了8,那么这个生成器永远也不会再生成元素3了,下一个生成的元素是13。也就是说对于生成器来说,已经访问过的元素就无法再次获取到。

然而对于集合来说,它所包含的元素总是客观存在的。为了能够多次遍历集合,我们抽象出了序列(Sequence)的概念。Sequence封装了Generator对象的创建过程:

protocol SequenceType {
    typealias Generator: GeneratorType
    func generate() -> Generator
}

序列(Sequence)相比于单纯的Generator,使反复遍历集合中的元素成为可能。这时候,我们已经可以通过for循环而不是Generator来遍历所有元素。

集合(Collection)

对比一下现有的Sequence和数组,会发现它还欠缺一个特性——下标。

回顾一下GeneratorSequence,它们只是实现了集合的遍历,但没有指定怎么遍历。也就是说,只要Generator设计“得当”,即使是1和2这两个元素,我们也可以不断遍历:“1的next是2,2的next是1”。这种情况显然不符合我们对数组的认识。归根结底,还是Sequence中无法确定元素的位置,也就无法确保不遍历到已经访问过的元素。

基于这种考虑,我们抽象出集合(Collection)的概念。在集合中,每个元素都有确切的位置,因此集合有明确的开始位置和结束位置。给定一个位置,就可以找到这个位置上的元素。CollectionSequence的基础上实现了Indexable协议


public protocol CollectionType : Indexable, SequenceType {
    public var startIndex: Self.Index { get }
    public var endIndex: Self.Index { get }
    public subscript (position: Self.Index) -> Self._Element { get }
}

当然,CollectionType中的内容远远不止这些。这里列出的仅仅是为了表示CollectionType的特性。

下标(Index)

虽然我们在使用数组的时候,元素下标总是从0开始,并且逐个递增。但下标不必是从0开始递增的整数。比如a、b、c……也可以作为下标。下标类型的关键在于能根据某一个下标推断出下一个下标是什么,比如对于整数来说下一个下标就是当前下标值加1。下标类型的协议如下:

public protocol ForwardIndexType : _Incrementable {
    ///....
}

public protocol _Incrementable : Equatable {
    public func successor() -> Self
}

对于下标类型来说,它们必须实现successor()方法,同时也得是Equatable的,否则怎么知道某个位置上的元素已经被访问过了呢。

数组简介

有了以上基本知识做铺垫,接下来就可以研究一下Swift中数组是怎么实现的了。

基本定义

我们可能早已体会到Swift数组的强大,它的下标脚本不仅可以读取元素,还可以直接修改元素。它可以通过字面量初始化,还可以调用
appendContentsOf方法从别的数组中添加元素。甚至于我们可能都没有仔细考虑过为什么可以用for number in array这样的语法。

首先,我们需要明确一个概念:数组丰富强大的特性绝不是由Array这一个类型可以提供的。实际上,这主要是协议的功劳。用OC写iOS时,协议几乎就是代理的代名词(可能是我对OC不甚精通,目光短浅),但毋庸置疑的是在Swift中,协议的功能被空前的强化。数组通过实现协议、以及协议的嵌套、拓展功能,具有了很多特性。数组的背后交织着错综复杂的协议、方法和拓展。

下面是数组的定义:

public struct Array<Element> : CollectionType, MutableCollectionType, _DestructorSafeContainer {
    public var startIndex: Int { get }
    public var endIndex: Int { get }
    public subscript (index: Int) -> Element
    public subscript (subRange: Range<Int>) -> ArraySlice<Element>
}

数组是一个结构体,它实现了三个协议,有两个变量和两个下标脚本。除此以外,数组还有大量的拓展。

数组拓展

数组的大量功能在拓展中完成,由于拓展很多,我就不列出完整代码,只是做一个整理。数组一共拓展了四类协议:

  • ArrayLiteralConvertible: 这个协议是为了支持这样的语法的:let a: Array<Int> = [1,2,3]。实现协议很简单,只要提供一个自定义方法即可:
public init(arrayLiteral elements: Element...)
  • _Reflectable:这个协议用于处理反射相关的内容,这里不做详解
  • CustomStringConvertibleCustomDebugStringConvertible:这两个是方便我们调试的协议,与数组自身的功能无关。
  • _ArrayType:这是数组最关键的部分。在实现这个协议之前,数组还只是一个普通的集合类型,它仅仅是拥有下标,而且可以重复遍历所有元素而已。而通过实现_ArrayType协议,它可以在指定位置(下标)添加或移除一个或多个元素,它还有了自己的count属性。

这一点也许有些颠覆我们此前的认识。一个集合类型,是不能添加或删除元素的。数组通过实现了_ArrayType协议提供了这样的功能。但这也很容易理解,因为集合的本质还是在于元素的收集,而非考虑如何改变这些元素。

_ArrayType协议还给了我们一个非常重要的启示。比如说我想实现自己的数据结构——栈,那么就应该实现对应的_StackType协议。这种协议要充分考虑数据结构自身的特点,从而提供对应的方法。比如我们不可能向栈的某个特定位置添加若干个元素(只能向栈顶添加一个)。所以_StackType协议中不会定义appendappendContentsOf这样的方法,而是应该定义poppush方法。

SequenceType

接下来的任务是搞清楚ColectionType的原理了。不过在此之前,我们先来看看SequenceType的一些细节,毕竟CollectionType协议是继承了SequenceType协议的。

在有了Generator之后,我们已经可以在while循环中用Generatornext方法遍历所有元素了。之前也说过,SequenceType使对元素的多次遍历成为可能。

注意,仅仅是成为可能而已。如果遍历的细节由Generator控制,那么多次遍历是没有问题的。在极个别情况下,但如果遍历的细节依赖于SequenceType自身的某个属性,而且这个属性会发生变化,那么就不能多次遍历所有元素了。

SequenceType协议的基本部分非常简单,只有一个generator()方法,封装了Generator的创建过程。

一旦有了遍历元素的概念,SequenceType立刻就有了非常多的拓展。这里简单列举几个比较关键的:

  • forEach:这个拓展使得我们可以用for循环遍历集合了:for item in sequence
  • dropFirst(n: Int)dropLast(n: Int):这两个方法返回的是除了前(后)n个元素之外的Sequence。需要提一下的是,由于此时的SequenceType还没有下标的概念,这两个方法的实现是非常复杂的。
  • prefix(maxLength: Int)suffix(maxLength: Int):和刚刚两个方法类似,这两个方法返回的是前(后)maxLength个元素,实现也不简单。
  • elementsEqualcontainsminElementmaxElement等,这些都是针对元素的判断和选择。
  • mapflatMapfilterreduce这些方法是针对所有元素的变换。

SequenceType的拓展实在是太多了,但总结来看不外乎两点:

  1. 由于可以多次遍历元素了,我们可以对元素进行各种比较、处理、筛选等等操作。这些派生出来的方法和函数极大的强化了SequenceType的功能。
  2. 由于SequenceType自身的局限性,不能保证一定可以多次遍历所有元素,还没有下标和元素位置的概念,因此某些方法的实现还不够高效,

带着这样的遗憾,我们来看看最关键的CollectionType是如何实现的。

细谈CollectionType

之前我们说过CollectionType协议是在SequenceType的基础上实现了Indexable协议。由于协议的继承关系,任何实现了CollectionType协议的类,必须实现Indexable协议规定的两个参数:startIndexendIndex,以及一个下标脚本:subscript (position: Self.Index) -> Self._Element { get }。即使这三个要求在CollectionType中没有直接标出来。

回顾一下数组定义的前三行,正是满足了这三个要求。再看CollectionType,它不仅重载了Indexable的一个下标脚本,还额外提供了一个下标脚本用来访问某一段元素,这个下标脚本返回的类型是切片(Slice)。这也正是数组定义的第四行,实现的内容。

细心的读者可能已经注意到,CollectionType还定义了很多属性和方法,比如:prefixUpTosuffixFromisEmptyfirst等等。但数组没有实现其中的任何一个。

事实上,这不仅不是数组设计的失败之处,而正是Swift协议的强大之处。Swift可以通过协议拓展,为计算属性和方法提供默认实现。因此,数组可以不用写任何代码就具备这些方法。更赞的是,任何实现了CollectionType协议的类型也因此具有了这些方法。

观察一下CollectionType的其它拓展,大部分都是重写了SequenceType中的实现。之前已经提到过SequenceType没有下标的概念,而类似于dropFirst这样的方法,利用下标的概念是非常容易实现的。

除了对一些已有方法的重写之外,CollectionType还新增了一些基于下标的方法。比如indexOf()等。

套用官方文档中对CollectionType的总结就是:

A multi-pass sequence with addressable positions

也就是说CollectionType是可以多次遍历,元素可定位的SequenceType

总结

ElementGeneratorSequenceTypeCollectionTypeArray由下至上构造了数组背后的层次结构。他们的关系如下图所示:

Swift数组层次结构

如果我们希望定义一个自己的数据结构,比如链表。首先可以明确它要实现CollectionType协议。链表应该是和Array同层次的类型。然后我们需要定义一个_ListType的协议,这个协议对应数组的_ArrayList协议,根据数据结构自身的特性定义一些方法。

如果觉得CollectionType甚至是SequenceType不满足我们的需求,我们还可以自己实现对应的类型。难度不会很大,因为它们虽然负责,但大多数方法已有默认实现,我们只要重写一些关键的逻辑即可。

最后需要说明的是,Swift中对集合的实现实在是太复杂了,如果每个都详细分析,怕是可以写一本书。希望读完这篇文章后,读者可以举一反三,自行阅读源码解决相关问题。

2016-07-21 09:25:14 mydo 阅读数 3136

我们知道Swift可以扩展已存在的类或结构,这些类或结构可以存在于标准库(或称为核心库)中.如果结构是一个集合类型(比如Array)就更有趣了.我们想尝试写一个限定Type数组的扩展,So我们就拿Array< Int>为例吧.

本猫想是不是可以这么写:

extension Array<Int>{
    //....
}

不过显然不可以 :[

翻看了一下Apple官方的Swift编程语言,一无所获.于是上网溜了一圈,发现一个可行的解决方法,是滴,必须要用where子句:

extension _ArrayType where Element == Int{
    func count(index:Int)->Int{
        print("In _ArrayType")
        return 11*11
    }
}

[1,2,3].count(2)
["1"].count(2) //error!!!

主要思想是我们不能直接拿Array开刀,但是可以间接用_ArrayType类型,可以看到最后一行代码出错,因为它是一个[String]型的数组.

不过别高兴太早了,上面的代码在Swift3中行不通,因为Swit3中压根就找不到_ArrayType类型 ;(

然而车到山前必有路,不能从Array入手,我们可以间接从其遵循的协议入手.于是在Swift3中有两种方法可以达到目的:

extension Sequence where Iterator.Element == Int{
    func count(index:Int)->Int{
        print("In Sequence")
        return index * index
    }
}

extension Collection where Iterator.Element == Int{
    func count(index:Int)->Int{
        print("In Collection")
        return index * index
    }
}

需要注意的是如果要把以上代码用在Swift2.x中需要在Sequence和Collection后面加上Type:

SequenceType
CollectionType

值得一提的是如果我们希望Array扩展中的元素遵循某个协议(而不是等于某种类型)的话可以这么写:

protocol Lovable{
    func fallInLove(with name:String)
}

struct Love:Lovable{
    func fallInLove(with name:String){
        print("fall in love with \(name)")
    }
}

extension Array where Element:Lovable{
    func count(index:Int)->Int{
        print("In Array")
        return index * index
    }
}

let loves = [Love(),Love()]
loves.count(index: 12)

Swift之协议

阅读数 2076

swift 协议

阅读数 0