４日目

テンプレート

汎用な関数とクラスを作成することができます．データ型ごとに専用のプログラムコードを書かなくても，１つの関数のプログラムコードで様々なデータ型に対応することができます．プログラミングによる記述ミスを少なくでき，手間も減らす事ができます．

汎用関数

様々なデータ型に適用できる汎用操作を定義する関数の事です．関数の実行時に実際に処理するデータ型に対して，適切なプログラムコードがコンパイラによって自動的に生成されます．

汎用関数の定義の基本形

template <class typeName>
returnType funcName(parameter list) {
    // 関数本体
}

汎用関数の呼び出しの基本形

funcName<typeName>(parameters);

絶対値を求める関数の汎用化

#include <iostream>

/**
 * int型の入力の絶対値を返す
 * @param v 入力
 * @return |v|
 */
int absolute_int(int v) {
    return (v >= 0) ? v : -v;
}

/**
 * double型の入力の絶対値を返す
 * @param v 入力
 * @return |v|
 */
double absolute_double(double v) {
    return (v >= 0) ? v : -v;
}

/**
 * 任意の型の入力の絶対値を返す
 * @param v 入力
 * @return |v|
 */
template<class T>
T absolute(T v) {
    return (v >= 0) ? v : -v;
}

int main(int argc, char **argv) {
    int v_i = -9;
    double v_d = -9.5;

    std::cout << absolute_int(v_i) << std::endl; // 9を出力
    std::cout << absolute_double(v_d) << std::endl; // 9.5を出力
    std::cout << absolute<int>(v_i) << std::endl; // 9を出力
    std::cout << absolute<double>(v_d) << std::endl; // 9.5を出力
    std::cout << absolute(v_i) << std::endl; // 9を出力 (型名省略可能)
    std::cout << absolute(v_d) << std::endl; // 9.5を出力 (型名省略可能)

    return 0;
}

テンプレートを使わない場合，同じ処理を行うにも関わらず，absolute_intやabsolute_doubleのようにデータ型毎に異なる関数を用意しなければなりません．このような場合，タイプミスにより予期せぬ誤りを引き起こしたり，仕様の変更に対して労力が必要であり，変更ミスのリスクが伴います．テンプレートを用いることで，これらを１つのabsoluteという関数にまとめることができ，このようなリスクをある程度回避できます．
また，39行目のabsoluteは仮引数にint型の変数v_iを渡しているので，int型に対応した関数absoluteが自動的に生成されます．同様に40行目のabsoluteは仮引数にdouble型の変数v_dを渡しているので，double型に対応した関数absoluteが自動的に生成されます．

汎用関数の呼び出しの省略形

funcName(parameters);

引数などから型が推測可能な場合はtype_name（型名）を省略することができ，通常の関数と同じように記述できます．この場合，コンパイラが型を推測し，自動的に適切な型の関数を生成してくれます．

汎用クラス

様々なデータ型に適用できる汎用操作を定義するクラスの事です．クラスのインスタンス化時に実際にインスタンス化するデータ型に対して，適切なプログラムコードがコンパイラによって自動的に生成されます．

汎用クラスの定義の基本形

template <class typeName>
class ClassName {
    // クラスの中身
};

汎用クラスの呼び出しの基本形

ClassName<typeName> object;

スタッククラス

#include <iostream>
#include <cstdlib>

template<class X>
class Stack {
private:
    X *data;
    int pos;
    int max;
public:

    /**
     * @brief コンストラクタ
     * @param size スタックサイズ
     */
    Stack(int size = 10) {
        data = new X[size];
        max = size;
        pos = 0;
    }

    /**
     * @brief デストラクタ
     */
    ~Stack() {
        delete data;
    }

    /**
     * @brief スタックの先頭にオブジェクトを入れる
     * @param v スタックに入れるオブジェクト
     */
    void push(X v) {
        if (pos >= max) {
            std::cerr << "stack full\n";
            exit(1);
        }
        data[pos++] = v;
    }

