向量 - 数组

Vector 实现方式:

集合S由n个元素组成，且各元素之间具有一个线性次序，则 可将它们存放于起始于地址A、物理位置连续的一段存储空间，并统称作数组（array），通常 以 A 作为该数组的标识。

动态空间管理

插入:

每次在插入数据之前都会调用扩容算法, 如果当前空间满了, 则扩容数组长度为2n, 每次由 n 扩容到 2n 都需要 O(n) 时间, 因为需要把数据拷贝到新的地址, 但每次扩容都会加倍, 在没有缩容的情况下, 扩容 i 次的空间大小为 2^i * n。

插入的具体实现：插入操作insert(r, e)负责将任意给定的元素e插到任意指定的 秩为r的单元。
为保证数组元素物理地址连续的特性，随后需要将后缀_elem[r, _size)（如果非空）整 体后移一个单元（图 1）

图 1

删除的具体实现：
设[lo, hi)为向量（图 2）的合法区间（图(b)），则 其后缀[hi, n)需整体前移hi - lo 个单元（图(c)）。与插入算法同理，这里后继元素自前向后的移动次序也不能颠倒（习题[2-10]）。
单个元素删除等同于区间删除。
每次删除操作之后，一旦空间利用率已降至某一阈值以下，该算法随即申请一个容量 减半的新数组，将原数组中的元素逐一搬迁至其中，最后将原数组所占空间交还操作系统。这里 以25%作为装填因子的下限，但在实际应用中，为避免出现频繁交替扩容和缩容的情况，可以选 用更低的阈值，甚至取作0（相当于禁止缩容）

图 2

Swift Array 的扩容实现与 Vector 大致相同, 但是删除单一数据并没有走缩容,
而 removeAll, replace, subscript(bounds: Range<Int>)([array[0..<2]]), insert

// 扩容
// 当容量不够, 当前容量变成两倍
internal func _growArrayCapacity(_ capacity: Int) -> Int {
  return capacity * 2
}

// 只删除 index 位置元素实现
@inlinable
  @discardableResult
  public mutating func remove(at index: Int) -> Element {
    _precondition(index < endIndex, "Index out of range")
    _precondition(index >= startIndex, "Index out of range")
    _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
  }

/// Moves instances from initialized source memory into the uninitialized
  /// memory referenced by this pointer, leaving the source memory
  /// uninitialized and the memory referenced by this pointer initialized.
  ///
  /// The region of memory starting at this pointer and covering `count`
  /// instances of the pointer's `Pointee` type must be uninitialized or
  /// `Pointee` must be a trivial type. After calling
  /// `moveInitialize(from:count:)`, the region is initialized and the memory
  /// region `source..<(source + count)` is uninitialized.
  ///
  /// - Parameters:
  ///   - source: A pointer to the values to copy. The memory region
  ///     `source..<(source + count)` must be initialized. The memory regions
  ///     referenced by `source` and this pointer may overlap.
  ///   - count: The number of instances to move from `source` to this
  ///     pointer's memory. `count` must not be negative.
@inlinable
  public func moveInitialize(from source: UnsafeMutablePointer, count: Int) {
    _debugPrecondition(
      count >= 0, "UnsafeMutablePointer.moveInitialize with negative count")
    if self < source || self >= source + count {
      // initialize forward from a disjoint or following overlapping range.
      Builtin.takeArrayFrontToBack(
        Pointee.self, self._rawValue, source._rawValue, count._builtinWordValue)
      // This builtin is equivalent to:
      // for i in 0..<count {
      //   (self + i).initialize(to: (source + i).move())
      // }
    }
    else {
      // initialize backward from a non-following overlapping range.
      Builtin.takeArrayBackToFront(
        Pointee.self, self._rawValue, source._rawValue, count._builtinWordValue)
      // This builtin is equivalent to:
      // var src = source + count
      // var dst = self + count
      // while dst != self {
      //   (--dst).initialize(to: (--src).move())
      // }
    }

@inlinable
  @_semantics("array.mutate_unknown")
  public mutating func replaceSubrange<C>(
    _ subrange: Range<Int>,
    with newElements: __owned C
  ) where C: Collection, C.Element == Element {
    _precondition(subrange.lowerBound >= self._buffer.startIndex,
      "Array replace: subrange start is negative")

    _precondition(subrange.upperBound <= _buffer.endIndex,
      "Array replace: subrange extends past the end")

    let oldCount = _buffer.count
    let eraseCount = subrange.count
    let insertCount = newElements.count
    let growth = insertCount - eraseCount

    if _buffer.requestUniqueMutableBackingBuffer(
      minimumCapacity: oldCount + growth) != nil {
// 当容量够, 并且唯一, 直接替换
// _ContiguousArrayBuffer
      _buffer.replaceSubrange(
        subrange, with: insertCount, elementsOf: newElements)
    } else {
// 当容量不够, 走扩容
      _buffer._arrayOutOfPlaceReplace(subrange, with: newElements, count: insertCount)
    }
  }

// _buffer.replaceSubrange
@inlinable
  internal mutating func replaceSubrange<C>(
    _ subrange: Range<Int>,
    with newCount: Int,
    elementsOf newValues: __owned C
  ) where C : Collection, C.Element == Element {
    _internalInvariant(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 {
      // Slide the tail part of the buffer forwards, in reverse order
      // so as not to self-clobber.
      newTailStart.moveInitialize(from: oldTailStart, count: tailCount)

      // Assign over the original subrange
      var i = newValues.startIndex
      for j in subrange {
        elements[j] = newValues[i]
        newValues.formIndex(after: &i)
      }
      // Initialize the hole left by sliding the tail forward
      for j in oldTailIndex..<newTailIndex {
        (elements + j).initialize(to: newValues[i])
        newValues.formIndex(after: &i)
      }
      _expectEnd(of: newValues, is: i)
    }
    else { // We're not growing the buffer
      // Assign all the new elements into the start of the subrange
      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 the size didn't change, we're done.
      if growth == 0 {
        return
      }

      // Move the tail backward to cover the shrinkage.
      let shrinkage = -growth
      if tailCount > shrinkage {   // If the tail length exceeds the shrinkage

        // Assign over the rest of the replaced range with the first
        // part of the tail.
        newTailStart.moveAssign(from: oldTailStart, count: shrinkage)

        // Slide the rest of the tail back
        oldTailStart.moveInitialize(
          from: oldTailStart + shrinkage, count: tailCount - shrinkage)
      }
      else {                      // Tail fits within erased elements
        // Assign over the start of the replaced range with the tail
        newTailStart.moveAssign(from: oldTailStart, count: tailCount)

        // Destroy elements remaining after the tail in subrange
        (newTailStart + tailCount).deinitialize(
          count: shrinkage - tailCount)
      }
    }
  }

链表的实现

通过轶来访问位置时需要从头依次找到, 但在某点的前后插入删除另一点是O(1), 所以具体情况具体分析, C++和 java 有 List, swift, oc 则需要自己来实现.

Reference: 图片来源《数据结构（C++语言版）》第三版 邓俊辉