第1章：STLの基礎

はじめに

CPP Module 08では、C++のStandard Template Library（STL）を学びます。STLはC++の最も強力な機能の一つであり、汎用的なデータ構造とアルゴリズムを提供します。

---

1. STLの歴史

1.1 Alexander Stepanovの貢献

Alexander Stepanovは「ジェネリックプログラミングの父」と呼ばれます。1970年代後半、彼はソビエト連邦で数学的な抽象化をプログラミングに適用する研究を始めました。

Stepanovの核心的なアイデア： > 「アルゴリズムは、可能な限り一般的に記述されるべきである。 > 型は、アルゴリズムに必要な操作をサポートするすべてのものであるべきだ。」

1.2 Hewlett-Packard研究所での開発

1988年、StepanovはHewlett-Packard研究所でジェネリックプログラミングの実装を開始しました。彼はDavid Musserと協力し、C++でジェネリックライブラリを開発しました。

1.3 C++標準への採用

1994年、Andrew Koenigの推薦により、STLはC++標準化委員会に提出されました。同年、STLはC++標準ライブラリの一部として採用されました。

これは異例の出来事でした。通常、標準ライブラリは言語仕様の後に設計されますが、STLは逆に言語機能（テンプレート）の使い方を定義しました。

---

2. STLの設計思想

2.1 三つの柱

STLは3つの核となる概念で構成されています：

+-------------+     +------------+     +-------------+
|  Container  | --> |  Iterator  | --> |  Algorithm  |
+-------------+     +------------+     +-------------+
| vector      |     | begin()    |     | sort()      |
| list        |     | end()      |     | find()      |
| map         |     | ++, *      |     | transform() |
| set         |     | ==, !=     |     | copy()      |
+-------------+     +------------+     +-------------+

この設計の利点：

  • 独立性: 各コンポーネントは独立して開発可能
  • 組み合わせ: 任意のコンテナに任意のアルゴリズムを適用
  • 拡張性: 新しいコンテナやアルゴリズムを追加可能

2.2 ゼロオーバーヘッド原則

Bjarne Stroustrupの設計原則： > 「使わないものにはコストを払わない。 > 使うものについては、手書きでより効率的なコードを書けない。」

STLはこの原則を完璧に実現しています：

  • コンパイル時特殊化: テンプレートにより型ごとに最適化
  • インライン展開: 関数呼び出しオーバーヘッドなし
  • 直接メモリアクセス: 仮想関数を使わない

2.3 概念（Concepts）

STLは概念（Concepts）という設計パターンを使用します。概念は型が満たすべき要件の集合です：

// ForwardIterator概念
// 型Tが以下を満たす：
// - コピー構築可能
// - ++演算子
// - *演算子（参照）
// - ==, !=演算子

C++20では、概念が言語機能として正式に導入されました。

---

3. コンテナ

3.1 シーケンスコンテナ

要素が順序を持って格納されるコンテナ：

#include <vector>
#include <deque>
#include <list>
#include <array>    // C++11
#include <forward_list>  // C++11

// vector: 動的配列
std::vector<int> vec;
vec.push_back(1);
vec.push_back(2);
// メモリ: [1][2][ ][ ]  (連続)

// deque: 両端キュー
std::deque<int> deq;
deq.push_front(1);
deq.push_back(2);
// メモリ: チャンク単位で管理

// list: 双方向リンクリスト
std::list<int> lst;
lst.push_back(1);
lst.push_back(2);
// メモリ: [prev|1|next] <-> [prev|2|next]

3.2 連想コンテナ

キーによる高速検索を提供：

#include <set>
#include <map>
#include <multiset>
#include <multimap>

// set: 重複なし、ソート済み
std::set<int> s;
s.insert(3);
s.insert(1);
s.insert(2);
// 内部: 赤黒木 (Red-Black Tree)
// {1, 2, 3}

// map: キーと値のペア
std::map<std::string, int> m;
m["one"] = 1;
m["two"] = 2;
// 内部: 赤黒木

3.3 ハッシュコンテナ（C++11）

#include <unordered_set>
#include <unordered_map>

// unordered_set: ハッシュテーブル
std::unordered_set<int> us;
us.insert(1);
// O(1)平均、O(n)最悪

// unordered_map: ハッシュマップ
std::unordered_map<std::string, int> um;
um["one"] = 1;

3.4 コンテナアダプタ

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

#include <stack>
#include <queue>
#include <priority_queue>

// stack: LIFO (Last In, First Out)
std::stack<int> stk;  // デフォルトはdequeをラップ
stk.push(1);
stk.push(2);
stk.top();  // 2
stk.pop();

// queue: FIFO (First In, First Out)
std::queue<int> q;
q.push(1);
q.push(2);
q.front();  // 1
q.pop();

// priority_queue: 最大ヒープ
std::priority_queue<int> pq;
pq.push(1);
pq.push(3);
pq.push(2);
pq.top();  // 3

---

4. イテレータ

4.1 イテレータの概念

イテレータは一般化されたポインタです。コンテナの要素を順次アクセスする統一的な方法を提供します。

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

