第9章：STL入門

はじめに

STL（Standard Template Library）は、Alexander Stepanovが設計した汎用プログラミングライブラリであり、C++の最も重要な構成要素の一つです。1994年にC++標準に採用されて以来、C++プログラミングのあり方を根本的に変えました。

本章では、STLの設計思想から始め、コンテナ、イテレータ、アルゴリズムの基本を学びます。

---

1. STLの歴史と設計思想

1.1 Alexander Stepanovの貢献

Stepanovは1970年代からジェネリックプログラミングを研究し、以下の洞察に至りました：

> "Algorithms are not attached to specific data structures. The same algorithm can work on different data structures, and the same data structure can be processed by different algorithms." > > （アルゴリズムは特定のデータ構造に結びついていない。同じアルゴリズムが異なるデータ構造で動作でき、同じデータ構造が異なるアルゴリズムで処理できる）

この考えは、アルゴリズムとデータ構造の分離というSTLの核心的な設計原則となりました。

1.2 STLの三要素

STLは3つの主要コンポーネントから構成されます：

+-------------+     +-----------+     +------------+
| Containers  |<--->| Iterators |<--->| Algorithms |
| (コンテナ)  |     | (イテレータ)|     | (アルゴリズム)|
+-------------+     +-----------+     +------------+

コンテナ: データを格納する構造（vector, list, mapなど）
イテレータ: コンテナ内の要素にアクセスする汎用的なインターフェース
アルゴリズム: イテレータを通じてコンテナを操作する関数

1.3 ジェネリックプログラミングの利点

// 従来のアプローチ：各データ構造ごとにソート関数が必要
void sortArray(int arr[], int size);
void sortLinkedList(Node* head);
void sortVector(std::vector<int>& vec);

// STLのアプローチ：1つのアルゴリズムがあらゆるコンテナで動作
std::sort(arr, arr + size);           // 配列
std::sort(vec.begin(), vec.end());    // vector
std::sort(deq.begin(), deq.end());    // deque

---

2. コンテナ

2.1 シーケンスコンテナ

要素を順序付けて格納するコンテナ：

vector

動的配列。最も頻繁に使用されるコンテナ：

#include <vector>

int main() {
    // 初期化
    std::vector<int> v1;                    // 空のvector
    std::vector<int> v2(10);                // 10要素、0で初期化
    std::vector<int> v3(10, 42);            // 10要素、42で初期化
    std::vector<int> v4 = {1, 2, 3, 4, 5};  // 初期化リスト

    // 要素の追加
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);

    // アクセス
    std::cout << v1[0] << std::endl;         // 10（境界チェックなし）
    std::cout << v1.at(1) << std::endl;      // 20（境界チェックあり）
    std::cout << v1.front() << std::endl;    // 10（先頭）
    std::cout << v1.back() << std::endl;     // 30（末尾）

    // サイズ
    std::cout << v1.size() << std::endl;     // 3
    std::cout << v1.capacity() << std::endl; // 実際に確保された容量

    // イテレーション
    for (int x : v1) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

deque

両端キュー（Double-Ended Queue）：

#include <deque>

int main() {
    std::deque<int> dq;

    // 前後両方から追加可能
    dq.push_back(10);
    dq.push_front(5);
    dq.push_back(20);

    // [5, 10, 20]
    for (int x : dq) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // 前後両方から削除可能
    dq.pop_front();
    dq.pop_back();

    return 0;
}

list

双方向連結リスト：

#include <list>

int main() {
    std::list<int> lst = {1, 2, 3, 4, 5};

    // 挿入と削除がO(1)
    auto it = lst.begin();
    std::advance(it, 2);  // 3番目の要素を指す
    lst.insert(it, 99);   // [1, 2, 99, 3, 4, 5]

    // 要素の削除
    lst.remove(99);  // 値99を削除

    // ソート（std::sortは使えない、listは双方向イテレータのため）
    lst.sort();

    // splice: 別のlistを結合
    std::list<int> other = {10, 20, 30};
    lst.splice(lst.end(), other);

    return 0;
}

2.2 連想コンテナ

キーによる高速検索を提供するコンテナ：

set

一意の要素を格納（赤黒木で実装）：

#include <set>

