SwiftのDictionaryはハッシュを用いるので、値をイテレータで取り出すと順番がバラバラになって出てきます。

今回、Dictionaryに入れた要素がArrayのように並んでいる、そんなデータ構造が欲しかったので作った話です。

ゴール

var orderedDictionary = OrderedDictionary(keys: ["foo", "bar"], values: ["hoge", "fuga"])
orderedDictionary["foo"] // -> "hoge"
orderedDictionary[1] // -> "fuga"

このようにアクセスできること、あと別途メソッドを用意して要素の追加/挿入/削除を行えるようにします。

コード

実際に構造体を作っていきます

基本形

struct OrderedDictionary<Key: Hashable, Value>: Sequence, IteratorProtocol, CustomStringConvertible {
    
    private(set) var keys = [Key]()
    private var values = [Key: Value]()

}

まんま、DictionaryとArrayを両方含んだ構成になります。ちなみに、上記のコードだと通常のDictionaryに加えて、Keyの順番をArrayで保持しています。

initializer

init() {}

init(dictionary: [Key: Value], order: [Key]) {
    self.keys = order
    self.values = dictionary
}

init(keys: [Key], values: [Value]) {
    self.keys = keys
    for i in 0..<Swift.min(keys.count, values.count) {
        self.values[keys[i]] = values[i]
    }
}

引数に合わせて変数に格納していきます。

subscript

変数名[Index or Key]で要素にアクセスできるようにします

subscript(index: Int) -> Value {
    return dictionary[keys[index]]!
}

subscript(key: Key) -> Value? {
    return dictionary[key]
}

properties

主によく使うものだけ

var count: Int {
    return keys.count
}

var values: [Value] {
    return keys.compactMap({ dictionary[$0] })
}

var first: (key: Key, value: Value)? {
    if count > 0 { return (keys[0], self[0]) }
    return nil
}

var last: (key: Key, value: Value)? {
    if count > 0 { return (keys[count - 1], self[count - 1]) }
    return nil
}

var description: String {
    if keys.count < 1 { return "[:]" }
    let str = keys.reduce("", { "($0), ($1): (dictionary[$1]!)"})
    return "[" + str[str.index(str.startIndex, offsetBy: 2)...] + "]"
}

keysは基本形にあるstored propertyが使えるので必要ない。

操作

値の追加/挿入/削除を行うメソッドです

mutating func append(_ value: Value, for key: Key) {
    keys.append(key)
    dictionary[key] = value
}

mutating func insert(_ value: Value, for key: Key, at index: Int) {
    keys.insert(key, at: index)
    dictionary[key] = value
}

@discardableResult
mutating func remove(at index: Int) -> (key: Key, value: Value) {
    let key = keys.remove(at: index)
    defer {
        dictionary[key] = nil
    }
    return (key, dictionary[key]!)
}

@discardableResult
mutating func remove(for key: Key) -> Value? {
    if let index = keys.firstIndex(of: key) {
        return remove(at: index).value
    }
    return nil
}

検索

func firstIndex(where predicate: ((key: Key, value: Value)) throws -> Bool) rethrows -> Int {
    for (i, key) in keys.enumerated() {
        if try predicate((key, dictionary[key]!)) { return i }
    }
    return -1
}

普段firstIndexしか使わないので、とりあえずこれだけ。

と言ってもfirst(where:)やlastIndex(where:)もほぼ同じ感じで書けるので問題ないかと。

イテレータ

for (key, value) in 変数名という形でループできるようにします

var iteratorCount = 0
mutating func makeIterator() -> OrderedDictionary<Key, Value> {
    iteratorCount = 0
    return self
}
mutating func next() -> (key: Key, value: Value)? {
    defer { iteratorCount += 1 }
    return iteratorCount < count ? (keys[iteratorCount], self[iteratorCount]) : nil
}

SequenceとIteratorProtocolに適応している必要があります

これで実用可能な程度には実装ができたと思います。

コード全体

追記

同じkeyの値を代入した場合

var orderedDictionary = OrderedDictionary<String, String>()
orderedDictionary.append("hoge", for: "foo")
orderedDictionary.append("fuga", for: "foo")
orderedDictionary // -> [foo: fuga, foo: fuga]

あくまでKeyの順番を配列で保持しているだけなので、同じKeyに値を代入すると最初の値が後の値に上書きされます。

以下のように配列にValueを格納し、DictionaryにIndexを格納するようにすれば後の値で上書きされずにIndexを指定して最初の値を取り出すことができますが、その場合insertやremoveの際にDictionaryを更新する手間が増えるのと、僕の用途では重複したKeyを指定して両方取り出したい場面がなかったので、こっちの実装にしました。

private(set) var values = [Value]()
private var indexes = [Key: Int]()

mutating func insert(_ value: Value, for key: Key, at index: Int) {
    values.insert(value, at: index)
    indexes = indexes.mapValues({ $0 >= index ? $0 + 1 : $0 })
    indexes[key] = index
}

気に入っている実装

自分で作ったオブジェクトを格納するだけなら、オブジェクトにString型のプロパティを用意してそれをキーに使用すれば、Keyを別途与えなくても配列と同じように操作できる。

protocol OrderedDictionaryItem {
    var id: String { get set }
}

struct OrderedDictionary<T: OrderedDictionaryItem>: Sequence, IteratorProtocol {
    
    private var ids = [String]()
    private var items = [String: T]()

    // 省略
}

汎用性は下がるが、アプリ内で保存しているデータを管理するならこっちの方が便利。