Standard Template Library

ウィキペディア

Standard Template Library

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/06/03 06:47 UTC 版)

Standard Template Library (STL) は、プログラミング言語C++の規格で定義された標準ライブラリのうち、コンテナなどに関するものの通称。

ヒューレット・パッカード社在籍の研究者（当時）であったアレクサンドル・ステパノフ等によって考案され、後にANSI/ISO標準に組み込まれた。

概要

「STL」という名前はC++の規格で定義されているわけではなく、C++標準ライブラリが提供するコンテナ、イテレータ（反復子）、アルゴリズム、関数オブジェクトなどの機能に対する通称である。

C++の比較的新しい機能であるテンプレートを最大限に生かす構成を取っており、C++におけるジェネリックプログラミングの嚆矢である。これにより、個別の型に依存しないプログラミングを実現している。

また、オブジェクトを格納するコンテナと、コンテナを操作するアルゴリズムが独立しているのが特徴である。

それぞれの要素はコンセプト（概念）と呼ばれる要求仕様を規定している。他のライブラリのようなcontainerといったような基底クラスは定義されていない。自作のクラスや関数であっても、コンセプトを満たしてさえいれば、STLのコンポーネントと（あたかもSTLの一部であるかのように）協調動作させることができる。

構成要素

コンテナ

オブジェクトを保持するデータ構造。基本的なものが一通り揃っている。

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<char>であるとき、&v[n - 1] - &v[0] == sizeof(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では、イテレータに対して行える操作によって幾つかのコンセプトが定義されている。

InputIterator

入力反復子。要素への読み込み専用アクセスを提供するイテレータ。要素の読み取りが可能であればInputIteratorとみなせる。入力ストリームに結び付けられたistream_iteratorが典型的な例である。

OutputIterator

出力反復子。要素への書き込み専用アクセスを提供するイテレータ。要素への代入が可能であればOutputIteratorとみなせる。出力ストリームに結び付けられたostream_iteratorが典型的な例である。

ForwardIterator

前方反復子。一旦前方へ進めると、逆方向へは戻れないイテレータ。要素への代入と読み取りが可能であればForwardIteratorとみなせる。InputIteratorとOutputIteratorを組み合せたものといえる。典型的な例として、単方向リストコンテナのイテレータがある。

BidirectionalIterator

双方向反復子。前方と後方のどちらへでも移動できる機能を持たせたもの。ForwardIteratorの要件に加え、デクリメントが可能であればBidirectionalIteratorとみなせる。list、set、multiset、map、multimapコンテナのイテレータがこれに該当する。

RandomAccessIterator

ランダムアクセス反復子。ポインタのようにランダムアクセスを行えるイテレータ。BidirectionalIteratorの要件に加え、算術演算が可能であればRandomAccessIteratorとみなせる。vector、array、dequeのイテレータ（およびポインタ）がこれに該当する。STLの仕様では、vector、array、dequeのイテレータが要素n個分進めるという操作をO(1)の効率で行うことが保証されている（逆に、これ以外のイテレータはO(n)の時間が必要である）。

以上の他、全てのイテレータは前進(++it)、等号比較(it1 != it2)、デリファレンス(*it)が可能でなければならない。

アルゴリズム

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());

copyは要素のコピーを行うSTLアルゴリズムである。コピー元としてコンテナv1の開始イテレータと終了イテレータを取り、v2のイテレータに順に出力する。 この例ではコピー元とコピー先のコンテナは同じ型であるが、コンテナ要素が同一あるいは変換可能であればよい。例えば、vector<int>からlist<int>、set<float>からvector<double>等でもよい。

関数オブジェクト

関数オブジェクトはoperator()（関数呼び出し演算子）をオーバーロードしたクラスの一種であり、オブジェクトでありながら関数のように呼び出せるという特徴を持つ。ファンクタ (functor) とも呼ばれる。

関数オブジェクトの定義は例えば以下のようなものである。

struct square
{
    template<typename T>
    T operator()(T n) const { return n * n; }
};

一般に関数オブジェクトで表された関数はオブジェクトとして作成したものをアルゴリズムに値渡しするため、同じような目的で使用できる関数ポインタよりもオーバーヘッドが大きいと思われることもあるが、実際にはコンパイラの最適化でコードのインライン展開が行われ関数呼び出しが無くなる可能性が高いため、関数ポインタを使うよりも高速であることが多い。例えばC標準ライブラリのqsortよりSTLアルゴリズムのsortの方が往々にして高速であるというのはよく知られている。

STLでは関数オブジェクトの代わりに関数ポインタを使うことも可能である。

また、標準規格C++11より導入されたラムダ式を使うことで、関数オブジェクトの定義をより簡潔に記述できるようになった。

配列とポインタ

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()
);

このコードは、何かのAPIから得られたデータの配列をdequeにコピーし、そのdequeの内容のうち20より大きい要素をコンテナの先頭に移動させた上で残りを削除している。

これほど複雑な処理がこれだけのコード量で表現できるのは素晴らしいとも言えるが、一時的なtypedef・クラス内宣言型・入れ子のアルゴリズム・関数オブジェクト・関数アダプタなどを使用しており、STLの使い方を知らない場合には非常に理解が難しくなるのは事実である。

