向量 - 数组
2019-07-08 本文已影响0人
幸运者_Lucky
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 则需要自己来实现.