int main() {
    std::set<int> s;

    // 挿入
    s.insert(30);
    s.insert(10);
    s.insert(20);
    s.insert(10);  // 重複は無視される

    // 要素数
    std::cout << s.size() << std::endl;  // 3

    // 検索
    if (s.find(20) != s.end()) {
        std::cout << "Found 20" << std::endl;
    }

    // C++20以降
    if (s.contains(20)) {
        std::cout << "Contains 20" << std::endl;
    }

    // イテレーション（自動的にソート順）
    for (int x : s) {
        std::cout << x << " ";  // 10 20 30
    }
    std::cout << std::endl;

    return 0;
}

map

キーと値のペアを格納：

#include <map>

int main() {
    std::map<std::string, int> ages;

    // 挿入
    ages["Alice"] = 30;
    ages["Bob"] = 25;
    ages.insert({"Charlie", 35});
    ages.emplace("David", 28);

    // アクセス
    std::cout << ages["Alice"] << std::endl;  // 30
    std::cout << ages.at("Bob") << std::endl; // 25

    // 存在しないキーへのアクセス
    // ages["Eve"]  // 0が挿入される！
    // ages.at("Eve")  // 例外が投げられる

    // 検索
    auto it = ages.find("Charlie");
    if (it != ages.end()) {
        std::cout << it->first << ": " << it->second << std::endl;
    }

    // イテレーション
    for (const auto& [name, age] : ages) {  // C++17
        std::cout << name << ": " << age << std::endl;
    }

    return 0;
}

multiset / multimap

重複を許可するバージョン：

#include <set>
#include <map>

int main() {
    std::multiset<int> ms;
    ms.insert(10);
    ms.insert(10);
    ms.insert(10);
    std::cout << ms.count(10) << std::endl;  // 3

    std::multimap<std::string, int> mm;
    mm.insert({"key", 1});
    mm.insert({"key", 2});
    mm.insert({"key", 3});

    auto range = mm.equal_range("key");
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << std::endl;
    }

    return 0;
}

2.3 非順序連想コンテナ（C++11）

ハッシュテーブルで実装されたコンテナ：

#include <unordered_set>
#include <unordered_map>

int main() {
    std::unordered_set<int> us = {3, 1, 4, 1, 5, 9};
    // 順序は保証されない
    // O(1)の平均検索時間

    std::unordered_map<std::string, int> um;
    um["hello"] = 42;
    // O(1)の平均挿入・検索時間

    // ハッシュ情報
    std::cout << "Buckets: " << us.bucket_count() << std::endl;
    std::cout << "Load factor: " << us.load_factor() << std::endl;

    return 0;
}

2.4 コンテナアダプタ

既存のコンテナをラップして特定のインターフェースを提供：

#include <stack>
#include <queue>

int main() {
    // スタック（LIFO）
    std::stack<int> stk;
    stk.push(1);
    stk.push(2);
    stk.push(3);
    while (!stk.empty()) {
        std::cout << stk.top() << " ";  // 3 2 1
        stk.pop();
    }
    std::cout << std::endl;

    // キュー（FIFO）
    std::queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    while (!q.empty()) {
        std::cout << q.front() << " ";  // 1 2 3
        q.pop();
    }
    std::cout << std::endl;

    // 優先度キュー（最大ヒープ）
    std::priority_queue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(4);
    while (!pq.empty()) {
        std::cout << pq.top() << " ";  // 4 3 1
        pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

---

3. イテレータ

3.1 イテレータの概念

イテレータは、コンテナの要素へのアクセスを抽象化したオブジェクトです：

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // begin(): 先頭を指すイテレータ
    // end(): 末尾の次を指すイテレータ（番兵）
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // auto を使った簡潔な書き方
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        *it *= 2;  // 各要素を2倍
    }

    // 範囲for文（内部でイテレータを使用）
    for (int x : vec) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

3.2 イテレータの種類

イテレータは機能によって5つのカテゴリに分類されます：

                    +-----------------+
                    | Random Access   |  vector, deque, 配列
                    | Iterator        |  +, -, <, >, [], +=, -=
                    +-----------------+
                           ↑
                    +-----------------+
                    | Bidirectional   |  list, set, map
                    | Iterator        |  --, 後退可能
                    +-----------------+
                           ↑
                    +-----------------+
                    | Forward         |  forward_list
                    | Iterator        |  複数パス可能
                    +-----------------+
                           ↑
                    +-----------------+
                    | Input Iterator  |  istream_iterator
                    | Output Iterator |  ostream_iterator
                    +-----------------+

各カテゴリの能力：

| カテゴリ | 読み取り | 書き込み | ++/-- | ランダムアクセス | 例 | |----------|----------|----------|-------|------------------|-----| | Input | ○ | × | ++ | × | istream_iterator | | Output | × | ○ | ++ | × | ostream_iterator | | Forward | ○ | ○ | ++ | × | forward_list | | Bidirectional | ○ | ○ | ++/-- | × | list, set, map | | Random Access | ○ | ○ | ++/-- | ○ | vector, deque |

3.3 イテレータ操作

#include <iterator>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // advance: イテレータを進める
    auto it = vec.begin();
    std::advance(it, 2);  // 2つ進める
    std::cout << *it << std::endl;  // 3

    // distance: 2つのイテレータ間の距離
    auto first = vec.begin();
    auto last = vec.end();
    std::cout << std::distance(first, last) << std::endl;  // 5

    // next / prev (C++11)
    auto it2 = vec.begin();
    auto it3 = std::next(it2, 3);  // 3つ先
    std::cout << *it3 << std::endl;  // 4

    auto it4 = std::prev(vec.end(), 2);  // 末尾から2つ前
    std::cout << *it4 << std::endl;  // 4

    return 0;
}

