1. 首页
  2. 问题列表
  3. 如何在本机Swift中实现以前称为NSMutableOrderedSet的可变有序集泛型类型？
提问者：小点点

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


我正在尝试实现一个通用的可变有序集合类型，它需要符合许多协议才能像数组和Swift中的集合一样表现。首先要完成的是，泛型类型元素需要符合哈希，泛型结构需要符合随机访问集合，SetAlgebra，ExpressibleByArrayLitald，AdditiveArithmetic，RangeReplace eableCollection和MutableCollection。我还想允许下标访问它的SubSequence添加对ParatalRangePass，ParatalRangeUpTo，ParatalRangeFrom和UnboundedRange的支持。

这是我的通用OrderedSet结构声明：

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

尽管这是一个自我回答的问题，但我真的很感激并鼓励新的答案、对此实施的一些反馈和/或关于如何修复/改进它的建议：

编辑/更新：

sorted方法按预期工作，但变异的sort它甚至没有改变元素顺序。

MutableCollection

声明变异

func排序

当Self符合R的AccessCollection和元素符合可比时可用。

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]"

我怎样才能修好它？


共2个答案

匿名用户

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

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

符合MutableCollection协议
要将MutableCollection协议的一致性添加到您自己的自定义集合中，请升级您的类型的下标以支持读取和写入访问。存储在MutableCollection实例的下标中的值随后必须在同一位置可访问。也就是说，对于可变集合实例a、索引i和值x，以下代码示例中的两组赋值必须等效：

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
        }

    }
}

符合R的AccessCollection协议
的R的AccessCollection协议对关联的索引和子序列类型增加了进一步的约束，但在其他方面对BiDirectionalCollection协议没有额外的要求。但是，为了满足随机访问集合的复杂性保证，您的自定义类型的索引必须符合Strideable协议，或者您必须实现index（_： offsetBy：）和距离（from：to：）方法，效率为O（1）。

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 }
}

符合哈希协议
要在集合中使用您自己的自定义类型或作为字典的键类型，请将哈希可一致性添加到您的类型中。哈希可哈协议继承自Equable协议，因此您还必须满足该协议的要求。当您在类型的原始声明中声明哈希可哈一致性并且您的类型满足这些标准时，编译器会自动合成您自定义类型的哈希可哈性和要求：对于结构，其所有存储的属性都必须符合哈希可哈性。对于枚举，其所有关联值都必须符合哈希可哈性。（没有关联值的枚举即使没有声明也具有哈希可哈性一致性。）

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

符合SetAlgebra协议
实现符合SetAlgebra协议的自定义类型时，必须实现所需的初始化器和方法。要使继承的方法正常工作，符合类型必须满足以下公理。假设：
•S是符合SetAlgebra协议的自定义类型，x和y是S的实例，e是S. Element类型-集合持有的类型。
•S() == [ ]
•x.交集（x）==x
•x.交集([ ]) == [ ]
•x.Union（x）==x
•x.Union([ ]) == x x.包含（e）暗示
•x.Union（y）。包含（e）
•x.联合（y）。包含（e）暗示x.包含（e）||y.包含（e）
•x.包含（e） 

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) })
    }
}

符合ExpressibleByArrayLitald
通过声明init（arrayLitald：）初始化器，将使用数组文字初始化的功能添加到您自己的自定义类型中。以下示例显示了假设OrderedSet类型的数组文字初始化器，该类型具有setlike语义学，但保持其元素的顺序。

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) }
}

符合AdditiveArithmetic Protocol
要将AdditiveArithmetic协议一致性添加到您自己的自定义类型，请实现所需的运算符，并使用可以表示自定义类型的任何值的大小的类型提供静态零属性。

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) }
}

符合RangeReplace eableCollection协议
要将RangeReplace eableCollection一致性添加到您的自定义集合，请将空初始化器和replace Subrange（： with：）方法添加到您的自定义类型。RangeReplace eableCollection使用此初始化器和方法提供其所有其他方法的默认实现。例如，RemoveSubrange（：）方法是通过使用newElements参数的空集合调用replace Subrange（_：with：）来实现的。您可以覆盖协议所需的任何方法来提供您自己的自定义实现。

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游乐场样品

快速游乐场测试（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

匿名用户

