Contest Duration: 2017-12-13 21:00:00+0900 - 4017-12-13 21:00:00+0900 (local time) Back to Home

AH - 4.03.テンプレート Editorial

Time Limit: 0 msec / Memory Limit: 0 KiB

キーポイント

テンプレートは構造体や関数の「型」を一般化するための機能
「同様の処理を行うが、利用する型が異なる関数」は関数テンプレートを用いてまとめることができる
関数テンプレートの宣言

template <typename テンプレート引数>
返り値の型 関数名(引数の型 引数...(必要な分だけ書く)) {
  // 処理内容
}

関数テンプレートとして定義された関数の呼び出し

関数名<テンプレート引数>(引数1, 引数2, ...);

構造体の内容を型について一般化したいときにはクラステンプレートを用いてまとめることができる
クラステンプレートの宣言

template <typename テンプレート引数>
struct 構造体名 {
  (構造体の内容)
};

クラステンプレートを用いて定義された構造体の使用

構造体名<テンプレート引数>

テンプレート

テンプレートは構造体や関数の「型」を一般化するための機能です。

関数テンプレート

関数テンプレートを用いることで「同様の処理を行うが、使用している型が異なる関数」をまとめることができます。

例えば、これまで扱ってきたSTLのmin関数やmax関数は関数テンプレートを用いて定義されています。これによってint型に対してもdouble型に対しても同じように使えるようになっています。

以下では「ある数値xを取って二乗する関数」を例として説明します。扱う数値がint型であれば次のように書くことができます。

// xの二乗を返す
int square_int(int x) {
  return x * x;
}

ここでdouble型の数値を二乗する関数も必要になったとします。

// xの二乗を返す
double square_double(double x) {
  return x * x;
}

これらの関数は次のように使うことができます。

#include <bits/stdc++.h>
using namespace std;

// xの二乗を返す
int square_int(int x) {
  return x * x;
}

// xの二乗を返す
double square_double(double x) {
  return x * x;
}

int main() {
  int a = 3;
  double b = 1.2;

  cout << square_int(a) << endl;
  cout << square_double(b) << endl;
}

実行結果

9
1.44

2つの関数（int用とdouble用）の関数内の記述は全く同じです。

関数テンプレートの機能を用いることでこのような「別の型に対する同じ処理」をまとめることができます。具体的には次のように関数を定義します。

// xの二乗を返す (関数テンプレート版)
template <typename T>
T square(T x) {
  return x * x;
}

この関数を呼び出す側は以下のようになります。

#include <bits/stdc++.h>
using namespace std;

// xの二乗を返す (関数テンプレート版)
template <typename T>
T square(T x) {
  return x * x;
}

int main() {
  int a = 3;
  double b = 1.2;

  cout << square<int>(a) << endl;  // int版のsquare関数の呼び出し
  cout << square<double>(b) << endl;  // double版のsquare関数の呼び出し
}

実行結果

9
1.44

関数テンプレートの宣言

関数テンプレートを宣言するには次のようにします。

template <typename テンプレート引数>
返り値の型 関数名(引数の型 引数...(必要な分だけ書く)) {
  // 処理内容
}

テンプレートは返り値の型や引数の型として用いることができます。

複数のテンプレート引数を取ることもできます。

template <typename テンプレート引数1, typename テンプレート引数2, ...(必要な分だけ書く)>
返り値の型 関数名(引数の型 引数...(必要な分だけ書く)) {
  // 処理内容
}

構造体のメンバ関数もテンプレートを用いて定義することができます。

テンプレートを用いた関数の呼び出し

テンプレートを用いて定義された関数を呼び出すには、以下のように書きます。

関数名<テンプレート引数>(引数1, 引数2, ...);

テンプレート引数は、関数を定義したときに指定した分だけ渡します。

関数名<テンプレート引数1, テンプレート引数2, ...(必要な分だけ書く)>(引数1, 引数2, ...);

ただし、引数の型から推定できる場合には、テンプレート引数の指定を省略することができます。

#include <bits/stdc++.h>
using namespace std;

// xの二乗を返す (関数テンプレート版)
template <typename T>
T square(T x) {
  return x * x;
}

int main() {
  int a = 3;
  double b = 1.2;

  // テンプレート引数の省略
  cout << square(a) << endl;  // int版のsquare関数の呼び出し
  cout << square(b) << endl;  // double版のsquare関数の呼び出し
}

実行結果

9
1.44

構造体におけるテンプレート

構造体を定義する際にもテンプレートを用いることができます。これによって、例えばメンバ変数の型を一般化した構造体を作ることができます。

このようなテンプレートをクラステンプレートといいます。

これまで扱ってきたvectorやmapなどのSTLのコンテナはクラステンプレートを用いて定義されています。例えばvectorはvector<int>としてint型の配列を、vector<double>としてdouble型の配列を使うことができました。

次のプログラムは座標値の型をテンプレートを用いて一般化したPoint構造体の例です。

