📖

【Swift】CollectionとSequenceの理解

に公開
Swift
collection
プロトコル
コレクション
sequence
tech

「Array」「Dictionary」「String」「Set」
これらはSequenceとCollectionの2つのプロトコル（制約）の下で成り立っています。

本記事では、筆者が学んだことを言語化しながら、SequenceプロトコルとCollectionプロトコルがコレクション操作においてなぜ重要なのかを紐解いていきます。

想定している読者

  • 2つのプロトコルSequenceとCollectionの役割と違いを知りたい人
  • Swiftのコレクションの基本を学びたい人

記事の概要

この記事では以下の3ステップでSequenceとCollectionの2つのプロトコルを紐解いていきます。

  1. 具体的なコレクション型の全体像
    代表的なArray, Dictionary, String, Setがもつ共通の仕組み

  2. なぜCollectionが必要？
    Collection が提供する便利機能を深掘り

  3. CollectionとSequenceのつながり
    Collectionの裏側に隠れたSequenceの仕組みを理解

1. 具体的なコレクション型の全体像

ここでは、みなさんにも馴染みのあるArray, Dictionary, String, Setをおさらいした後、それぞれがもつコレクションとしての共通の要件をみていきます。

1.1. Array

Arrayは可変長の順序付きコレクションです。
ご存知の通り、要素数の取得やランダムアクセスなどをサポートしています。

let fruits = ["🍎", "🍊", "🍇"]
print(fruits.count)    // 3
print(fruits[1])       // 🍊
for fruit in fruits {
    print(fruit)
}

主な特徴は以下の通りです。

countプロパティによる要素数の呼び出し

Arrayは内部で要素数を保持しているため、countの呼び出しは O(1) です。
UIの表示件数や計算ロジックで要素数を頻繁に参照しても、性能への影響がほとんどありません。

subscriptでインデックス指定の取得が可能

fruits[1]のようにインデックスを指定すれば、指定位置の要素を直接取得できます。これも O(1) の動作なので、必要な要素を走査せずに迅速に取り出せます。

indicesで有効な範囲を取得でき、多重列挙も容易

0..<fruits.countと同等のRangeを返します。for i in fruits.indicesのように使うと、境界外アクセスの心配なくインデックスで列挙でき、複数回走査しても同じ範囲を保証します。

1.2. Dictionary

Dictionaryはキーと値を対応付ける連想配列でした。

let dict: [String: Int] = ["A": 1, "B": 2]
print(dict.count)      // 2
print(dict["A"]!)     // 1
for (key, value) in dict {
    print("\(key): \(value)")
}

Dictionaryの特徴として、以下のようなものがあります。

countで要素数が取得可能

Dictionaryは内部で格納している要素数を常に管理しているため、countプロパティを呼び出すだけで即座に要素数を取得できます。全要素を走査する必要がないため、高速かつ O(1) の計算量で利用できます。

subscriptでキーに対応する値を取得

dict["A"] のように、キーを指定するだけで対応する値を高速に取得できます。ハッシュベースの実装により、通常は O(1) の時間でアクセスできるため、頻繁な検索にも耐えられます。キーが存在しない場合は nil が返されるので、エラーハンドリングも簡単です。

keys / values でキー一覧・値一覧のコレクションを取得

keysはすべてのキーを列挙するコレクション、valuesはすべての値を列挙するコレクションを返します。たとえば、すべてのキーだけをリスト表示したい場合や、すべての値に対して操作を行いたい場合に便利です。これらも遅延評価（lazy）で実装されているため、大規模な辞書でも効率よく利用できます。

1.3. String

文字列をCharacter単位で列挙でき、文字数の取得やインデックスアクセスも提供します。

let text = "Hello"
print(text.count)      // 5
print(text[text.index(text.startIndex, offsetBy: 1)]) // e
for char in text {
    print(char)
}

Stringの特徴は以下の通りです。

countプロパティによる文字数の取得

Stringのcountプロパティは、文字列内の "Unicodeスカラ"（1文字として認識される単位）の数を返します。アルファベットや日本語だけでなく、Emoji（例えば "🌟" ⭐️）など、複数のコードポイントからなる文字も1文字とカウントされるため、見た目の文字数と一致する形になります。文字列を UI に表示するときなど、実際の見た目を意識した文字数を知るために役立ちます。

index(_:offsetBy:)メソッドによるアクセス

Stringは単純な配列とは異なり、内部的に可変長の文字（複数バイト）を扱うため、整数インデックスでは直接アクセスできません。代わりに、startIndexからの距離を指定して、正しい位置を計算する必要があります。index(startIndex, offsetBy: n)を使うことで、文字列を正しくナビゲートし、安全に特定の位置にある文字へアクセスできます。

1.4. Set

最後にSetです。
Setは簡単に説明すると、順序を持たない重複排除コレクションです。

