プログラミング実習 III (クラス 4)
- [B10] C++ (2) 「標準ライブラリ STL」

プログラミング実習 III (クラス 4)

[B10] C++ (2) 「標準ライブラリ STL」

今回の実習では、 C++ の強力な武器である「STL (Standard Template Library)」を学ぶ。これまでの C 言語によるプログラミングでは、配列のメモリ管理やリスト構造のポインタ操作など、データ構造の「実装」そのものに多くの労力を割いてきた。

しかし、 C++ の STL を利用することで、これらの低レイヤの管理から解放され、より本質的な「アルゴリズム」や「アプリケーションのロジック」に集中できるようになる。

今回の課題に着手する前に、以下の要点を整理し、それぞれのツールの特性を理解しておこう。

今回の課題のねらい

何を学ぶか
- C++ 標準ライブラの一部である (STL) が提供する、主要なクラス string, vector, list, map の基本的な使用法。
- コンテナ（データを格納する器）とアルゴリズム（検索やソートなどの処理）を結びつける「イテレータ (iterator)」の概念。
- データ構造ごとの特性（計算量やアクセスの可否）に応じた適切な使い分け。
何のために学ぶか
- メモリ管理（確保・解放）や基本的なデータ構造の実装コストを削減し、生産性と安全性を高めるられるようになるため。
- C++ における現代的なプログラミングスタイル（抽象化されたデータ操作）を習得するため。
どのように学ぶか
- 電話帳や成績管理といった具体的なデータ操作を通じて、各コンテナクラスの挙動を確認する。
- 従来の配列操作と STL を用いた操作を比較し、その利便性と注意点を体感する。

今回の課題の到達目標

std::string による文字列操作
- C 言語の char 配列と比較し、代入・連結・比較・検索が直感的に行えることを理解し、実装できるようになる。
STL コンテナの適切な選択と操作
- 可変長配列が必要な場合は vector、頻繁な挿入削除が必要な場合は list、キーによる検索が必要な場合は map を選択できるようになる。
- 各コンテナに対して、要素の追加（ push_back 等）、削除（ erase 等）、走査（イテレータ）ができるようになる。
共通アルゴリズムの利用
- find や sort などのアルゴリズムが、異なるコンテナに対して統一的なインタフェースで適用できることを理解し、利用できるようになる。
- 独自の比較関数（関数オブジェクト）を定義し、任意のルールでソートができるようになる。

重要な C++ の概念

今回の課題の範囲で特に重要な概念を説明しておこう。

テンプレート (Template)

テンプレート利用の例:

#include <iostream>
#include <vector>

template <typename T>
T add(T a, T b) {
  return a + b;
}

int main() {
  std::cout << add<int>(3, 5) << std::endl;  // 8
  std::cout << add<double>(1.2, 3.4) << std::endl;  // 4.6

  std::vector<int> v = {1, 2, 3};
  std::cout << v.size() << std::endl;  // 3
}

概念: データ型に依存しない汎用的なクラスや関数を作る仕組み。 vector<int> や vector<string> のように山括弧内に型を指定することで、特定の型専用のクラスをコンパイラが生成する。

重要性: 型の安全性 (Type Safety) を保ちつつ、コードの再利用性を高める。 C 言語の void* を用いた汎用化とは異なり、コンパイル時に型チェックが行われるため安全である。

C 言語では? : C 言語では、 (1) 型ごとに関数を別々に実装する (コード重複)、 (2) void * とサイズ引数を用いた汎用関数 (例: qsort)、 (3) C のプリプロセッサを使ったマクロ展開、などの方法で書く必要があった (C++ 言語では、C 言語から大幅に使い勝手が向上している)。

コンテナ (Container)

コンテナ利用の例:

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>

int main() {
  // vector: 可変長配列（末尾追加が容易）
  std::vector<int> v = {1, 2, 3};
  v.push_back(4);
  std::cout << "vector size = " << v.size() << std::endl;

  // list: 連結リスト（途中の挿入・削除が容易）
  std::list<std::string> lst = {"Alice", "Bob"};
  lst.push_front("Zoe");
  lst.remove("Bob");  // 値に一致する要素を削除
  std::cout << "list size = " << lst.size() << std::endl;

  // map: 連想配列（キー→値）
  std::map<std::string, int> score;
  score["Alice"] = 90;  // [] は存在しないキーなら要素を生成する点に注意
  score["Bob"] = 75;

  // 走査（イテレータ）
  for (std::map<std::string, int>::iterator it = score.begin(); it != score.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
  }

  return 0;
}

概念: オブジェクトを格納するデータ構造の総称。 vector （可変長配列）、 list （連結リスト）、 map （連想配列）などが含まれる。

重要性: メモリ管理が自動化されており、領域の拡張や縮小、再配置 (reallocation) が隠蔽されている。ユーザはサイズを意識せずにデータを追加できる。コンテナを用いることで、データ構造の実装（メモリ確保・解放、境界管理、ポインタ操作など）を自前で書く必要がなくなり、要素の追加・削除・検索といった操作を安全かつ簡潔に記述できるようになる。また、コンテナが提供する共通インタフェース（ begin(), end() など）により、 sort や find といったアルゴリズムを「データ構造の種類に依存せず」再利用できる（実装と利用の分離）。

