arrays - 如何在 native Swift 中实现以前称为 NSMutableOrderedSet 的可变有序集泛型类型？

Question

我正在尝试实现一个通用的 Mutable Ordered Set 类型，它需要符合许多协议(protocol)才能与 Swift 中的 Array 和 Set 行为相同。首先要实现泛型类型元素需要符合 Hashable 并且通用结构需要符合 RandomAccessCollection , SetAlgebra , ExpressibleByArrayLiteral , AdditiveArithmetic , RangeReplaceableCollection 和 MutableCollection .我还想允许下标访问它的SubSequence添加对 PartialRangeThrough 的支持, PartialRangeUpTo , PartialRangeFrom和 UnboundedRange也是。
这是我的通用 OrderedSet结构声明:

public struct OrderedSet<Element: Hashable> {
    public init() { }
    private var elements: [Element] = []
    private var set: Set<Element> = []
}

尽管这是一个自我回答的问题，但我真的很感激并鼓励新的答案，对此实现的一些反馈和/或有关如何修复/改进它的建议:
编辑/更新: sorted方法按预期工作，但变异 sort它甚至没有改变元素的顺序。

MutableCollection

Declaration mutating

func sort()

Available when Self conforms to RandomAccessCollection and Element conforms to Comparable.

var numbers: OrderedSet = [15, 40, 10, 30, 60, 25, 5, 100]

numbers[0..<4]           // [15, 40, 10, 30]
numbers[0..<4].sorted()  // [10, 15, 30, 40]

numbers[0..<4].sort()    // [15, 40, 10, 30, 60, 25, 5, 100]

print(numbers) 
// Prints "[15, 40, 10, 30, 60, 25, 5, 100]"
// But it should print "[10, 15, 30, 40, 60, 25, 5, 100]"

我该如何解决？

Answer 1

可变有序集的原生 Swift 实现:

public struct OrderedSet<Element: Hashable> {
    public init() { }
    private var elements: [Element] = []
    private var set: Set<Element> = []
}

Conforming to the MutableCollection Protocol
To add conformance to the MutableCollection protocol to your own custom collection, upgrade your type’s subscript to support both read and write access. A value stored into a subscript of a MutableCollection instance must subsequently be accessible at that same position. That is, for a mutable collection instance a, index i, and value x, the two sets of assignments in the following code sample must be equivalent:

extension OrderedSet: MutableCollection {
    public subscript(index: Index) -> Element {
        get { elements[index] }
        // set {
        //     guard set.update(with: newValue) == nil else {
        //         insert(remove(at: elements.firstIndex(of: newValue)!), at: index)
        //         return 
        //     }
        //     elements[index] = newValue
        // }
        set {
            guard let newMember = set.update(with: newValue) else { return }
            elements[index] = newMember
        }

    }
}

Conforming to the RandomAccessCollection Protocol
The RandomAccessCollection protocol adds further constraints on the associated Indices and SubSequence types, but otherwise imposes no additional requirements over the BidirectionalCollection protocol. However, in order to meet the complexity guarantees of a random-access collection, either the index for your custom type must conform to the Strideable protocol or you must implement the index(_:offsetBy:) and distance(from:to:) methods with O(1) efficiency.

extension OrderedSet: RandomAccessCollection {
    
    public typealias Index = Int
    public typealias Indices = Range<Int>
    
    public typealias SubSequence = Slice<OrderedSet<Element>>
    public typealias Iterator = IndexingIterator<Self>
    
    // Generic subscript to support `PartialRangeThrough`, `PartialRangeUpTo`, `PartialRangeFrom` and `FullRange` 
    public subscript<R: RangeExpression>(range: R) -> SubSequence where Index == R.Bound { .init(elements[range]) }
    
    public var endIndex: Index { elements.endIndex }
    public var startIndex: Index { elements.startIndex }

    public func formIndex(after i: inout Index) { elements.formIndex(after: &i) }
    
    public var isEmpty: Bool { elements.isEmpty }

    @discardableResult
    public mutating func append(_ newElement: Element) -> Bool { insert(newElement).inserted }
}

Conforming to the Hashable Protocol
To use your own custom type in a set or as the key type of a dictionary, add Hashable conformance to your type. The Hashable protocol inherits from the Equatable protocol, so you must also satisfy that protocol’s requirements. The compiler automatically synthesizes your custom type’s Hashable and requirements when you declare Hashable conformance in the type’s original declaration and your type meets these criteria: For a struct, all its stored properties must conform to Hashable. For an enum, all its associated values must conform to Hashable. (An enum without associated values has Hashable conformance even without the declaration.)

extension OrderedSet: Hashable {
    public static func ==(lhs: Self, rhs: Self) -> Bool { lhs.elements.elementsEqual(rhs.elements) }
}