ちなみに、こういった一時オブジェクトを使うために入れ子になった関数呼び出しは関数型プログラミング言語の書式に類似しており、実際に同じ考え方でできている側面がある。

歴史

STLのアーキテクチャの多くはアレクサンドル・ステパノフという一人の人物の手によって作られた。1979年に彼はジェネリックプログラミングの初期アイデアを練り始め、そしてソフトウェア開発に革命をもたらす可能性を探究し始めた。ジェネリックプログラミングの一部は1971年にはすでにデイビッド・マッサー(Dave Musser)により開発されて提唱されていたが、どちらかといえばコンピュータ代数学というある特定のソフトウェア開発の分野に限定されたものであった。

ステパノフはジェネリックプログラミングの大きな可能性に気づき、ゼネラル・エレクトリックのR&D部門の仲間たち(前述のデイビッド・マッサーとデイーパック・カプール(Deepak Kapur))に対し、ジェネリックプログラミングがソフトウェア開発の広範囲に渡る基礎として研究されるべきだということを説得した。当時はジェネリックプログラミングを実際にサポートしているプログラミング言語がまだなかった。

それをサポートする最初のメジャーな言語はジェネリックユニット(汎用体)の機能があるAdaであった。1987年までにステパノフとマッサーはジェネリックプログラミングの研究成果としてAdaのリスト処理ライブラリを開発してリリースしていた。しかしながらAdaは軍需産業以外ではあまり普及しておらず、C++は当時まだ言語として未成熟ではあったものの(テンプレートはまだなく後から実装された)、より広く普及してジェネリックプログラミングの良好なサポートが提供される可能性が高いと考えられた。それ以前にもステパノフはまた別の理由でC++へ転向することを考えており、ポインタを使うことで効率を損なうことなくメモリに対して非常に柔軟にアクセスできるC/C++の計算モデルは普及のための決定要素と思われた。

単なる個々のコンポーネント開発ではなく、ジェネリックプログラミングに基づくコンポーネントライブラリの包括的なアーキテクチャを開発するためには、十分な研究と実験が必要であった。初めはAT&Tベル研究所で、後にはヒューレット・パッカード(HP)研究所で、ステパノフはC言語で(後にC++で)数多くのアーキテクチャとアルゴリズムの実装法を検証した。マッサーは共同で研究し、さらに1992年にはメン・リー(Meng Lee)がHPのステパノフのプロジェクトに加入して主要な貢献者の一人となった。

ベル研究所のアンドリュー・コーニグ(Andrew Koenig)がこの動きを察知して、1993年11月のANSI/ISOのC++標準化委員会にアイデアを提出するように求めるようなことがもしなければ、この作業は間違いなく、さしあたっては研究プロジェクトとして、あるいはHPのプロプライエタリなライブラリとして継続されたであろう。提案は委員会で全面的に賛同を得て、すぐさま1994年3月のミーティングでのコーニグからの正式なリクエストへとつながった。非常に厳しいスケジュールであったが、ステパノフとリーはミーティングに先だって事前承認されたドラフト案を提出できた。

委員会は変更と拡張(主要な点を含む)を数点要求し、詳細を詰めるために委員会の小さなグループがステパノフやリーと打ち合わせた。特に重要な(コンテナに関する)拡張について、それらを全て実装することにより一貫性があることを証明することが要求され、ステパノフはマッサーにこの作業を任せた。この時点で事業全体がコントロール不能になり暴走する可能性が高まっていたが、ステパノフとリーは果敢に立ち向かい、1994年7月のANSI/ISO委員会で最終承認を得ることになる提案を提出した。

次にステパノフとリーのドキュメント17はANSI/ISO C++標準ドラフト版に取り入れられた(17条〜27条の一部)。また同様にstringのようなその他のC++標準ライブラリの機能にも影響を与え、それらの領域ですでに標準化されていた部分が修正された。

委員会でSTLが成功したにもかかわらず、STLがどのように実際に利用され活用されるのかという点においては問題が残されていた。公開版ドラフト標準の一部をSTLが要求したことにより、コンパイラメーカーと独立系ソフトウェアライブラリメーカーはそれをセールスポイントにしたプロダクトを開発して販売できた。初版の共著者の一人であるアトゥル・サイニ(Atul Saini)は初期の段階でこれの商品価値に気づき、STLがまだ委員会で最終承認される前であったにもかかわらず、彼の会社であるモデナソフトウェア(Modena Software Incorporated)のビジネスとして研究を開始していた。

STLが早いうちに広く普及するという見通しは、1994年春にヒューレット・パッカードがその実装をインターネットに公開し自由に利用可能とするという決定をしたことで相当よくなった。標準化の過程でステパノフ、リー、マッサーにより開発されたこの実装は、今日ではコンパイラやライブラリのメーカーがリリースしている多くの実装の基礎となった。

関連項目

• 総称型
• Boost C++ライブラリ
• TR1
• C++11
• STLport