標準テンプレートライブラリ

標準テンプレートライブラリ（STL）は、元々はアレクサンダー・ステパノフが C++プログラミング言語用に設計したソフトウェアライブラリで、 C++標準ライブラリの多くの部分に影響を与えましたが、現在は積極的にメンテナンスされておらず、ほとんどがC++標準ライブラリ自体に統合されています。STLは、アルゴリズム、コンテナ、ファンクタ、イテレータと呼ばれる4つのコンポーネントを提供します。^[¹^]

STLは、コンテナや連想配列など、C++用の共通クラス群を提供します。これらのクラスは、基本的な操作（コピーや代入など）をサポートする組み込み型やユーザー定義型であれば、どれでも使用できます。STLのアルゴリズムはコンテナに依存しないため、ライブラリの複雑さが大幅に軽減されます。

STLはテンプレートを用いることでその性能を実現しています。このアプローチはコンパイル時のポリモーフィズムを提供し、多くの場合、従来の実行時ポリモーフィズムよりも効率的です。最新のC++コンパイラは、STLの多用によって生じる抽象化によるペナルティを最小限に抑えるように調整されています。

STLは、C++用の汎用アルゴリズムとデータ構造の最初のライブラリとして、汎用プログラミング、効率を損なわない抽象性、フォン・ノイマン計算モデル^{[ 2 ]}、値セマンティクスという4つのアイデアを念頭に置いて作成されました。

STLとC++標準ライブラリは2つの異なる実体である^{[ 3 ]}が、STLから直接影響を受けたり継承されたりしたC++標準ライブラリの部分は「STL」と呼ばれることもある^{[ 4 ] 。}

歴史

1993年11月、アレクサンダー・ステパノフは、汎用プログラミングに基づくライブラリをANSI/ISO C++標準化委員会に提出した。委員会の反応は圧倒的に好意的で、アンドリュー・ケーニッヒから1994年3月の会議に間に合うように正式な提案を提出するよう要請があった。委員会には変更や拡張に関する要望がいくつかあり、委員会のメンバーはステパノフとメン・リーと会合を開き、詳細を詰めた。最も重要な拡張（連想コンテナ）の要件は、完全に実装することで一貫性があることを示す必要があり、ステパノフはこの作業をデビッド・マッサーに委任した。提案は1994年7月のANSI/ISO委員会会議で最終承認を受けた。その後、ステパノフとリーの文書17はANSI/ISO C++ドラフト標準（1、条項17～27の一部）に組み込まれた。

1994年8月、ヒューレット・パッカード社がSTLの実装をインターネット上で無償公開することを決定したことで、STLの早期普及の見通しは大幅に改善された。標準化プロセス中にステパノフ、リー、マッサーによって開発されたこの実装は、今日、コンパイラやライブラリベンダーが提供する多くの実装の基礎となっている。

構成

コンテナ

STLには、シーケンスコンテナと連想コンテナが含まれています。コンテナはデータを格納するオブジェクトです。標準のシーケンスコンテナvectorには、、、、dequeおよびがあります。標準の連想コンテナは、、、、、、、およびです。またlist、特定のsetインターフェースを持ち、他のコンテナを実装として使用するコンテナアダプタ、、、およびもあります。multisetmapmultimaphash_sethash_maphash_multisethash_multimapqueuepriority_queuestack

イテレータ

STL は 5 種類のイテレータを実装しています。これらは入力イテレータ(値のシーケンスを読み取るためだけに使用できます)、出力イテレータ(値のシーケンスを書き込むためだけに使用できます)、前方イテレータ(読み取り、書き込み、および前方への移動が可能です)、双方向イテレータ(前方イテレータに似ていますが、後方にも移動できます) です。ランダムアクセスイテレータ（1回の操作で任意の数のステップを自由に移動できる）。

STLの基本的な概念は範囲であり、これは計算の開始と終了を指定するイテレータのペアです。ライブラリのデータ構造を操作するアルゴリズムテンプレートのほとんどは、範囲を使用するインターフェースを備えています。^{[ 8 ]}

