テンプレート

ここでは，C++の中でも特に高度な2つの機能，テンプレートと例外処理について学ぶ．これらの機能を用いると，再利用可能で，堅牢なプログラムコードを作成することができる．　 テンプレート(template)は具体的なコードを作り出すための抽象的な処方(ひな形)を提供する．テンプレートは汎用関数やクラスを作ることに用いることもできる．コンパイラはテンプレートを用いて関数やクラスのコードを生成する．テンプレートを用いて生成された汎用関数やクラスはテンプレートのインスタンス(instance)とよばれる．

また，同じテンプレートからいろいろ異なるインスタンスを生成することができる．これはパラメタが関数に対して行う役割をまねたテンプレートパラメタにより行われる．だたし，テンプレートパラメタは型やクラスを引数として扱うことができる．そこで，テンプレートパラメタを汎用型(generic type)という．

テンプレートは，ジェネリックプログラミング(generic programming)，つまり，引数として汎用型を使うプログラミングを直接サポートする．また，C++テンプレートメカニズムは，クラスや関数定数で，型を汎用型化できるようにする．

汎用関数(generic function)

汎用関数とは，さまざまな型のデータに適用できる一連の汎用操作を定義する関数のことである．汎用関数は，処理するデータの型を仮引数として受け取る．したがって，この仕組みを利用すれば，1つの汎用手順を広範囲なデータに対して利用することができるようになる．

汎用関数を作成するには，templateキーワードを用いる．その構文は

template

class T

戻り値の型　関数名(T& 引数, T& 引数, ... )
{
関数の本体
}

となる．

関数テンプレート(Function Templates)

多くのソートのアルゴリズムでは，1組の要素を入れ替える必要がある．そして，このタスクは一般に次のような関数によって行われる．

void swap(int& m, int& n)
{
int temp = m;
m = n;
n = temp;
}

次に，整数の入れ替えではなく，文字列の入れ替えを行うならば，

void swap(string& s1, string& s2)
{
string temp = s1;
s1 = s2;
s2= temp;
}

と書かなくてはならない．しかし，この2つの関数をよく見るとほとんど同じで，違うのは入れ替えるオブジェクトの型だけである．こんなとき，関数テンプレートを用いると次のようにあらわせる．

#include <iostream>
using namespace std;

template <class T>　void swapargs(T& x, T& y)
{
T temp = x;
x = y;
y = temp;
}

例題 13..1 swap関数テンプレート
次のテストドライバを実行するとどんな結果が得られるか調べよ．

int main()
{
int n = 22, m = 44;
cout << n << " " << m << endl;
swapargs(n,m);
cout << n << " " << m << endl;
string s1 = "Yokota", s2 = "Hisashi";
cout << s1 << " " << s2 << endl;
swapargs(s1,s2);
cout << s1 << " " << s2 << endl;
}

解答関数名swap()をそのまま使うと標準ライブラリで定義されているswap()関数とぶつかるので，swapargs()に変更している．

記号Tは汎用型とよばれ，実際の型またはクラスのための場所を確保しているだけである．

関数テンプレートの宣言は普通の関数の宣言と基本的に同じである．ただ1つの違いは関数の前に

template <class T>

という接頭語が必要であり，また，汎用型Tが普通の型の変わりに用いられることである．classという言葉は，ここではどんな型でもという意味になる．一般に，テンプレートは次のようにいくつかの汎用型をとることができる．

template <class T, class U, class V >

このように，関数の前にtemplateキーワードがついた関数を汎用関数という．

実行結果

$\begin{figure}% latex2html id marker 3842 \centering\includegraphics[width=7.9cm]{CPPPIC/reidai13-1.eps} \end{figure}$

関数テンプレートの呼び出し方は，普通の関数の場合と同じである．例えば，

int m = 11, n = 55
swapargs(m,n);
string s1 = "紫式部", s2 = "吉田兼好";
swapargs(s1,s2);
Rational x(22/7), y(-3);
swapargs(x,y);

