📏

SwiftのRangeとSwift6.0からのRangeSet

2024/12/22に公開

iOS

Swift

tech

はじめに

SwiftにはRangeと呼ばれる値の範囲を表す型があります。

// 1以上10未満
1..<10
// 1.0以上10.0以下
1.0...10.0

範囲の始まりと終わりを内部に持つ単純な型ですが

Swift 4.0で少し変更・型の追加が入った
Swift 6.0でRangeSetと呼ばれるRangeの集合を扱える型が増えた

のでこの機会にRange関連についてまとめなおしました。（広く浅く基礎的な内容が中心になっています）

歴史を学べるSwift 3.0での詳しい解説

Rangeとその仲間たち

public struct Range<Bound: Comparable> {

Comparableな型の範囲を表す型。内部的にlower boundとupper boundを持つ。
containsメソッドを用いて範囲に値が含まれるかをチェックしたり、Collectionのメソッドと合わせて使ったりする。

let range = 1..<10
range.contains(5)

let array = [1, 2, 3, 4, 5]
array[1..<3] // ArraySlice [2, 3]

範囲の指定方法にバリエーションがあり、全部で6通りある。それぞれが別々の型として存在する。

let array = [1, 2, 3, 4, 5]

// Range
array[1..<3] // ArraySlice [2, 3]
// ClosedRange
array[1...3] // ArraySlice [2, 3, 4]
// PartialRangeUpTo
array[..<3] // ArraySlice [1, 2, 3]
// PartialRangeThrough
array[...3] // ArraySlice [1, 2, 3, 4]
// PartialRangeFrom
array[3...] // ArraySlice [4, 5]
// UnboundedRange
array[...] // ArraySlice [1, 2, 3, 4, 5]

upper boundを範囲に含むか否か (… or ..< ) の2通り * lower/upper boundをそれぞれ持つ/持たないの4通りで全部で8通り。
ただしupper boundを持たない場合、範囲にupper boundを含むか否かのバリエーションは不要なので-2通りして6通り。

lower boundあり	upper boundあり	upper bound含む	表現	型
0	0	0	..<	必要なし (UnboundedRangeで吸収)
0	0	1	…	UnboundedRange
0	1	0	..<1	PartialRangeUpTo
0	1	1	…1	PartialRangeThrough
1	0	0	1..<	必要なし (PartialRangeFromで吸収)
1	0	1	1…	PartialRangeFrom
1	1	0	1..<2	Range
1	1	1	1…2	ClosedRange

RangeとClosedRange以外はSwift4.0から導入。
該当SE: SE-0172 One-sided Ranges

..<や … はComparableに対する演算子として定義されている。（リテラルではない）

extension Comparable {
  public static func ..< (minimum: Self, maximum: Self) -> Range<Self> {
    _precondition(minimum <= maximum,
      "Range requires lowerBound <= upperBound")
    return Range(_uncheckedBounds: (lower: minimum, upper: maximum))
  }
}

RangeExpression protocol

UnboundedRange以外の5種類のRangeはRangeExpression protocolに準拠しており、抽象化可能。containsとrelativeが使える。

contains

Rangeが示す範囲に引数の値が含まれているかどうかを評価する関数。

(0..<10).contains(1)
// containsと同値な演算子
0..<10 ~= 1

relative

XXXRangeをそのCollectionのindexをベースとしたRangeに変換するメソッド。主にPartialなRange向け。

let numbers = [1, 2, 3, 4, 5]

print((0...).relative(to: numbers)) // 0..<5
print((...3).relative(to: numbers)) // 0..<4

実際にCollectionのsubscriptで使われている。

@inlinable
public subscript<R: RangeExpression>(r: R)
-> SubSequence where R.Bound == Index {
  return self[r.relative(to: self)]
}

Sequence

Range, Closed Range, PartialRangeFrom（左端が決まっている物）は BoundがStrideableでStrideがSingedIntegerな場合Sequenceに準拠する。

extension Range: Sequence where Bound: Strideable, Bound.Stride: SignedInteger

例えばfor inループが可能。PartialRangeFromでも書けるのが面白い。

for i in 0..<10 {}
for i in 0... {
    print(i)
    if i == 1_000 {
        break
    }
}

Strideable.StrideにSignedIntegerを要求する理由は、整数は単位間隔（最小粒度？）が1と決まっており範囲内の数を数えることができるから。例えばDoubleだと範囲内の全てのDoubleを数えることができないためイテレートもできない。

for i in 1.0..<10.0 { } // 🔴 Protocol 'Sequence' requires that 'Double.Stride' (aka 'Double') conform to 'SignedInteger'

（ちなみにこういう場合はstrideを使う）

for i in stride(from: 0.0, to: 10.0, by: 0.1) {}

また、この「数えることができるRange」としてCountableRangeというtypealiasがある。（Conditional Conformance導入前はtypealiasではなくて別の型だった）

public typealias CountableRange<Bound: Strideable> = Range<Bound>
  where Bound.Stride: SignedInteger
public typealias CountablePartialRangeFrom<Bound: Strideable> = PartialRangeFrom<Bound>
  where Bound.Stride: SignedInteger
public typealias CountableClosedRange<Bound: Strideable> = ClosedRange<Bound>
  where Bound.Stride: SignedInteger

Collection

Range, Closed Range（両端が決まっている物）はSequenceと同条件でさらにCollection (+BidirectionalCollection, RandomAccessCollection) に準拠するためsubscriptやcountなどが使える。

(0..<10).count // 10
(0..<10)[1] // 1

Codable

デフォルトで準拠。(Swift 5.0~)

unkeyedContainerで実装されている。（例えばJSONでは配列）

import Foundation

struct Container: Codable {
    var range: Range<Int>
}

let data = """
{
    "range": [
        0,
        9
    ]
}
""".data(using: .utf8)
let content = try! JSONDecoder().decode(Container.self, from: data!)

print(content)

UnboundedRange

「全ての範囲」を表すRange。このRangeだけ実装が特別なので紹介。

let array = [1, 2, 3, 4, 5]
array[...] // ArraySlice [1, 2, 3, 4, 5]

ここで、UnboundedRangeは他のRangeと異なり関数型である。

public typealias UnboundedRange = (UnboundedRange_)->()

… はSwiftでは演算子だが、引数なし演算子は書けないのでfunc ... () -> UnboundedRange的なアプローチは無理。そのためfunc ... (_: UnboundedRange_) -> Voidを定義して typealias UnboundedRange = (UnboundedRange_) -> Void とすると、...の記述をUnboundedRange型にできるというワークアラウンドが用いられている。

// 演算子を定義するためだけのcaseなしenum
public enum UnboundedRange_ {
  public static postfix func ... (_: UnboundedRange_) -> () {
  }
}

extension Collection {
  @inlinable
  public subscript(x: UnboundedRange) -> SubSequence {
    return self[startIndex...]
  }
}

RangeSet

Swift 6.0 (iOS18~)から

Rangeの集合。複数の非連続のRangeをflatにして一つのRangeかのように扱えるインターフェースを持つ。（Set<Range<Bound>>を使うのではなくRangeSetを定義している理由。）

var set = RangeSet([0.0..<5.0, 10.0..<15.0])
set.contains(1.0) // true
// Set<Range>ではRange型としか比較できない

set.formUnion(.init(4.0..<6.0)) // [Range(0.0..<6.0), Range(10.0..<15.0)]
// Set<Range>だと[Range(4.0..<6.0), Range(10.0..<15.0), Range(0.0..<5.0)]になってしまう

set.remove(contentsOf: 1.0..<2.0) // [Range(0.0..<1.0), Range(2.0..<6.0), Range(10.0..<15.0)]

FoundationのIndexSetと比べてInt以外にも使えるという利点がある。

Rangeの結合・分解というめんどくさい挙動を吸収してくれているので、何かに使えたら使っていきたい。

Collectionとの連携

RangeSetは直接initするのとは別に、Collectionに追加されているメソッドindices(where: ), indices(of:)から取得可能。計算量はO(n)。

var numbers = Array(1...15)

// O(n)
let indicesOfEvens = numbers.indices(where: { $0.isMultiple(of: 2) })

また、CollectionのsubscriptにRangeSetを指定すると複数の非連続区間を表すスライスであるDiscontiguousSliceが取得可能。

filterなどに比べRangeSetやDiscontiguousSliceを使う利点はパフォーマンス面。計算量は同じだが、filterは新しいArrayを生成するのに対してDiscontiguousSliceは生成しないためメモリ的に優しい（普通のスライスと同じ挙動）

なお、DiscontiguousSliceはImmutableで読み取り専用なので要素のコピーが起きることはない（普通のSliceはCoWに基づき、mutateすると要素のコピーが起きる）

// O(n)
let indicesOfEvens = numbers.indices(where: { $0.isMultiple(of: 2) })
// O(1) 元のArrayを内部で参照しているだけ
let evensSlice = numbers[indicesOfEvens]

// O(n)　新しいArrayを生成
let evens = numbers.filter { $0.isMultiple(of: 2) }

また、RangeSetで指定した範囲をまとめてmove/removeするメソッドが生えている。

let rangeOfEvens = numbers.moveSubranges(indicesOfEvens, to: numbers.startIndex)
// [2, 4, 6, 8, 10, 12, 14, 1, 3, 5, 7, 9, 11, 13, 15]

日常使いというよりかは、パフォーマンスが必要な時に使うと良さそう。他に役立ちそうなユースケースがあったらぜひ教えてください。