#include <bits/stdc++.h>
using namespace std;

// クラステンプレートの宣言
template <typename T>
struct Point {
  T x;
  T y;
  void print() {
    cout << "(" << x << ", " << y << ")" << endl;
  }
};

int main() {
  // int型用のPoint構造体
  Point<int> p1 = { 0, 1 };
  p1.print(); // (0, 1)

  // double型用のPoint構造体
  Point<double> p2 = { 2.3, 4.5 };
  p2.print(); // (2.3, 4.5)
}

実行結果

(0, 1)
(2.3, 4.5)

クラステンプレートの宣言

クラステンプレートを宣言するには次のようにします。

template <typename テンプレート引数>
struct 構造体名 {
  (構造体の内容)
};

テンプレート引数は型名として用いることができます。

複数のテンプレート引数を取ることもできます。

template <typename テンプレート引数1, テンプレート引数2, ...(必要な分だけ書く)>
struct 構造体名 {
  (構造体の内容)
};

テンプレートを用いた構造体の使用

クラステンプレートを用いて定義した構造体を使うには、次のようにテンプレート引数を指定します。

構造体名<テンプレート引数>

上のサンプルプログラムではPointというクラステンプレートに対してPoint<int>やPoint<double>として利用しています。

関数テンプレートと違い、クラステンプレートのテンプレート引数は省略することはできません。

定数のテンプレート

関数テンプレートもクラステンプレートも、整数型の定数をテンプレート引数として用いることができます。定数のテンプレートは、使う場所に応じて定数を切り替えたい場合などに便利です。

具体例として、tupleの要素取得に用いるget関数や、bitsetは定数のテンプレートを用いて定義されています。

以下は関数テンプレートにおいて定数のテンプレート引数をとる例です。

#include <bits/stdc++.h>
using namespace std;

// タプルのINDEX1番目とINDEX2番目を交換する関数
template <int INDEX1, int INDEX2>
void tuple_swap(tuple<int, int, int> &x) {
  swap(get<INDEX1>(x), get<INDEX2>(x));
}

int main() {
  tuple<int, int, int> x = make_tuple(1, 2, 3);

  tuple_swap<0, 2>(x);  // 1番目と3番目を交換
  cout << get<0>(x) << ", " << get<1>(x) << ", " << get<2>(x) << endl;

  tuple_swap<0, 1>(x);  // 1番目と2番目を交換
  cout << get<0>(x) << ", " << get<1>(x) << ", " << get<2>(x) << endl;
}

実行結果

3, 2, 1
2, 3, 1

以下はクラステンプレートにおいて定数のテンプレート引数をとる例です。

#include <bits/stdc++.h>
using namespace std;

// MODで割ったあまりをxに保持するような構造体
template <int MOD>
struct Modulo {
  int x;
  Modulo() {}
  Modulo(int v) {
    x = v % MOD;
  }
  // 足し算
  Modulo plus(Modulo<MOD> other) {
    Modulo<MOD> result;
    result.x = (x + other.x) % MOD;
    return result;
  }
};

int main() {
  Modulo<10> a(7), b(5);
  auto c = a.plus(b);
  cout << c.x << endl; // (5 + 7) % 10 == 2
}

実行結果

注意点

テンプレートを用いて宣言された関数や構造体にタイプミスなどのミスがあったとしても、それがプログラムの中で使われていない場合に、コンパイルエラーにならないことがあります。これは、使われていないテンプレートはコンパイル時に無視されるからです。詳しくは「細かい話の実体化について」を読んでください。

以下は関数テンプレートの中でタイプミスをしている例です。

#include <bits/stdc++.h>
using namespace std;

struct X {
  void f() {
    cout << "X" << endl;
  }
};
struct Y {
  void f() {
    cout << "Y" << endl;
  }
};

template <typename T>
void call_f(T v) {
  v.g();  // fと書くところをタイプミスでgと書いてしまったとする
}

int main() {
  // 何もしない
}

実行結果

本来、関数fを呼び出すために用意された関数call_fですが、タイプミスで関数gを呼び出そうとしています。タイプミスしていますが、このテンプレートはプログラム中で使われていないため、正常にコンパイル・実行されます。

次のように、call_fを使おうとしたときに初めてコンパイルエラーが発生します。

#include <bits/stdc++.h>
using namespace std;

struct X {
  void f() {
    cout << "X" << endl;
  }
};
struct Y {
  void f() {
    cout << "Y" << endl;
  }
};

template <typename T>
void call_f(T v) {
  v.g();  // fと書くところをタイプミスでgと書いてしまったとする
}

int main() {
  X x;
  Y y;
  call_f(x); // Xのfが呼ばれてほしい
  call_f(y); // Yのfが呼ばれてほしい
}

標準エラー出力