において，swapargs()関数が呼ばれるたびに，コンパイラは汎用型を引数の型またはクラスで置き換える．よって，swapargs(m,n)は整数型のswapargs関数を作り，swapargs(s1,s2)は文字列型のswapargs関数を生成する．

関数テンプレートは関数多重定義を一般化したものである．関数多重定義を用いてswapargs関数を書くこともできたが，関数テンプレートを用いることには2つの利点がある．１つは，関数テンプレートでは１つのプログラムで2つの異なる型に対応していることである．2つ目は，どの型に対応しているかを事前に決める必要がないことである．

例題 13..2 バブルソートテンプレート
例題6.9を，テンプレートを用いて書き直し，次の2つのベクトルをソートせよ．
{55, 33, 88, 11, 44, 99, 77, 22, 66}
{"Tim", "Henry", "Don", "Ben", "Ses", "Andy", "Joe"}

解答

#include <iostream>
#include <string>
using namespace std;
template<class T>
void sort(T& v, int n)
{
for (int i=1; i < n; i++){
for (int j = 0; j < n-1; j++){
if(v[j] > v[j+1]) swap(v[j],v[j+1]);
}
}
}
template<class T>
void print(T* v, int n)
{
for (int i=0; i < n; i++){
cout << " " << v[i];
}
cout << endl;
}
int main()
{
short a[9] = {55, 33, 88, 11, 44, 99, 77, 22, 66};
print(a,9);
sort(a,9);
print(a,9);
string s[7] = {"Tim", "Henry", "Don", "Ben", "Ses", "Andy", "Joe"};
print(s,7);
sort(s,7);
print(s,7);
}

$\begin{figure}% latex2html id marker 3851 \centering \includegraphics[width=8.05cm]{CPPPIC/reidai13-2.eps} \end{figure}$

ここで，sort関数とprint関数は共に関数テンプレートである．また，汎用型Tは最初の呼び出しでshort型に，2回目の呼び出しでstring型に置き換えられた．

関数テンプレートはoutlineのような働きをする．コンパイラはテンプレートを用いて必要な関数を生成する．例題14-2では，コンパイラは２つのバージョンのsort関数と2つのバージョンのprint関数を生成している．それぞれのバージョンをテンプレートのインスタンスという．テンプレートのインスタンスである関数をテンプレート関数(template function)ともいう．テンプレートを用いることは，自動コード生成の１つである．

汎用クラス(Generic Classes)

汎用関数に加えて，汎用クラス(generic class)を定義することもできる．汎用クラスを定義するには，そのクラスで使用するすべてのアルゴリズムを定義したクラスを作成するが，操作する実際のデータの型は，そのクラスのオブジェクトを作成する際に仮引数として指定する．

クラステンプレートは関数の代わりに汎用クラスを生成する以外は関数テンプレートと同じである．その構文は

template<class T, ...> class X {...};

となる．関数テンプレートと同じようにクラステンプレートも数個の引数をとることができ，引数には普通の型が含まれていてもよい．つまり，

template<class T, int n, class U> class X {...};

と書くこともできる．

コンパイラでテンプレートはインスタンス化されるので，普通の型は定数である必要がある．

template<class T, int n>
class X {};
int main()
{
X<float, 22> x1; // ok
const int n = 44;
X<<char, n> x2; // ok
int m = 66;
X<short, m> x2; // ERROR: mは定数でなければならない
}

クラステンプレートのメンバ関数はそれ自身が関数テンプレートである．例えば，次のクラステンプレート

template<class T>
class X
{
T square(T t) {return t*t};
};

で宣言されている関数f()は, 次のテンプレート関数

template<class T>
T square(T t) {return t*t};

と同じ働きをする．つまり，まずコンパイラでインスタンス化され，テンプレート引数Tを渡された型で置き換える．よって，宣言

X<short> x;

により，次のクラスとオブジェクトが生成される．

class X_short
{
short square(short t) {return t*t;}
};
X_short x;

ただし，あなたが用いているコンパイラーはX_short以外のクラス名を使用するかもしれない．

スタッククラス(Stack Class)

