Wikipedia

Standard Template Library

Standard Template Library (STL) は、プログラミング言語C++の規格で定義された標準ライブラリの一つ。ヒューレット・パッカード社在籍の研究者（当時）であったアレクサンドル・ステパノフ等によって考案され、後にANSI/ISO標準に組み込まれた。

概要

編集

STLは、その名の通りC++の比較的新しい機能であるテンプレートを最大限に生かす構成を取っており、コンテナ、イテレータ（反復子）、アルゴリズム、そして関数オブジェクトと呼ばれる各要素から成っている。

テンプレート機能を駆使することで、決まった型に依存しないプログラミングを実現し、C++におけるジェネリックプログラミングのはしりとなった。オブジェクトを格納するコンテナとそれを操作するアルゴリズム、その接点としてイテレータが存在し、コンテナとアルゴリズムが互いに完全に独立しているのも特徴の一つである。

それぞれの要素はコンセプト（概念）と呼ばれる要求仕様が厳格に規定され、STLと共に動作するコンポーネントはこの要求を満たしていなければならない。しかしそれによって、条件を満たしたクラスや関数を自作し、STLのコンポーネントと（あたかもSTLの一部であるかのように）協調動作させることが簡単にできるようになっている。STLの要素は何か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<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委員会で最終承認を得ることになる提案を提出した[注釈 1]。

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

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

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

脚注

編集

注釈

編集
  1. ^ 本件についての詳細は1995年3月に発刊されたDr. Dobb's Journalに掲載されているアレクサンドル・ステパノフへのインタビューで確認できる[1]。

出典

編集
  1. ^ Al Stevens (March 1995). “Al Stevens Interviews Alex Stepanov”. Dr. Dobb's Journal. 

関連項目

編集
 

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

「https://ja.wikipedia.org/w/index.php?title=Standard_Template_Library&oldid=103079454」から取得