Leo*_*bus 2 arrays set nsorderedset nsmutableorderedset swift
我正在尝试实现一个通用的 Mutable Ordered Set 类型，它需要符合许多协议才能与 Array 和 Set 在 Swift 中的行为方式相同。首先要做到的是，泛型类型元素的需求，以符合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它的变异甚至不会改变元素顺序。
可变集合
声明变异
功能排序（）
当 Self 符合 RandomAccessCollection 并且 Element 符合 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]"
我该如何解决？
可变有序集的原生 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
}
}
}
符合 RandomAccessCollection 协议
该RandomAccessCollection协议对相关的 Indices 和 SubSequence 类型添加了进一步的约束，但在其他方面没有对BidirectionalCollection协议施加额外的要求。但是，为了满足随机访问集合的复杂性保证，您的自定义类型的索引必须符合Strideable协议，或者您必须以 O(1) 的效率实现index(_:offsetBy:)和distance(from:to:)方法。
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 }
}
符合 Hashable 协议
要在集合中使用您自己的自定义类型或作为字典的键类型，请将 Hashable 符合性添加到您的类型。Hashable 协议继承自 Equatable 协议，因此您还必须满足该协议的要求。当您在类型的原始声明中声明 Hashable 一致性并且您的类型满足以下条件时，编译器会自动综合您的自定义类型的 Hashable 和要求： 对于结构，其所有存储的属性都必须符合 Hashable。对于枚举，其所有关联的值必须符合 Hashable。（即使没有声明，没有关联值的枚举也具有 Hashable 一致性。）
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.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) 当且仅if y.isSuperset(of: x)
• x.isStrictSuperset(of: y) 当且仅当 x.isSuperset(of: y) && x != y
• x.isStrictSubset(of: y) 当且仅当 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) })
}
}
符合 ExpressibleByArrayLiteral
通过声明 init(arrayLiteral:) 初始化程序，将使用数组文字初始化的功能添加到您自己的自定义类型。以下示例显示了假设的 OrderedSet 类型的数组文字初始值设定项，该类型具有类似 set 的语义但保持其元素的顺序。
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 协议
要将 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) }
}
符合 RangeReplaceableCollection 协议
要将 RangeReplaceableCollection 符合性添加到您的自定义集合，请向您的自定义类型添加一个空的初始值设定项和 replaceSubrange( :with:) 方法。RangeReplaceableCollection 使用此初始值设定项和方法提供其所有其他方法的默认实现。例如，removeSubrange( :) 方法是通过使用 newElements 参数的空集合调用 replaceSubrange(_: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) : () }
}
}
快速 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