スタック(stacke)は代表的なデータ構造の一つで，日常の生活でいうと棚に積み重ねた皿のようなものである．違いといえば，上からしかデータを出し入れできないところである．つまり，後入れ先出し(LIFO)のデータ構造をしている．別の言い方をすると，スタックは一端からしか出し入れできない線形構造（一列に並んでもの）をしている．

スタッククラスはデータ構造に用いる道具を隠すことにより，この考えを抽象化し後入れ先出しの機能だけを用いてデータへのアクセスを可能にしている．

$\begin{figure}\centering \includegraphics[width=13.3cm]{CPPPIC/stackop.eps} \end{figure}$

スタックは物を追加するのに，push()関数を用い，物を取り出すのにpop()関数を用いる．

スタックに格納されたオブジェクトはパイル状に保存される．最後に追加されたものはtopの位置に格納される．物を取り出すときは，いつもtopの位置にある物から取り出す．最後に追加されたものが常に最初に取り出されるので，スタックはlast-in, first-out(LIFO)データ構造である．

スタッククラスのテンプレートは次のようになる．

#include <iostream>
using namespace std;

template<class T>
class Stack
{
public:
Stack(int s=100): size(s), top(-1){data = new T[size];}
~Stack() {delete [] data;}
void push(const T& x) {data[++top] = x;}
T pop() {return data[top-];}
int isEmpty() const {return top == -1;}
int isFull() const {return top == size - 1;}
private:
int size;
int top;
T* data;
};

このクラスの定義は配列dataを用いてスタックを作っている．コンストラクタは配列のサイズを初期化し，型Tの要素を配列に配置し，topポインタを-1に設定している．topの値は空のスタックのとき以外，スタックの要素の数より常に１少ない．push()関数はスタックにオブジェクトを挿入し，pop()関数はスタックからオブジェクトを取り出す．

例題 13..3 スタッククラステンプレート
次のテストドライバを実行するとどんな結果が得られるか調べよ．

int main()
{
Stack<int> intStack1(5);
Stack<int> intStack2(10);
Stack<char> charStack(8);
intStack1.push(77);
charStack.push('A');
intStack2.push(22);
charStack.push('E');
charStack.push('K');
intStack2.push(44);
cout << intStack2.pop() << endl;
cout << intStack2.pop() << endl;
if(intStack2.isEmpty()) cout << "intStack2 is empty. \n";
}

解答このテンプレートはスタックに格納されたオブジェクトの型を明記するために1つの引数Tを持っている．1行目は5個の整数を格納できるスタックとしてintStack1を宣言している．同様に，intStack2は10個の整数を格納できるスタックである．そして，charStackは8文字までの文字を格納できるスタックである．pushとpopでオブジェクトを入れたり出したりしながら，最後の行でintStack2が空がテストする．そのときのスタッククラスとスタックオブジェクトは次のようになっている．

$\begin{figure}\centering \includegraphics[width=11.7cm]{CPPPIC/fig13-3.eps} \end{figure}$

実行結果

$\begin{figure}% latex2html id marker 3876 \centering \includegraphics[width=8.2cm]{CPPPIC/reidai13-3.eps} \end{figure}$

コンテナクラス(Container Classes)

コンテナ(container)は他のオブジェクトを保持するオブジェクトのことをいう．平たく言うと，他のオブジェクトの入れ物である．ということは，配列やスタックはコンテナである．コンテナクラス(container class)はインスタンスがコンテナであるクラスのことをいう．例題13-3のStack $<$ int $>$ クラスやStack $<$ char $>$ クラスはコンテナクラスである．クラステンプレートはコンテナクラスを生成するための自然なメカニズムである．なぜならば，含まれているオブジェクトの型はテンプレート引数で明示することができるからである．

コンテナはそのオブジェクトが全て同じ型であるとき同型(homogeneous)であるという．そうでないときは，異型コンテナ(heterogeneous container)という．これより，スタックや配列は同型コンテナである．

