ＳＴＬ演習

ＳＴＬの概要
コンテナ
反復子
アルゴリズム
関数オブジェクト
演習問題
演習問題のプログラム解答例
ＳＴＬ関連のリンク

1. ＳＴＬの概要

ＳＴＬは、一言で言えば、テンプレートのライブラリです。Ｃ＋＋の標準ライブラリとして汎用性の高いものになるはずです。（９８年現在：過渡期でそうでもない。）
内容としては、

コンテナ
反復子
アルゴリズム
関数オブジェクト

などがあります。
また、コンテナには、ベクタ、リスト、両端キュー、セット、マルチセット、マップ、マルチマップ、スタック、キュー、優先順位キューがあります。

反復子はコンテナを参照、操作するためのもので、ある決められたインターフェースを備えているものは何でも反復子となれます。
反復子は入力（出力）反復子、前方反復子、両方向反復子、ランダムアクセス反復子があります。また、後ろのものは前のものとしても使えます。（前方反復子は、入力反復子であり、ランダムアクセス反復子は他の全ての反復子として使えます。）

アルゴリズムは、コンテナに対して様々な処理を行う関数の集まりです。
例えば、

fill		初期値でうめる
copy		コピー
generate	生成
find		条件に合う値を探す
for_each	全ての要素に対し操作を行う

などがあります。（参照：役に立つ汎用アルゴリズム）

関数オブジェクトは関数のように振る舞うオブジェクトです。（）演算子メンバ関数を持っていれば関数オブジェクトになれます。

2. コンテナ

ここでは､ベクタとリストの使い方を説明します。その他のコンテナはヘルプを参照して下さい。コンテナやアルゴリズムを使うためには、ヘッダーをインクルードする必要があります。今回の演習では、以下のものをインクルードして下さい。

#include <vector>
#include <list>
#include <algorithm>
using namespace std;

using ... はＳＴＬを使うために必要なものです。とりあえずおまじないだと思って覚えてください。

まず、ベクタを使って見ましょう。配列と同じように使えます。（VC++4.2では、さらにおまじないが必要になりますが、今回は説明を省略します。）

	vector<int>	vec(10);
	for (int i=0;i<10;++i) vec[i] = i;

最初の宣言で１０個のintを使うことを宣言しています。（注意：ＭＦＣのコレクションクラスと違い、添え字の範囲チェックや自動拡張などはサポートされていません。間違って使用した場合、配列と同じく何が起きるか分かりません。）

リストも殆ど使い方は同じです。

	list<int>	lst;
	for (int i=0;i<10;++i) lst.push_back(i);

3. 反復子

まず、使ってみましょう。さっきのベクタを使います。

	vector<int>	vec(10);
	vector<int>::iteartor it;
	for (it=vec.begin();it!=vec.end();++it) *it = i;

（注意：時として、(*it).func()のような書き方が出てきますが、 it->func()に直さないで下さい。itが反復子の場合、後者はコンパイルエラーになることがあります。（ならないこともあります。）なぜなら反復子はポインタと同じように振る舞っても、ポインタではないからです。）
（1998/8/20 注：「More Effective C++」の91ページによれば、 1995年7月標準化委員会は、反復子の->演算子サポートを決定したそうです。ということは、it->func() と使ってもよいということですね。）

次に、リストについてもやってみましょう。ベクタと同じように書くことができます。

重要:
２つの反復子を使ってシーケンスを表します。その場合、最初の反復子から次の反復子の直前までが対象となります。

4. アルゴリズム

ＳＴＬの特徴として、アルゴリズムとコンテナの独立性があげられます。例えば、copy というアルゴリズムは、ベクタでもリストでも使うことができます。但し、実際にアルゴリズムが認識するのは反復子だけです。また、通常の配列も同じように扱うことができます。その場合、反復子はポインタになります。（ポインタがランダムアクセス反復子としてのインターフェースを持っているからです。）

今回の演習では、以下のアルゴリズムを使うのでヘルプで調べて使えるようにして下さい。この他にもいろいろあります。

for_each
copy
generate
accumulate
next_permutation

２つほど、使い方を見てみましょう。

	copy(vec.begin(),vec.end(),ostream_iterator<int,char,char_traits<char> >(cout));

