swift - Swift 中的插入顺序字典(如 Java 的 LinkedHashMap)？

Question

是否有一个标准的 swift 类，它是一个字典，但保持键的插入顺序，如 Java's LinkedHashMap ？如果没有，将如何实现？

Answer 1

不知道有一个，这是一个需要解决的有趣问题(已经把它放在我的标准库中)大多数情况下，这只是并排维护字典和键数组的问题。但是标准操作，如 for (key, value) in od 和 for key in od.keys 将按插入顺序而不是半随机方式迭代。

// OrderedDictionary behaves like a Dictionary except that it maintains
//  the insertion order of the keys, so iteration order matches insertion
//  order.
struct OrderedDictionary<KeyType:Hashable, ValueType> {
    private var _dictionary:Dictionary<KeyType, ValueType>
    private var _keys:Array<KeyType>

    init() {
        _dictionary = [:]
        _keys = []
    }

    init(minimumCapacity:Int) {
        _dictionary = Dictionary<KeyType, ValueType>(minimumCapacity:minimumCapacity)
        _keys = Array<KeyType>()
    }

    init(_ dictionary:Dictionary<KeyType, ValueType>) {
        _dictionary = dictionary
        _keys = map(dictionary.keys) { $0 }
    }

    subscript(key:KeyType) -> ValueType? {
        get {
            return _dictionary[key]
        }
        set {
            if newValue == nil {
                self.removeValueForKey(key)
            }
            else {
                self.updateValue(newValue!, forKey: key)
            }
        }
    }

    mutating func updateValue(value:ValueType, forKey key:KeyType) -> ValueType? {
        let oldValue = _dictionary.updateValue(value, forKey: key)
        if oldValue == nil {
            _keys.append(key)
        }
        return oldValue
    }

    mutating func removeValueForKey(key:KeyType) {
        _keys = _keys.filter { $0 != key }
        _dictionary.removeValueForKey(key)
    }

    mutating func removeAll(keepCapacity:Int) {
        _keys = []
        _dictionary = Dictionary<KeyType,ValueType>(minimumCapacity: keepCapacity)
    }

    var count: Int { get { return _dictionary.count } }

    // keys isn't lazy evaluated because it's just an array anyway
    var keys:[KeyType] { get { return _keys } }

    // values is lazy evaluated because of the dictionary lookup and creating a new array
    var values:GeneratorOf<ValueType> {
        get {
            var index = 0
            return GeneratorOf<ValueType> {
                if index >= self._keys.count {
                    return nil
                }
                else {
                    let key = self._keys[index]
                    index++
                    return self._dictionary[key]
                }
            }
        }
    }
}

extension OrderedDictionary : SequenceType {
    func generate() -> GeneratorOf<(KeyType, ValueType)> {
        var index = 0
        return GeneratorOf<(KeyType, ValueType)> {
            if index >= self._keys.count {
                return nil
            }
            else {
                let key = self._keys[index]
                index++
                return (key, self._dictionary[key]!)
            }
        }
    }
}

func ==<Key: Equatable, Value: Equatable>(lhs: OrderedDictionary<Key, Value>, rhs: OrderedDictionary<Key, Value>) -> Bool {
    return lhs._keys == rhs._keys && lhs._dictionary == rhs._dictionary
}

func !=<Key: Equatable, Value: Equatable>(lhs: OrderedDictionary<Key, Value>, rhs: OrderedDictionary<Key, Value>) -> Bool {
    return lhs._keys != rhs._keys || lhs._dictionary != rhs._dictionary
}