是否有一个标准的Swift类是一个字典,但保持键的插入顺序,类似于Java的LinkedHashMap?如果没有,应该如何实现?
我之前不知道有这样一个问题,但解决它非常有趣(我已经将其放入我的标准库中)。主要就是维护一个字典和一个与其键对应的数组。但像 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
}
Swift 5 版本:
// 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 = dictionary.keys.map { $0 }
}
subscript(key: KeyType) -> ValueType? {
get {
_dictionary[key]
}
set {
if newValue == nil {
self.removeValueForKey(key: key)
} else {
_ = self.updateValue(value: 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.removeValue(forKey: key)
}
mutating func removeAll(keepCapacity: Int) {
_keys = []
_dictionary = Dictionary<KeyType, ValueType>(minimumCapacity: keepCapacity)
}
var count: Int {
get {
_dictionary.count
}
}
// keys isn't lazy evaluated because it's just an array anyway
var keys: [KeyType] {
get {
_keys
}
}
var values: Array<ValueType> {
get {
_keys.map { _dictionary[$0]! }
}
}
static func ==<Key: Equatable, Value: Equatable>(lhs: OrderedDictionary<Key, Value>, rhs: OrderedDictionary<Key, Value>) -> Bool {
lhs._keys == rhs._keys && lhs._dictionary == rhs._dictionary
}
static func !=<Key: Equatable, Value: Equatable>(lhs: OrderedDictionary<Key, Value>, rhs: OrderedDictionary<Key, Value>) -> Bool {
lhs._keys != rhs._keys || lhs._dictionary != rhs._dictionary
}
}
extension OrderedDictionary: Sequence {
public func makeIterator() -> OrderedDictionaryIterator<KeyType, ValueType> {
OrderedDictionaryIterator<KeyType, ValueType>(sequence: _dictionary, keys: _keys, current: 0)
}
}
struct OrderedDictionaryIterator<KeyType: Hashable, ValueType>: IteratorProtocol {
let sequence: Dictionary<KeyType, ValueType>
let keys: Array<KeyType>
var current = 0
mutating func next() -> (KeyType, ValueType)? {
defer { current += 1 }
guard sequence.count > current else {
return nil
}
let key = keys[current]
guard let value = sequence[key] else {
return nil
}
return (key, value)
}
}
我还没有找到让值“惰性”的方法...需要更多的研究。
Dictionary
语法而言,这应该是一个无需更改即可替换的版本,除了类型之外,当然,由于它不是子类,你不能将其作为字典传递。 - David BerryArray
与Dictionary
结合作为实现有序关联数据结构的手段比使用链式结构(如LinkedHashMap
)更慢。首先,平均情况下删除操作的时间复杂度为O(n)
,而LinkedHashMap
的删除操作时间复杂度为O(1)
。 - Alexander