./Main.cpp: In instantiation of ‘void call_f(T) [with T = X]’:
./Main.cpp:23:11:   required from here
./Main.cpp:17:3: error: ‘struct X’ has no member named ‘g’
   v.g();  // fと書くところをタイプミスでgと書いてしまったとする
   ^
./Main.cpp: In instantiation of ‘void call_f(T) [with T = Y]’:
./Main.cpp:24:11:   required from here
./Main.cpp:17:3: error: ‘struct Y’ has no member named ‘g’

「少しずつ書いてコンパイルして確認して……」というようなコーディングを行う場合には注意が必要です。

細かい話

テンプレートの実体化

テンプレートは同じような処理を一般化できる便利な機能ですが、実は「関数・構造体を自動的に生成するための設計図」にすぎません。例えば、関数テンプレートは「それぞれの型専用の関数を自動的に生成するための機能」です。

テンプレートを用いて定義された関数・構造体を使うときには、実際にはその実体（関数・構造体）が生成されてから使われることになります。このようにテンプレートから実体が作られることをテンプレートの実体化といいます。

テンプレートの実体化はコンパイラによって自動的に行われます。プログラム中でテンプレートが使われているときに、その使われ方に応じて実体化が行われるので、あるテンプレートがプログラム中で全く使われていない場合には実体化は行われません。

`square`関数における例

関数テンプレートの具体例として紹介したsquare関数を例として説明します。

#include <bits/stdc++.h>
using namespace std;

/*
// xの二乗を返す
int square_int(int x) {
  return x * x;
}

// xの二乗を返す
double square_double(double x) {
  return x * x;
}
*/

// xの二乗を返す (関数テンプレート版)
template <typename T>
T square(T x) {
  return x * x;
}

int main() {
  int a = 3;
  double b = 1.2;

  cout << square<int>(a) << endl;  // int版のsquare関数の呼び出し
  cout << square<double>(b) << endl;  // double版のsquare関数の呼び出し
}

実行結果

9
1.44

まず、squareの関数テンプレートを宣言しただけでは関数は何も生成されません。

プログラム中でsquare<int>(a)のように使われることで、コンパイラによって「int用のsquare関数」（square_int関数と同等な関数）が生成されます。同様にsquare<double>(b)のように使われていると「double用の関数」（square_double関数と同等な関数）が作られます。 square<int>(a)とsquare<double>(b)ではそれぞれが実体化されるので、プログラムが実行される際に実際に呼ばれている関数は別のものということになります。

ただし、square<int>(2)とsquare<int>(3)のように同じint型に対する呼び出しについては、同じ関数がよばれることになります。 square<int>(2)によってint型に対する実体化が行われ、square<int>(3)については既に実体化したものを呼び出す、とイメージするとよいでしょう。

競技プログラミングでよく用いられるテンプレートの例

競技プログラミングでよく用いられる関数テンプレートとして、chmax/chminを紹介します。

#include <bits/stdc++.h>
using namespace std;

// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}

//-------------------------------

int f(int n) {
  // (適当な関数)
  return n * n - 8 * n + 3;
}

int main() {
  // f(1), f(2), ..., f(10)の最小値と最大値を求める
  int ans_min = 1000000000;
  int ans_max = 0;
  for (int i = 1; i <= 10; i++) {
    chmin(ans_min, f(i));  // 最小値を更新
    chmax(ans_max, f(i));  // 最大値を更新
  }
  cout << ans_min << " " << ans_max << endl;
}

実行結果

-13 23

chminは最小値を求める際に、chmaxは最大値を求める際などに用いると便利です。

typenamとclass

テンプレートの宣言におけるtypenameの部分はclassと書いても全く同じ意味になります。

// template <typename T>と書くのと同じ
template <class T>
T square(T x) {
  return x * x;
}

// template <typename T>と書くのと同じ
template <class T>
struct Point {
  T x;
  T y;
  void print() {
    cout << "(" << x << ", " << y << ")" << endl;
  }
};

ここで紹介しなかった機能

このページで紹介しなかったテンプレートに関する機能の例を載せておきます。もっと深く知りたい人は是非調べてみてください。

テンプレートの特殊化
- 特殊化を行うことで「テンプレートを用いて一般化したいが、特定の型に対するものだけ別の内容にしたい」ということが可能になります
テンプレートの明示的な実体化
可変長テンプレート
変数テンプレート
エイリアステンプレート
SFINAEルール
など

前のページ | 次のページ

キーポイント

テンプレート

関数テンプレート

実行結果

実行結果

関数テンプレートの宣言

テンプレートを用いた関数の呼び出し

実行結果

構造体におけるテンプレート

実行結果

クラステンプレートの宣言

テンプレートを用いた構造体の使用

定数のテンプレート

実行結果

実行結果

注意点

実行結果

標準エラー出力

細かい話

テンプレートの実体化

square関数における例

実行結果

競技プログラミングでよく用いられるテンプレートの例

実行結果

typenamとclass

ここで紹介しなかった機能

`square`関数における例