3.4 逆イテレータ

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 逆イテレータで逆順にアクセス
    for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
        std::cout << *rit << " ";  // 5 4 3 2 1
    }
    std::cout << std::endl;

    // crbegin/crend: const逆イテレータ
    for (auto rit = vec.crbegin(); rit != vec.crend(); ++rit) {
        std::cout << *rit << " ";
    }
    std::cout << std::endl;

    return 0;
}

3.5 挿入イテレータ

#include <iterator>
#include <algorithm>

int main() {
    std::vector<int> src = {1, 2, 3};
    std::vector<int> dst;

    // back_inserter: 末尾に挿入
    std::copy(src.begin(), src.end(), std::back_inserter(dst));
    // dst: {1, 2, 3}

    // front_inserter (dequeやlistで使用)
    std::list<int> lst;
    std::copy(src.begin(), src.end(), std::front_inserter(lst));
    // lst: {3, 2, 1}

    // inserter: 指定位置に挿入
    std::set<int> s = {10, 20};
    std::copy(src.begin(), src.end(), std::inserter(s, s.end()));
    // s: {1, 2, 3, 10, 20}

    return 0;
}

---

4. アルゴリズム

4.1 非変更シーケンス操作

#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 3, 2, 1};

    // find: 値を検索
    auto it = std::find(vec.begin(), vec.end(), 3);
    if (it != vec.end()) {
        std::cout << "Found at index: " << std::distance(vec.begin(), it) << std::endl;
    }

    // count: 値の出現回数
    int cnt = std::count(vec.begin(), vec.end(), 3);
    std::cout << "Count of 3: " << cnt << std::endl;  // 2

    // find_if: 条件に合う要素を検索
    auto it2 = std::find_if(vec.begin(), vec.end(), [](int x) {
        return x > 3;
    });
    std::cout << "First > 3: " << *it2 << std::endl;  // 4

    // all_of, any_of, none_of
    bool allPositive = std::all_of(vec.begin(), vec.end(), [](int x) {
        return x > 0;
    });
    std::cout << "All positive: " << allPositive << std::endl;  // 1

    // for_each: 各要素に関数を適用
    std::for_each(vec.begin(), vec.end(), [](int x) {
        std::cout << x << " ";
    });
    std::cout << std::endl;

    return 0;
}

4.2 変更シーケンス操作

#include <algorithm>