ベクタ(vector)は同じ型のオブジェクトの指標付きの列である．ベクタとは数学で用いられるベクトルにその名前の由来がある．例えば，x = (x_1,x_2,x_3)という3次元ベクトルを配列を用いて表すことを考えてみる．このベクトルの成分x_1, x_2, x_3の添え字は配列の指標と同じである．ただし，配列の場合，指標は1からではなく０から始まる．また，ソースコードでは添え字を用いることができないので，その代わりに[ ]を用いて，x_1の代わりにx[0]，x_2の代わりにx[1]，x_3の代わりにx[2]と表す．

例題 13..4 ベクタクラステンプレート
次のプログラムを実行するとどんな結果が得られるか調べよ．

#include <iostream>
using namespace std;

template<class T>
class Vector
{
public:
Vector(unsigned n = 8) : siz(n), data(new T[siz]) { }
Vector(const Vector<T>& v) : siz(v.siz), data(new T[siz])
{ copy(v);}
~Vector() {delete [] data;}
Vector<T>& operator= (const Vector<T>&);
T& operator[](unsigned i) const {return data[i];}
unsigned size() {return siz;}
protected:
T* data;
unsigned siz;
void copy(const Vector<T>&);
};
このファイルは後で使うので，Vector.hという名前で保存しておく．

template<class T>
Vector<T>& Vector<T>::operator=(const Vector<T>& v)
{
siz = v.siz;
data = new T[siz];
copy(v);
return *this;
}
template<class T>
void Vector<T>::copy (const Vector<T>& v)
{
unsigned min_siz = (siz < v.siz ? siz: v.siz);
for (int i=0; i < min_siz; i++){
data[i] = v.data[i];
}
}
int main()
{
Vector<short> v;
v[5] = 127;
Vector<short> w = v, x(3);
cout << w.size();
}

解答ここで，vとwは8個のshort型を保持するVectorオブジェクトである．また，xは3個のshort型を保持するVectorオブジェクトである．クラスと3つのオブジェクトは次の表のようになっている．

$\begin{figure}\centering \includegraphics[width=15.15cm]{CPPPIC/fig13-4.eps} \end{figure}$

例外処理(Exception Handling)

C++には，例外処理(exception handling)というエラー処理機構が組み込まれている．例外処理を行うと，実行時エラーをより容易に管理し対処することができる．C++の例外処理では，try, catch, throwの３つのキーワードが基礎となっている．一般に，例外が発生したかどうかを監視したいプログラム文をtryブロック内に含め，tryブロック内で例外が発生すると，その例外はthrow文を使って投げられ，catch文を用いて捕獲し処理される．その構文は，

try{
// try ブロック
} catch (type1 arg){
// catch ブロック
}

のようになる．

tryブロックには，１つの関数内の数行の文を含めても，main()関数のプログラムコードを全て含めても構わない．例外が投げられると，対応するcatch文によって捕獲され例外が処理される．１つのtryブロックに複数のcatch文を対応つけることもできる．その場合，どのcatch文を利用するかは例外の型によって決まる．例外を捕獲すると，argはその値を受け取る．例外自体にアクセスする必要がない場合は，catch句で型だけを指定することもできる．

throw文の構文は

throw exception

となる．

throwは，tryブロック内から実行するか，ブロック内のプログラムコードから呼び出す関数内で実行する．exceptionには投げる値を指定する．

対応するcatch文のない例外を投げるとプログラムが異常終了する．

例題 13..5 例外処理
次のプログラムは，C++の例外処理の仕組みを示す．

#include <iostream>
using namespace std;

int main()
{
cout << "開始 \n";
try{tryブロックの開始
cout<< "tryブロック内部" << endl;
throw 10; //エラーを投げる
cout << "このブロックは表示されない" << endl;
}
catch(int i) {//エラーの捕獲
cout << "１個のエラーを捕獲：その数は：";
cout << i << endl;
}
cout << "終了" << endl;
}

実行結果

$\begin{figure}% latex2html id marker 3921 \centering \includegraphics[width=7.95cm]{CPPPIC/reidai13-5.eps} \end{figure}$

