Add Collection Operations on Noncontiguous Elements

標準ライブラリに、離れた複数の範囲を保持する RangeSet 型と、それを使ってコレクションを操作するアルゴリズム群が追加されます。RangeSet は任意の Comparable な型をバウンドに取れるため、String.Index のような非整数のインデックスを持つコレクションにも使えます。

RangeSet 型

RangeSet は、重なりも隣接もしない複数の Range を昇順に保持する値型です。個別の値や範囲の包含判定、範囲の追加・削除ができます。

var set = RangeSet([0..<5, 10..<15])
set.insert(contentsOf: 7..<7)   // 空の範囲は無視される
set.insert(contentsOf: 11..<14) // 既存の範囲に含まれるので変化なし
// Array(set.ranges) == [0..<5, 10..<15]

set.insert(contentsOf: 5..<7)
// Array(set.ranges) == [0..<7, 10..<15]

set.insert(contentsOf: 7..<10)
// 隣接する範囲は自動的に併合される
// Array(set.ranges) == [0..<15]

内部に保持されている範囲は、ranges プロパティを通じてランダムアクセス可能なコレクションとして取り出せます。ranges の要素は常に昇順で、空ではなく、互いに重なりも隣接もしません。

RangeSet どうしの集合演算も用意されており、union / intersection / symmetricDifference / subtracting と、そのミューテーティング版 (formUnion など)、さらに isSubset(of:) や isDisjoint(with:) といった判定メソッドが使えます。Bound が Sendable なら RangeSet も Sendable に、Hashable なら Hashable になります。

コレクションのインデックスに対して使う場合のために、個別のインデックスを追加・削除するための初期化子とメソッドも用意されています。

let str = "Swift"
var set = RangeSet<String.Index>()
set.insert(str.startIndex, within: str)
// str[set] == "S"

これらは内部で「そのインデックスのひとつ次」を計算することで、単一のインデックスを長さ 1 の範囲として保持します。そのため、endIndex を渡すことはできません。

条件に合うインデックスをまとめて得る: indices(where:) / indices(of:)

コレクションから、条件に合う要素のインデックスを RangeSet として一括で取り出せます。firstIndex(where:) や firstIndex(of:) の、複数要素版にあたる API です。

let str = "Fresh cheese in a breeze"
let vowels: Set<Character> = ["a", "e", "i", "o", "u"]

let vowelIndices = str.indices(where: { vowels.contains($0) })
// str[vowelIndices].count == 9

let eIndices = str.indices(of: "e")
// str[eIndices].count == 7

計算量はいずれもコレクションの長さを $n$ として $O(n)$ です。

RangeSet でコレクションにアクセスする: DiscontiguousSlice

RangeSet<Index> をコレクションの subscript に渡すと、そのインデックス集合に対応する要素だけを見せる DiscontiguousSlice が返ります。DiscontiguousSlice は元のコレクションと RangeSet を保持するだけの軽量なビューで、生成自体は $O(1)$ です。

var numbers = Array(1...15)

let indicesOfEvens = numbers.indices(where: { $0.isMultiple(of: 2) })
let sumOfEvens = numbers[indicesOfEvens].reduce(0, +)
// sumOfEvens == 56

DiscontiguousSlice は Collection に適合し、元のコレクションが BidirectionalCollection なら双方向にもなります。元が MutableCollection なら subscript 経由で要素を書き換えることもできます（ただし DiscontiguousSlice 自体は MutableCollection には適合しません）。

要素をまとめて移動する: moveSubranges(_:to:)

MutableCollection には、RangeSet で指定した位置の要素を、特定のインデックスの直前に連続して集める moveSubranges(_:to:) が追加されます。それ以外の要素の順序は保たれ、戻り値として「集めた要素の新しい範囲」が返されます。

var letters = Array("ABCdeFGhijkLMNOp")
let uppercaseRanges = letters.indices(where: { $0.isUppercase })
let rangeOfUppercase = letters.moveSubranges(uppercaseRanges, to: 10)
// String(letters) == "dehiABCFGLMNOjkp"
// rangeOfUppercase == 4..<13

計算量は $O(n \log n)$ です（$n$ はコレクションの長さ）。

要素をまとめて削除する: removeSubranges(_:) / removingSubranges(_:)

RangeReplaceableCollection には、RangeSet で指定した位置の要素をまとめて削除する removeSubranges(_:) が追加されます。既存の removeSubrange(_:) の複数範囲版にあたる API です。

var str = "The rain in Spain stays mainly in the plain."
let vowels: Set<Character> = ["a", "e", "i", "o", "u"]
let vowelIndices = str.indices(where: { vowels.contains($0) })

str.removeSubranges(vowelIndices)
// str == "Th rn n Spn stys mnly n th pln."

元のコレクションを変更せず、削除後に残る要素を DiscontiguousSlice として取り出すだけの removingSubranges(_:) も Collection に用意されています。

let str = "The rain in Spain stays mainly in the plain."
let vowels: Set<Character> = ["a", "e", "i", "o", "u"]
let vowelIndices = str.indices(where: { vowels.contains($0) })

let disemvoweled = str.removingSubranges(vowelIndices)
// String(disemvoweled) == "Th rn n Spn stys mnly n th pln."

いずれも計算量は $O(n)$ で、ひとつずつ削除したときに起きがちな $O(n^2)$ の性能問題を避けられます。