    /**
     * @breif スタックの先頭のオブジェクトを削除し，そのオブジェクトを返す
     * @return スタックの先頭のオブジェクト
     */
    X pop() {
        if (pos <= 0) {
            std::cerr << "stack empty\n";
            exit(1);
        }
        return data[--pos];
    }

    /**
     * @brief スタックが空かどうかを判断
     * @retval true スタックが空
     * @retval false スタックが空でない
     */
    bool empty() const {
        return pos == 0;
    }

    /**
     * @brief スタックがいっぱいかどうかを判断
     * @retval true スタックがいっぱい
     * @retval false スタックがいっぱいでない
     */
    bool full() const {
        return pos == max;
    }

    /**
     * @brief スタックの先頭にあるオブジェクトを取り出す．この時，オブジェクトはスタックから削除されない
     * @return スタックの先頭のオブジェクト
     */
    X peek() const {
        // ここを実装せよ
    }

    /**
     * @brief このスタックにあるオブジェクトの位置を1から始まるインデックスで返す．オブジェクトがスタック内にある場合，スタックの先頭からもっとも近いオブジェクトの位置までの距離を返す．スタックの1番上は距離1とする．
     * @param v 目的のオブジェクト
     * @return オブジェクトの位置を表す1から始まるスタックの先頭からのインデックス．オブジェクトが見つからない場合は-1
     */
    int search(X v) {
        // ここを実装せよ
    }
};

int main(int argc, char** argv) {
    Stack<int> i_stack;
    Stack<double> d_stack;

    i_stack.push(3);
    i_stack.push(1);
    i_stack.push(4);

    d_stack.push(2.5);
    d_stack.push(7.2);

    std::cout << "i_stack" << std::endl;
    while (!i_stack.empty()) {
        std::cout << i_stack.pop() << std::endl;
    }

    std::cout << "d_stack" << std::endl;
    while (!d_stack.empty()) {
        std::cout << d_stack.pop() << std::endl;
    }

    i_stack.push(3);
    i_stack.push(1);
    i_stack.push(4);

    std::cout << "top of stack = " << i_stack.peek() << std::endl;
    std::cout << "distance from top of stack = " << i_stack.search(1)
            << std::endl;
    std::cout << "distance from top of stack = " << i_stack.search(4)
            << std::endl;
    std::cout << "distance from top of stack = " << i_stack.search(3)
            << std::endl;
    std::cout << "distance from top of stack = " << i_stack.search(2)
            << std::endl;

    return 0;
}

出力例

i_stack
4
1
3
d_stack
7.2
2.5
top of stack = 4
distance from top of stack = 2
distance from top of stack = 1
distance from top of stack = 3
distance from top of stack = -1

スタッククラスの未実装の2つのメンバ関数を実装しましょう．

Standard Template Library (STL)

STL は，C++言語のテンプレート機能を利用して実装されたC++言語の標準的なライブラリです．その中には，プログラムを作成する上でよく利用されるリストやベクトル（可変長配列）などの便利なクラスや関数がテンプレートで実装されています．これらはC++言語の機能をフルに使用して実装されているため，初心者には少々分かりにくくなっているが，使いこなせば非常に有用なライブラリとなっています． STLの実現方法は非常に高度で複雑ですが，その目指すところは単純で，ソフトウェアをコンテナ，アルゴリズム，イテレータ（反復子）といった構成要素に分解し，それらを自由に組み合わせられる汎用部品にしようというものです．ここではSTLの中心的な存在である以下の３つの要素について説明します．

コンテナ
アルゴリズム
イテレータ

コンテナ

コンテナは他のオブジェクトを格納しておく入れ物の事です．最も馴染み深い例は「配列」でしょう．「配列」はintやdoubleといった基本データ型や，構造体データなどを格納することができ，ランダムアクセス可能な（a[i]のようにインデックスで参照する要素を指定可能な）コンテナです． STLにはいろいろなコンテナクラスが用意されていますが，ここではその中からよく利用されるベクトル，リスト，マップについて説明します．