// イテレータを使った走査
for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
}

// C++11: auto
for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
}

// C++11: 範囲for
for (int x : vec) {
    std::cout << x << " ";
}

4.2 イテレータカテゴリ

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

+-------------------+
| Input Iterator    |  読み取り、前進のみ
+-------------------+
        ↓
+-------------------+
| Forward Iterator  |  複数回走査可能
+-------------------+
        ↓
+-------------------+
| Bidirectional     |  後退可能（--）
| Iterator          |
+-------------------+
        ↓
+-------------------+
| Random Access     |  任意位置アクセス（+n, [n]）
| Iterator          |
+-------------------+


// Input Iterator: istream_iterator
std::istream_iterator<int> in(std::cin);

// Forward Iterator: forward_list::iterator
std::forward_list<int> fl;
auto it = fl.begin();  // ++のみ

// Bidirectional Iterator: list::iterator
std::list<int> lst;
auto it = lst.begin();
++it;  // OK
--it;  // OK

// Random Access Iterator: vector::iterator
std::vector<int> vec;
auto it = vec.begin();
it += 5;     // OK
it[3];       // OK
it - vec.begin();  // 距離

4.3 イテレータの無効化

コンテナの操作によってイテレータが無効になることがあります：

std::vector<int> vec = {1, 2, 3};
auto it = vec.begin();

vec.push_back(4);  // 再割り当てが発生する可能性
// itは無効になっている可能性がある！

// 安全なパターン
for (auto it = vec.begin(); it != vec.end(); ) {
    if (*it == 2) {
        it = vec.erase(it);  // eraseは次の有効なイテレータを返す
    } else {
        ++it;
    }
}

---

5. アルゴリズム

5.1 非変更アルゴリズム

コンテナを変更しないアルゴリズム：

#include <algorithm>

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

// find: 要素の検索
auto it = std::find(vec.begin(), vec.end(), 3);
if (it != vec.end()) {
    std::cout << "Found: " << *it << std::endl;
}

// count: 要素のカウント
int cnt = std::count(vec.begin(), vec.end(), 3);

// find_if: 条件を満たす要素の検索
auto it = std::find_if(vec.begin(), vec.end(),
    [](int x) { return x > 3; });

// all_of, any_of, none_of (C++11)
bool allPositive = std::all_of(vec.begin(), vec.end(),
    [](int x) { return x > 0; });

5.2 変更アルゴリズム

コンテナを変更するアルゴリズム：

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

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

// reverse: 反転
std::reverse(vec.begin(), vec.end());
// {9, 8, 5, 2, 1}

// transform: 変換
std::transform(vec.begin(), vec.end(), vec.begin(),
    [](int x) { return x * 2; });

// remove: 削除（実際には移動）
auto newEnd = std::remove(vec.begin(), vec.end(), 2);
vec.erase(newEnd, vec.end());  // 実際に削除

// unique: 連続する重複を削除
std::sort(vec.begin(), vec.end());
auto newEnd = std::unique(vec.begin(), vec.end());
vec.erase(newEnd, vec.end());

5.3 数値アルゴリズム

#include <numeric>

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

// accumulate: 累積
int sum = std::accumulate(vec.begin(), vec.end(), 0);
// 15

// min_element, max_element
auto minIt = std::min_element(vec.begin(), vec.end());
auto maxIt = std::max_element(vec.begin(), vec.end());

---

6. 42課題での使用ポイント

6.1 ex00: easyfind

template <typename T>
typename T::iterator easyfind(T& container, int value) {
    typename T::iterator it = std::find(container.begin(), container.end(), value);
    if (it == container.end()) {
        throw std::exception();
    }
    return it;
}

6.2 ex01: Span

class Span {
private:
    std::vector<int> _numbers;
    unsigned int _capacity;

public:
    Span(unsigned int n);
    void addNumber(int number);

    template <typename Iterator>
    void addNumbers(Iterator begin, Iterator end);

    int shortestSpan() const;
    int longestSpan() const;
};

6.3 ex02: MutantStack

template <typename T>
class MutantStack : public std::stack<T> {
public:
    typedef typename std::stack<T>::container_type::iterator iterator;

    iterator begin() { return this->c.begin(); }
    iterator end() { return this->c.end(); }
};

---

7. STLの制限（42課題）

7.1 許可されるコンテナ

42課題では、一般的に以下が許可されています：

  • std::vector
  • std::list
  • std::deque
  • std::stack
  • std::queue
  • std::map
  • std::set

    • 7.2 禁止されることが多いもの

  • std::array（C++11）
  • unordered_*（C++11）
  • std::string::find()などのメンバ関数

    • ---

    まとめ

    本章で学んだこと：

  • STLの歴史: Stepanovとジェネリックプログラミング
  • 設計思想: コンテナ、イテレータ、アルゴリズムの分離
  • コンテナ: シーケンス、連想、アダプタ
  • イテレータ: カテゴリと操作
  • アルゴリズム: 非変更、変更、数値

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

Next →
実装ガイド