# 機能設計書 7-System.Collections

## 概要

本ドキュメントは、.NET runtimeプロジェクトにおけるSystem.Collectionsライブラリの機能設計について記述する。System.CollectionsはList、Dictionary、Queue、Stack等の汎用コレクション型を提供する基本クラスライブラリである。

### 本機能の処理概要

**業務上の目的・背景**：System.Collectionsは、.NETアプリケーションで最も頻繁に使用されるデータ構造を提供する基盤ライブラリである。効率的なデータの格納、検索、列挙を可能にし、開発者が独自にデータ構造を実装する必要をなくす。ジェネリックコレクションにより型安全性を保証し、ボックス化によるパフォーマンス低下を回避する。

**機能の利用シーン**：
- 動的配列としてのList<T>の使用
- キー値ペアの格納にDictionary<TKey, TValue>
- FIFO処理にQueue<T>
- LIFO処理にStack<T>
- ソート済みデータにSortedSet<T>、SortedDictionary<TKey, TValue>

**主要な処理内容**：
1. 要素の追加、削除、検索
2. 列挙子（Enumerator）によるイテレーション
3. コレクションの容量管理
4. 比較器（Comparer）によるソート・検索
5. スレッドセーフではないシングルスレッド向け操作

**関連システム・外部連携**：
- LINQ（System.Linq）との統合
- シリアライズ（System.Runtime.Serialization）との連携

**権限による制御**：
- 特になし（汎用ライブラリ）

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| 5 | Benchmark Sample | 補助機能 | ベンチマークタスクとリザルトのコレクション管理 |

## 機能種別

データ構造 / コレクション操作

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| 要素 | T | Yes | コレクションに格納する要素 | 型制約による |
| 容量 | int | No | 初期容量 | 非負整数 |
| 比較器 | IComparer<T> | No | カスタム比較ロジック | null許容 |

### 入力データソース

- アプリケーションコードからの直接操作
- デシリアライズによるデータ復元

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 要素 | T | 取得された要素 |
| インデックス | int | 検索結果のインデックス |
| 列挙子 | IEnumerator<T> | イテレーション用 |

### 出力先

- 呼び出し元への戻り値
- LINQクエリ結果

## 処理フロー

### 処理シーケンス

```
1. コレクション初期化
   └─ 初期容量の確保
2. 要素追加（Add）
   └─ 容量チェック→必要に応じてリサイズ
3. 要素検索（Contains/IndexOf）
   └─ 比較器による等価性判定
4. 要素削除（Remove）
   └─ 検索→削除→詰め替え
5. 列挙（foreach）
   └─ 列挙子による順次アクセス
```

### フローチャート

