Provide Custom Collections for Dictionary Keys and Values

Swift 3 時点の Dictionary の keys プロパティと values プロパティは、どちらも LazyMapCollection 型でした。これは元のコレクション（ここでは Dictionary 本体）の要素をクロージャで変換して見せるだけの薄いラッパーであり、「この要素は辞書のキーである」といったドメイン固有の情報を一切持っていません。そのため、利用する側から見ると無視できない問題が二つありました。

keys.contains がハッシュ検索にならない

辞書にあるキーが含まれているかを調べる一番読みやすい書き方は dict.keys.contains(...) ですが、keys が単なる LazyMapCollection だった都合で、この呼び出しは内部の辞書ストレージにハッシュで問い合わせることができず、線形探索に落ちていました。

var dict = ["one": [1], "two": [2, 2], "three": [3, 3, 3]]

// 読みやすいが O(n)
if dict.keys.contains("one") { ... }

同じ意味になる書き方はいくつかありましたが、どれも「Swifty」ではない、あるいは意図が伝わりにくいものでした。

// O(1) だが読みにくい
if dict["one"] != nil { ... }
if let _ = dict["one"] { ... }

dict.keys.index(of:) と dict.index(forKey:) の関係にも同じ不整合があり、自然に書いた方が遅い、という落とし穴になっていました。

値をその場で書き換える手段がない

辞書の値を書き換える手段はキー添字しかなく、しかもその添字は Optional<Value> を返す setter なので、格納されている値が copy-on-write なコレクションでも「自分が唯一の保持者である」ことを Swift が認識できませんでした。結果として、以下のような素直な更新でも内部ストレージの不要なコピーが発生します。

// どちらも配列のコピーを伴う
dict["one"] = (dict["one"] ?? []) + [1]
dict["one"]?.append(1)

一つ目はそもそも読みにくく、二つ目はキーが存在しないケースを無視してしまいます。さらに根本的な問題として、辞書のキー添字はミュータブルな形では “in-place” な更新を表現できないため、格納されている配列やデータを「ここにある値を直接ミュータブルに触る」形で書き換えられません。

インデックス添字に書き込み可能な setter を持たせる手もありません。インデックスに紐づくキーを書き換えるとハッシュ値が変わってしまい、MutableCollection の要件（インデックスが指す位置が書き換え後も有効であること）を満たせないからです。

つまり、keys の高速検索も、values のミュータブルなアクセスも、LazyMapCollection のままでは表現できない、というのがこの Proposal の出発点です。