双方向イテレータをランダムアクセスイテレータのように動作させることも可能です。例えば、10ステップ進むには、一度に1ステップずつ合計10回進むだけで済みます。しかし、個別のランダムアクセスイテレータを用意することで、効率面で有利になります。例えば、ベクトルにはランダムアクセスイテレータがありますが、リストには双方向イテレータしかありません。

イテレータは、STLの汎用性を実現する主要な機能です。例えば、シーケンスを反転させるアルゴリズムは双方向イテレータを使用して実装でき、同じ実装をリスト、ベクトル、デックにも適用できます。ユーザーが作成したコンテナは、5つの標準イテレータインターフェースのいずれかを実装するイテレータを提供するだけでよく、STLで提供されるすべてのアルゴリズムをコンテナ上で使用できます。

この汎用性には、時として代償が伴う。例えば、マップやセットといった連想コンテナに対して検索を行う場合、イテレータを用いるよりも、コンテナ自体が提供するメンバ関数を呼び出す方がはるかに処理速度が遅くなることがある。これは、連想コンテナのメソッドは内部構造に関する情報を利用できるのに対し、イテレータを用いるアルゴリズムではその内部構造が不透明であるためだ。

アルゴリズム

STLには、検索やソートなどの処理を実行するための多数のアルゴリズムが用意されており、それぞれが特定のレベルのイテレータを必要とするように実装されています（そのため、イテレータによるインターフェースを提供する任意のコンテナで動作します）。検索アルゴリズム（例：）は二分探索を使用しbinary_search、ソートアルゴリズム（例：）は、データ型が比較演算子を実装しているか、カスタム比較関数を指定する必要があります。このような比較演算子または比較関数は、厳密な弱順序付けを保証する必要があります。これらに加えて、要素の範囲からヒープを作成するアルゴリズム、要素の範囲の辞書順に並べられた順列を生成するアルゴリズム、ソートされた範囲をマージするアルゴリズム、およびソートされた範囲の和集合、積集合、差集合を実行するアルゴリズムも用意されています。lower_bound<

機能

STLには、関数呼び出し演算子（）をオーバーロードするクラスが含まれています。このようなクラスのインスタンスは、ファンクタまたは関数オブジェクトと呼ばれます。ファンクタを使用すると、関連付けられた関数の動作をパラメータ化できます（たとえば、ファンクタのコンストラクタに渡される引数を介して）。また、ファンクタは、関数とともにファンクタごとの状態情報を保持するために使用できます。ファンクタと関数ポインタはどちらも関数呼び出しの構文を使用して呼び出すことができるため、対応するパラメータが関数呼び出しのコンテキストにのみ現れる場合、テンプレートの引数として互換性があります。operator()

特に一般的なファンクターの種類は述語です。たとえば、などのアルゴリズムは、シーケンスの要素に対して動作する単項find_if述語を受け取ります。sort、partial_sort、nth_elementなどのアルゴリズム、およびすべてのソート済みコンテナは、厳密な弱い順序付けを提供する必要のある二項述語を使用します。つまり、推移的で、非反射的で、非対称な二項関係に対するメンバーシップテストのように動作する必要があります。何も指定されていない場合、これらのアルゴリズムとコンテナはデフォルトでless を使用し、これにより、小なり演算子 < が呼び出されます。

批判

C++コンパイラの実装品質（QoI）は、STL（および一般的にテンプレート化されたコード）の使いやすさに大きな影響を与えます。