ベクトル

ベクトルとは可変長配列のことです． (可変長配列とは，必要に応じてサイズを変更できる配列です．)

vectorの使用例

#include <iostream>
#include <vector> // vectorを使用する場合には必ずincludeする必要がある

/**
 * @brief ベクトル表示関数
 * @param vec 表示するベクトル
 */
template <class X>
void print_vector(std::vector<X> vec) {
    std::cout << "size=" << vec.size() << std::endl; // サイズを表示
    for (int i = 0; i < vec.size(); i++) {
        std::cout << "v[" << i << "]=" << vec[i] << std::endl;
    }
    std::cout << std::endl;
}

/**
 * @brief int型のvectorのテスト関数
 */
void test_vector_int() {
    std::vector<int> vi(3); // int型ベクトル (サイズ3)

    for (int i = 0; i < vi.size(); i++) { // sizeで要素数にアクセスできる
        vi[i] = i + 1; // 配列のようにアクセスできる
    }

    // ベクトルの内容表示
    std::cout << "=== phase 1 (int) ===" << std::endl;
    print_vector(vi);

    // viの末尾に追加 (サイズが増加)
    vi.push_back(125);

    // ベクトルの内容表示
    std::cout << "=== phase 2 (int) ===" << std::endl;
    print_vector(vi);

    // ベクトルのサイズを 2増やす
    vi.resize(vi.size() + 2);
    for (int i = 0; i < vi.size(); i++) {
        vi[i] = (i + 1) * 3;
    }

    // ベクトルの内容表示
    std::cout << "=== phase 3 (int) ===" << std::endl;
    print_vector(vi);
}

/**
 * @brief double型のvectorのテスト関数
 */
void test_vector_double() {
    std::vector<double> vd(3); // double型ベクトル (サイズ3)

    for (int i = 0; i < 3; i++) {
        vd[i] = (i + 1) * 0.1;
    }

    // ベクトルの内容表示
    std::cout << "=== phase 1 (double) ===" << std::endl;
    print_vector(vd);

    // vdの末尾に追加 (サイズが増加)
    vd.push_back(1.25);

    // ベクトルの内容表示
    std::cout << "=== phase 2 (double) ===" << std::endl;
    print_vector(vd);

    // ベクトルのサイズを 2増やす
    vd.resize(vd.size() + 2);
    for (int i = 0; i < vd.size(); i++) {
        vd[i] = (i + 1)*0.3;
    }
    // ベクトルの内容表示
    std::cout << "=== phase 3 (double) ===" << std::endl;
    print_vector(vd);
}

int main(int argc, char **argv) {
    test_vector_int();
    test_vector_double();

    return 0;
}

出力例

=== phase 1 (int) ===
size=3
v[0]=1
v[1]=2
v[2]=3

=== phase 2 (int) ===
size=4
v[0]=1
v[1]=2
v[2]=3
v[3]=125

=== phase 3 (int) ===
size=6
v[0]=3
v[1]=6
v[2]=9
v[3]=12
v[4]=15
v[5]=18

=== phase 1 (double) ===
size=3
v[0]=0.1
v[1]=0.2
v[2]=0.3

=== phase 2 (double) ===
size=4
v[0]=0.1
v[1]=0.2
v[2]=0.3
v[3]=1.25

=== phase 3 (double) ===
size=6
v[0]=0.3
v[1]=0.6
v[2]=0.9
v[3]=1.2
v[4]=1.5
v[5]=1.8

（線形）リスト

双方向の(線形)リストです．リストであるためランダムアクセスはできず，シーケンシャル(順次)にしかアクセスができません．また，双方向であるため，前方にも後方にもアクセスができるようになっています．

listの使用例

#include <iostream>
#include <list> // listを利用するためには必ずincludeする必要がある

const int MaxNameLen = 20;

/**
 * @class Student
 * @brief 生徒情報クラス
 */
class Student {
private:
    /** 生徒名 */
    char name[MaxNameLen];
    /** 点数 */
    int point;
public:

    /**
     * @brief 生徒名の設定
     * @param n 生徒名
     */
    void setName(const char *n) {
        std::strncpy(name, n, MaxNameLen);
    }

    /**
     * @brief 生徒名の取得
     * @return 生徒名
     */
    char *getName() {
        return name;
    }

    /**
     * @brief 点数の設定
     * @param po 点数
     */
    void setPoint(int po) {
        point = po;
    }

    /**
     * @brief 点数の取得
     * @return 点数
     */
    int getPoint() const {
        return point;
    }

    /**
     * @brief 氏名と点数を表示
     */
    void print() {
        std::cout << "name=" << name << " point=" << point << std::endl;
    }
};

/**
 * 登録生徒の情報と平均点を表示
 * @param stlst 登録生徒リスト
 */
void print_list(std::list<Student> stlst) {
    int total_sum = 0;

    std::cout << "size=" << stlst.size() << std::endl;
    for (std::list<Student>::iterator i = stlst.begin(); i != stlst.end(); i++) { // iteratorを使ってlistにアクセス
        i->print();
        total_sum += i->getPoint();
    }
    std::cout << "average=" << ((double) total_sum / stlst.size()) << std::endl;
}

int main(int argc, char** argv) {
    std::list<Student> stlst; // Studentクラスのリスト (サイズ 0)
    Student st;

    // リストに追加 (サイズが増加)
    st.setName("Hamm");
    st.setPoint(7);
    stlst.push_back(st);
    st.setName("Slink");
    st.setPoint(4);
    stlst.push_back(st);
    st.setName("Potato");
    st.setPoint(6);
    stlst.push_back(st);

    // リストの内容表示
    std::cout << "=== phase 1 ===\n";
    print_list(stlst);

    // リストに追加 (サイズが増加)
    st.setName("Woody");
    st.setPoint(8);
    stlst.push_back(st);
    st.setName("Sarge");
    st.setPoint(9);
    stlst.push_back(st);

    // リストの内容表示
    std::cout << "=== phase 2 ===\n";
    print_list(stlst);

    return 0;
}

出力例

=== phase 1 ===
size=3
name=Hamm point=7
name=Slink point=4
name=Potato point=6
average=5.66667
=== phase 2 ===
size=5
name=Hamm point=7
name=Slink point=4
name=Potato point=6
name=Woody point=8
name=Sarge point=9
average=6.8

マップ

マップとはキー（key）と値（value）を対応付けるデータ構造を持つコンテナクラスです．（注：ここで説明するmapではあるキーに対しては一意となる値しか格納することができないようになっています．重複したキーを許す（つまり，同じキーに対して異なる複数の値を対応付ける）マップを使いたい場合はmultimapを使用する）

mapの使用例

#include <iostream>
#include <map> // mapを利用するためには必ずincludeする必要がある
#include <string> // stringを利用する

int main(int argc, char** argv) {
    std::map<std::string, int> symtab; // 文字列からintへのマップ
    std::map<std::string, int>::iterator i; // イテレータ

    // マップに登録
    symtab.insert(std::pair<std::string, int>("red", 1)); // "red"=>1を登録
    symtab.insert(std::pair<std::string, int>("green", 2)); // "green"=>2を登録
    symtab.insert(std::make_pair("blue", 4)); // "blue"=>4を登録 pair<>と同じ

    // マップの中身を表示
    std::cout << "=== map ===" << std::endl;
    for (i = symtab.begin(); i != symtab.end(); i++) { // iteratorを使ってlistにアクセス
        std::cout << i->first << "=" << i->second << std::endl;
    }

    // マップを使って検索
    std::cout << "=== search ===" << std::endl;
    i = symtab.find("red"); // 指定したキーを指す反復子を返す
    std::cout << i->first << "=" << i->second << std::endl;
    i = symtab.find("blue");
    std::cout << i->first << "=" << i->second << std::endl;

    return 0;
}

出力例

=== map ===
blue=4
green=2
red=1
=== search ===
red=1
blue=4

