如何在本机 Swift 中实现以前称为 NSMutableOrderedSet 的可变有序集泛型类型? [英] How to implement a Mutable Ordered Set generic type formerly known as NSMutableOrderedSet in native Swift?
问题描述
我正在尝试实现一个通用的 Mutable Ordered Set 类型，它需要符合许多协议才能像 Swift 中的 Array 和 Set 一样运行.首先要实现泛型类型元素需要符合 Hashable 并且通用结构需要符合 RandomAccessCollection, SetAlgebra, ExpressibleByArrayLiteral,AdditiveArithmetic, RangeReplaceableCollection 和 MutableCollection.我还想允许下标访问它的 SubSequence 添加对 PartialRangeThrough、PartialRangeUpTo、PartialRangeFrom 和 的支持>UnboundedRange 也是如此.
这是我的通用 OrderedSet 结构声明:
public struct OrderedSet{公共初始化(){}私有 var 元素:[元素] = []私有变量集:设置<元素>= []} 尽管这是一个自我回答的问题，但我真的很感激并鼓励新的答案，对此实施的一些反馈和/或关于如何修复/改进它的建议:
编辑/更新:
sorted 方法按预期工作，但变异 sort 它甚至没有改变元素顺序.
可变集合
声明变异
函数排序()
当 Self 符合 RandomAccessCollection 且 Element 符合 Comparable 时可用.
var numbers: OrderedSet = [15, 40, 10, 30, 60, 25, 5, 100]数字[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]打印(数字)//打印[15, 40, 10, 30, 60, 25, 5, 100]"//但它应该打印[10, 15, 30, 40, 60, 25, 5, 100]"我该如何解决?
可变有序集的原生 Swift 实现:
public struct OrderedSet{公共初始化(){}私有 var 元素:[元素] = []私有变量集:设置<元素>= []} <块引用>
符合 MutableCollection 协议
要将 MutableCollection 协议的一致性添加到您自己的自定义集合中，请升级您的类型的下标以支持读取和写入访问.存储在 MutableCollection 实例的下标中的值随后必须可以在同一位置访问.也就是说，对于可变集合实例 a、索引 i 和值 x，以下代码示例中的两组赋值必须相等:
扩展 OrderedSet: MutableCollection {公共下标(索引:索引)->元素 {获取{元素[索引]}//放 {//守卫 set.update(with: newValue) == nil else {//insert(remove(at: elements.firstIndex(of: newValue)!), at: index)// 返回//}//元素[索引] = newValue//}放 {守卫让 newMember = set.update(with: newValue) else { return }元素[索引] = newMember}}}<块引用>
符合 RandomAccessCollection 协议RandomAccessCollection 协议对关联的 Indices 和 SubSequence 类型添加了进一步的约束，但对 BidirectionalCollection 协议没有其他要求.但是，为了满足随机访问集合的复杂性保证，您的自定义类型的索引必须符合 Strideable 协议，或者您必须实现 index(_:offsetBy:) 和 distance(from:to:) 方法的效率为 O(1).
扩展 OrderedSet: RandomAccessCollection {公共类型别名索引 = Int公共类型别名索引 = Range<Int>public typealias SubSequence = Slice>public typealias Iterator = IndexingIterator<Self>//支持 `PartialRangeThrough`、`PartialRangeUpTo`、`PartialRangeFrom` 和 `FullRange` 的通用下标公共下标<R: RangeExpression>(范围: R) ->SubSequence where Index == R.Bound { .init(elements[range]) }公共变量 endIndex:索引 { elements.endIndex }公共 var startIndex:索引 { elements.startIndex }public func formIndex(after i: inout Index) { elements.formIndex(after: &i) }公共 var isEmpty: 布尔 { element.isEmpty }@discardableResult公共变异函数追加(_新元素:元素)->布尔 { 插入(新元素).插入 }} <块引用>
符合哈希协议
要在集合中使用您自己的自定义类型或作为字典的键类型，请将 Hashable 一致性添加到您的类型.Hashable 协议继承自 Equatable 协议，因此您还必须满足该协议的要求.当您在类型的原始声明中声明 Hashable 一致性并且您的类型满足以下条件时，编译器会自动合成您自定义类型的 Hashable 和要求:对于结构，其所有存储的属性都必须符合 Hashable.对于一个枚举，它的所有关联值都必须符合 Hashable.(没有关联值的枚举即使没有声明也具有 Hashable 一致性.)
扩展 OrderedSet: Hashable {公共静态函数 ==(lhs: Self, rhs: Self) ->布尔 { lhs.elements.elementsEqual(rhs.elements) }}<块引用>
符合 SetAlgebra 协议
在实现符合 SetAlgebra 协议的自定义类型时，您必须实现所需的初始化程序和方法.为了使继承的方法正常工作，符合类型必须满足以下公理.假设:
• S 是符合 SetAlgebra 协议的自定义类型，x 和 y 是 S 的实例，e 是 S.Element 类型——集合所持有的类型.
• S() == [ ]
• x.intersection(x) == x
• x.intersection([ ]) == [ ]
• x.union(x) == x
• x.union([ ]) == x x.contains(e) 暗示
• x.union(y).contains(e)
• x.union(y).contains(e) 意味着 x.contains(e) ||y.contains(e)
• x.contains(e) &&y.contains(e) 当且仅当 x.intersection(y).contains(e)
• x.isSubset(of: y) 意味着 x.union(y) == y
• x.isSuperset(of: y) 意味着 x.union(y) == x
• x.isSubset(of: y) 当且仅当 y.isSuperset(of: x)
• x.isStrictSuperset(of: y) 当且仅当 x.isSuperset(of: y) &&x != y
• x.isStrictSubset(of: y) 当且仅当 x.isSubset(of: y) &&x != y
扩展 OrderedSet: SetAlgebra {公共变异函数插入(_ newMember:元素)->(插入:布尔，memberAfterInsert:元素){让插入 = set.insert(newMember)如果插入.插入 {元素.附加(新成员)}返回插入}公共变异函数删除(_成员:元素)->元素?{if let index = elements.firstIndex(of: member) {元素.删除(在:索引)返回 set.remove(成员)}返回零}公共变异函数更新(带有新成员:元素)->元素?{if let index = elements.firstIndex(of: newMember) {元素[索引] = newMember返回 set.update(with: newMember)} 别的 {元素.附加(新成员)设置.插入(新成员)返回零}}公共函数联合(_其他:自我)->自己 {var orderedSet = 自我orderedSet.formUnion(其他)返回有序集}公共函数交集(_其他:自我)->自己 {var orderedSet = 自我orderedSet.formIntersection(其他)返回有序集}公共函数对称差异(_其他:自我)->自己 {var orderedSet = 自我orderedSet.formSymmetricDifference(其他)返回有序集}公共变异函数formUnion(_其他:自我){其他.forEach {追加($ 0)}}公共变异函数formIntersection(_其他:自我){self = .init(filter { other.contains($0) })}公共变异函数 formSymmetricDifference(_ other: Self) {self = .init(filter { !other.set.contains($0) } + other.filter { !set.contains($0) })}}<块引用>
符合 ExpressibleByArrayLiteral
通过声明 init(arrayLiteral:) 初始化程序，将使用数组文字初始化的功能添加到您自己的自定义类型.下面的示例展示了一个假设的 OrderedSet 类型的数组字面量初始值设定项，它具有类似集合的语义，但保持其元素的顺序.
扩展 OrderedSet: ExpressibleByArrayLiteral {公共初始化(arrayLiteral:元素...){self.init()对于 arrayLiteral 中的元素 {self.append(元素)}}}扩展 OrderedSet: CustomStringConvertible {公共变量描述:字符串{ .init(描述:元素)}}<块引用>
符合 AdditiveArithmetic 协议
要将 AdditiveArithmetic 协议一致性添加到您自己的自定义类型，请实现所需的运算符，并使用可以表示自定义类型的任何值的大小的类型提供静态零属性.
扩展 OrderedSet: AdditiveArithmetic {公共静态变量零:Self { .init() }公共静态 func + (lhs: Self, rhs: Self) ->自我 { lhs.union(rhs) }公共静态函数-(lhs:Self，rhs:Self)->自我 { lhs.subtracting(rhs) }公共静态 func += (lhs: inout Self, rhs: Self) { lhs.formUnion(rhs) }公共静态 func -= (lhs: inout Self, rhs: Self) { lhs.subtract(rhs) }}<块引用>
符合 RangeReplaceableCollection 协议
要将 RangeReplaceableCollection 一致性添加到您的自定义集合，请添加一个空初始化程序和 replaceSubrange(:with:) 方法到您的自定义类型.RangeReplaceableCollection 使用此初始化程序和方法提供了所有其他方法的默认实现.例如，removeSubrange(:) 方法是通过调用 replaceSubrange(_:with:) 来实现的，其中 newElements 参数为空集合.您可以覆盖任何协议所需的方法来提供您自己的自定义实现.
扩展 OrderedSet: RangeReplaceableCollection {public init<S>(_ 元素:S) 其中 S:序列，S.Element == Element {elements.forEach { set.insert($0).inserted ?self.elements.append($0) : () }}mutating public func replaceSubrange(_ subrange: R, with newElements: C) where Element == C.Element, C.Element: Hashable, Index == R.Bound {元素[子范围].forEach { set.remove($0) }元素.removeSubrange(子范围)newElements.forEach { set.insert($0).inserted ?元素.append($0) : () }}} 快速 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//假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()//9I am trying to implement a generic Mutable Ordered Set type and it needs to conform to many protocols to behave the same way as an Array and a Set does in Swift. First of all to accomplish that the generic type element needs to conform to Hashable and the generic struct needs to conform to RandomAccessCollection, SetAlgebra, ExpressibleByArrayLiteral,AdditiveArithmetic, RangeReplaceableCollection and MutableCollection. I would like also to allow subscript access to its SubSequence adding support to PartialRangeThrough, PartialRangeUpTo, PartialRangeFrom and UnboundedRange as well.
This is my generic OrderedSet struct declaration:
public struct OrderedSet<Element: Hashable> {
public init() { }
private var elements: [Element] = []
private var set: Set<Element> = []
}
Even though this is a self-answered question I would really appreciate and encourage new answers, some feedback on this implementation and/or suggestions on how to fix/improve it as well:
edit/update:
The sorted method works as expected but the mutating sort it is not even changing the elements order.
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]"
How can I fix it?
A native Swift implementation of a Mutable Ordered Set:
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
TheRandomAccessCollectionprotocol adds further constraints on the associated Indices and SubSequence types, but otherwise imposes no additional requirements over theBidirectionalCollectionprotocol. However, in order to meet the complexity guarantees of a random-access collection, either the index for your custom type must conform to theStrideableprotocol or you must implement theindex(_:offsetBy:)anddistance(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) : () }
}
}
Quick Playground Test (OrderedSet should have all methods that are available to Swift native Array and Set structures)
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
这篇关于如何在本机 Swift 中实现以前称为 NSMutableOrderedSet 的可变有序集泛型类型?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
