第1章：高度なSTLアプリケーション

はじめに

CPP Module 09では、STLを使った実践的なアプリケーションを開発します。ファイルパース、式評価、高度なソートアルゴリズムなど、実務で必要となるスキルを習得します。

---

1. ファイルパースの基礎

1.1 CSVの歴史

CSV（Comma-Separated Values）は1970年代に登場したデータ形式です。IBMのFortranコンパイラが最初にサポートしたとされています。

CSVの利点：

  • 可読性: テキストエディタで閲覧可能
  • 互換性: ほとんどのソフトウェアがサポート
  • シンプルさ: 複雑なパーサー不要

1.2 C++でのファイル処理

#include <fstream>
#include <sstream>
#include <string>

// ファイル読み込み
std::ifstream file("data.csv");
if (!file.is_open()) {
    throw std::runtime_error("Cannot open file");
}

// 行ごとに読み込み
std::string line;
while (std::getline(file, line)) {
    // 行の処理
    std::stringstream ss(line);
    std::string cell;

    // カンマ区切りで分割
    while (std::getline(ss, cell, ',')) {
        // セルの処理
    }
}

1.3 日付処理

日付文字列のパースは多くのアプリケーションで必要です：

// 日付パース（YYYY-MM-DD形式）
bool parseDate(const std::string& dateStr, int& year, int& month, int& day) {
    if (dateStr.length() != 10) return false;
    if (dateStr[4] != '-' || dateStr[7] != '-') return false;

    std::stringstream ss(dateStr);
    char dash1, dash2;
    ss >> year >> dash1 >> month >> dash2 >> day;

    if (ss.fail()) return false;

    // 日付の妥当性チェック
    if (month < 1 || month > 12) return false;
    if (day < 1 || day > 31) return false;

    // 月ごとの日数チェック
    int daysInMonth[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    // 閏年チェック
    if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)) {
        daysInMonth[2] = 29;
    }

    if (day > daysInMonth[month]) return false;

    return true;
}

---

2. スタックと式評価

2.1 逆ポーランド記法の歴史

逆ポーランド記法（Reverse Polish Notation, RPN）は、1920年代にポーランドの論理学者Jan Łukasiewiczが考案しました。

通常の記法（中置記法）：3 + 4 逆ポーランド記法（後置記法）：3 4 +

2.2 なぜRPNか

  • 括弧が不要: 演算順序が明確
  • スタックで評価可能: 簡単なアルゴリズム
  • 電卓での実装が容易: HP電卓で採用

中置記法:    (3 + 4) * 5 = 35
逆ポーランド: 3 4 + 5 * = 35

評価手順:
1. 3をスタックにpush     → [3]
2. 4をスタックにpush     → [3, 4]
3. +: 3と4をpop、加算、7をpush → [7]
4. 5をスタックにpush     → [7, 5]
5. *: 7と5をpop、乗算、35をpush → [35]

2.3 Dijkstraのシャンティングヤードアルゴリズム

中置記法からRPNへの変換には、Edsger Dijkstraのシャンティングヤードアルゴリズム（1961年）が使われます：

// シャンティングヤードアルゴリズムの概念
// 入力: 3 + 4 * 5
// 出力: 3 4 5 * +

// 演算子の優先順位
int precedence(char op) {
    switch (op) {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        default: return 0;
    }
}

// 変換アルゴリズム
std::string infixToRPN(const std::string& infix) {
    std::string output;
    std::stack<char> operators;

    for (char c : infix) {
        if (isdigit(c)) {
            output += c;
            output += ' ';
        } else if (c == '+' || c == '-' || c == '*' || c == '/') {
            while (!operators.empty() &&
                   precedence(operators.top()) >= precedence(c)) {
                output += operators.top();
                output += ' ';
                operators.pop();
            }
            operators.push(c);
        }
    }

    while (!operators.empty()) {
        output += operators.top();
        output += ' ';
        operators.pop();
    }

    return output;
}

---

3. ソートアルゴリズム

3.1 ソートの歴史

コンピュータ科学の初期から、ソートは重要な研究対象でした。

歴史的なマイルストーン：

  • 1945年: John von Neumannがマージソートを発明
  • 1959年: Tony Hoareがクイックソートを発明
  • 1964年: Heapsortが発明される
  • 1979年: Timsortの基礎となるアイデアが登場
  • 2002年: Tim PetersがTimsortを開発（Python用）

3.2 比較ソートの下限

比較ソート（要素を比較して順序を決定するソート）の計算量下限はΩ(n log n)です。

証明の概要：

  • n個の要素の順列はn!通り
  • 二分決定木で表現すると、葉の数はn!
  • 木の高さはlog(n!) = Ω(n log n)

3.3 Ford-Johnsonアルゴリズム

Ford-Johnson（別名Merge-Insertion Sort）は、1959年にLester FordとSelmer Johnsonによって発明されました。

このアルゴリズムは最少比較回数を達成するために設計されました。

アルゴリズムの概要：

  • 要素をペアにする
  • 各ペア内で比較し、大小を決定
  • 大きい方を再帰的にソート
  • 小さい方を二分挿入でソート済み列に挿入

入力: [3, 1, 4, 1, 5, 9, 2, 6]

Step 1: ペア化
(3,1), (4,1), (5,9), (2,6)

Step 2: 各ペアで比較（大きい方を先に）
(3,1), (4,1), (9,5), (6,2)