３番目の引数は、出力ストリーム反復子と呼ばれるものです。呪文だと思って覚えて下さい。うまくいけば、「0123456789」と出力されます。
（注意：「> >」を「>>」と書かないで下さい。コンパイルエラーになります。）

	next_permutation(vec.begin(),vec.end());

順番に順列が生成されます。vec のサイズが３であれば、「123」、「132」、「213」、「231」、「312」、「321」となります。「321」の次は、また「123」に戻りますが、そのときだけfalse を返します。

ちなみにvec の代わりにlst でも、あるいは次のような配列でもＯＫです。

	int	ary[10];
	next_permutation(ary,ary+10);

シーケンスは途中でもＯＫです。

	next_permutation(ary+2,ary+5);

アルゴリズムで使える反復子は、プロトタイプ宣言の変数名を見ると、ある程度推測できます。

5. 関数オブジェクト

これも例からいきましょう。

	template <class T>
	class FuncObj {
	public:
		FuncObj(T t) : val(t) {}
		T operator()(T t){return val + t;}
	private:
		T	val;
	};

これが、関数オブジェクトのクラス定義です。（テンプレートクラスである必要はありません。）次のように使えます。

	FuncObj<int>	fo(3);
	cout << fo(4);		// ７と出力される

（）演算子を使うと関数のように見えるので関数オブジェクトといいます。ちなみに、上の例とよく似たものでplus という関数オブジェクトがＳＴＬにあります。
ＳＴＬのライブラリの中には通常の関数ではなく関数オブジェクトしか受け取らないものもあります。また、上のようにインラインで定義してあると、アルゴリズムを用いた場合、非常に高速に動くプログラムになります。

よくある例を１つ。

	class Gen {
		int	i;
	public:
		Gen(){i = 0;}
		int operator()(){return ++i;}
	};
		vector<int>	v(10);
		generate(v.begin(),v.end(),Gen());

こうすると、v が１から１０で初期化されます。

6. 演習問題

８クィーン
８×８の桝目に８つのクィーンを互いに取られないように置くという問題です。クィーンは将棋の飛車と角を合わせた動きをします。
全ての配置を求めて下さい。下の答えは16837425という出力で構いません。

○ . . . . . . .

. . . . . . ○ .

. . . ○ . . . .

. . . . . ○ . .

. . . . . . . ○

. ○ . . . . . .

. . . . ○ . . .

. . ○ . . . . .

1 6 8 3 7 4 2 5
魔方陣
３×３のマスに１から９までの数字を入れて、縦・横・斜めの和が全て１５になるものを全て求めてください。下の答えは、276951438という出力で構いません。

2 7 6

9 5 1

4 3 8
小町算
1+2+3-4+5+6+78+9=100
というように、１から９までの数字を順番に使って＋と－を間に入れて１００になるような式を全て求めて下さい。
（－で始まる場合も含めて１２通りあります。）

ヒント：「８クィーン」と「魔方陣」は順列を使います。「小町算」はいろいろやり方はありますが、generate を使うとＳＴＬらしいでしょう。

7. 演習問題のプログラム解答例

先頭へ

戻る

○	.	.	.	.	.	.	.
.	.	.	.	.	.	○	.
.	.	.	○	.	.	.	.
.	.	.	.	.	○	.	.
.	.	.	.	.	.	.	○
.	○	.	.	.	.	.	.
.	.	.	.	○	.	.	.
.	.	○	.	.	.	.	.

○	.	.	.	.	.	.	.
.	.	.	.	.	.	○	.
.	.	.	○	.	.	.	.
.	.	.	.	.	○	.	.
.	.	.	.	.	.	.	○
.	○	.	.	.	.	.	.
.	.	.	.	○	.	.	.
.	.	○	.	.	.	.	.

○	.	.	.	.	.	.	.
.	.	.	.	.	.	○	.
.	.	.	○	.	.	.	.
.	.	.	.	.	○	.	.
.	.	.	.	.	.	.	○
.	○	.	.	.	.	.	.
.	.	.	.	○	.	.	.
.	.	○	.	.	.	.	.