Last update 1999/08/07
(C)平山直之
無断転載は禁止、リンクはフリー
誤字脱字の指摘は歓迎
STLの知名度が意外と低いので、啓蒙のためにSTL入門を書くことにします。普段双方向リンクリストや動的配列のコードを書くのに飽きている人は、読んでみてください。絶対使ったほうがラクですから。
STLはC++の「テンプレート」という機能を使っていますので、普段C/C++コンパイラをCコンパイラとして使ってる人も、C++コンパイラとして使わなければなりません。STLをただ使うだけなら大して難しくはないので、C++をbetter Cとして使うのもよいかと思います。これ以後もそのような前提で説明します。よく分からないことがあったら掲示板で質問してください。
※要するにCが解っている人向け※
STLとは、動的配列や双方向リンクリスト、連想配列などといった基本的なデータ構造を、type-safeかつ最小コーディングで再利用するためのライブラリです。ライブラリとはいっても、ほとんどtemplateでできているので、ヘッダファイルをインクルードすればすぐ使えます（バイナリライブラリのリンクは必要ありません）。
STLの各コンポーネントはヘッダファイルで提供されます。したがって、使いたいヘッダファイルをインクルードすれば事足ります。インクルードファイルはC++Builder/VisualC++なら標準のディレクトリに置かれていますので、フツーにstdio.hなんかをインクルードするのと同じようなつもりでやればOKです。
たとえば、動的配列（vector）を使うには、
#include <vector>とします。ヘッダファイル名に".h"がつかないのはC++の規約であって、間違いではありません。includeディレクトリを覗いてみればわかりますが、実際にそういうファイルが置いてあります。
同様に、双方向リンクリスト、セット、連想配列を使うときはそれぞれ
#include <list> #include <set> #include <map>とします。
C++の新機能に、「ネームスペース」というものがあります。これはライブラリなどでの名前の衝突を避けるための機能ですが、面倒なので説明は省略します。知りたい人はC++の本を読んで下さい。とりあえずここでは、まじないだと思って、ソースファイルの最初のほう（ヘッダファイルの次くらい）に
using namespace std;と書いておいてください。
ネームスペースが解る人への説明
ちなみに、私はusingしないで、いちいちstd::と指定しています。タイピングが面倒でなければそうした方がよいと思います。
例として、動的配列（vector）を作ってみましょう。大きさを与えないで作るには
vector<int> v;
などとします。これで要素がint型でvという名の動的配列が作られます。要素の型を指定するところ（例で言うと「int」のところ）には、スカラ型でもポインタでも構造体でも好きな型を置いて構いません。
大きさを指定したい場合は、
vector<int> v(256);などとします。
templateが解らない人への説明
templateとは、簡単に言うとマクロのかっこいい奴です。<>という記号についてはこういうもんだと思い込んでください。とりあえずそれで問題ありません。詳しく知りたい場合は自分で調べてください。
要素へのアクセス
vectorの要素にアクセスするには、フツーの配列のように
v[10]=173;とするのですが、まだ大きさを指定していない場合、いきなりこうやってもアクセス例外が出るだけです。動的配列といっても、単に大きさをいつでも変えられるだけで、perlのように大きい添え字にアクセスすると自動的に拡張されるわけではないのです。そういうわけで、大きさを変えるには、
v.resize(20);などとします。これで0から19までのスロットにアクセスできるようになります。
自動的に拡張されないのはいくつか理由があると思いますが、主に処理速度を重視しているためだと思われます。
C++が解らない人への説明
ベクタの要素アクセスのスピードは、コンパイラの最適化（関数のインライン展開）がかかっている場合フツーの配列と同じです。
C++が解る人への説明
実際には、ベクタのオーバーロード演算子関数operator[](int n)は、添え字の示す場所への参照を返すだけです。だから範囲外だとアクセス例外が出ます。
要素へのアクセス（その２）
もう一つよく使うやり方を書いておきましょう。配列の末尾に要素を一つ追加するやり方です。これはvectorだけでなく、双方向リンクリスト（list）でも使えます。
v.push_back(94);これで配列の大きさが1大きくなって、末尾に指定した要素が追加されます。
効率が気になる人への説明
実際のメモリ割り当ては適当な単位で行われますので、push_backを呼び出すたびにmallocとmemcpyが実行し直される、というようなことはありません。実際には、何百回かに一回まとめて実行されます。
ただし、はじめから挿入する要素数が解っている場合は、resizeしてから[]（もしくは後述のイテレータ）を使うか、
v.reserve(256);としたほうが効率的です。reserveは、指定した要素数に見合う分だけメモリを確保しておくメンバ関数であり、push_back()やresize()を行うまで実際の配列の大きさは変更されません。
要素数を得る
配列の実際の要素数を得るには、size()を使います。
int n=v.size();という感じです。
ポインタが解らない人は出直してきてください。
その前に
とりあえずC++のbetter Cとしての新機能ですが、forの第一要素で変数の宣言ができますので覚えといてください。
走査
配列やリストを走査するときの決まり文句として、
for(char* p=&v[0];p<&v[256];p++){...} for(node* p=first->next;p!=first;p=p->next){...}みたいなのがありますね。配列やリンクリストならこの程度ですみますが、ハッシュ表や２分木なんかでいちいちこんなことをやるのはかったるくて仕方がありません。またこれでは一般性がなく、データ構造を変えれば修正を余儀なくされます。こうしたコードが散らばっていると、効率の調査のためにデータ構造を気軽に変えるようなことができなくなるわけです。
そこで、STLでは、これらを一般化した「イテレータ」という概念を用意しています。
イテレータを使えば、vector,list,set,mapなどシーケンシャルに処理をする可能性があるデータ構造（シーケンスと呼びます）の要素の列挙を、すべて同じ方法で行うことができます。
実際にはこのようにします。
for(vector<int>::iterator i=v.begin();i!=v.end();i++);これで、vectorのところをlist/set/mapなどに代えても同じように動作します。このときの変数「i」がイテレータです。listなんかは[]演算子がないので、要素にアクセスする方法は他にはほとんどありません。
イテレータを用いて要素にアクセスするには、ポインタだと思えばokです。実際、vectorのイテレータは、classスコープでiteratorとtypedefされているだけで、本当にポインタです（ヘッダを覗いてみましょう）。一方、listでは、ポインタのような操作ができるように作られたlist::iteratorというクラスのインスタンスです。
たとえば、vectorの全要素に7を足すには
for(vector<int>::iterator i=v.begin();i!=v.end();i++){ *i+=7; }とすればOkです。
[begin,end)
イテレータであるiに代入したり比較したりしていることからも分かるように、
vector::begin()
vector::end()
もイテレータを返すメンバ関数です。
STLでは、これらのメンバ関数について、
beginはシーケンスの最初の要素を指すイテレータを返す
endはシーケンスの最後の要素の次の要素を指すイテレータを返す
と明確に定めています。ですから、*(begin())は有効ですが、*(end())は無効なのです。
このことを明確に表すために、STLではしばしば
[begin,end)
という表記をします。誤植ではないので注意してください。
ワンポイント
せっかくだから、マクロでも定義しちゃいましょうか。こんな感じで。
#define foreach(a,b,c) \ for(a::iterator c=(b).begin();(c)!=(b).end();(c)++) #define const_foreach(a,b,c) \ for(a::const_iterator c=(b).begin();(c)!=(b).end();(c)++)もちろん、こういうふうに使います。
foreach(std::vector<int>,v,i){ ... }これでも十分便利なんですけど、こんなとき「typeofっていう演算子があったらなあ」と思いませんか？ 私はよく思います。このマクロで言えば、マクロ引数の「a」はなくてもいいはずなんです。そうできれば、
foreach(v,i){ ... }と書けるんですね。もしこう書ければ、データ構造の変更の影響を受けることもないし、ああ、なんて極楽なんでしょうか。
注意点
listのイテレータはポインタではないので（正確にいうとポインタでもランダムアクセスイテレータでもないため）、いくつか制限があります。
大小比較の結果が順番と一致しない
大小比較の結果は順番と一致しません。したがって、
for(list<x>::iterator i=l.begin();i!=l.end();i++)を、
for(list<x>::iterator i=l.begin();i<l.end();i++)とは書けません。ですから、vectorでも大小比較ではなく等号・不等号を使っておくほうが便利です（後で変更がしやすいからです）。
インクリメントとデクリメント以外の演算ができない
単に実装されてないだけなので仕方ありません。listはランダムアクセスすべき物ではないという思想による仕様のようです。それでも任意の数を足したりしたい場合は、<algorithm>（このヘッダファイルの名前は8文字を超えるため、処理系・バージョンなどによって違う多少可能性があります。本当のファイル名は自分で確認してください）をインクルードして
advance(i,n);などとします。
->が実装されていない
->が実装されていないので、構造体を要素に持った場合でも
(*i).foo=bar;などと組み合わせて使わなければなりません。
typedefすべし
今までは説明のために生のテンプレートで使ってきましたが、なるべく
typedef vector<int> int_vector;などと別名を作ってからから使いましょう。いままで書いてきたような注意点を守っていれば、こうすることで他のデータ型との交換が容易になるからです。例えば、私の経験ですが、以前「要素の削除が妙に遅い」と感じてvectorをsetに置き換えてみたら、それだけで桁違いに速くなったことがありました。
もっとも、ここでint_vectorなんて名前をつけたら、変えたときにちょっと格好悪いですけどね。必要に応じてもうちょっと汎用的な名前をつけるべきでしょう。候補としては、
array
container
sequence
……s
辺りが挙げられるでしょうか。自分なりに考えてみてください。
きりがないのでこれで最後にします。
アルゴリズム
STLには、前述のイテレータという汎用ポインタを利用したアルゴリズムがたくさん用意されています。イテレータを利用しているため、ほとんどのアルゴリズムをすべてのデータ構造に対して適用することができます（制限があってできないものやある種のデータ構造には適用しても無意味なものも少なくありませんが）。また、当然ながら、標準のコンテナと同じインターフェイスを持つコンテナを作れば、これらのアルゴリズムを適用することができます。例えば私は以前、ギャップバッファ（emacsなんかがバッファ管理に用いているアルゴリズム）のようなベクタを作ったことがあります。
これらを利用するには、<algorithm>をインクルードします。
以下に例を挙げてみます。
検索
find(v.begin(),v.end());成功した場合は発見した要素を指すイテレータ、失敗した場合は渡した第2引数が返ります。
ランダムにシャッフル
random_shuffle(v.begin(),v.end());ソート
sort(v.begin(),v.end());ユニーク（隣接する「等しい」オブジェクトを取り除く）
unique(v.begin(),v.end());こうしたアルゴリズムでは、よく要素の比較（<,==,!=など）が行われるので、データ構造の要素が構造体の場合など、比較演算子をオーバーロードしておかなければならないことがあります。
これ以外については、各自文献を参照したりヘルプを読んだり（VC++のが詳しいです）algorithmを解析したりするなどして自習に励んでください。
もうvectorとかlistとかstringとかを自分で作るのはやめて、標準ライブラリを使ってください。
ではまたお会いしましょう。
(C) 1998 Naoyuki Hirayama. All rights reserved.