📘

[Swift] Collectionとその仲間たち

2025/01/02に公開

はじめに

SwiftにはCollectionというprotocolがあります。その代表例がArrayです。

var numbers = [1, 2, 3]
// 読み取り可能
numbers[0] // 1

// 書き込み可能
numbers[0] = 10
// 要素を追加可能
numbers.append(40)

他の例としてRangeがあります。しかし、Rangeは書き込みや要素の追加はできません。

var range = 0..<4
range[0] // 0

range[0] = 10 // 🔴 Cannot assign through subscript: subscript is get-only
range.append(40) // 🔴 Value of type 'Range<Int>' has no member 'append'

実はCollection protocolには複数の子protocolがあり、それぞれが定義する機能が異なります。
ArrayとRangeで準拠しているprotocolが実際には異なるためこのようなArrayとRangeの機能の違いが生まれるわけです。Collectionの関連protocolはメジャーなものだけで5つあります。

Collection: 基本protocol。読み取りのみ。
MutableCollection: 書き込み（要素を変更）ができるCollection
RangeReplaceableCollection: 長さや要素を変更できるCollection
BidirectionalCollection: 末尾からの先頭方向への探索が可能なCollection
RandomAccessCollection: 任意位置のIndexがO(1)で計算できるCollection

この記事では、これらのCollectionの子protocolの機能を簡潔にまとめます。これらのprotocolを知ることで、未知のCollectionの具体型に遭遇した時に準拠しているprotocolからその型が持つ機能（書き込み可能か？要素を追加可能か？など）を瞬時にある程度把握することができます。
また、同じメソッドインターフェースでも準拠しているprotocolによって計算量が異なる場合があるため、準拠しているprotocolを把握・理解することは重要です。

Sequence

CollectionはSequenceの子protocolなので、一応Sequenceも紹介。

Sequenceは全部で何要素あるのか不明、有限個かどうかも不明で、一つづつ手繰り寄せる（イテレートする）ことしかできません。そのため特定要素へのアクセス（Collectionのsubscriptのようなもの）は提供されておらず、要素の書き込みもできません。
できるのはfor inでのイテレーションとmap,sorted,filterなどの非破壊操作メソッドのみです。

公式ドキュメントに記述がある通り、次の要素の取り出しはO(1)ですが、全探索を必要とする操作メソッドが多く計算量はO(n)です。

A sequence should provide its iterator in O(1). The Sequence protocol makes no other requirements about element access, so routines that traverse a sequence should be considered O(n) unless documented otherwise.
シーケンスはそのイテレータをO(1)で提供すべきである。シーケンスプロトコルは、要素アクセスについて他の要求をしていないので、シーケンスを横断するルーチンは、他に文書化されていない限り、O(n)とみなされるべきである。

要素数が無限のSequence

エッジケースではありますがSequenceは要素数が無限になることもあります。Standard Libraryの例だとPartialRangeFromがあります。（実際はInt64の最大値に達してランタイムエラーになるが、理論的には無限長）
よって具体型の分からないSequenceに対してfor inや全探索が必須のmap, sorted, filterなどを行うと処理が終わらない or クラッシュの可能性があるため注意が必要です。

// PartialRangeFrom
for i in 0... {
}

Collection

Collectionはインデックスを用いて単一/複数要素へのアクセスができる。
例: Range

var range = 0..<10
range[5] // 5
range[5..<10] // 5..<10

しかし、書き込みはできない。protocolのsubscriptがgetのみになっているため。

var range = 0..<10
range[5] = 100 // 🔴 Cannot assign through subscript: subscript is get-only
range[5..<10] = 100..<105 // 🔴 Cannot assign through subscript: subscript is get-only

MutableCollection

要素の変更ができるCollection。Collectionの子protocolになっており、subscriptがgetとset両方になっている。

例: CollectionOfOne

var one = CollectionOfOne(1)
one[0] = 10

しかし、Collectionのサイズ変更はできないためappend, insert, removeなどが使えません。

var one = CollectionOfOne(1)
one.append(10) // 🔴 Value of type 'CollectionOfOne<Int>' has no member 'append'

RangeReplaceableCollection

任意範囲の置き換えができるCollection。Collectionの子protocolで、任意範囲を任意長で置き換えることができる=要素の追加や削除ができる。append,insert,removeなどが使えるようになる。

例: Array

var numbers = [1, 2, 3]

numbers.append(40)
numbers.replaceSubrange(3..<3, with: CollectionOfOne(40))

最低限必要な実装はreplaceSubrange(:with:)のみで、その他append,insert,removeなどはreplaceSubrangeを内部で呼ぶデフォルト実装が存在します。

（ただ、ArrayはreplaceSubrangeの実装だけではなく、それぞれのメソッドごとに最適化された実装があるっぽいです。）

Rangeを用いた範囲書き込みで少しややこしいのが、書き込み先と書き込み内容の長さが一致する場合はMutableCollectionで可能ですが、長さが不一致の場合はRangeReplaceableCollectionが必要です。呼ばれる関数は同一のため（長さの一致を型で縛れないため）ややこしい。

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

// これはMutableCollection
numbers[0..<2] = [10, 20]

// これはRangeReplaceableCollection
numbers[0..<2] = [10]
numbers[0..<2] = [10, 20, 30]

BidirectionalCollection

endIndexからstartIndex方向への探索が可能なCollection。Collectionの子protocolになっており、通常のCollectionが要求するindex(after:)に加えindex(before:)の実装が追加で必要。

startIndex<->endIndexの双方向に探索が可能であるため、Collectionに比べ一部メソッドを効率的に処理できる。
nをCollection長とした時

計算量	Collection	BidirectionalCollection
suffix(k)	O(n)	O(k)
reversed	O(n)	O(1)

また、.last,dropLast()やlastIndexなどもBidirectionalCollectionで使えるようになる。

例: String

let reversed = "swift".reversed() // O(1)

RandomAccessCollection

任意のindexの算出がO(1)で可能なCollection。BidirectionalCollectionの子protocolになっており、要求する実装はBidirectionalCollectionと同じだが、indexに関連するメソッドをO(1)で実装するようにドキュメント上で指定がある。

計算量	BidirectionalCollection	RandomAccessCollection
distance	O(k)	O(1)
index(:offsetBy: k)	O(k)	O(1)
count	O(n)	O(1)

例えばStringはBidirectionalCollectionではあるがRandomAccessCollectionではないので、countがO(n)かかる。（SwiftのStringはただの8bit単位の配列ではなく、絵文字などを含めた”文字”単位のCollectionなため、indexの算出がO(1)で不可能。）
例えば空Collectionの判定の場合は常にO(1)のisEmptyを使うことが推奨されている。

（おまけ）具象Collection型の実装

Array, ArraySlice: MutableCollection, RangeReplaceableCollection, RandomAccessCollection
String, SubString: RangeReplaceableCollection, BidirectionalCollection
Range, ClosedRange: RandomAccessCollection
- Bound: StrideableでBound.Stride: SignedIntegerの場合
Set: Collection
- insertなどはSetAlgebra由来
Dictionary: Collection

Collectionはインデックスアクセスを前提とした設計なのに対して、SetやDictionaryはインデックスアクセスがメインではないデータ構造なため、最低限の準拠に留めているように見える。
このように、protocolはあくまで制約の話であって「MutableCollectionなら書き込みができる」は成り立ってもその裏「MutableCollectionではないなら書き込みができない」は成り立たたないことに注意は必要である。