概要

配列のように複数の要素の入れ物として機能するクラスをコンテナとよびます。コンテナクラスには vector、list、queue/stack などがあります。それぞれのコンテナクラスはクラステンプレートとして提供されており、したがってヘッダファイルを include するだけで使用できます。ヘッダファイルにはコンテナクラスのクラステンプレートだけでなく、そのコンテナのイテレータクラスのクラステンプレートも定義されています。イテレータはコンテナクラスの要素へのポインタとして振る舞うクラスです。

イテレータクラスを利用すると、配列の要素をポインタで扱うのと同じ文法でコンテナクラスの要素を扱うことができます。これは、関数テンプレートを利用することで各種イテレータクラスとポインタを区別することなく汎用的に扱えることを意味しています。これら汎用的な処理はアルゴリズムとよばれており algorithm ヘッダファイルに多数の関数テンプレートが定義されています。

コンテナクラスのクラステンプレートやアルゴリズムの関数テンプレートを総称して標準テンプレートライブラリ (standard template library; STL) とよびます。

イテレータクラスの中にはポインタの振舞のうち一部しか模擬できていないものがあります。ポインタの振舞を完全に模擬できているものを特にランダムアクセスイテレータとよびます。STLで定義されているアルゴリズムの中にはランダムアクセスイテレータを前提として作られているものがあります。したがって、アルゴリズムによってはそれを利用できないコンテナクラスのイテレータも存在しています。例えば vector クラスのイテレータはランダムアクセスイテレータですが list クラスのイテレータはそうではありません。そのため sort アルゴリズムは vector では利用できますが list では利用できません。

主要アルゴリズムのサンプルコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool MyPred(int val) {
    return val == 1;
}

int main() {
    int arr[4];
    vector<int> vec(4);

    // 要素の初期化
    fill_n(arr, 4, 1);
    fill(arr, arr + 4, 1); // としても同じ
    fill_n(vec.begin(), 4, -1);
    fill(vec.begin(), vec.end(), -1); // としても同じ

    // 要素のコピー
    copy(arr, arr + 4, vec.begin()); // 指定範囲のコピーを指定位置から開始
    copy_backward(arr, arr + 4, vec.end()); // としても同じ
    copy(vec.begin(), vec.end(), arr); // ベクトルから配列へのコピー
    copy_backward(vec.begin(), vec.end(), arr + 4); // としても同じ

    // 並べ替え (list クラスでは使用不可のためメンバ関数 lst.sort() で代用)
    sort(arr, arr + 4); // 既定値は昇順
    sort(vec.begin(), vec.end());
    sort(arr, arr + 4, less<int>()); // 明示的な昇順
    sort(vec.begin(), vec.end(), less<int>());

    sort(arr, arr + 4, greater<int>()); // 降順
    sort(vec.begin(), vec.end(), greater<int>());

    stable_sort(arr, arr + 4); // 安定ソート (同じ値の要素の前後関係が並べ替え前後で保存されることを保証)

    // 検索
    vector<int>::iterator pos = find(vec.begin(), vec.end(), 1); // 値 1 を検索
    // int* pos = find(arr, arr + 4, 1);

    if ( pos != vec.end() ) { // 検索結果がなければ終端イテレータが返される
    // if ( pos != arr + 4 ) {
        cout << "found: " << *pos << endl; // 検索結果があればその要素へのイテレータが返される
    }

    pos = find_if(vec.begin(), vec.end(), MyPred); // MyPred が true を返す要素を検索
    if ( pos != vec.end() ) {
        cout << "found: " << *pos << endl;
    }


    // 二分探索
    cout << boolalpha;

    sort(arr, arr + 4); // 事前ソートをしておかないと正しい結果が得られません
    cout << binary_search(arr, arr + 4, 1) << endl; //=> true (真偽値を返す)

    sort(vec.begin(), vec.end());
    cout << binary_search(vec.begin(), vec.end(), 1) << endl; //=> true

    sort(arr, arr + 4, greater<int>()); // 特殊なソートの場合は ↓ の引数でその特殊さを渡します
    cout << binary_search(arr, arr + 4, 1, greater<int>()) << endl; //=> true


    // 反転
    reverse(arr, arr + 4);
    reverse(vec.begin(), vec.end());

    return 0;
}