派生クラステンプレート(Subclass Templates)

クラステンプレートでの継承は一般のクラスの継承と同じように働く．このことをもっとよく理解するために，例題13-4で定義したVectorクラステンプレートの派生クラステンプレートを定義する．

例題13-4におけるテンプレートを用いたVectorクラスの問題は，全ての添え字が0から始まらなければならないことである．そこで，Vectorクラステンプレートの派生クラステンプレートを宣言することにより，添え字が1から始まるようにする

template <class T>
class Array : public Vector{
public:
Array(int i, int j); index0(i), Vector<T>(j-i+1) { }
Array(const Array<T> v) : index0(v.index0), Vector(v) { }
T& operator[] (int i) const {return Vector<T>::operator[] (i-index0);
int firstSubscript() const() {return index0;}
int lastSubscript() cosnt() {return index0 + siz - 1;}
protectd:
int index0;
};

この派生クラスをArray.hという名前で保存しておく．

このArrayクラステンプレートはVectorクラステンプレートの全ての機能を継承している．また，添え字がどんな数字からでも始められる．

例題 13..6 添え字の開始
次のテストドライバを実行するとどんな結果が得られるか調べよ．

#include<iostream>
#include "Array.h"
#include "Vector.h"R Array x(1,3);
x[1] = 3.14159;
x[2] = 0.08516;
x[3] = 5041.92;
cout << "x.size() = " << x.size() << endl;
cout << "x.firstSubscript() = " << x.firstSubscript() << endl;
cout << "x.lastSubscript() = " << x.lastSubscript() << endl;
for (int i = 1; i <= 3; i++){
cout << "x[" << i <<"] = " << x[i] << endl;
}
}

実行結果

$\begin{figure}% latex2html id marker 3931 \centering \includegraphics[width=8.25cm]{CPPPIC/reidai13-6.eps} \end{figure}$

テンプレートクラスをテンプレートの引数に渡す(Passing Template Classes to Template Parameters)

クラスをテンプレートの引数に渡す例はすでに見たことがある．例えば，
Stack $<$ Rational $>$ s; // Rationalオブジェクトのスタック
Vector $<$ string $>$ a; // stringオブジェクトのベクタ
などである．これと同様なことがテンプレートクラスでも可能である．
Stack $<$ Vector $<$ int $>>$ s; // Vectorオブジェクトのスタック
Array $<$ Stack $<$ Rational $>>$ a; // スタックオブジェクトの配列

2行3列の行列 $\left(\begin{array}{ccc} a & b & c\\ d & e & f \end{array}\right)$ は成分を3個持った2つのベクトルからなっていると考えることができる．つまり $\left(\begin{array}{cc} [a b c] & [d e f] \end{array}\right)$ このようにして行列を考えると，MatrixクラスをVectorクラステンプレートの再利用により定義することができる．

メモリの動的配置を促進するために，次のように行列をベクタへのポインタベクトルとして定義する．

Vector*>

外側の角括弧によりクラステンプレートポインタをテンプレート引数へ渡す．つまり，Matrixクラスのインスタンス化が行なわれると，インスタンスはベクタへのポインタベクトルを保持しているということである．

template<class T>
class Matrix
{
public:
Matrix(unsigned r=1, unsigned c = 1) : row(r)
{for (int i=0; i < r; i++) row[i] = new Vector<T>(c);}
~Matrix() {for (int i=0; i < row.size(); i++) delete row[i];}
Vector<T>& operator[] (unsigned i) const { return *row[i];}
unsigned rows() {return row.size();}
unsigned columns() { return row[0] -> size();}
protected:
Vector<Vector>T>* > row;
};

ここで，メンバ変数はベクタへのポインタベクトルrowだけである．rowはベクトルより添え字演算子と一緒に用いることができる．よって，row[i]は行列のi行目をあらわすベクタへのポインタを返す．

ディフォルトコンストラクタはそれぞれのrow[i]にc個の型Tを保持した新しいベクタを用意する．

ディストラクタはこれらのベクタを別々に消去しなければならない．メンバ関数rows()とcolumns()はそれぞれ行の数と列の数を返す．

