Swift Digest
Adding in-place removeAll(where:) to the Standard Library
01 何が問題だったのか
コレクションから「ある条件を満たす要素をすべて取り除きたい」という操作は日常的に登場します。しかし Swift 3 の時点の標準ライブラリには、これを直接表現するメソッドがありませんでした。
最も素朴な方法は filter を使って残したい要素だけを集め直し、自分自身に代入し直すというものです。filter は「残す要素」を返すクロージャを取るため、消したい条件に対して否定を書く必要があります。
var nums = [1, 2, 3, 4, 5]
// 奇数を取り除く
nums = nums.filter { !isOdd($0) }
この書き方には読みづらさに加えて二つの性能上の問題があります。新しいメモリを確保し直してしまうこと、そして取り除く要素が一つもなかったとしても全要素をコピーしてしまうことです。
性能を意識して書き直そうとすると、配列を先頭から走査しながら残す要素を前に詰めていき、最後に余った末尾を切り落とす、いわゆる「シャッフルダウン」方式の for ループを自分で実装することになります。
if var i = nums.index(where: isOdd) {
var j = i + 1
while j != nums.endIndex {
let e = nums[j]
if !isOdd(nums[j]) {
nums[i] = nums[j]
i += 1
}
j += 1
}
nums.removeSubrange(i...)
}
決して難しすぎるわけではないものの、インデックス計算や境界条件の扱いを間違えやすく、バグや性能劣化が入り込みやすいコードです。
さらにこの方式は、単一要素の置き換えが定数時間で行えないコレクション（RangeReplaceableCollection ではあるが MutableCollection ではない型）には適用できません。代表例が String で、グレフェーム単位の要素が可変長であるため、インデックスによる一要素の上書きが効率的にできません。こうした型についても、利用者ごとにその型の内部構造に合わせた実装を書かなければならない状況でした。
02 どのように解決されるのか
RangeReplaceableCollection にインプレースで条件に合致する要素をすべて取り除くメソッド removeAll(where:) を追加します。
var nums = [1, 2, 3, 4, 5]
nums.removeAll(where: isOdd)
// nums == [2, 4]
クロージャが true を返した要素が取り除かれます。filter が「残す要素」に true を返すのと逆なので、消したい条件をそのまま書けます。
使い方
任意の述語を渡して、合致する要素をまとめて削除できます。
var names = ["Alice", "Bob", "Charlie", "Dan"]
names.removeAll(where: { $0.count <= 3 })
// names == ["Alice", "Charlie"]
String のように RangeReplaceableCollection ではあるが MutableCollection ではないコレクションにも適用できます。
var greeting = "Hello, world!"
greeting.removeAll(where: { $0 == "l" })
// greeting == "Heo, word!"
Dictionary や Set は RangeReplaceableCollection に適合していませんが、同じ操作が欲しくなる場面が多いため、これらの型にも同じシグネチャの removeAll(where:) が個別に提供されます。
var scores = ["Alice": 80, "Bob": 42, "Charlie": 95]
scores.removeAll(where: { $0.value < 60 })
// scores == ["Alice": 80, "Charlie": 95]
実装と計算量
RangeReplaceableCollection にはプロトコルのデフォルト実装として、init() と append(_:) を使ったコピーベースの実装が与えられます。加えて MutableCollection にも適合している型については、「シャッフルダウン」方式によるメモリ確保を伴わない、より効率的なデフォルト実装が使われます（末尾の切り詰めのために RangeReplaceableCollection が必要です）。Array のようにメモリコピーの最適化が効く型や、String のように内部表現に合わせた実装が有利な型は、それぞれ独自のより速い実装を提供できます。
いずれの場合も、利用者側から見れば取り除きたい条件をクロージャで書くだけで、コレクションの種類に応じて適切な実装が選ばれます。自前でシャッフルダウンを書いていたコードは、removeAll(where:) への置き換えで済むようになります。
filter との使い分け
filter は新しいコレクションを返す非破壊的な操作で、元のコレクションを残したいときに使います。一方 removeAll(where:) は既存のコレクションを直接書き換える操作で、もう不要な要素を捨ててしまってよい場合に使います。またクロージャの意味も逆で、filter は「残す要素」、removeAll(where:) は「取り除く要素」に true を返します。