C++ジェネリックプログラミング入門


# はじめに
本記事は、STLなどで使用されているジェネリックプログラミングの入門記事である。[こちらの記事](https://isocpp.org/blog/2014/04/preferring-stl-algorithms)の内容をベースに、反復子やテンプレートなど、ジェネリックプログラミングを行うための基礎知識を追加した。
本記事の構成は、はじめにジェネリックプログラミングの概要を示し、続いてジェネリックプログラミングを行う際に必要となる反復子とテンプレートに関する基礎知識を紹介し、最後にマクロではなくテンプレートを推奨する理由について簡単に触れる、という構成になっている。

# 1. ジェネリックプログラミングとは
ジェネリックプログラミングとは、 **特定の型に依存しない実装をするプログラミングスタイル** のこと。[こちらの記事](https://isocpp.org/blog/2014/04/preferring-stl-algorithms)の ```sum``` 関数を例に、テンプレートを用いたジェネリックな関数を作成する手法を紹介する。

※ ```sum``` 関数はあくまで例。実際に ```std::vector``` の様なコンテナに格納された値の合計値を計算したい場合は、 ```std::accumulate``` を使うのが良いと思う。

出発点となる ```sum``` 関数は下記の様な実装をしている。

```sample.cpp
double sum(const std::vector<double> &vec) {
    double result = 0.0;
    for(const auto e : vec) {
        result += e;
    }   
    return result;
}
```

これは ```std::vector<double>``` という特定の型に依存しているため、要素の型をテンプレートパラメータに置き換え、 ```std::vector<int>``` などにも適用できる様に ```sum``` 関数を下記の様に書き直す。

```sample.cpp
template <class T>
T sum(const std::vector<T> &vec, T start) {
    for(const auto e : vec) {
        start += e;
    }
    return start;
}
```

これにより ```sum``` 関数は、任意の要素の型に対して適用できる様になったが、 ```std::vector``` という特定のコンテナに依存しているため、反復子を使って、 ```std::list``` などにも適用できる様に ```sum``` 関数を下記の様に書き直す。

```sample.cpp
template <class InputIterator, class T>
T sum(InputIterator first, InputIterator last, T start) {
    while(first != last) {
        start += *first++;
    }   
    return start;
}
```

これで、特定の型に依存しない ```sum``` 関数を実装をすることができた。
以上の手順をまとめると、

1. doubleなどの型をテンプレートパラメータに置き換える。
2. コンテナ要素へのアクセス方法を反復子に置き換える。

という手順を踏むことで、ジェネリックな関数を作ることができるのだが、そのためには反復子とテンプレートについての理解が必要となる。

# 2. 反復子基礎知識

## 2.1 反復子とは
反復子とは、ポインタに似たオブジェクトで、コンテナに格納されている要素にアクセスするのに使用される。STLにおいて反復子は、コンテナと汎用アルゴリズムの仲介役としての役割を担っており、そのため、コンテナごとに専用のアルゴリズムを用意する手間を省いてくれる。

## 2.2 反復子のカテゴリ
反復子は、 **入力反復子** 、 **出力反復子** 、 **前方向反復子** 、 **双方向反復子** 、 **ランダムアクセス反復子** の5つのカテゴリに分類できる。各反復子の特徴は下記の通り。

 * 入力反復子
   前方に移動しながら値を読むことができる反復子。インクリメント、比較、参照はずしが可能。

 * 出力反復子
   前方に移動しながら値を書き出すことができる反復子。インクリメント、参照はずしが可能。

 * 前方向反復子
   前方に移動しながら値を読み書きすることができる反復子。

 * 双方向反復子
   前方/後方へ移動しながら値を読み書きすることができる反復子。

 * ランダムアクセス反復子
   値の読み書きとランダムアクセスをすることができる反復子。

多くのアルゴリズムは入力反復子か前方向反復子の機能のみを使用するが、 ```std::sort()``` の様に、ランダムアクセス反復子の機能を必要とするものもある。従って、アルゴリズムを設計する際は、どの反復子の機能が必要なのかをしっかりと考える必要がある。

# 3. テンプレート基礎知識

## 3.1 テンプレートとは
テンプレートとは、 **C++の言語機能の一つで、型を差し替え可能なクラスや関数を作成するための仕組み** である。テンプレートを使うことで、型とコンテナとアルゴリズムを分離することができ、コードの再利用性を高めることができる。

## 3.2 テンプレートの種類
C++11のテンプレートには、

 * 関数テンプレート
 * クラステンプレート
 * メンバテンプレート
 * エイリアステンプレート

の4種類がある。
上記4種類のサンプルを紹介する。

### 3.2.1 関数テンプレート
例えば下記の様な関数が関数テンプレート。

```sample.cpp
template <class T>
T max(const T &x, const T &y) 
{
    return x < y ? y : x;
}
```
上記関数の意味を説明をすると、 ```template <class T>``` の部分が 「 ```T``` は何らかの型 」であることを示しており、 ```int``` や ```SomeUserDefinedType``` など、任意の型を指定することができる。この様に、関数の引数の型を明示せず、差し替え可能な型として定義できるものが関数テンプレートである。

ちなみに、冒頭で見た ```sum``` 関数も関数テンプレートである。

### 3.2.2 クラステンプレート
2次元座標を表すクラスをテンプレートを使って作成した、下記の様なクラスがクラステンプレート。

```sample.cpp
template <class T>
class Point
{
    private:
        T x_; 
        T y_; 
    public:
        Point(T x, T y) : x_(x), y_(y) {}

        Point(const Point &other) : x_(other.x_), y_(other.y_) {}

        // その他ごにょごにょ
};
```

### 3.2.3 メンバテンプレート
下記の様なテンプレート化されたメソッド ```get``` が、メンバーテンプレート。

```sample.cpp
template <class T>
class Point
{
    private:
        T x_;
        T y_;
    public:
        Point(T x, T y) : x_(x), y_(y) {}

        Point(const Point &other) : x_(other.x_), y_(other.y_) {}

        template <class U> void get(U &dst_x, U &dst_y) const
        {
            dst_x = this->x_;
            dst_y = this->y_;
        }

        // その他ごにょごにょ
};
```

### 3.2.4 エイリアステンプレート
下記の様に、テンプレートを使用して、型の別名を定義する機能。C++11から使用可能。

```sample.cpp
template <class T>
using Vec = std::vector<T>;

// 使用例
Vec<int> v; // std::vector<int> v; と同じ
```

テンプレートでない型についても、 ```using new_type_name = old_type_name``` の様にして、別名を定義することができる。

### 補足:関数テンプレートとクラステンプレートの型推論の違い
関数テンプレートの場合は与えた引数から型推論を行うが、クラステンプレートは型推論が行われない。つまり、先ほど示した ```max``` と ```Point```は、

```sample.cpp
int max_value1 = max(1, 2); 　　　// OK. max<int>と型推論される。
int max_value2 = max<int>(1, 2); // 明示的に指定してもOK.

Point pt(1, 2); 　　　// NG. Point<int>と型推論してくれない。
Point<int> pt(1, 2); // OK.
```

の様な動作をする。

### 補足:コンストラクタテンプレート
先ほどの例で示したクラステンプレート ```Point``` に対して、下記の様なことをした場合、コンパイルエラーとなる。

```sample.cpp
Point<int> int_pt(1, 2);
Point<long> long_pt = int_pt; // コンパイルエラー
```

上記コードの意図は、 ```int``` から ```long``` へは暗黙の型変換が働くのだから、 ```Point<int>``` から ```Point<long>``` への型変換も暗黙的に働くハズ...というものだが、 ```Point<int>``` と ```Point<long>``` は全くの別物なので暗黙の型変換は行われない。もしこの様な暗黙の変換を行いたいのであれば、下記の様にコンストラクタテンプレートを使う必要がある。

```sample.cpp
template <class T>
class Point
{
    private:
        T x_; 
        T y_; 

        // コンストラクタテンプレートのメンバ初期化子でotherのx_, y_へアクセスするのに必要
        template <class> friend class Point;
    public:
        Point(T x, T y) : x_(x), y_(y) {}

        // コンストラクタテンプレート
        template <class U> Point(const Point<U> &other) : x_(other.x_), y_(other.y_) {}

        // その他ごにょごにょ
};
```

### 補足:テンプレート引数に整数値を指定する
今まで紹介した例では、テンプレート引数に型のみを指定していたが、下記サンプルの様に、整数値を指定することもできる。

```sample.cpp
template <int N>
struct factorial
{
    static const int value = N == 0 ? N : N * factorial<N-1>::value;
};

template <>
struct factorial<0>
{
    static const int value = 1;
};

// 使用例
factorial<3>::value; // 6
```

```template<>``` の部分は **特殊化** と呼ばれるもので、引数 ```N``` が0の時は　```N == 0 ? N : N * factorial<N-1>::value``` とは別の処理( 今回は ```static const int value = 1;``` )を行いたい場合、それを明示的に指定するために使用する。

なお、上記 ```factorial<3>::value``` の値は(実行時ではなく)コンパイル時に計算できる。この様に、コンパイル時に様々な処理を行ってしまうテクニックを、 **テンプレートメタプログラミング** と言う。

### 補足:可変引数テンプレート
可変引数テンプレートとは、任意の数のテンプレート引数を受け取ることができるテンプレートを宣言できる機能のこと。受け取った任意の数のテンプレート引数を全て標準出力に出力するサンプルは下記の様になる。

```sample.cpp
// print_argsの再帰呼び出しの終端
void print_args()
{
    std::cout << std::endl;
}

template <class Head, class... Tail>
void print_args(Head head, Tail... tail)
{
    std::cout << head << " ";

    // 引数を一つずつ減らして再帰的にprint_argsを呼び出す
    print_args(tail...);
}

// 使用例
print_args(3, 'a', 1.5); // => 3 a 1.5
```

テンプレート引数の ```class... Tail``` の部分は、「0個以上のテンプレートパラメータの並び」を意味している。関数引数の ```Tail... tail``` も同じ意味。

## 4. マクロとテンプレート
例えば関数テンプレートの例で示した ```max``` 程度なら、マクロで良いじゃんって思うかもしれない。
しかしマクロには、

 * 型安全ではない
 * 型推論もできない
 * C++と文法が違う(引数を括弧でくくる必要があるなど)
 * マクロは単なるテキスト処理であり、言語機能ではない

などなど、多くの問題がある。そのためマクロではなく言語機能としてちゃんとサポートしよう...という流れになり、今のテンプレートができあがったのだそう。なのでC++を使うのであれば、マクロではなく、言語機能としてサポートされているテンプレートを使おう。

# 最後に
今回は

 * イテレータの基礎
 * テンプレートの基礎
 * ジェネリックプログラミングの基礎

について紹介した。テンプレートには他にも、 **SFINAE** や **ポリシー** など、興味深い話題がたくさんある。テンプレートに興味が湧いたら、参考資料に挙げた資料に説明があるので、読んでみると良いと思う。

# 参考資料

* [C++テンプレートテクニック 第2版](http://www.amazon.co.jp/C-%E3%83%86%E3%83%B3%E3%83%97%E3%83%AC%E3%83%BC%E3%83%88%E3%83%86%E3%82%AF%E3%83%8B%E3%83%83%E3%82%AF-%E7%AC%AC2%E7%89%88-%CE%B5%CF%80%CE%B9%CF%83%CF%84%CE%B7%CE%BC%CE%B7/dp/4797376686/ref=sr_1_1?ie=UTF8&qid=1397898058&sr=8-1&keywords=C%2B%2B)

* [STL―標準テンプレートライブラリによるC++プログラミング 第2版](http://www.amazon.co.jp/STL%E2%80%95%E6%A8%99%E6%BA%96%E3%83%86%E3%83%B3%E3%83%97%E3%83%AC%E3%83%BC%E3%83%88%E3%83%A9%E3%82%A4%E3%83%96%E3%83%A9%E3%83%AA%E3%81%AB%E3%82%88%E3%82%8BC-%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0-%E7%AC%AC2%E7%89%88-%E3%83%87%E3%82%A3%E3%83%93%E3%83%83%E3%83%89%E3%83%BBR-%E3%83%9E%E3%83%83%E3%82%B5%E3%83%BC/dp/4894714329/ref=sr_1_8?ie=UTF8&qid=1399249055&sr=8-8&keywords=C%2B%2B+stl)