Step 3: 大きい方をソート
[3, 4, 6, 9]

Step 4: 小さい方を挿入
- 1を挿入 → [1, 3, 4, 6, 9]
- 1を挿入 → [1, 1, 3, 4, 6, 9]
- 5を挿入 → [1, 1, 3, 4, 5, 6, 9]
- 2を挿入 → [1, 1, 2, 3, 4, 5, 6, 9]

3.4 Jacobsthal数列

Ford-Johnsonでは、挿入順序を最適化するためにJacobsthal数列を使用します：

Jacobsthal数列: 1, 1, 3, 5, 11, 21, 43, 85, ...

漸化式: J(n) = J(n-1) + 2*J(n-2)
       J(0) = 0, J(1) = 1

この数列により、二分探索の範囲を最適化し、比較回数を削減します。

---

4. std::mapの詳細

4.1 内部実装

std::mapは赤黒木で実装されています：

#include <map>

std::map<std::string, double> prices;

// O(log n)での挿入
prices["2022-01-01"] = 42000.0;

// O(log n)での検索
auto it = prices.find("2022-01-01");
if (it != prices.end()) {
    std::cout << it->second << std::endl;
}

// lower_bound: キー以上の最小要素
auto lb = prices.lower_bound("2022-06-01");

// upper_bound: キーより大きい最小要素
auto ub = prices.upper_bound("2022-06-01");

4.2 lower_boundとupper_bound

std::map<int, std::string> m;
m[10] = "ten";
m[20] = "twenty";
m[30] = "thirty";

// lower_bound(25): 25以上の最小キー → 30を指す
// upper_bound(20): 20より大きい最小キー → 30を指す
// lower_bound(20): 20以上の最小キー → 20を指す

auto lb = m.lower_bound(25);
if (lb != m.begin()) {
    --lb;  // 25より小さい最大キー → 20を指す
}

---

5. std::stackの活用

5.1 基本操作

#include <stack>

std::stack<int> stk;

stk.push(1);  // [1]
stk.push(2);  // [1, 2]
stk.push(3);  // [1, 2, 3]

int top = stk.top();  // 3
stk.pop();            // [1, 2]

bool empty = stk.empty();  // false
size_t size = stk.size();  // 2

5.2 RPN電卓での使用

int evaluateRPN(const std::string& expr) {
    std::stack<int> stk;
    std::stringstream ss(expr);
    std::string token;

    while (ss >> token) {
        if (token == "+" || token == "-" ||
            token == "*" || token == "/") {
            int b = stk.top(); stk.pop();
            int a = stk.top(); stk.pop();

            int result;
            if (token == "+") result = a + b;
            else if (token == "-") result = a - b;
            else if (token == "*") result = a * b;
            else result = a / b;

            stk.push(result);
        } else {
            stk.push(std::stoi(token));
        }
    }

    return stk.top();
}

---

6. コンテナの選択

6.1 std::vector vs std::deque

| 特性 | vector | deque | |------|--------|-------| | 連続メモリ | Yes | No | | 先頭挿入 | O(n) | O(1) | | 末尾挿入 | 償却O(1) | O(1) | | ランダムアクセス | O(1) | O(1) | | キャッシュ効率 | 高 | 中 |

6.2 std::list vs std::vector

| 特性 | list | vector | |------|------|--------| | 挿入/削除（中間） | O(1) | O(n) | | ランダムアクセス | O(n) | O(1) | | メモリオーバーヘッド | 高 | 低 | | イテレータ無効化 | なし | あり |

6.3 42課題での選択

// ex02: PmergeMe
// 2種類のコンテナで同じアルゴリズムを実装

// std::vectorを使用
void mergeInsertSort(std::vector<int>& vec);

// std::dequeを使用
void mergeInsertSort(std::deque<int>& deq);

// 実行時間を比較

---

7. エラー処理パターン

7.1 入力検証

bool validateInput(const std::string& input) {
    // 空文字列チェック
    if (input.empty()) {
        std::cerr << "Error: empty input" << std::endl;
        return false;
    }

    // 数値範囲チェック
    long value;
    try {
        value = std::stol(input);
    } catch (const std::exception& e) {
        std::cerr << "Error: invalid number" << std::endl;
        return false;
    }

    if (value < 0 || value > INT_MAX) {
        std::cerr << "Error: value out of range" << std::endl;
        return false;
    }

    return true;
}

7.2 ファイルエラー

void processFile(const std::string& filename) {
    std::ifstream file(filename);

    if (!file.is_open()) {
        throw std::runtime_error("Error: could not open file.");
    }

    std::string line;
    int lineNum = 0;

    while (std::getline(file, line)) {
        lineNum++;

        if (line.empty()) {
            continue;  // 空行はスキップ
        }

        try {
            processLine(line);
        } catch (const std::exception& e) {
            std::cerr << "Error at line " << lineNum << ": "
                      << e.what() << std::endl;
        }
    }
}

---

まとめ

本章で学んだこと：

  • ファイルパース: CSV処理、日付パース
  • 式評価: RPN、スタック、シャンティングヤード
  • ソートアルゴリズム: Ford-Johnson、比較ソートの下限
  • コンテナ選択: vector vs deque vs list
  • エラー処理: 入力検証、ファイルエラー

次章では、各演習の詳細な実装を解説します。

Next →
実装ガイド