int main() {
    std::vector<int> vec = {5, 2, 8, 1, 9, 3};

    // sort: ソート
    std::sort(vec.begin(), vec.end());
    // vec: {1, 2, 3, 5, 8, 9}

    // reverse: 逆順
    std::reverse(vec.begin(), vec.end());
    // vec: {9, 8, 5, 3, 2, 1}

    // fill: 値で埋める
    std::fill(vec.begin(), vec.end(), 0);
    // vec: {0, 0, 0, 0, 0, 0}

    // transform: 変換
    std::vector<int> src = {1, 2, 3, 4, 5};
    std::vector<int> dst(5);
    std::transform(src.begin(), src.end(), dst.begin(), [](int x) {
        return x * x;
    });
    // dst: {1, 4, 9, 16, 25}

    // copy: コピー
    std::vector<int> copy_dst(5);
    std::copy(src.begin(), src.end(), copy_dst.begin());

    // replace: 値の置換
    std::replace(src.begin(), src.end(), 3, 100);
    // src: {1, 2, 100, 4, 5}

    // remove: 値の削除（実際には末尾に移動）
    auto new_end = std::remove(src.begin(), src.end(), 100);
    src.erase(new_end, src.end());  // 実際に削除

    // unique: 連続する重複を削除
    std::vector<int> dup = {1, 1, 2, 2, 2, 3, 3};
    auto unique_end = std::unique(dup.begin(), dup.end());
    dup.erase(unique_end, dup.end());
    // dup: {1, 2, 3}

    return 0;
}

4.3 ソートと検索

#include <algorithm>

int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};

    // sort
    std::sort(vec.begin(), vec.end());

    // カスタム比較関数
    std::sort(vec.begin(), vec.end(), std::greater<int>());  // 降順

    // partial_sort: 上位N個だけソート
    std::vector<int> v2 = {3, 1, 4, 1, 5, 9, 2, 6};
    std::partial_sort(v2.begin(), v2.begin() + 3, v2.end());
    // v2: {1, 1, 2, ...}  上位3個だけソート

    // nth_element: N番目の要素を正しい位置に配置
    std::vector<int> v3 = {3, 1, 4, 1, 5, 9, 2, 6};
    std::nth_element(v3.begin(), v3.begin() + 4, v3.end());
    // v3[4] が正しい位置に配置

    // stable_sort: 等しい要素の順序を保持
    std::stable_sort(vec.begin(), vec.end());

    // binary_search: ソート済み範囲での検索
    bool found = std::binary_search(vec.begin(), vec.end(), 5);

    // lower_bound / upper_bound
    auto lower = std::lower_bound(vec.begin(), vec.end(), 5);
    auto upper = std::upper_bound(vec.begin(), vec.end(), 5);

    return 0;
}

4.4 数値アルゴリズム

#include <numeric>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // accumulate: 合計
    int sum = std::accumulate(vec.begin(), vec.end(), 0);
    std::cout << "Sum: " << sum << std::endl;  // 15

    // カスタム操作
    int product = std::accumulate(vec.begin(), vec.end(), 1, std::multiplies<int>());
    std::cout << "Product: " << product << std::endl;  // 120

    // inner_product: 内積
    std::vector<int> v2 = {1, 2, 3, 4, 5};
    int dot = std::inner_product(vec.begin(), vec.end(), v2.begin(), 0);
    std::cout << "Dot product: " << dot << std::endl;  // 55

    // partial_sum: 累積和
    std::vector<int> sums(5);
    std::partial_sum(vec.begin(), vec.end(), sums.begin());
    // sums: {1, 3, 6, 10, 15}

    // adjacent_difference: 隣接要素の差
    std::vector<int> diffs(5);
    std::adjacent_difference(vec.begin(), vec.end(), diffs.begin());
    // diffs: {1, 1, 1, 1, 1}

    // iota: 連続値で埋める
    std::vector<int> seq(10);
    std::iota(seq.begin(), seq.end(), 1);
    // seq: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

    return 0;
}

---

5. 関数オブジェクト（ファンクタ）

5.1 関数オブジェクトとは

operator()をオーバーロードしたクラスのオブジェクト：

class Adder {
    int value;
public:
    Adder(int v) : value(v) {}

    int operator()(int x) const {
        return x + value;
    }
};

int main() {
    Adder add5(5);
    std::cout << add5(10) << std::endl;  // 15

    // アルゴリズムで使用
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::transform(vec.begin(), vec.end(), vec.begin(), add5);
    // vec: {6, 7, 8, 9, 10}

    return 0;
}

5.2 標準関数オブジェクト

#include <functional>

int main() {
    // 算術演算
    std::plus<int> add;
    std::cout << add(3, 5) << std::endl;  // 8

    std::minus<int> sub;
    std::multiplies<int> mul;
    std::divides<int> div;
    std::modulus<int> mod;
    std::negate<int> neg;

    // 比較演算
    std::equal_to<int> eq;
    std::not_equal_to<int> neq;
    std::greater<int> gt;
    std::less<int> lt;
    std::greater_equal<int> ge;
    std::less_equal<int> le;

    // ソートで使用
    std::vector<int> vec = {3, 1, 4, 1, 5};
    std::sort(vec.begin(), vec.end(), std::greater<int>());
    // vec: {5, 4, 3, 1, 1}

    return 0;
}