アルゴリズム

（STL での）アルゴリズムとは，（その言葉通りに）アルゴリズムを型に依存しない形で汎用化したものです．例えば，「ソートする」という作業はそれ自体はデータ構造に依存しないはずですが，実際にプログラムを作成する場合は，配列には配列用のソート関数，リストにはリスト用のソート関数を記述する必要があります．これを，配列やリストなどのデータ構造（つまり型）に依存しない形で実現したものを用意することで，どんな型にでも利用できるようにしたものが，ここでいう「アルゴリズム」です．

algorithmの使用例

#include <iostream>
#include <vector> // vectorを利用する
#include <algorithm> // algorithmを利用するためには必ずincludeする必要がある

int main(int argc, char** argv) {
    std::vector<int> vi; // int型ベクトル (サイズ0)
    std::vector<int>::iterator iter; // イテレータ

    for (int i = 0; i < 10; i++) {
        vi.push_back((i * 7 + 3) % 11); // 要素を1個追加
    }

    // ソート前のベクトルの内容表示
    std::cout << "=== before sort ===" << std::endl;
    for (iter = vi.begin(); iter != vi.end(); iter++) {
        std::cout << *iter << std::endl;
    }
    std::cout << std::endl;

    // ベクトルの内容をソート(処理範囲を反復子によって指定)
    std::sort(vi.begin(), vi.end());

    // ソート後のベクトルの内容表示
    std::cout << "=== after sort ===" << std::endl;
    for (iter = vi.begin(); iter != vi.end(); iter++) {
        std::cout << *iter << std::endl;
    }
    std::cout << std::endl;

    // ベクトルの内容を反転(処理範囲を反復子によって指定)
    std::reverse(vi.begin(), vi.end());

    // 反転後のベクトルの内容表示
    std::cout << "=== after reverse ===" << std::endl;
    for (iter = vi.begin(); iter != vi.end(); iter++) {
        std::cout << *iter << std::endl;
    }
    std::cout << std::endl;

    return 0;
}

出力例

=== before sort ===
3
10
6
2
9
5
1
8
4
0

=== after sort ===
0
1
2
3
4
5
6
8
9
10

=== after reverse ===
10
9
8
6
5
4
3
2
1
0

イテレータ（反復子）

イテレータ(反復子) とは，コンテナに対しての操作のうち頻繁に利用される「順に参照する」という操作を汎用化したものです．例えば，以下のようなforループやリストを順に辿るコードはよく使用されるが，これらはデータ構造(型)に依存しています．

配列を端から順に参照する例

for (i = 0; i < N; i++) {
    process(a[i]);
}

リストを端から順に参照する例

for (p = base; p != NULL; p = p->next) {
    process(p->data);
}

しかし，本来これらは「先頭から最後尾まで要素を1つずつ参照する」という意味では同じものです．この「先頭から最後尾まで要素を1つずつ参照する」という操作を汎用化したものが，イテレータです．ここで「先頭から最後尾まで要素を1つずつ参照する」という操作を細かく分解してみると以下の4つの操作が出来ればよいことがわかります．

先頭位置の設定
次の要素への移動
要素の参照
終了位置の判定

イテレータでは上記の4操作を以下のようにして実現します．

先頭位置の設定 … begin()メソッドの値を設定
次の要素への移動 … インクリメント演算子 ++
要素の参照 … 間接演算子 *
終了位置の判定 … end()メソッドの結果との比較

以下のようにしてこの4つの操作を用いることで，要素を順次参照するという操作が実現できます．

イテレータを用いてコンテナに順にアクセスする例

for (iter = v.begin(); iter != v.end(); iter++) {
	process(*iter);
}

このforループにおいて，最初のiter = v.begin()により，先頭位置の設定を行なっています．次のiter != v.end()により，終了位置に到達したかどうかを判定しています． 3つ目のiter++により，次の要素への移動を行なっています．そして，最後にループボディにある*iterにより，要素の参照を行なっています． 4つの操作は各コンテナクラスによって実装は異なる（つまりvectorはvector，listはlistに応じた実装が必要）が，使う側の立場からすれば，中がどういう実装になっているかは気にする必要はありません．