テンプレートに関するエラーメッセージは非常に長く、解読が難しい傾向があります。この問題は深刻であるため、 STL関連のエラーメッセージを簡略化して見やすく表示するツールが数多く開発されています。
テンプレートを不用意に使用すると、コードが肥大化する可能性があります。^{[ 9 ]}これは、STL 実装内の特別なテクニック (たとえば、内部で void* コンテナを使用したり、その他の「ダイエットテンプレート」テクニックを使用したり) や、コンパイラの最適化テクニックを改善することによって対処されています。しかし、この症状は、異なる型で動作するように一連の関数を素朴に手動でコピーすることと似ており、どちらも注意深く適切なテクニックを使用すれば回避できます。
テンプレートのインスタンス化は、コンパイル時間とメモリ使用量を増加させる可能性がありますが、その代償として、通常は実行時の意思決定（仮想関数などによるもの）を削減できます。コンパイラ技術が十分に向上するまでは、この問題は、慎重なコーディング、特定のイディオムの回避、そしてテンプレートが不適切な場合やコンパイル時のパフォーマンスが優先される場合はテンプレートを使用しないことによってのみ、部分的に解消できます。

その他の問題点としては、以下のものが挙げられます。

ソースコード内で定数を使用してSTLコンテナを初期化することは、Cから継承したデータ構造ほど簡単ではありません（ C++11では初期化リストで対応されています）。
STLコンテナは基底クラスとして使用することを意図していません（デストラクタは意図的に非仮想になっています）。コンテナから派生させるのはよくある間違いです。^{[ 10 ]}^{[ 11 ]}
STL で実装されているイテレータの概念は、最初は理解しにくい場合があります。たとえば、イテレータが指す値が削除されると、イテレータ自体が無効になります。これはよくあるエラーの原因です。ほとんどの STL 実装では、デバッグモードが提供されていますが、これは遅いものの、使用すればこのようなエラーを特定できます。同様の問題は、Javaなどの他の言語にも存在します。イテレータよりも安全で柔軟な代替手段として、範囲が提案されています。^{[ 12 ]}
コールバック列挙APIなどの特定の反復パターンは、コルーチンを使用しない限りSTLモデルに適合させることはできません^{[ 13 ]。}コルーチンはC++20まではC++標準の範囲外でした。
コンパイラの準拠は、コンテナのメモリ管理に使用されるアロケータオブジェクトが状態依存の動作で機能することを保証するものではありません。たとえば、移植可能なライブラリは、その型の異なるアロケータオブジェクトを使用して異なるプールからメモリをプルするアロケータ型を定義することはできません。（Meyers、p. 50）（C++11で対応済み）。
アルゴリズムのセットは完全ではありません。たとえば、copy_ifアルゴリズムは省略されていますが、^{[ 14 ]} C++11で追加されています。^{[ 15 ]}

実装

オリジナルのSTL実装はStepanovとLeeによって1994年にHewlett-Packard社で開発されました。現在はメンテナンスされていません。
- SGI STLは、StepanovとLeeによるオリジナルの実装に基づいています。1997年、Silicon Graphics社。現在はメンテナンスされていません。
  - SGI STL に基づくSTLPort
  - Rogue Wave標準ライブラリ（HP、SGI、SunSoft、Siemens-Nixdorf）
  - Apache C++ 標準ライブラリ（このライブラリの出発点は Rogue Wave 標準ライブラリの 2005 年版^{[ 16 ]}でした）
  - Libstdc++ は、C++03で定義されているアルゴリズムとコンテナのために、SGI STL から派生したコードを使用します。
PJ PlaugerによるDinkum STLライブラリ

注記