在MutableCollection中，您可以通过支持写访问的下标更改单个元素（或元素切片）。这就是问题的开始：应该输出什么 

var oset: OrderedSet = [1, 2, 3, 4]
oset[0] = 3
print(oset)

是？我们不能简单地替换第一个元素，因为这样集合成员就不再是唯一的了。您当前的实现返回[1,2,3,4]，即如果新成员已经存在于集合中，它会拒绝设置。

这使得MutableCollection方法的许多默认实现失败：sort（）、swapAt（）、shuffle（）可能更多：

var oset: OrderedSet = [4, 3, 2, 1]
oset.swapAt(0, 2)
print(oset) // [4, 3, 2, 1]
oset.sort()
print(oset) // [4, 3, 2, 1]
oset.shuffle()
print(oset) // [4, 3, 2, 1]

在您的实现中，您选择了Slice

let oset: OrderedSet = [1, 2, 3, 4, 5]
var oslice = oset[0..<3]
oslice[0] = 5
print(oslice) // [1, 2, 3]

设置oslice[0]被拒绝，因为原始集包含新成员。这当然不是预期的。对切片进行排序

var oset: OrderedSet = [6, 5, 4, 3, 2, 1]
oset[0..<4].sort()
print(oset) // [6, 5, 4, 3, 2, 1]

失败是因为排序的元素被一个接一个地写回，而失败是因为成员已经存在于集合中。切片分配也会发生同样的事情：

var o1: OrderedSet = [1, 2]
let o2: OrderedSet = [2, 1]
o1[0..<2] = o2[0..<2]
print(o1) // [1, 2]

另一个问题是切片oset[0…

我会认真考虑不采用MutableCollection协议。这并没有使有序集合不可变：它只是意味着不能通过下标设置器修改单个成员。您仍然可以插入或删除元素，或者与其他集合形成联合或交集。只有对于排序等“复杂”操作，您才必须通过一个额外的临时集：

var oset: OrderedSet = [4, 3, 2, 1]
oset = OrderedSet(oset.sorted())
print(oset) // [1, 2, 3, 4]

最大的优势是不再有不明确的行为。

好的，你要求它-让我们看看我们能做什么。我们可以尝试通过“修复”下标设置器来解决这个问题。一次尝试是您注释掉的代码：

    set {
        guard set.update(with: newValue) == nil else {
            insert(remove(at: elements.firstIndex(of: newValue)!), at: index)
            return 
        }
        elements[index] = newValue
    }

这具有将现有成员移动到给定位置的效果，移动其他元素：

var oset: OrderedSet = [1, 2, 3, 4]
oset[0] = 3
print(oset) // [3, 1, 2, 4]

这似乎使大多数方法正常工作：

var oset: OrderedSet = [4, 3, 2, 1]
oset.swapAt(0, 2)
print(oset) // [2, 3, 4, 1]
oset.sort()
print(oset) // [1, 2, 3, 4]
oset.shuffle()
print(oset) // [1, 4, 3, 2]

甚至下标排序：

var oset: OrderedSet = [6, 5, 4, 3, 2, 1]
oset[0..<4].sort()
print(oset) // [3, 4, 5, 6, 2, 1]

但是我看到了两个缺点：

  • 用户可能没有预料到下标设置器的这种副作用。
  • 它破坏了下标设置器所需的O（1）一致性。

另一种选择是保持下标设置器不变（即拒绝无效设置），并实现有问题的方法，而不是使用MutableCollection的默认实现：

extension OrderedSet {
    public mutating func swapAt(_ i: Index, _ j: Index) {
        elements.swapAt(i, j)
    }

    public mutating func partition(by belongsInSecondPartition: (Element) throws -> Bool) rethrows -> Index {
        try elements.partition(by: belongsInSecondPartition)
    }

    public mutating func sort(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
        try elements.sort(by: areInIncreasingOrder)
    }
}

extension OrderedSet where Element : Comparable {
    public mutating func sort() {
        elements.sort()
    }
}

另外我们需要实现下标setter取一个范围

public subscript(bounds: Range<Index>) -> SubSequence

以便将排序后的切片作为一个操作分配回集合，而不是单独分配给每个元素。

这在我的测试中奏效了，但我有可能忽略了一些东西。

对于切片，我将使OrderedSet成为它自己的SubSequence类型。这意味着元素是重复的。这可以通过使元素存储成为ArraySlice来避免，但是-正如我们在上面看到的-不同成员的set无论如何都必须被复制，以避免原始集发生突变时不需要的副作用。

这是我目前所拥有的。据我所知，它工作正常，但需要更多的测试。

注意有些方法是不需要实现的，例如ExpressibleByArrayLitald在SetAlgebra中已经有了默认实现，各种索引计算都有默认实现，因为Index是Strideable。

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

    public init() { }

}

