STL (Standard Template Library

STL (Standard Template Library)

ここでは STLについて学ぶ。
※ 教科書の第14章「標準テンプレートライブラリ (STL)」もよく読んでSTLについて理解を深めること。

STL (Standard Template Library)

STL (Standard Template Library) とは、C++言語のテンプレート機能を利用して実装された C++言語の標準的なライブラリである。
その中には、プログラムを作成する上でよく利用されるリストやベクトル (可変長配列)などの便利なクラスや関数がテンプレートで実装されている。
これらはC++言語の機能をフルに使用して実装されているため、初心者には少々分かりにくくなっているが、使いこなせば非常に有用なライブラリである。

STLの実現方法は非常に高度で複雑ではあるが、その目指すところは単純で、ソフトウェアをコンテナ、アルゴリズム、イテレータ(反復子)といった構成要素に分解し、それらを自由に組み合わせられる汎用部品にしようというものである。

ここではSTLの中心的な存在である以下の3つの要素について説明する。

コンテナ
アルゴリズム
イテレータ (反復子)

※ 他にも関数オブジェクトやアダプタなど、STLを真に使いこなす上で重要な要素があるが、全てを説明するには時間が足りないためここでは説明しない。興味のある者は、STLに関する書籍を調べてみるとよい。

※ 教科書の 14.1節も参照せよ。

コンテナ

コンテナとは他のオブジェクトを格納するための入れ物である。
最も分かりやすいコンテナの例としては「配列」がある。
「配列」は int型、double型などの基本データ型や、構造体データなどを格納することができ、ランダムアクセスができる (インデックスで参照する要素を指定することができる)コンテナである。

STLにはいろいろなコンテナクラスが用意されているが、ここではその中からよく利用されるベクトル、リスト、マップについて説明する。

※ 教科書の 14.2節も参照せよ。

ベクトル (vector)

ベクトルとは可変長配列のことである。
(可変長配列とは、必要に応じてサイズを変更できる配列である)

具体的な使用例は以下の通りである。

  1 : //
  2 : // vector test
  3 : //
  4 : #include <iostream>
  5 : #include <vector>            // vectorを使用する
  6 : using namespace std;
  7 : 
  8 : // テンプレートを使って表示関数を定義
  9 : template <class X>
 10 : void print_vector(vector<X> vec)
 11 : {
 12 :     cout << "size=" << vec.size() << "\n";    // サイズを表示
 13 :     for (int i = 0; i < vec.size(); i++)
 14 :         cout << "v[" << i << "]=" << vec[i] << "\n";
 15 :     cout << endl;
 16 : }
 17 : 
 18 : void test_vector_int()
 19 : {
 20 :     vector<int>     vi(3);   // int型ベクトル (サイズ3)
 21 : 
 22 :     for (int i = 0; i < vi.size(); i++)
 23 :         vi[i] = i+1;         // 配列のようにアクセスできる
 24 : 
 25 :     // ベクトルの内容表示
 26 :     cout << "=== phase 1 (int) ===" << endl;
 27 :     print_vector(vi);
 28 : 
 29 :     // viの末尾に追加 (サイズが増加)
 30 :     vi.push_back(125);
 31 : 
 32 :     // ベクトルの内容表示
 33 :     cout << "=== phase 2 (int) ===" << endl;
 34 :     print_vector(vi);
 35 : 
 36 :     // ベクトルのサイズを 2増やす
 37 :     vi.resize(vi.size() + 2);
 38 :     for (int i = 0; i < vi.size(); i++)
 39 :         vi[i] = (i+1)*3;
 40 : 
 41 :     // ベクトルの内容表示
 42 :     cout << "=== phase 3 (int) ===" << endl;
 43 :     print_vector(vi);
 44 : }
 45 : 
 46 : void test_vector_double()
 47 : {
 48 :     vector<double>  vd(3);   // double型ベクトル (サイズ3)
 49 : 
 50 :     for (int i = 0; i < 3; i++)
 51 :         vd[i] = (i+1) * 0.1;
 52 : 
 53 :     // ベクトルの内容表示
 54 :     cout << "=== phase 1 (double) ===" << endl;
 55 :     print_vector(vd);
 56 : 
 57 :     // vdの末尾に追加 (サイズが増加)
 58 :     vd.push_back(1.25);
 59 : 
 60 :     // ベクトルの内容表示
 61 :     cout << "=== phase 2 (double) ===" << endl;
 62 :     print_vector(vd);
 63 : 
 64 :     // ベクトルのサイズを 2増やす
 65 :     vd.resize(vd.size() + 2);
 66 :     for (int i = 0; i < vd.size(); i++)
 67 :         vd[i] = (i+1)*0.3;
 68 : 
 69 :     // ベクトルの内容表示
 70 :     cout << "=== phase 3 (double) ===" << endl;
 71 :     print_vector(vd);
 72 : }
 73 : 
 74 : int main()
 75 : {
 76 :     test_vector_int();
 77 :     test_vector_double();
 78 : 
 79 :     return 0;
 80 : }

(ダウンロード)

vectorを使用する場合には、vectorをインクルードする必要がある。 (上記サンプルコードでは、5行目で vectorをインクルードしている)

18行目から44行目までがint型を格納する vectorの使用例、 46行目から72行目までがdouble型を格納する vectorの使用例である。
各データ型の vectorの作成方法は汎用クラスのインスタンス化の場合と同様にすればよい。例えば、int型の vectorを作成する場合は "vector<int>" double型の vectorを作成する場合は "vector<double>" と記述する。

また、このサンプルコードでは、vectorに格納されているデータを表示する関数をテンプレートを用いることで、データ型に依存しない形で定義している。 (9行目から16行目の関数 print_vector() )

上記サンプルコードの実行結果は以下の通りになる。
前半がint型のvector、後半がdouble型のvectorについての表示結果である。

=== phase 1 (int) ===
size=3
v[0]=1
v[1]=2
v[2]=3

=== phase 2 (int) ===
size=4
v[0]=1
v[1]=2
v[2]=3
v[3]=125

=== phase 3 (int) ===
size=6
v[0]=3
v[1]=6
v[2]=9
v[3]=12
v[4]=15
v[5]=18

=== phase 1 (double) ===
size=3
v[0]=0.1
v[1]=0.2
v[2]=0.3

=== phase 2 (double) ===
size=4
v[0]=0.1
v[1]=0.2
v[2]=0.3
v[3]=1.25

=== phase 3 (double) ===
size=6
v[0]=0.3
v[1]=0.6
v[2]=0.9
v[3]=1.2
v[4]=1.5
v[5]=1.8

※ 教科書の 14.3節も参照せよ。

(線形)リスト (list)

双方向の(線形)リストである。
リストであるためランダムアクセスはできず、シーケンシャル(順次)にしかアクセスができない。
また、双方向であるため、前方にも後方にもアクセスができるようになっている。

具体的な使用例は以下の通りである。

  1 : //
  2 : // list test
  3 : //
  4 : #include <iostream>
  5 : #include <list>              // listを使用する
  6 : using namespace std;
  7 : 
  8 : const int MaxNameLen = 20;
  9 : 
 10 : class Student {
 11 :     char    name[MaxNameLen];
 12 :     int     point;
 13 : public:
 14 :     void    setName(const char *n) { strncpy(name, n, MaxNameLen); }
 15 :     char    *getName() { return name; } 
 16 : 
 17 :     void    setPoint(int po) { point = po; }
 18 :     int     getPoint() { return point; }
 19 : 
 20 :     void    print() {
 21 :         cout << "name=" << name << " point=" << point << endl;
 22 :     }
 23 : };
 24 : 
 25 : void print_list(list<Student> stlst)
 26 : {
 27 :     int total_sum = 0;
 28 : 
 29 :     cout << "size=" << stlst.size() << endl;
 30 :     for (list<Student>::iterator i = stlst.begin(); i != stlst.end(); i++) {
 31 :         i->print();
 32 :         total_sum += i->getPoint();
 33 :     }
 34 :     cout << "average=" << ((double)total_sum / stlst.size()) << endl;
 35 : }
 36 : 
 37 : int main()
 38 : {
 39 :     list<Student> stlst;     // Studentクラスのリスト (サイズ 0)
 40 :     int total_sum;
 41 :     Student st;
 42 : 
 43 :     // リストに追加 (サイズが増加)
 44 :     st.setName("Hamm"); st.setPoint(7);
 45 :     stlst.push_back(st);
 46 :     st.setName("Slink"); st.setPoint(4);
 47 :     stlst.push_back(st);
 48 :     st.setName("Potato"); st.setPoint(6);
 49 :     stlst.push_back(st);
 50 : 
 51 :     // リストの内容表示
 52 :     cout << "=== phase 1 ===\n";
 53 :     print_list(stlst);
 54 : 
 55 :     // リストに追加 (サイズが増加)
 56 :     st.setName("Woody"); st.setPoint(8);
 57 :     stlst.push_back(st);
 58 :     st.setName("Sarge"); st.setPoint(9);
 59 :     stlst.push_back(st);
 60 : 
 61 :     // リストの内容表示
 62 :     cout << "=== phase 2 ===\n";
 63 :     print_list(stlst);
 64 : 
 65 :     return 0;
 66 : }

(ダウンロード)

listを使用する場合は、listをインクルードする必要がある。
(上記サンプルコードでは、5行目で listをインクルードしている)

このサンプルコードでは、Studentクラスを定義し(10行目から23行目)、 Studentのリストを作成している(39行目)。

また、リストに格納されているデータを表示する関数 print_list() (25行目から35行目)では、後述するイテレータ(反復子)を用いている。

上記サンプルコードの実行結果は以下の通りになる。

=== phase 1 ===
size=3
name=Hamm point=7
name=Slink point=4
name=Potato point=6
average=5.66667
=== phase 2 ===
size=5
name=Hamm point=7
name=Slink point=4
name=Potato point=6
name=Woody point=8
name=Sarge point=9
average=6.8

※ 教科書の 14.4節も参照せよ。

マップ (map)

マップとはキー(key)と値(value)を対応付けるデータ構造を持つコンテナクラスである。
(注：ここで説明するmapではあるキーに対しては一意となる値しか格納することができないようになっている。重複したキーを許す(つまり、同じキーに対して異なる複数の値を対応付ける) マップを使いたい場合は multimapを使用する)

具体的な使用例は以下の通りである。

  1 : //
  2 : // map test
  3 : //
  4 : #include <iostream>
  5 : #include <map>               // mapを使用する
  6 : #include <string>            // stringクラスを使用する
  7 : using namespace std;
  8 : 
  9 : int main()
 10 : {
 11 :     map<string, int> symtab;         // 文字列からintへのマップ
 12 :     map<string, int>::iterator i;    // イテレータ
 13 : 
 14 :     // マップに登録
 15 :     symtab.insert(pair<string, int>("red", 1));
 16 :     symtab.insert(pair<string, int>("green", 2));
 17 :     symtab.insert(pair<string, int>("blue", 4));
 18 : 
 19 :     // マップの中身を表示
 20 :     cout << "=== map ===\n";
 21 :     for (i = symtab.begin(); i != symtab.end(); i++) {
 22 :         cout << i->first << "=" << i->second << endl;
 23 :     }
 24 : 
 25 :     // マップを使って検索
 26 :     cout << "=== search ===\n";
 27 :     i = symtab.find("red");
 28 :     cout << i->first << "=" << i->second << endl;
 29 :     i = symtab.find("blue");
 30 :     cout << i->first << "=" << i->second << endl;
 31 : 
 32 :     return 0;
 33 : }

(ダウンロード)

mapを使用する場合は、mapをインクルードする必要がある。
(上記サンプルコードでは、5行目で mapをインクルードしている)

このプログラムでは文字列と整数値を対応付けるマップを作成している。
ここで、文字列を後述する stringクラスを用いて実現している。
(そのために必要なヘッダ string を6行目でインクルードしている)

実行結果は以下の通りになる。

=== map ===
blue=4
green=2
red=1
=== search ===
red=1
blue=4

※ 教科書の 14.5節も参照せよ。

アルゴリズム

(STL での) アルゴリズムとは、(その言葉通りに)アルゴリズムを型に依存しない形で汎用化したものである。
例えば、「ソートする」という作業はそれ自体はデータ構造に依存しないはずだが、実際にプログラムを作成する場合は、配列には配列用のソート関数、リストにはリスト用のソート関数を記述する必要があった。
これを、配列やリストなどのデータ構造(つまり型)に依存しない形で実現したものを用意することで、どんな型にでも利用できるようにしたものが、ここでいう「アルゴリズム」である。

STLのアルゴリズムを使用する場合は、algorithmをインクルードする必要がある。

具体的な使用例は以下の通りである。

  1 : //
  2 : // algorithm test
  3 : //
  4 : #include <iostream>
  5 : #include <vector>                   // vectorを使用する
  6 : #include <algorithm>                // algorithmを使用する
  7 : using namespace std;
  8 : 
  9 : int main()
 10 : {
 11 :     vector<int>     vi;             // int型ベクトル (サイズ0)
 12 :     vector<int>::iterator iter;     // イテレータ
 13 : 
 14 :     for (int i = 0; i < 10; i++)
 15 :         vi.push_back((i*7+3)%11);  // 要素を1個追加
 16 : 
 17 :     // ソート前のベクトルの内容表示
 18 :     cout << "=== before sort ===" << endl;
 19 :     for (iter = vi.begin(); iter != vi.end(); iter++)
 20 :         cout << *iter << "\n";
 21 :     cout << endl;
 22 : 
 23 :     // ベクトルの内容をソート
 24 :     sort(vi.begin(), vi.end());
 25 : 
 26 :     // ソート後のベクトルの内容表示
 27 :     cout << "=== after sort ===" << endl;
 28 :     for (iter = vi.begin(); iter != vi.end(); iter++)
 29 :         cout << *iter << "\n";
 30 :     cout << endl;
 31 : 
 32 :     // ベクトルの内容を反転
 33 :     reverse(vi.begin(), vi.end());
 34 : 
 35 :     // 反転後のベクトルの内容表示
 36 :     cout << "=== after reverse ===" << endl;
 37 :     for (iter = vi.begin(); iter != vi.end(); iter++)
 38 :         cout << *iter << "\n";
 39 :     cout << endl;
 40 : 
 41 :     return 0;
 42 : }

(ダウンロード)

ここでは、ソートを行なうアルゴリズム sort()と、内容の逆順にする reverse()を使った例を示す。
sort()と reverse()のテンプレート指定はそれぞれ以下の通りであり、処理対象の範囲を後述するイテレータ (反復子)により与えるようになっている。

template <class RandIter>
  void sort(RandIter start, RandIter end);

template <class BiIter>
  void reverse(BiIter start, BiIter end);

実行結果は以下の通りになる。

=== before sort ===
3
10
6
2
9
5
1
8
4
0

=== after sort ===
0
1
2
3
4
5
6
8
9
10

=== after reverse ===
10
9
8
6
5
4
3
2
1
0

※ 教科書の 14.6節も参照せよ。

イテレータ (反復子)

イテレータ(反復子) とは、コンテナに対しての操作のうち頻繁に利用される「順に参照する」という操作を汎用化したものである。
例えば、以下のようなforループやリストを順に辿るコードはよく使用されるが、これらはデータ構造(型)に依存している。

/* 配列を端から順に参照 */
for (i = 0; i < N; i++)
    process(a[i]);

/* リストを端から順に参照 */
for (p = base; p != NULL; p = p->next)
    process(p->data);

しかし、本来これらは「先頭から最後尾まで要素を1つずつ参照する」という意味では同じものである。
この「先頭から最後尾まで要素を1つずつ参照する」という操作を汎用化したものが、イテレータである。

ここで「先頭から最後尾まで要素を1つずつ参照する」という操作を細かく分解してみると以下の4つの操作が出来ればよいことが分かる。

先頭位置の設定
次の要素への移動
要素の参照
終了位置の判定

イテレータでは上記の4操作を以下のようにして実現する。

先頭位置の設定 … begin()メソッドの値を設定
次の要素への移動 … インクリメント演算子 ++
要素の参照 … 間接演算子 *
終了位置の判定 … end()メソッドの結果との比較

以下のようにしてこの4つの操作を用いることで、要素を順次参照するという操作が実現できる。

※ vは vectorや listなどのコンテナクラスのオブジェクト
   iterはコンテナクラスに対応したイテレータ

for (iter = v.begin(); iter != v.end(); iter++)
    process(*iter);

このforループにおいて、最初の iter = v.begin()により、先頭位置の設定を行なっている。
次の iter != v.end()により、終了位置に到達したかどうかを判定している。
3つ目の iter++により、次の要素への移動を行なっている。
そして、最後にループボディにある *iterにより、要素の参照を行なっている。

4つの操作は各コンテナクラスによって実装は異なる(つまりvectorは vector、 listは listに応じた実装が必要)が、使う側の立場からすれば、中がどういう実装になっているかは気にする必要はない。

具体的な使用例は以下の通りである。

  1 : //
  2 : // iterator test
  3 : //
  4 : #include <iostream>
  5 : #include <vector>                   // vectorを使用する
  6 : #include <list>                     // listを使用する
  7 : using namespace std;
  8 : 
  9 : void test_vector()
 10 : {
 11 :     vector<int>     vi;             // int型ベクトル (サイズ0)
 12 :     vector<int>::iterator iter;     // イテレータ
 13 : 
 14 :     cout << "[vector]" << endl;
 15 : 
 16 :     for (int i = 0; i < 5; i++)
 17 :         vi.push_back(i+1);          // 要素を1個追加
 18 : 
 19 :     // ベクトルの内容表示
 20 :     cout << "=== phase 1 ===" << endl;
 21 :     for (iter = vi.begin(); iter != vi.end(); iter++)
 22 :         cout << *iter << "\n";
 23 :     cout << endl;
 24 : 
 25 :     // ベクトルの内容変更
 26 :     for (iter = vi.begin(); iter != vi.end(); iter++)
 27 :         *iter += 1;                 // 要素の値を1増加
 28 : 
 29 :     // ベクトルの内容表示
 30 :     cout << "=== phase 2 ===" << endl;
 31 :     for (iter = vi.begin(); iter != vi.end(); iter++)
 32 :         cout << *iter << "\n";
 33 :     cout << endl;
 34 : }
 35 : 
 36 : void test_list()
 37 : {
 38 :     list<int>     li;               // int型リスト (サイズ0)
 39 :     list<int>::iterator iter;       // イテレータ
 40 : 
 41 :     cout << "[list]" << endl;
 42 : 
 43 :     for (int i = 0; i < 5; i++)
 44 :         li.push_back(i+1);          // 要素を1個追加
 45 : 
 46 :     // リストの内容表示
 47 :     cout << "=== phase 1 ===" << endl;
 48 :     for (iter = li.begin(); iter != li.end(); iter++)
 49 :         cout << *iter << "\n";
 50 :     cout << endl;
 51 : 
 52 :     // リストの内容変更
 53 :     for (iter = li.begin(); iter != li.end(); iter++)
 54 :         *iter *= 2;                // 要素の値を2倍
 55 : 
 56 :     // リストの内容表示
 57 :     cout << "=== phase 2 ===" << endl;
 58 :     for (iter = li.begin(); iter != li.end(); iter++)
 59 :         cout << *iter << "\n";
 60 :     cout << endl;
 61 : }
 62 : 
 63 : int main()
 64 : {
 65 :     test_vector();                  // ベクトル版
 66 :     test_list();                    // リスト版
 67 : 
 68 :     return 0;
 69 : }

(ダウンロード)

9行目から34行目の関数 test_vector() がvectorクラスでイテレータを使った例、
36行目から61行目の関数 test_list() がlistクラスでイテレータを使った例である。
データの表示や更新のためのループの記述方法が同じであることが分かる。

実行結果は以下の通りになる。

[vector]
=== phase 1 ===
1
2
3
4
5

=== phase 2 ===
2
3
4
5
6

[list]
=== phase 1 ===
1
2
3
4
5

=== phase 2 ===
2
4
6
8
10

前半が vectorに対してイテレータを用いて操作をした場合の表示結果で、後半が listに対してイテレータを用いて操作をした場合の表示結果である。

文責：大津