↑ホルツナー、スティーブン (2001)。C++ : ブラックブック。アリゾナ州スコッツデール：コリオリグループ。 p. 648.ISBN 1-57610-777-9STLは、コンテナ、イテレータ、関数オブジェクト、およびアルゴリズムで構成されています。
↑ Musser , David (2001). STLチュートリアルとリファレンスガイド：標準テンプレートライブラリを使用したC++プログラミング。Addison Wesley。ISBN 0-201-37923-6。
↑ Lightness Races in Orbit (2011年3月5日)。「STL」と「C++標準ライブラリ」の違いは何ですか？ Stack Overflow 。 2021年10月21日取得。
↑ C++ 標準委員会。(2021)。P2412R0 - C++ モジュール設計のさらなる改良。https ://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p2412r0.pdfから取得。2024 年 11 月 20 日^{(日付の不一致)}にWayback Machineにアーカイブ済み。
↑ " [ vector.bool ] "。Eelis 。 2024年12月22日取得。
↑ Josuttis, Nicolai M. (1999). C++標準ライブラリ：チュートリアルとハンドブック. Addison - Wesley Professional. p. 547. ISBN 9780201379266。
↑ヴァンデフォールデ、デヴィッド;ジョスティス、ニコライ M. (2002)。C++ テンプレート: 完全ガイド。アディソン・ウェスリーISBN 0-201-73484-2。
↑ステパノフ、アレクサンダー、リー、メン (1995 年 10 月 31 日)。「標準テンプレートライブラリ」(PDF) 。2018年12 月 16 日取得。ライブラリのアルゴリズムテンプレートのほとんどは、データ構造を操作するため、範囲を使用するインターフェースを備えています。範囲とは、計算の開始と終了を指定するイテレータのペアです。[...]一般に、範囲 [i, j) は、i が指す要素から始まり、j が指す要素を含まないデータ構造内の要素を指します。範囲 [i, j) は、j が i から到達可能な場合に限り有効です。
↑エイドリアン・ストーン。「コードの肥大化を最小限に抑える：テンプレートの過剰な特殊化」。
↑スコット・マイヤーズ (2005). 『Effective C++ Third Edition – 55 Specific Ways to Improve Your Designs』. Addison Wesley . ISBN 0-321-33487-6。
↑サッター、ハーブ；アレクサンドレスク、アンドレイ（2004）。C ++コーディング標準：101のルール、ガイドライン、およびベストプラクティス。アディソン・ウェスリー。ISBN 0-321-11358-6。
↑ Andrei Alexandrescu (2009年5月6日). "Iterators Must Go" (PDF) . BoostCon 2009. 2011年3月19日取得。
↑マシュー・ウィルソン（2004年2月）。「コールバック列挙APIと入力イテレータの概念」。Dr . Dobb's Journal。
↑ビャルネ・ストロヴストルップ(2000). C++ プログラミング言語(第 3版). Addison-Wesley. ISBN 0-201-70073-5。^{: p.530}
↑ STLアルゴリズムの追加（改訂版2）
↑ 「Apache C++ 標準ライブラリ」。stdcxx.apache.org。2023年3月 1 日に取得。

参考文献

Alexander Stepanovおよび Meng Lee、「標準テンプレートライブラリ」。HP Laboratories テクニカルレポート 95-11(R.1)、1995 年 11 月 14 日。（AA Stepanov および M. Lee 著「標準テンプレートライブラリ」、テクニカルレポート X3J16/94-0095、WG21/N0482、ISO プログラミング言語 C++ プロジェクト、1994 年 5 月の改訂版。）
Alexander Stepanov (2007).プログラミングに関するノート(PDF)。ステパノフはSTLの設計について考察する。
Nicolai M. Josuttis (2000). C++標準ライブラリ：チュートリアルとリファレンス. Addison-Wesley. ISBN 0-201-37926-0。
スコット・マイヤーズ（2001）。『効果的なSTL：標準テンプレートライブラリの利用を改善する50の具体的な方法』アディソン・ウェスリー。ISBN 0-201-74962-9。
アル・スティーブンス（1995年3月）。「アル・スティーブンスがアレックス・ステパノフにインタビュー」。ドクター・ドブス・ジャーナル。2007年7月18日取得。
David VandevoordeとNicolai M. Josuttis (2002)。C++ テンプレート: 完全ガイド。アディソン・ウェスリー・プロフェッショナル。ISBN 0-201-73484-2。
Atul SainiおよびDavid R. Musser (1996). STL チュートリアルおよびリファレンスガイド: 標準テンプレートライブラリを使用した C++ プログラミング。Alexander Stepanov による序文。Copyright Modena Software Inc. Addison-Wesley。ISBN 0-201-63398-1。

外部リンク

C++リファレンス
C++ STLリファレンス（C++11の機能を含む）
SGIのSTL プログラマーガイド。元々は（提供終了コンテンツ）
Apache（旧Rogue Wave）C++標準ライブラリクラスリファレンス
Apache（旧Rogue Wave）C++標準ライブラリユーザーガイド
ビャルネ・ストロヴストルップによるSTLの出現に関する考察（5ページ、3.1節）
C++標準仕様