例題 13..7 行列クラステンプレート
次のテストドライバを実行するとどんな結果が得られるか調べよ．

int main()
{
Matrix<floa> a(2,3);
a[0][0] = 0.0; a[0][1] = 0.1; a[0][2] = 0.2;
a[1][0] = 1.0; a[1][1] = 1.1; a[1][2] = 1.2;
cout << "行列aの大きさは" << a.rows() << "行" << a.columns() << "列" << endl;
for (int i=0; i < 2; i++){
   for (int j=0; j < 3; j++)
      cout << a[i][j] << " ";
   cout << endl;
}
}

解答 MatrixクラステンプレートはVectorクラステンプレートの合成を用い，ArrayクラステンプレートはVectorクラステンプレートの派生を用いる．

連結リストのクラステンプレート(Class Template for Linked Lists)

連結リストは例題10.6ですでに紹介した．これらのデータ構造はベクタの代わりをすることができる．実は単なる代わりではなく，ベクタと異なり連結リストが動的に増えたり減ったりすることができる．これを動的格納(dynamic allocation)という．これにより，データの無駄なく連結リストを作成できる．

Listクラステンプレート
リストは連結したノードから成り立っている．それぞれのノードは1つのデータと次のノードへのリンクを保持している．そこで，ListNodeクラステンプレートの作成から始める．

template<class T>
class ListNode
{
friend class List<T>;
public:
   ListNode(T& t, ListNode<T>* p) : data(t), next(p) {}
protected:
   T data;
   ListNode* next;
};

このコンストラクタは新しいノードを作成し，そのデータフィールドにT値ｔをそしてポインタpを次のフィールドに割り当てる．

$\begin{figure}\centering \includegraphics[width=13.6cm]{CPPPIC/fig13-9-1.eps} \end{figure}$

もし，Tがクラスならば，そのコンストラクタはdataの宣言により呼ばれる．クラス List $<$

はここで，ListNodeクラスのfriendとして宣言されている．これにより，Listクラスのメンバ関数がNodeクラスのprotectedメンバへアクセスすることができる．ただし，このプログラムをコンパイルするときには，コンパイラによっては，ListNodeテンプレート定義の前に次の前進参照(forward reference)が必要になる．
template $<$

class

class List;
これはコンパイラにListがクラステンプレートとして後で定義されることを告げるものである．

次に，Listクラスのテンプレートを記す．

template<class T>
class List
{
public:
List() : first(0) {}
~List();
void insert(T t);
int remove(T& t);
bool isEmpty() {return (first == 0);}
void print();
protected:
ListNode* first;
ListNode* newNode(T& t, ListNode* p)
{ListNode* q = new ListNode(t,p); return q;}
};

Listオブジェクトはfirstという名前のポインタを保持しているだけである．このポインタはListNodeオブジェクトを指している．ディフォルトコンストラクタはNULLへのポインタを初期化する．リストに項目が挿入された後，firstポインタはリストの最初の項目を指す．

$\begin{figure}\centering \includegraphics[width=4.0cm]{CPPPIC/fig13-9-2.eps} \end{figure}$

newNode()関数はListNode()コンストラクタを用いて新しいListNodeオブジェクトを得るために，new演算子を呼び出す．新しくできたノードはdataフィールドに型T値tをそして，nextフィールドにポインタpを保持する．この関数は新しいノードへのポインタを返す．newNode()関数はprotectedで宣言されている．その理由は，この関数は他のメンバ関数に用いられるだけの万能関数だからである．

次にListのディストラクタを記す．

template<class T>
List<T>::~List()
{
ListNode<T>* temp;
for(ListNode<T>* p = first; p; ){
   temp = p;
   p = p->next;
   delete temp;
}
}

insert()関数は型T値tを保持する新しいノードを作成し，この新しいノードをリストの先頭に挿入する．

template<class T>
void List<T>::insert(T t)
{
ListNode<T>* p = newNode(t, first);
first = p;
}