5.3 ラムダ式（C++11）

int main() {
    // 基本的なラムダ式
    auto add = [](int a, int b) { return a + b; };
    std::cout << add(3, 5) << std::endl;  // 8

    // キャプチャ
    int multiplier = 10;
    auto mul = [multiplier](int x) { return x * multiplier; };
    std::cout << mul(5) << std::endl;  // 50

    // 参照キャプチャ
    int counter = 0;
    auto increment = [&counter]() { ++counter; };
    increment();
    increment();
    std::cout << counter << std::endl;  // 2

    // キャプチャの種類
    // [=]  : 全てを値でキャプチャ
    // [&]  : 全てを参照でキャプチャ
    // [x]  : xを値でキャプチャ
    // [&x] : xを参照でキャプチャ
    // [=, &x] : 全て値、xのみ参照
    // [&, x]  : 全て参照、xのみ値

    // アルゴリズムで使用
    std::vector<int> vec = {1, 2, 3, 4, 5};
    int threshold = 3;
    auto count = std::count_if(vec.begin(), vec.end(), [threshold](int x) {
        return x > threshold;
    });
    std::cout << "Count > 3: " << count << std::endl;  // 2

    return 0;
}

5.4 std::function（C++11）

#include <functional>

int main() {
    // 関数を格納できる汎用ラッパー
    std::function<int(int, int)> op;

    // 通常の関数
    op = [](int a, int b) { return a + b; };
    std::cout << op(3, 5) << std::endl;  // 8

    // 別のラムダを代入
    op = [](int a, int b) { return a * b; };
    std::cout << op(3, 5) << std::endl;  // 15

    // 関数オブジェクト
    op = std::plus<int>();
    std::cout << op(3, 5) << std::endl;  // 8

    return 0;
}

---

6. コンテナの選択指針

6.1 性能比較

| 操作 | vector | deque | list | set/map | unordered_set/map | |------|--------|-------|------|---------|-------------------| | 末尾挿入 | O(1) | O(1) | O(1) | O(log n) | O(1) | | 先頭挿入 | O(n) | O(1) | O(1) | O(log n) | O(1) | | 中央挿入 | O(n) | O(n) | O(1) | O(log n) | O(1) | | 検索 | O(n) | O(n) | O(n) | O(log n) | O(1) | | ランダムアクセス | O(1) | O(1) | O(n) | O(log n) | O(n) |

: 償却計算量 / : 位置が既知の場合

6.2 選択のフローチャート

要素の順序が重要？
├─ No → キーで検索する？
│       ├─ Yes → 順序が重要？
│       │        ├─ Yes → set/map
│       │        └─ No  → unordered_set/map
│       └─ No  → vector
│
└─ Yes → どこに挿入/削除する？
         ├─ 末尾のみ → vector
         ├─ 両端    → deque
         └─ 中央    → list

6.3 具体的なガイドライン

デフォルトはvectorを使う

先頭への挿入が多い場合はdeque

中央への挿入/削除が多い場合はlist

キーによる検索が必要な場合はmap/set

順序不要でO(1)検索が必要な場合はunordered_map/set

---

まとめ

本章で学んだこと：

STLの設計思想: Stepanovのジェネリックプログラミング

コンテナ: シーケンス、連想、非順序連想

イテレータ: 5つのカテゴリ、操作関数

アルゴリズム: 非変更、変更、ソート、数値

関数オブジェクト: ファンクタ、ラムダ式

コンテナ選択**: 性能特性と選択指針

次章では、例外処理について学びます。

---

練習問題

vectorに格納された整数の中から、偶数のみを抽出して新しいvectorに格納してください。

mapを使って、文字列の出現回数をカウントするプログラムを作成してください。

以下の操作を行うプログラムを作成してください：

- vectorに1から100までの整数を格納 - 3の倍数をすべて削除 - 残った要素を降順にソート - 上位10個を出力

カスタム比較関数を使って、構造体のvectorを複数のキーでソートしてください：

struct Person {
    std::string name;
    int age;
    double salary;
};