Swift源码分析-Array

Swift源码分析 - Array

ContiguousArray:A fast, contiguously-stored array of Element.(快速连续存储的数组)

ArraySlice:The Array-like type that represents a sub-sequence of any Array, ContiguousArray, or other ArraySlice.(可以是ContiguousArray,Array,ArraySlice的子序列)

Array:is an efficient, tail-growable random-access collection of arbitrary elements.(一个高效的,可增长的,可随机访问的集合)

除了Array能和Objective-c桥接,其他都不行.

Array

/// Construct a Array of `count` elements, each initialized to
/// `repeatedValue`.
@swift3_migration(renamed="init(repeating:count:)")
@_semantics("array.init")
public init(count: Int, repeatedValue: Element) {
  var p: UnsafeMutablePointer<Element>
  (self, p) = Array._allocateUninitialized(count)
  for _ in 0..<count {
    p.initialize(repeatedValue)
    p += 1
  }
}

数组初始化为同一个值:先分配一块没有初始化的区域,再逐个初始化.

/// The number of elements the Array stores.
public var count: Int {
  return _getCount()
}

/// The number of elements the `Array` can store without reallocation.
public var capacity: Int {
  return _getCapacity()
}

第一个是数组的个数,第二个至关重要!!因为这关系到数组的性能,在后面补充会详细说.

/// Extend `lhs` with the elements of `rhs`.
public func += <
  Element, S : SequenceType
  where S.Generator.Element == Element
>(inout lhs: Array<Element>, rhs: S) {
  let oldCount = lhs.count
  let capacity = lhs.capacity
  let newCount = oldCount + rhs.underestimateCount()

  if newCount > capacity {
    lhs.reserveCapacity(
      max(newCount, _growArrayCapacity(capacity)))
  }
  _arrayAppendSequence(&lhs._buffer, rhs)
}

从这我们可以看出，数组也是可以用｀＋＝｀运算符的，前提数组中存储的元素是同一个类型。

@warn_unused_result
public func == <Element : Equatable>(
  lhs: Array<Element>, rhs: Array<Element>
) -> Bool {
  let lhsCount = lhs.count
  if lhsCount != rhs.count {
    return false
  }

  // Test referential equality.
  if lhsCount == 0 || lhs._buffer.identity == rhs._buffer.identity {
    return true
  }

  var streamLHS = lhs.generate()
  var streamRHS = rhs.generate()

  var nextLHS = streamLHS.next()
  while nextLHS != nil {
    let nextRHS = streamRHS.next()
    if nextLHS != nextRHS {
      return false
    }
    nextLHS = streamLHS.next()
  }

  return true
}

这个是比较数组是否相同的代码，仔细看lhs._buffer.identity == rhs._buffer.identity可以猜出，每个数组都有一个唯一id，通过判断id来判断数组是否是同一个’引用’

#补充:

数组中capacity和count的区别

capacity:容量和count:数量,至于为什么要弄这两个参数,那就要提到数组实现原理了.

在分析之前先看结果:

数组的实现原理

我们在使用数组的时候通常都是这样的:

var array: [Int] = []
array.append(0)
array.append(1)
...

我们从最底层的C语言开始比较:

//C语言中我们这样写

int array[5];
array[0] = 0;
array[1] = 1;
...

当我们执行int array[5]的时候就已经分配好了内存空间,不管你数组中只有一个数,所占空间都是5*sizeof(int).

但是在swift中好像我们也没有分配具体大小的空间,感觉要多少有多少,从来没有关心容量不够的情况.

那是因为Swift已经为我们弄好了,但是这也是一个坑!!!下面是append方法实现.

/// Append `newElement` to the Array.
///
/// - Complexity: Amortized O(1) unless `self`'s storage is shared with another live array; O(`count`) if `self` does not wrap a bridged `NSArray`; otherwise the efficiency is unspecified..
public mutating func append(newElement: Element) {
  _makeUniqueAndReserveCapacityIfNotUnique()
  let oldCount = _getCount()
  _reserveCapacityAssumingUniqueBuffer(oldCount)
  _appendElementAssumeUniqueAndCapacity(oldCount, newElement: newElement)
}

我们再调用append方法的时候实现了数组的扩容,这样保证不浪费内存空间,但是我们知道在C语言中我们malloc一块内存用来存放数据,当不够的时候我们会采用realloc.而realloc的原理大家都是知道了,就是重新找一块内存分配空间,然后将原来的数据复制过去.

Swift的做法和这个差不多,我们来看看:

仔细的看内存地址和之前的那张对比,是有规律的,2,4,8,16…每次分配的大小为2的N次方.这在数组很小的时候是有用的,但是如果我们存储33个数,其实Swift为我们分配了64的存储空间,这样就了白白浪费了很多的空间,而且随着数组数量的增大,越明显,但是Apple其实也知道,在平常的开发中很难遇到那么多的数.

Note: 这样一来就应该明白count和capacity的区别了,count表示数组中实际存在的元素个数,而capacity表示数组的容量大小.剩下的就是空闲的,避免每次append都要重新拷贝数据.

下面的这个函数我们不经常用到,但是如果你不想白白浪费空间,你可以使用.前提你要知道你的数组大概是多少个,下面这个方法就是设定一个最小分配容量.

/// Reserve enough space to store `minimumCapacity` elements.
///
/// - Postcondition: `capacity >= minimumCapacity` and the array has
///   mutable contiguous storage.
///
/// - Complexity: O(`self.count`).
@_semantics("array.mutate_unknown")
public mutating func reserveCapacity(minimumCapacity: Int) {
  if _buffer.requestUniqueMutableBackingBuffer(minimumCapacity) == nil {

    let newBuffer = _ContiguousArrayBuffer<Element>(
      count: count, minimumCapacity: minimumCapacity)

    _buffer._uninitializedCopy(
      _buffer.indices, target: newBuffer.firstElementAddress)
    _buffer = _Buffer(newBuffer, shiftedToStartIndex: _buffer.startIndex)
  }
  _sanityCheck(capacity >= minimumCapacity)
}