问题 1：制作OrderedSet一个MutableCollection
在 a中，您可以通过支持写访问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]
问题 2：切片
在您的实现中，您选择Slice<OrderedSet<Element>>了SubSequence类型。Slice使用来自原始（基本）集合的存储，并且只维护自己的startIndex和endIndex. 这会导致意想不到的结果：
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..<3]不符合OrderedSetProtocol：它是一个（可变）集合，但例如不是一个SetAlgebra，因此它不能用于形成联合、交叉或对称差异。
你真的需要MutableCollection一致性吗？
我会认真考虑不采用该MutableCollection协议。这不会使有序集不可变：它仅意味着不能通过下标设置器修改单个成员。您仍然可以插入或删除元素，或与其他集合形成联合或交集。仅对于诸如排序之类的“复杂”操作，您必须通过一个额外的临时集：
var oset: OrderedSet = [4, 3, 2, 1]
oset = OrderedSet(oset.sorted())
print(oset) // [1, 2, 3, 4]
最大的优点是不再有不明确的行为。
是的，我想要MutableCollection一致性！
好的，你要求的——让我们看看我们能做些什么。我们可以尝试通过“修复”下标设置器来解决这个问题。一种尝试是您注释掉的代码：
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()
}
}
另外我们需要实现下标设置器取一个范围
public subscript(bounds: Range<Index>) -> SubSequence
以便将排序的切片作为一个操作分配回集合，而不是单独分配给每个元素。
这在我的测试中有效，但有可能我忽略了一些东西。
对于切片，我会制作OrderedSet自己的SubSequence类型。这意味着元素是重复的。这可以通过将element存储设置为ArraySlice但——正如我们在上面看到的——set无论如何都必须复制不同成员的存储来避免，以避免在原始集发生突变时产生不必要的副作用。
编码
这就是我到目前为止所拥有的。据我所知，它可以正常工作，但需要更多测试。
注意有些方法是不需要实现的，比如ExpressibleByArrayLiteral已经有默认实现了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一致性将是更安全的解决方案。
上面的方法可行但很脆弱：我不得不“猜测”必须实现哪些方法，因为默认实现不起作用。如果MutableCollectionSwift 标准库中的协议获得了具有默认实现的新方法。事情可能会再次破裂。