iteratorの使用例

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

void test_vector() {
    std::vector<int> vi; // int型ベクトル (サイズ0)
    std::vector<int>::iterator iter; // イテレータ

    std::cout << "[vector]" << std::endl;

    for (int i = 0; i < 5; i++) {
        vi.push_back(i + 1); // 要素を1個追加
    }

    // ベクトルの内容表示
    std::cout << "=== phase 1 ===" << std::endl;
    for (iter = vi.begin(); iter != vi.end(); iter++) {
        std::cout << *iter << std::endl;
    }
    std::cout << std::endl;

    // ベクトルの内容変更
    for (iter = vi.begin(); iter != vi.end(); iter++)
        *iter += 1; // 要素の値を1増加

    // ベクトルの内容表示
    std::cout << "=== phase 2 ===" << std::endl;
    for (iter = vi.begin(); iter != vi.end(); iter++) {
        std::cout << *iter << std::endl;
    }
    std::cout << std::endl;
}

void test_list() {
    std::list<int> li; // int型リスト (サイズ0)
    std::list<int>::iterator iter; // イテレータ

    std::cout << "[list]" << std::endl;

    for (int i = 0; i < 5; i++) {
        li.push_back(i + 1); // 要素を1個追加
    }

    // リストの内容表示
    std::cout << "=== phase 1 ===" << std::endl;
    for (iter = li.begin(); iter != li.end(); iter++) {
        std::cout << *iter << std::endl;
    }
    std::cout << std::endl;

    // リストの内容変更
    for (iter = li.begin(); iter != li.end(); iter++) {
        *iter *= 2; // 要素の値を2倍
    }

    // リストの内容表示
    std::cout << "=== phase 2 ===" << std::endl;
    for (iter = li.begin(); iter != li.end(); iter++) {
        std::cout << *iter << std::endl;
    }
    std::cout << std::endl;
}

int main(int argc, char **argv) {
    test_vector(); // ベクトル版
    test_list(); // リスト版

    return 0;
}

出力例

[vector]
=== phase 1 ===
1
2
3
4
5

=== phase 2 ===
2
3
4
5
6

[list]
=== phase 1 ===
1
2
3
4
5

=== phase 2 ===
2
4
6
8
10

Stringクラス

C++言語での文字列の扱いは，２種類の方法があり，１つは，C言語と同様に'\0'(ナル文字)で終端する文字型の配列として扱う方法であり，もう１つは，ここで説明するstringクラスを用いる方法です． stringクラスは，正確には，basic_stringという名のテンプレートクラスを，8ビット文字列を扱うようにインスタンス化したクラスです．日本語などのワイド文字（２バイト以上で表現される文字）での扱いを必要とする文字列については，wstringクラスを用いましょう． C++言語で文字列を扱う際は，C言語と同様の方式を用いてもよいですが，このstringクラスを使って扱う方がいろいろと便利なことが多いです．例えば，C言語の文字列では常に文字型配列の長さに注意を払わなければなりませんが，stringクラスでは格納する文字列の長さに応じて必要な記憶域の大きさを自動的に調整してくれます．また，文字列の最後に'\0'を付け忘れてプログラムが思った通りに動かないという事態も避けることができます．さらに，C言語の文字列では文字列のコピーや連結，内容の比較といった操作は文字列操作ライブラリを呼び出して行なっていましたが，stringクラスでは演算子を用いるだけで簡単に実現できます．

stringの使用例

string s("cat"); // 初期値付き文字列
string s2; // 空の文字列

s2 = "dog"; // 文字列の代入

s = s2; // 文字列のコピー
s2 = s1 + " and cat"; // 文字列の連結
s2 += " and mouse"; // 文字列の連結(追加)

if (s == s2) { // 文字列の比較
    cout << "equal" << endl;
}