Conforming to the SetAlgebra Protocol
When implementing a custom type that conforms to the SetAlgebra protocol, you must implement the required initializers and methods. For the inherited methods to work properly, conforming types must meet the following axioms. Assume that:
• S is a custom type that conforms to the SetAlgebra protocol, x and y are instances of S, and e is of type S.Element—the type that the set holds.
• S() == [ ]
• x.intersection(x) == x
• x.intersection([ ]) == [ ]
• x.union(x) == x
• x.union([ ]) == x x.contains(e) implies
• x.union(y).contains(e)
• x.union(y).contains(e) implies x.contains(e) || y.contains(e)
• x.contains(e) && y.contains(e) if and only if x.intersection(y).contains(e)
• x.isSubset(of: y) implies x.union(y) == y
• x.isSuperset(of: y) implies x.union(y) == x
• x.isSubset(of: y) if and only if y.isSuperset(of: x)
• x.isStrictSuperset(of: y) if and only if x.isSuperset(of: y) && x != y
• x.isStrictSubset(of: y) if and only if x.isSubset(of: y) && x != y

extension OrderedSet: SetAlgebra {
    public mutating func insert(_ newMember: Element) -> (inserted: Bool, memberAfterInsert: Element) {
        let insertion = set.insert(newMember)
        if insertion.inserted {
            elements.append(newMember)
        }
        return insertion
    }
    public mutating func remove(_ member: Element) -> Element? {
        if let index = elements.firstIndex(of: member) {
            elements.remove(at: index)
            return set.remove(member)
        }
        return nil
    }
    public mutating func update(with newMember: Element) -> Element? {
        if let index = elements.firstIndex(of: newMember) {
            elements[index] = newMember
            return set.update(with: newMember)
        } else {
            elements.append(newMember)
            set.insert(newMember)
            return nil
        }
    }
    
    public func union(_ other: Self) -> Self {
        var orderedSet = self
        orderedSet.formUnion(other)
        return orderedSet
    }
    public func intersection(_ other: Self) -> Self {
        var orderedSet = self
        orderedSet.formIntersection(other)
        return orderedSet
    }
    public func symmetricDifference(_ other: Self) -> Self {
        var orderedSet = self
        orderedSet.formSymmetricDifference(other)
        return orderedSet
    }
    
    public mutating func formUnion(_ other: Self) {
        other.forEach { append($0) }
    }
    public mutating func formIntersection(_ other: Self) {
        self = .init(filter { other.contains($0) })
    }
    public mutating func formSymmetricDifference(_ other: Self) {
        self = .init(filter { !other.set.contains($0) } + other.filter { !set.contains($0) })
    }
}

Conforming to ExpressibleByArrayLiteral
Add the capability to be initialized with an array literal to your own custom types by declaring an init(arrayLiteral:) initializer. The following example shows the array literal initializer for a hypothetical OrderedSet type, which has setlike semantics but maintains the order of its elements.

extension OrderedSet: ExpressibleByArrayLiteral {
    public init(arrayLiteral: Element...) {
        self.init()
        for element in arrayLiteral {
            self.append(element)
        }
    }
}

extension OrderedSet: CustomStringConvertible {
    public var description: String { .init(describing: elements) }
}

Conforming to the AdditiveArithmetic Protocol
To add AdditiveArithmetic protocol conformance to your own custom type, implement the required operators, and provide a static zero property using a type that can represent the magnitude of any value of your custom type.

extension OrderedSet: AdditiveArithmetic {
    public static var zero: Self { .init() }
    public static func + (lhs: Self, rhs: Self) -> Self { lhs.union(rhs) }
    public static func - (lhs: Self, rhs: Self) -> Self { lhs.subtracting(rhs) }
    public static func += (lhs: inout Self, rhs: Self) { lhs.formUnion(rhs) }
    public static func -= (lhs: inout Self, rhs: Self) { lhs.subtract(rhs) }
}

Conforming to the RangeReplaceableCollection Protocol
To add RangeReplaceableCollection conformance to your custom collection, add an empty initializer and the replaceSubrange(:with:) method to your custom type. RangeReplaceableCollection provides default implementations of all its other methods using this initializer and method. For example, the removeSubrange(:) method is implemented by calling replaceSubrange(_:with:) with an empty collection for the newElements parameter. You can override any of the protocol’s required methods to provide your own custom implementation.

extension OrderedSet: RangeReplaceableCollection {

    public init<S>(_ elements: S) where S: Sequence, S.Element == Element {
        elements.forEach { set.insert($0).inserted ? self.elements.append($0) : () }
    }
        
    mutating public func replaceSubrange<C: Collection, R: RangeExpression>(_ subrange: R, with newElements: C) where Element == C.Element, C.Element: Hashable, Index == R.Bound {
        elements[subrange].forEach { set.remove($0) }
        elements.removeSubrange(subrange)
        newElements.forEach { set.insert($0).inserted ? elements.append($0) : () }
    }
}

OrderedSet Playground Sample
快速 Playground 测试(OrderedSet 应该包含 Swift 原生 Array 和 Set 结构可用的所有方法)

var ordereSet1: OrderedSet = [1,2,3,4,5,6,1,2,3]  // [1, 2, 3, 4, 5, 6]
var ordereSet2: OrderedSet = [4,5,6,7,8,9,7,8,9]  // [4, 5, 6, 7, 8, 9]

ordereSet1 == ordereSet2                     // false
ordereSet1.union(ordereSet2)                 // [1, 2, 3, 4, 5, 6, 7, 8, 9]

ordereSet1.intersection(ordereSet2)          // [4, 5, 6]
ordereSet1.symmetricDifference(ordereSet2)   // [1, 2, 3, 7, 8, 9]

ordereSet1.subtract(ordereSet2)              // [1, 2, 3]
ordereSet2.popLast()                         // 9