extension OrderedSet {
    public init<S>(distinctElements elements: S) where S : Sequence, S.Element == Element {
        self.elements = Array(elements)
        self.set = Set(elements)
        precondition(self.elements.count == self.set.count, "Elements must be distinct")
    }
}

extension OrderedSet: SetAlgebra {
    public func contains(_ member: Element) -> Bool {
        set.contains(member)
    }

    @discardableResult public mutating func insert(_ newMember: Element) -> (inserted: Bool, memberAfterInsert: Element) {
        let insertion = set.insert(newMember)
        if insertion.inserted { elements.append(newMember) }
        return insertion
    }

    @discardableResult public mutating func remove(_ member: Element) -> Element? {
        if let oldMember = set.remove(member) {
            let index = elements.firstIndex(of: member)!
            elements.remove(at: index)
            return oldMember
        } else {
            return nil
        }
    }

    @discardableResult public mutating func update(with newMember: Element) -> Element? {
        if let member = set.update(with: newMember) {
            return member
        } else {
            elements.append(newMember)
            return nil
        }
    }

    public mutating func formUnion(_ other: Self) {
        other.elements.forEach { self.insert($0) }
    }

    public mutating func formIntersection(_ other: Self) {
        for element in elements {
            if !other.contains(element) {
                remove(element)
            }
        }
    }

    public mutating func formSymmetricDifference(_ other: Self) {
        for member in other.elements {
            if set.contains(member) {
                remove(member)
            } else {
                insert(member)
            }
        }
    }

    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 init<S>(_ elements: S) where S : Sequence, S.Element == Element {
        elements.forEach { insert($0) }
    }
}

extension OrderedSet: CustomStringConvertible {
    public var description: String { elements.description }
}

extension OrderedSet: MutableCollection, RandomAccessCollection {

    public typealias Index = Int
    public typealias SubSequence = OrderedSet

    public subscript(index: Index) -> Element {
        get {
            elements[index]
        }
        set {
            if !set.contains(newValue) || elements[index] == newValue {
                set.remove(elements[index])
                set.insert(newValue)
                elements[index] = newValue
            }
        }
    }

    public subscript(bounds: Range<Index>) -> SubSequence {
        get {
            return OrderedSet(distinctElements: elements[bounds])
        }
        set {
            replaceSubrange(bounds, with: newValue.elements)
        }

    }
    public var startIndex: Index { elements.startIndex}
    public var endIndex:   Index { elements.endIndex }

    public var isEmpty: Bool { elements.isEmpty }
} 

extension OrderedSet {
    public mutating func swapAt(_ i: Index, _ j: Index) {
        elements.swapAt(i, j)
    }

    public mutating func partition(by belongsInSecondPartition: (Element) throws -> Bool) rethrows -> Index {
        try elements.partition(by: belongsInSecondPartition)
    }

    public mutating func sort(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
        try elements.sort(by: areInIncreasingOrder)
    }
}

extension OrderedSet where Element : Comparable {
    public mutating func sort() {
        elements.sort()
    }
}

extension OrderedSet: RangeReplaceableCollection {

    public mutating func replaceSubrange<C>(_ subrange: Range<Index>, with newElements: C) where C : Collection, C.Element == Element {

        set.subtract(elements[subrange])
        let insertedElements = newElements.filter {
            set.insert($0).inserted
        }
        elements.replaceSubrange(subrange, with: insertedElements)
    }
}

我已经说过，放弃MutableCollection一致性将是更安全的解决方案。

上面的工作但脆弱：我不得不“猜测”哪些方法必须实现，因为默认实现不起作用。如果Swift标准库中的MutableCollection协议得到一个具有默认实现的新方法。事情可能会再次中断。

相关问题



热门标签
Java JavaScript Python PHP C# Android Html jQuery C++ Css IOS MySQL NodeJS