Standard Template Library
Standard Template Library (STL) は、プログラミング言語C++の規格で定義された標準ライブラリの一つ。ヒューレット・パッカード社在籍の研究者(当時)であったアレクサンドル・ステパノフ等によって考案され、後にANSI/ISO標準に組み込まれた。
概要
編集container
といったような基底クラスから派生するのではない。コンセプトを満たしていればどのような要素でも協調動作する点では、動的な型付けシステムを持つ言語のダック・タイピングと良く似るが、STLのそれは静的︵テンプレートによるコンパイル時解決︶であり、よく比較される。
STLの定義︵何がSTLの一部であるか︶には様々な意見があり、人によりその解釈は違っていることがある。ここではC++標準ライブラリのコンテナ、イテレータ、アルゴリズム、関数オブジェクトを指すものとする。
構成要素
編集コンテナ
編集vector
動的配列。
array
(*) 固定長配列。
deque
両端キュー︵Double Ended QUEueの略︶。
list
双方向リスト。
forward_list
(*) 単方向リスト。
set
集合。順序付けられている︵このためツリーにより実装されるのが通常で、他言語のライブラリによく見られるハッシュテーブルではない︶。
map
連想配列。順序付けられている。実装に付いてはsetと同様。
multiset
要素の重複が許されているset。
multimap
要素のキーの重複が許されているmap。
unordered_set
(*) 集合。順序づけされない。ハッシュテーブルによる実装が意図されている。
unordered_map
(*) 連想配列。順序づけされない。unordered_set同様、ハッシュテーブルによる実装が意図されている。
unordered_multiset
(*) 要素の重複が許されているunoredered_set。
unordered_multimap
(*) 要素のキーの重複が許されているunoredered_map。
(*)の印の付いたものは、C++11規格で導入・標準化されたものである。
コンテナのうち、vectorとarrayはCの配列と互換性を持ち、データ領域の連続性が保証されている︵vがn要素のvector<c
har>
であるとき、&v[n - 1] - &v[0] == s
izeof(char) * (n - 1)
である。arrayも同様︶。
unorderedコンテナの名称として、例の少ないunordered_set/unordered_mapなどではなくhash_set/hash_mapなどとすることも検討された。しかし、hash_set/hash_mapなどといった名称はすでに外部のライブラリなどでよく用いられており、混乱を避けるため現在の名称となった。
この他、C++標準ライブラリのbasic_stringクラスがSTLのコンテナの要件を満たしていることから、これもSTLの一部として捉える向きもある。
コンテナアダプタ
編集stack
スタック。(FILO; First In, Last Out)
queue
キュー。(FIFO; First In, First Out)
priority_queue
優先順位付きキュー。
他のコンテナを内部に保持してそのコンテナの一部の機能のみを公開することにより、特殊な機能を実現している。STLのコンテナの要件を満たさないため、標準の一部ではあるがSTLのコンテナとしては扱えない。
イテレータ
編集アルゴリズム
編集STLで言うアルゴリズムは一般的なアルゴリズムより限定された用語であり、イテレータで指定されたコンテナの要素に対して特定の操作を行う関数である。
STLのアルゴリズムは標準で定義されているものだけでも多数あり、100以上の強力なアルゴリズムが用意されている。
std::vector<int> v1(3), v2(3);
v1[0] = 2;
v1[1] = 1;
v1[2] = 7;
std::copy(v1.begin(), v1.end(), v2.begin());
vector<int>
からlist<int>
、set<f
loat>
からvector<double>
等でもよい。
関数オブジェクト
編集関数オブジェクトはoperator()
(関数呼び出し演算子)をオーバーロードしたクラスの一種であり、オブジェクトでありながら関数のように呼び出せるという特徴を持つ。ファンクタ (functor) とも呼ばれる。
関数オブジェクトの定義は例えば以下のようなものである。
struct square
{
template<typename T>
T operator()(T n) const { return n * n; }
};
配列とポインタ
編集STLの長所の一つにCの配列との親和性の高さがある。具体的にはポインタがそのままRandomAccessIteratorとして使用できる。実のところイテレータの走査の方法はポインタ演算を模倣して作られている。アルゴリズムで配列を扱う場合、配列の先頭要素を指すポインタが開始イテレータ、そのポインタに要素数を加算したものが終了イテレータになる。
std::vector<int> v(N);
const int N = 16;
int array[N]; // [0..15]
// このときarrayが配列の最初の要素へのイテレータ、
// array + Nが最後の要素の次へのイテレータとして使用できる。
std::copy(array, array + N, v.begin());
STLの欠点
編集プログラムサイズの増大
編集C++のテンプレートはテンプレート引数が違うとそれぞれ全く別の型として扱われ、それぞれ別の機械語コードにコンパイルされてしまう。
以下のようなプログラムをコンパイルすると、std::vector<int>
のコードが作成される。
// vectorコンテナを使う
#include <vector>
std::vector<int> vecInt;
ここへさらに、
std::vector<double> vecDouble;
std
::vector<double>
のコードも作成され、結果として二つ分の別個のクラスのコードが実行ファイルに含まれることになる。たとえstd::vector
の型引数にまったく同じ型を指定した場合であっても、異なる翻訳単位︵異なるソースファイル︶で利用している場合、それぞれ別個に実体化される可能性もある。このため最終的に生成されるコードの量が急激に増大しやすく、組み込み向けなど記憶容量に制限のある環境ではSTLに限らずテンプレート全般の使用を禁止している開発現場もある。ただのクラスで実装した場合も事情は同じである。テンプレートを使わずに、int
型専用にstd::vector
<int>
と同等のクラスMyDynamicArrayOfInt
を書き、double
型専用にstd::vector<double>
と同等のクラスMyDynamicArrayOfDouble
も書き、両方のクラスをインスタンス化すれば、同様にコードの増大が起こる。特にクラスのメンバー関数の実装がヘッダーですべてインライン定義されている場合、たとえ同じ型を使用していたとしても利用する翻訳単位ごとに都度コードが生成されてしまう可能性もある。テンプレートはその性質上、型引数に依存する実装はインラインで公開・提供せざるを得ないため、テンプレートを使わない場合と比べてコード量の増大を招きやすい。
しかしながら、PCのようにメモリやストレージ容量に余裕のある環境に限れば、実行プログラムとして出力されるコード量の増大は相対的に微々たるものと言える。コンパイラによっては、インライン展開せず重複を取り除くことで、コード量の増大をある程度抑制してくれるかもしれない。
未対応コンパイラ
編集STLはほとんど全ての要素がC++の比較的新しい機能であるテンプレートを用いて作られているので、テンプレート関連のC++標準への準拠度が低いコンパイラやテンプレート機能を持たないEmbedded C++では、一部に使用の制限があったりSTLの使用自体が不可能なことがある。
ただし2003年にはC++標準への準拠度が高められた最適化コンパイラであるVisual C++ Toolkit 2003がマイクロソフトから無償配布されるなど、多くの環境ではテンプレートの利用における問題は少なくなってきている。
なお前述のコード量増大もそうであるが、これらはC++のテンプレート機能一般の問題であってSTL固有のものではない。
難解さ
編集一般にSTLは柔軟で強力であると評価されているが、ライブラリを十分に生かしたプログラミングを行おうとすると、従来のC/C++プログラミングからは大きく離れた考え方や書法が必要になる。そのため、STLの使用経験を持たないプログラマには、一見して何をしているのか全くわからないソースコードになってしまうことがある。それは例えば以下のようなものである。
size_t N = 0;
int *pdata = NULL;
GetData(&pdata, &N); // データとデータ数を得る
typedef std::deque<int> Cont;
Cont deq(pdata, pdata + N);
FreeData(&pdata, &N); // データを解放
// 典型的なSTLコード
deq.erase(
std::partition(
deq.begin(),
deq.end(),
std::bind1st(std::less<Cont::value_type>(), 20)
),
deq.end()
);
歴史
編集脚注
編集注釈
編集出典
編集- ^ Al Stevens (March 1995). “Al Stevens Interviews Alex Stepanov”. Dr. Dobb's Journal.