A simple OrderedSet implementation backed by an Array and a Set

OrderedSet.swift

import Foundation

struct OrderedSet<Element: Hashable>: Sequence {
    private var order: [Element]
    private var membership: Set<Element>
    
    func makeIterator() -> IndexingIterator<Array<Element>> {
        order.makeIterator()
    }
    
    var underestimatedCount: Int { order.underestimatedCount }
    
    func withContiguousStorageIfAvailable<R>(_ body: (UnsafeBufferPointer<Element>) throws -> R) rethrows -> R? {
        try order.withContiguousStorageIfAvailable(body)
    }
}

extension OrderedSet: Hashable {
}

extension OrderedSet /* partial SetAlgebra conformance */ {
    init() {
        order = []
        membership = []
    }
    
    @discardableResult
    mutating func insert(_ newMember: __owned Element) -> (inserted: Bool, memberAfterInsert: Element) {
        let result = membership.insert(newMember)
        if result.inserted {
            order.append(newMember)
        }
        return result
    }
}

extension OrderedSet /* partial RangeReplaceableCollection conformance */ {
    init<S: Sequence>(_ elements: S) where S.Element == Element {
        self.init()
        append(contentsOf: elements)
    }
    
    mutating func reserveCapacity(_ n: Int) {
        order.reserveCapacity(n)
        membership.reserveCapacity(n)
    }
    
    mutating func append(_ newElement: Element) {
        insert(newElement)
    }
    
    mutating func append<S: Sequence>(contentsOf newElements: S) where S.Element == Element {
        newElements.forEach { append($0) }
    }
    
    @discardableResult
    mutating func remove(at index: Int) -> Element {
        let element = order.remove(at: index)
        membership.remove(element)
        return element
    }
    
    mutating func removeAll(keepingCapacity keepCapacity: Bool = false) {
        order.removeAll(keepingCapacity: keepCapacity)
        membership.removeAll(keepingCapacity: keepCapacity)
    }
}

extension OrderedSet: ExpressibleByArrayLiteral {
    init(arrayLiteral elements: Element...) {
        self.init(elements)
    }
}

extension OrderedSet {
    // convenience
    static func += <S: Sequence>(lhs: inout Self, rhs: S) where S.Element == Element {
        lhs.append(contentsOf: rhs)
    }
}

extension OrderedSet: RandomAccessCollection {
    func index(before i: Int) -> Int {
        order.index(before: i)
    }
    
    func index(after i: Int) -> Int {
        order.index(after: i)
    }
    
    subscript(position: Int) -> Element {
        order[position]
    }
    
    var startIndex: Int { order.startIndex }
    var endIndex: Int { order.endIndex }
    
    var indices: Range<Int> { order.indices }
    var isEmpty: Bool { order.isEmpty }
    var count: Int { order.count }
}

extension OrderedSet: Encodable where Element: Encodable {
    func encode(to encoder: Encoder) throws {
        var container = encoder.singleValueContainer()
        try container.encode(order)
    }
}

extension OrderedSet: Decodable where Element: Decodable {
    init(from decoder: Decoder) throws {
        let container = try decoder.singleValueContainer()
        let elements = try container.decode([Element].self)
        self.init(elements)
    }
}