let set: Set<Int> = [1, 2, 3, 2]
print(set.count)       // 3
for num in set {
    print(num)
}

Setの特徴は以下の通りです。

countプロパティとcontains(_:)メソッド

Setはハッシュテーブルというデータ構造を使って内部的に要素を管理しているため、要素数の取得（count）や、特定の要素が存在するかを調べる（“contains(_:)`）操作が非常に高速（平均 O(1)）で行えます。
これにより、大量のデータからの検索や存在確認でもパフォーマンスが劣化しにくくなっています。

順序の保証がないこと

Setでは、要素の挿入順や取り出す順序が保証されていません。
同じSetに対してfor inで要素を列挙するたびに、順番が異なる可能性があります。
これは、データ構造であるハッシュテーブルの特性によるもので、このハッシュテーブルでは、各要素に対して計算されたハッシュ値をもとに、内部のメモリ上の位置が決まります。
このため、格納や検索は高速に行えますが、ハッシュ値の計算結果や格納順序に依存するため、列挙時の順番は保証されず、実行ごとに変わる可能性があります。
順番が重要な場合（例：ユーザー表示順を保ちたい場合）はArrayなど、順序を持つコレクションを選ぶ必要があります。

ここまでで、具体的なコレクション型についてそれぞれの特徴を見てきました。

それでは次に、これらに共通する「必要な機能」が何なのか、そしてなぜCollectionプロトコルという共通の型制約が必要になるのかを掘り下げていきましょう！

2. なぜCollectionが必要か: 具体的コレクション型の共通要件

セクション1でそれぞれのコレクションの型の特徴で見てきたように、これらには以下の共通したニーズがあるというわけです。

要素数の即時取得

UI 表示やバッチ処理では、データ数を表示・計算する場面が多い。
countで即時取得できないと、全要素を列挙してカウントする非効率が生じます。

インデックス／キーによるランダムアクセス

配列や文字列は位置指定で、「3番目の要素」を取り出す必要がある。
辞書はキー指定で値を引きたい。
これらをサポートしないと、目的の要素を探すために全体を走査するコストが発生します。

複数回の列挙（多重走査）

表示更新や再処理で、同じデータを何度もイテレートする必要がある。
Sequenceのみではイテレータが一度限りなので、再列挙に都度イテレータを作り直す手間と実装ミスのリスクが増します。

安全なインデックス操作

startIndex / endIndex / indicesを提供すると、境界チェックを標準的に行いやすくなり、配列の範囲を一つずれてアクセスしてしまうようなミス（例えば、存在しないインデックスを参照してしまうミス）を防げます。

これらを満たすため、Swift はCollectionプロトコルを定義し、標準コレクション型はすべてこのプロトコルに準拠しています。
逆に言えば、「Collectionに準拠した型は、上記の要件を低コストかつ安全に実現できる API（count, subscript, indicesなど）を手に入れられる」というわけですね。

Collectionプロトコルが提供するAPIはたくさんありますが、以下は上記をコードに落とした一例です。

public protocol Collection: Sequence {
    associatedtype Element
    var startIndex: Index { get }
    var endIndex: Index { get }
    subscript(position: Index) -> Element { get }
    func index(after i: Index) -> Index
    var count: Int { get }
}

3. CollectionとSequenceの関係性

さて、具体的なコレクション型（Array, Dictioanry, String, Setなど）がCollectionという共通の規約をベースに便利な機能を利用できることがわかりました。

実はさらに深ぼっていくと、Collectionプロトコルのさらにベースとなる『あるプロトコル』が存在します。
それが、Sequenceプロトコルです。

『Collection』と『Sequence』の2つの関係は以下の図のようになります。

簡単に説明すると、
Sequenceは基本的な機能を、CollectionはSequenceに加えて+αの機能を提供します。

let arr = [1, 2, 3]
// Collection としての機能
print(arr.count)       // 3
print(arr[1])          // 2

// Sequence としての機能
for num in arr.makeIterator() {
    print(num)
}

つまりCollectionのインスタンスはfor ... inを使って一方向に列挙できる機能（Sequence由来）を持ちながら、さらにインデックス指定によるランダムアクセスや要素数の即時取得といった高機能な操作（Collection独自の拡張機能）も利用できるようになっています。

一方、Sequence単体では、次の要素を順番に取り出す最低限の列挙機能（makeIterator()とnext()）のみが保証されており、要素数取得やランダムアクセスのような便利な操作は標準では提供されていないのです。

本記事では、よく使われる具体的なコレクション型から2つのプロトコルCollectionとSequenceを紹介してみました。
私たちが使うコレクション型は『共通の要件』『共通の規約』の下で成り立っています。
Apple公式のドキュメントから基礎的なプロトコルを改めて見ると、まだまだ知らない世界があるなと実感させられました。
今回紹介したもの以外にも基盤となるプロトコルがたくさんありますので、興味を持った方はぜひみてみてはいかがでしょうか。

Discussion