[1] ホルツナー、スティーブン (2001)。C++ : ブラックブック。アリゾナ州スコッツデール：コリオリグループ。 p. 648.ISBN 1-57610-777-9STLは、コンテナ、イテレータ、関数オブジェクト、およびアルゴリズムで構成されています。

[stltutorial-2] Musser , David (2001). STLチュートリアルとリファレンスガイド：標準テンプレートライブラリを使用したC++プログラミング。Addison Wesley。ISBN 0-201-37923-6。

[3] Lightness Races in Orbit (2011年3月5日)。「STL」と「C++標準ライブラリ」の違いは何ですか？ Stack Overflow 。 2021年10月21日取得。

[P2412R0-4] C++ 標準委員会。(2021)。P2412R0 - C++ モジュール設計のさらなる改良。https ://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p2412r0.pdfから取得。2024 年 11 月 20 日^{(日付の不一致)}にWayback Machineにアーカイブ済み。

[5] " [ vector.bool ] "。Eelis 。 2024年12月22日取得。

[6] Josuttis, Nicolai M. (1999). C++標準ライブラリ：チュートリアルとハンドブック. Addison - Wesley Professional. p. 547. ISBN 9780201379266。

[7] ヴァンデフォールデ、デヴィッド;ジョスティス、ニコライ M. (2002)。C++ テンプレート: 完全ガイド。アディソン・ウェスリーISBN 0-201-73484-2。

[8] ステパノフ、アレクサンダー、リー、メン (1995 年 10 月 31 日)。「標準テンプレートライブラリ」(PDF) 。2018年12 月 16 日取得。ライブラリのアルゴリズムテンプレートのほとんどは、データ構造を操作するため、範囲を使用するインターフェースを備えています。範囲とは、計算の開始と終了を指定するイテレータのペアです。[...]一般に、範囲 [i, j) は、i が指す要素から始まり、j が指す要素を含まないデータ構造内の要素を指します。範囲 [i, j) は、j が i から到達可能な場合に限り有効です。

[9] エイドリアン・ストーン。「コードの肥大化を最小限に抑える：テンプレートの過剰な特殊化」。

[effcpp-10] スコット・マイヤーズ (2005). 『Effective C++ Third Edition – 55 Specific Ways to Improve Your Designs』. Addison Wesley . ISBN 0-321-33487-6。

[cppcs-11] サッター、ハーブ；アレクサンドレスク、アンドレイ（2004）。C ++コーディング標準：101のルール、ガイドライン、およびベストプラクティス。アディソン・ウェスリー。ISBN 0-321-11358-6。

[itersmustgo-12] Andrei Alexandrescu (2009年5月6日). "Iterators Must Go" (PDF) . BoostCon 2009. 2011年3月19日取得。

[13] マシュー・ウィルソン（2004年2月）。「コールバック列挙APIと入力イテレータの概念」。Dr . Dobb's Journal。

[14] ビャルネ・ストロヴストルップ(2000). C++ プログラミング言語(第 3版). Addison-Wesley. ISBN 0-201-70073-5。^{: p.530}

[15] STLアルゴリズムの追加（改訂版2）

[16] 「Apache C++ 標準ライブラリ」。stdcxx.apache.org。2023年3月 1 日に取得。

[

[ 2 ]

[ 3 ]

[ 4 ] 。

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]。

[ 14 ]

[ 15 ]

[ 16 ]

標準テンプレートライブラリ

歴史

構成

コンテナ

イテレータ

アルゴリズム

機能

批判

実装

関連項目

注記

参考文献

外部リンク

関連するトピック

アレクサンダー・ステパノフが

C++

ソフトウェアライブラリで、

C++標準ライブラリの多くの部分に影響を与えましたが、現在は積極的にメンテナンスされておらず、ほとんどがC++標準ライブラリ自体に統合されています。STLは、