STLというのはC++標準のテンプレートライブラリです。STLを知らないというのは、C言語で printf や malloc を知らないということと同じです。なんとしても覚えてください。
さて脅しはここまでにしておきましょう。STLは膨大な規模のライブラリで、プログラミング言語の標準としては他に例を見ないほどのものです。また分量だけでなく、その構造も難解で、これからC++を習得しようとする初学者の壁となっていきなり立ちはだかります。STLの学習にくじけている人は少なくないはずです。
しかし大規模で難解なSTLですが、無節操に多機能化しているわけではなく、むしろひとつの方針の上に体系化されていますので、その方針さえ理解できれば実はそれほど難しくありません。本を読んだりしていまいち納得できないのは、その方針がわかってないからでしょう。そこで今回はSTLが基盤としているデザインパターン、イテレーターについて説明します。
STLには、コンテナ、アルゴリズム、ストリームに加え、いくつかの有用なテンプレートが収められています。コンテナとは可変長配列やリスト、キューなど、データを収めるための構造です。アルゴリズムとは、検索やソートなど、コンテナに対する操作一般です。ストリームはファイルや画面に対する操作です。この中で特に重要なのはコンテナとアルゴリズムです。
例えば CData オブジェクトをリストで保存するなら list コンテナを使用します。その中から特定の CData を検索したければ find アルゴリズムで検索するだけです。双方向リストやキューや可変長配列といったコンテナや、ソートやサーチといったアルゴリズムをコーディングする必要は、C++を使っている限り一生ないのです。
STLで用意されているコンテナやアルゴリズムはすべてのオブジェクトを扱うことができます。こうした汎用性はイテレーター(反復子)によって実現されています。
イテレーターを簡単に言えば、仮想的なポインタです。ポインタについて基礎的なことがわかっていれば、イテレーターを理解するのは簡単です。まずはポインタによる検索ついて、復習がてらに見て下さい。
void foo()
{
const int MAX = 256;
CData d[MAX];
CData *f = DataFind(&d[0], &d[MAX], CData(80));
if (f == d[MAX]) throw Exception("Not Found");
}CData *DataFind(CData *start, CData *end, CData &match)
{
for (CData *i = start; i != end; i++)
if (*i == match)
break;
return i;
}
DataFind 関数は CData の配列から match と同じオブジェクトを見つけ出して返す関数です。
この関数にはいくつか奇妙なところがありますが、気づかれましたか? 従来のCによるプログラミングでこうした関数を作る場合、データが見つからなければ NULL を返すのが一般的だったと思います。しかしC++ではこのように、配列の最後尾から1つはみ出したところを指していたら失敗となります。これはイテレーターパターンと関係があります。
とにかく i というポインタが配列の先頭から最後まで1つづつ進んでいることに注目してください。またテンプレートを使用すれば、CData だけでなく、どのようなクラスにも適用できることに気づいてください。DataFind をテンプレートにすれば、以下のようになるでしょう。
template <class T> DataFind(T *start, T *end, const T &match)
{
for (T *i = start; i != end; i++)
if (*i == match)
break;
return i;
}
しかしこの関数は配列にしか使えないという欠点があります。配列にしか使えない理由は簡単で、ポインタを使っているからです。この欠点を解決するために、ポインタではなくイテレーターを使います。
class iterator : public __it
{
protected:
__link_type node;
public:
bool operator== (const iterator& x) const { return node == x.node; }
reference operator* () const { return (*node).data; }
pointer operator-> () const { return &(node->data); }
iterator& operator++ () { node = (__link_type)((*node).next); return *this; }
iterator& operator-- () { node = (__link_type)((*node).prev); return *this; }
};
上記は本物の list コンテナのイテレーターからの抜粋です。イテレーターはクラスオブジェクトですが、++ や -> といった演算子が利用されたときに、ポインタであるかのように振舞います。あるイテレーターがなんらかのオブジェクトへのポインタであるフリをしているとき、++ すると、次のポインタへ進んだフリをします。配列のイテレーターなら本当に++するだけですし、リストのイテレーターなら次のノードを参照するようにします。
要するにイテレーターとは、どんな複雑なメモリ管理をしているコンテナも、単純な配列であるかのようにテンプレートをダマす、仮想的なポインタなのです。
イテレーターはデザインパターンのひとつです。STLではイテレーターを積極的に活用することでコンテナとアルゴリズムの相互運用性を高めています。アルゴリズムを自作した場合でも、イテレーターパターンに従っていれば、どの標準コンテナに対しても使えるようになります。逆にコンテナにイテレーターを用意しておけば標準のアルゴリズムを使用することができます。そして、まったくお互いの存在を知ることなく作られたコンテナとアルゴリズムが、相互に利用可能になるわけです。
STL を使用したり拡張したりするには、STL が決めたイテレーターの振る舞いに従う必要があります。例えば find(foo.start(), foo.end()) == foo.end() ならば find が失敗であることを保証しないといけません。STL はコーディング規約という側面も持っているのです。
コンテナやアルゴリズムによって制限があることも知っておいて下さい。例えば binary_search はソート済みのコンテナに対してしか適用できませんし、sort はランダムアクセスできない list には適用できません(もちろんエラーが出ます)。
こうした細かい制限は、各コンテナの性質で仕方がなかったということもありますが、それよりもC++の設計思想に深い理由があります。研究段階からいつまでも脱却できない他のプログラミング言語と違って、C++は現場から厳しい要求を受けています。C++はあらゆる面でパフォーマンスに対して丹念に配慮してあり、STL もまた例外ではないのです。
イテレーターさえ理解できてしまえば、あとはヘルプや書籍を読むだけです。たくさんのコンテナやアルゴリズムがありますが、分量が多いだけで考え方はひとつしかありません。なんとかSTLを覚えて、楽チンプログラミングを堪能してください。もう双方向リストのバグで悩む必要が無いなんて、すばらしいと思いませんか?