新しいノードのnextポインタは現在リストの先頭のノードを指すはずである．firstポインタをnewNodeコンストラクタに渡すことにより，このことが行なわれる．その後，firstポインタは新しいノードを指すようにリセットされる．

remove()関数は，そのdata値を引数tによる参照によりリストの最初の項目を削除する．この関数の戻り値はうまく行けば1で，失敗すると０である．

template<class T>
int List<T>:: remove(T& t)
{
if (isEmpty()) return 0;
t = first->data;
ListNode<T>* p = first;
first = first-> next;
delete p;
return 1;
}

これで，ListNodeクラステンプレートとListクラステンプレートができた．これらをまとめてList.hという名前で保存する．

例題 13..8 Listクラステンプレート
次のテストドライバを実行するとどんな結果が得られるか調べよ．

#include <iostream>
#include "List.h"
int main()
{
List<string> friends;
friends.insert("Row, Tom");
friends.insert("Yocum, Ken");
friends.insert("Bergum, Jerry");
friends.insert("Kemp, Dan");
friends.print();
string name;
friends.remove(name);
cout << "削除:" << name << endl;
friends.print();
}

実行結果

$\begin{figure}% latex2html id marker 3978 \centering \includegraphics[width=13.2cm]{CPPPIC/reidai13-8.eps} \end{figure}$

反復子クラス(Iterator Classes)

コンテナオブジェクトでよく行なわれることは，オブジェクトの横断処理である．例えば，Listオブジェクトを横断するとは，Listのそれぞれの要素を訪ねるということである．例題13－8のListではこのことを，ディストラクタとprint()関数ともforループを用いて行なわれている．

反復子(iterator)はオブジェクトで，コンテナの内容を横断処理することができる．反復子はポインタと似ていて，一度にコンテナの1つの項目を見つけることができる．反復子には色々な種類があるが，どれも基本的には次の5つの機能を満たす．

コンテナのある場所で反復子を初期化する．
現在位置に格納されているデータの値を戻す．
現在位置に格納されているデータの値を変える．
反復子の現在位置に項目が存在しているか確認する．
コンテナの次の位置に進む．

これらの5つの機能は全ての反復子に搭載されているべきなので，これらの5つの関数の抽象基本クラスを宣言することに意味がある．コンテナクラスはテンプレートインスタンスとなるので，抽象基本クラステンプレートが必要になる．次に記すのが反復子の抽象基本クラステンプレートである．このファイルは後で使うのでIterator.hという名前で保存しておく．

template<class T>
class Iterator
{
public:
virtual void reset() = 0; //反復子の初期化
virtual T operator() () = 0; //現行の値を読む
virtual void operator=(T t) = 0; // 現行の値を書く
virtual int operator!() = 0; // 項目の存在を確認
virtual int operator++() = 0; // 次の項目へ進む
};

全ての純粋仮想関数プロトタイプは予約語"virtual"で始まり，コード"() = "で終わる．関数なので括弧が必要である．また，=0により純粋仮想関数になる．さらに，抽象基本クラスは少なくとも1つの純粋仮想関数を含んでいるクラスである．

この抽象基本クラステンプレートを用いて色々なコンテナクラスのための」反復子テンプレートを派生させる．

例題13－8のListクラステンプレートには明らかな欠点がある．それは挿入と削除が最初と最後でしかできないことである．そこで，次の例題でこの問題を解決するlist反復子を紹介する．

例題 13..9 Listクラステンプレートのための反復子クラステンプレート

#include "List.h"
#include "Iterator.h"
template<class T>
class ListIter : public Iterator<T>
{
public:
ListIter(List<T>& l) : list(l) {reset();}
virtual void reset() { previous = NULL; current = list.first;}
virtual T operator() (){return current->data;}
virtual void operator=(T t) {current ->data = t;}
virtual int operator!();
virtual int operator{\small ++}();
void insert(T t);
void preInsert(T t);
void remove();
protected:
ListNode<T>* current;
ListNode<T>* previous;
List<T>& list;
};