```mermaid
flowchart TD
    A[Add要求] --> B{容量十分?}
    B -->|Yes| C[要素追加]
    B -->|No| D[容量拡張]
    D --> C
    C --> E[Count増加]

    F[Contains要求] --> G[比較器で検索]
    G --> H{見つかった?}
    H -->|Yes| I[true返却]
    H -->|No| J[false返却]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | 容量拡張 | 不足時に2倍に拡張 | Add時 |
| BR-02 | バージョン管理 | 変更時にバージョンインクリメント | 構造変更時 |
| BR-03 | 赤黒木バランス | SortedSetは赤黒木で実装 | ソート済みコレクション |

### 計算ロジック

- List<T>：配列ベース、O(1)アクセス、O(n)挿入/削除
- Dictionary<TKey, TValue>：ハッシュテーブル、O(1)平均アクセス
- SortedSet<T>：赤黒木、O(log n)操作

## データベース操作仕様

### 操作別データベース影響一覧

| 操作 | 対象テーブル | 操作種別 | 概要 |
|-----|-------------|---------|------|
| - | - | - | コレクションライブラリはデータベースを操作しない |

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| ArgumentNullException | 引数null | nullキー等 | null検証 |
| ArgumentOutOfRangeException | 範囲外 | 不正インデックス | 範囲検証 |
| InvalidOperationException | 不正操作 | 列挙中の変更 | 変更回避 |
| KeyNotFoundException | キー不在 | Dictionary[key]アクセス | TryGetValue使用 |

### リトライ仕様

- 該当なし（同期的操作）

## トランザクション仕様

コレクションライブラリはトランザクション管理を行わない。

## パフォーマンス要件

- List<T>アクセス：O(1)
- Dictionary<TKey, TValue>アクセス：O(1)平均
- SortedSet<T>操作：O(log n)

## セキュリティ考慮事項

- ハッシュDoS対策：ランダム化ハッシュシード
- 信頼されない比較器の防御

## 備考

- System.Collections.Genericが主要な名前空間
- 非ジェネリック版（System.Collections）は互換性のため維持

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | SortedSet.cs | `src/libraries/System.Collections/src/System/Collections/Generic/SortedSet.cs` | 赤黒木実装 |
| 1-2 | SortedDictionary.cs | `src/libraries/System.Collections/src/System/Collections/Generic/SortedDictionary.cs` | TreeSet使用 |

**読解のコツ**:
- **SortedSet.cs 13-27行目**: 赤黒木の性質説明コメント
  - 全ノードは赤か黒
  - 葉は黒
  - 赤ノードの子は黒
  - ルートから葉への黒ノード数は一定
- **SortedSet.cs 29-33行目**: `NodeColor`列挙（Black/Red）
- **SortedSet.cs 37-43行目**: `TreeRotation`列挙（Left/LeftRight/Right/RightLeft）
- **SortedSet.cs 49行目**: `SortedSet<T>`クラスの継承インターフェース
- **SortedSet.cs 53-56行目**: フィールド定義（root, comparer, count, version）

#### Step 2: 比較器を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | SortedSet.cs (71-79行目) | `src/libraries/System.Collections/src/System/Collections/Generic/SortedSet.cs` | コンストラクタ |

**主要処理フロー**:
- **SortedSet.cs 71-74行目**: デフォルトコンストラクタでComparer<T>.Default使用
- **SortedSet.cs 76-79行目**: カスタム比較器コンストラクタ

#### Step 3: SortedDictionaryを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | SortedDictionary.cs | `src/libraries/System.Collections/src/System/Collections/Generic/SortedDictionary.cs` | TreeSetラッパー |

**主要処理フロー**:
- **SortedDictionary.cs 14行目**: `SortedDictionary<TKey, TValue>`クラス定義
- **SortedDictionary.cs 21行目**: `TreeSet<KeyValuePair<TKey, TValue>> _set` - 内部データ構造

### プログラム呼び出し階層図

```
SortedSet<T>
    │
    ├─ Add(T item)
    │      └─ Node挿入 → 赤黒木リバランス
    │
    ├─ Remove(T item)
    │      └─ Node検索 → 削除 → リバランス
    │
    ├─ Contains(T item)
    │      └─ 二分探索
    │
    └─ GetEnumerator()
           └─ 中間順走査

SortedDictionary<TKey, TValue>
    │
    └─ TreeSet<KeyValuePair<TKey, TValue>>
           └─ KeyValuePairComparer による比較
```

### データフロー図

```
[入力]                    [処理]                         [出力]

Add要素 ──────▶ 挿入位置検索 ──────▶ Nodeオブジェクト
     │                │
     │                ▼
     │            赤黒木リバランス
     │                │
     ▼                ▼
比較器 ──────▶ 比較判定 ──────▶ 挿入位置決定
     │                │
     │                ▼
     │            回転操作
     │                │
     ▼                ▼
ルートNode ◀──────── 色変更 ──────▶ バランス木
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| SortedSet.cs | `src/libraries/System.Collections/src/System/Collections/Generic/SortedSet.cs` | ソース | 赤黒木Set |
| SortedDictionary.cs | `src/libraries/System.Collections/src/System/Collections/Generic/SortedDictionary.cs` | ソース | ソート済み辞書 |
| SortedList.cs | `src/libraries/System.Collections/src/System/Collections/Generic/SortedList.cs` | ソース | ソート済みリスト |
| LinkedList.cs | `src/libraries/System.Collections/src/System/Collections/Generic/LinkedList.cs` | ソース | 双方向リンクリスト |
| PriorityQueue.cs | `src/libraries/System.Collections/src/System/Collections/Generic/PriorityQueue.cs` | ソース | 優先度キュー |
| OrderedDictionary.cs | `src/libraries/System.Collections/src/System/Collections/Generic/OrderedDictionary.cs` | ソース | 順序付き辞書 |
| SortedSet.TreeSubSet.cs | `src/libraries/System.Collections/src/System/Collections/Generic/SortedSet.TreeSubSet.cs` | ソース | 部分集合ビュー |
| SortedSetEqualityComparer.cs | `src/libraries/System.Collections/src/System/Collections/Generic/SortedSetEqualityComparer.cs` | ソース | Set等価比較 |