C 言語では? : 「コンテナ」という抽象化は基本的に用意されていないため、用途に応じたデータ構造を自分で実装する必要があった。固定長配列や可変長配列を利用するか、連結リストや連想配列を自分で実装するか外部のライブラリを使う必要があった。

イテレータ (Iterator / 反復子)

イテレータ利用の例:

#include <iostream>
#include <vector>
#include <list>

int main() {
  // vector の走査（ランダムアクセス可能）
  std::vector<int> v = {10, 20, 30};

  // 典型例: begin() から end() まで ++ で進め、* で要素参照
  for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << std::endl;
  }

  // list の走査（ランダムアクセス不可だが、同じ書き方で走査できる）
  std::list<int> lst = {1, 2, 3};
  for (std::list<int>::iterator it = lst.begin(); it != lst.end(); ++it) {
    std::cout << *it << std::endl;
  }

  // const イテレータ（読み取り専用）
  const std::vector<int> cv = {100, 200};
  for (std::vector<int>::const_iterator it = cv.begin(); it != cv.end(); ++it) {
    std::cout << *it << std::endl;
  }

  return 0;
}

概念: コンテナ内の要素を指し示し、移動するためのオブジェクト。「ポインタを抽象化したもの」と捉えるとよい。

重要性: 内部構造が異なるコンテナに対しても、 begin(), end(), ++, * といった共通操作を提供する。これにより、アルゴリズムをコンテナの実装から分離できる。

C 言語では? : C 言語では汎用のコンテナが存在しないため、 C 言語はイテレータに存在するものを持っていない。配列に対してはポインタ（ int * など）をインクリメントして走査するのが最も近い。ただし、これは「連続メモリである」という前提に強く依存する。このため、連結リスト等の非連続なデータ構造では、 struct に next ポインタを持たせて辿るなど、データ構造ごとに走査方法（アクセス手段）を個別に実装する必要があった。

関数オブジェクト (Function Object)

関数オブジェクト利用の例:

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

// 関数オブジェクト（比較器）: 文字列長で昇順ソート
struct ByLength {
  bool operator()(const std::string& a, const std::string& b) const {
    return a.size() < b.size();
  }
};

// 関数オブジェクト（状態を持つ述語）: 閾値以上かどうか
class AtLeast {
 public:
  explicit AtLeast(int threshold) : threshold_(threshold) {}
  bool operator()(int x) const { return x >= threshold_; }

 private:
  int threshold_;
};

int main() {
  // sort に比較規則を渡す（関数オブジェクト）
  std::vector<std::string> words = {"network", "AI", "STL", "template"};
  std::sort(words.begin(), words.end(), ByLength());
  for (std::vector<std::string>::const_iterator it = words.begin(); it != words.end(); ++it) {
    std::cout << *it << std::endl;
  }

  // find_if に「状態を持つ」条件を渡す（threshold=10 を埋め込む）
  std::vector<int> v = {3, 7, 10, 12};
  std::vector<int>::iterator it = std::find_if(v.begin(), v.end(), AtLeast(10));
  if (it != v.end()) {
    std::cout << "first >= 10: " << *it << std::endl;
  }

  return 0;
}

概念: 関数のように振る舞うオブジェクト（ operator() をオーバーロードしたクラス）。例えば、 sort などに比較規則として渡すことで、関数ポインタより柔軟な処理が可能となる。

重要性: 関数オブジェクトは「状態 (state) を持てる関数」である点が重要である。関数ポインタと異なり、メンバ変数としてパラメータ（閾値、重み、辞書、正規化規則など）を保持できるため、同じアルゴリズム呼び出しでも「設定を埋め込んだ振る舞い」を安全に渡せる。

C 言語では? : C 言語において、アルゴリズムに「処理（振る舞い）」を渡したい場合は、関数ポインタ（ function pointer ）を渡すという方法があった。

STL で注意すべきポイント

STL は非常に便利であるが、その裏側で何が起きているかを理解していないと、非効率なコードやバグの原因となる。

vector の再配置とポインタ

vector は容量不足時に新たな領域を確保し、全要素をコピーする再配置を行う。この際、要素を指していたポインタやイテレータは無効となる。要素へのポインタ保持は避ける。
map の [] 演算子の副作用

m[key] は、 key が存在しない場合に自動的に新要素を生成（デフォルト初期化）する。存在確認や参照のみの場合は find() を使用すること。
list における要素削除

ループ中に erase を行うと、削除対象のイテレータは無効になる。 erase の戻り値（次の有効なイテレータ）を利用するなどの工夫が必要である。
計算量（オーダー）の意識

vector や deque のランダムアクセスは O(1)、 list は O(n) である。用途に応じて最適なコンテナを選択する視点を持つこと。

Hiroyuki Ohsaki (ohsaki[atmark]lsnl.jp)