5つの基本機能に3つの関数を加えた．これにより，リストの途中でも挿入と削除が可能となった．

operator!()関数は2つの目的がある．1つは必要ならば現行のポインタをリセットし，そのポインタがナルかどうか報告する．

template<class T>
int ListIter<T>::{bf operator!()}
{
if (current == NULL)
if (previous == NULL) current = list.first;
else current = previous-{\small$>$}next;
return (current != NULL);
}

もし，currentとpreviousポインタが両方ともNULLならば，listが空か項目が1つしかないことになる．したがって，currentをlistのfirstポインタに設定すると，currentはNULLかlistの最初の項目を指すようになる．もし，currentがNULLでpreviousがノードを指していれば，currentをノードの後にくる項目を指すようにする．最後に，関数はcurrentがNULLかでないかで0または1を返す．これにより，関数は次の形で呼ぶことができる．
if (!it) . . .
ここで，itは反復子である．(!it)は反復子が存在すればと読める．なぜならば，currentがNULLでないとき，1を返すからである．この関数を用いて挿入関数や削除関数を呼ぶ前にcurrentポインタの状態を調べる．

operator++()はpreviousポインタを進めた後で，currentポインタを次の項目へ進めることにより反復子を増加させる．この動きはoperator!()がcurrentポインタがNULLであることを見つけたときと同じである．

template <class T$>
int ListIter<T>::operator{\small ++}()
{
if (current == NULL)
if (previous == NULL) current = list.first;
else current = previous-> next;
else {
previous = current;
current = current->next;
}
return (current != NULL);
}

この演算子によりlistの横断が簡単になる．つまり，
for (it.reset(); !it; ++it) . . .
と書くことができ，一般のforループを用いて配列を横断するのと同じである．これはlistの最初の項目を見つけるように反復子をリセットする．そして，その項目を訪れた後，反復子を増加し次の項目を訪ねるようにする．このループは!itが真である間繰り返される．

insert(t)関数はtの新しいノードを作成し，現行のノードのすす後にそのノードを挿入する．

template<class T>BR> void ListIter<$T>::insert(T t)
{
ListNode<T>* p = list.newNode(t, 0);
if (list.isEmpty()) list.first = p;
else {
p ->next = current->next;
current->next = p;
}
}

preinsert()関数はinsert()関数と似ているが，その違いはcurrentノードの前に新しいノードを挿入するところである．

template<class T>
void ListIter<T>::preInsert(T t)
{
ListNode<T>* p = list.newNode(t, current);
if (current == list.first) list.first = previous = p;
else previous-{\small$>$}next = p;
}

remove()関数はcurrentノードを削除する．

template<class T>
void ListIter<T>::remove()
{
if (current == list.first) list.first = current->next;
else previous->next = current->next;
delete current;
current = 0;
}

これらをListIter.hという名前で保存する．この反復子のテストドライバを次に示す．

#include "ListIter.h"
int main()
{
List{\small$<$}string{\small$>$} friends;
ListIter{\small$<$}string{\small$>$} it(friends);
it.insert("Row, TOm");
++it;
it.insert("Yocum, Ken");
++it;
it.insert("Bergum, Jerry");
++it;
it.insert("Kemp, Dan");
++it;
friends.print();
it.reset();
++it;
it = "Schmidt, Bob";
++it;
it.remove();
friends.print();
if(!it) it.preInsert("Webb, Bill");
friends.print();
for (it.reset(); !it; ++it)
it = "{" + it() + "}";
friends.print();
}

$\begin{figure}% latex2html id marker 3994 \centering \includegraphics[width=14.6cm]{CPPPIC/reidai13-9.eps} \end{figure}$

確認問題 13..1

1. 関数テンプレートとテンプレート関数の違いは何か

2. クラステンプレートとテンプレートクラスの違いは何か

3. ベクタの代わりに連結リストを用いる利点と欠点は何か

演習問題 13..1

1. 2つの値のうち小さいほうを返す関数テンプレートをインスタンス化するプログラムを作成せよ．

2. Queueクラスを生成するテンプレートを作成せよ．