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

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

標準テンプレートライブラリSTL)はC++標準ライブラリの多くの部分に影響を与えたC++プログラミング言語用にAlexanderStepanovによって最初に設計されたソフトウェアライブラリです。アルゴリズムコンテナ関数イテレータと呼ばれる4つのコンポーネントを提供します[1]

STLは、コンテナーや連想配列など、C ++の共通クラスのセットを提供します。これらは、任意の組み込み型および一部の基本操作(コピーや割り当てなど)をサポートする任意のユーザー定義型で使用できます。STLアルゴリズムはコンテナから独立しているため、ライブラリの複雑さが大幅に軽減されます。

STLは、テンプレートを使用してその結果を達成しますこのアプローチは、従来のランタイムポリモーフィズムよりも効率的であることが多いコンパイル時ポリモーフィズムを提供します。最新のC++コンパイラは、STLの多用から生じる抽象化のペナルティを最小限に抑えるように調整されています。

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

STLとC++標準ライブラリは2つの異なるエンティティです。[3]

歴史

1993年11月、 Alexander Stepanovは、ジェネリックプログラミングに基づくライブラリをC++標準化のためにANSI/ISO委員会に提出しました。委員会の反応は圧倒的に好意的であり、1994年3月の会議に間に合うように正式な提案を求めるAndrewKoenigからの要請につながりました。委員会は変更と拡張を求めるいくつかの要求を持ち、委員会のメンバーは詳細を検討するためにStepanovとMengLeeと会いました。最も重要な拡張機能(連想コンテナ)の要件は、それらを完全に実装することによって一貫していることを示す必要がありました。これは、StepanovがDavidMusserに委任したタスクです提案は、1994年7月のANSI/ISO委員会会議で最終承認を受けました。その後、Stepanov and Leeのドキュメント17は、ANSI / ISO C ++ドラフト標準(1、条項17から27の一部)に組み込まれました。

STLの早期普及の見通しは、1994年8月にインターネット上でその実装を自由に利用できるようにするというヒューレットパッカードの決定によって大幅に改善されました。この実装は、標準化プロセス中にStepanov、Lee、およびMusserによって開発されました。今日、コンパイラおよびライブラリベンダーによって提供される多くの実装。

作曲

コンテナ

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

容器 説明
シンプルなコンテナ
ペア ペアコンテナは、 「first」および「second」と呼ばれる、データ要素またはオブジェクトの2つのタプルで構成される単純な連想コンテナです。STLの「ペア」は、割り当て、コピー、および比較できます。マップまたはhash_map(以下で説明)に割り当てられたオブジェクトの配列は、デフォルトで「ペア」タイプであり、すべての「最初の」要素が一意のキーとして機能し、それぞれが「2番目の」値オブジェクトに関連付けられます。
シーケンス(配列/リンクリスト):順序付けられたコレクション
ベクター オブジェクトを挿入または消去するときに自動的にサイズを変更する機能を備えたC配列のような動的配列(つまり、ランダムアクセスが可能)。ベクトルの最後に要素を挿入するには、一定の時間がかかります。サイズ変更が行われないため、最後の要素の削除には一定の時間しかかかりません。最初または途中での挿入と消去は時間的に直線的です。

bool値をビットとして 格納することにより、スペースを最適化するbool型の特殊化が存在します。

リスト 重にリンクされたリスト; 要素は連続したメモリに保存されません。ベクトルからの反対のパフォーマンス。ルックアップとアクセスが遅い(線形時間)が、位置が見つかったら、挿入と削除をすばやく行う(一定時間)。
slist
単一リンクリスト; 要素は連続したメモリに保存されません。ベクトルからの反対のパフォーマンス。ルックアップとアクセスが遅い(線形時間)が、位置が見つかったら、挿入と削除をすばやく行う(一定時間)。挿入と削除の効率がわずかに高く、二重リンクリストよりもメモリの使用量が少なくなりますが、反復処理のみが可能です。これは、C++標準ライブラリにとして実装されています。 forward_list
deque 両端キュー 償却された一定時間の開始または終了に挿入/消去があるベクトル。ただし、両端キューを変更した後のイテレーターの有効性については、いくつかの保証がありません。
コンテナアダプタ
///操作の観点からFIFO キューインターフェイスを提供しますpushpopfrontback

操作をサポートする任意のシーケンス、、、、およびキューをインスタンス化するために使用できます(例および)。 front()back()push_back()pop_front()listdeque

優先キュー 操作の観点から優先キューインターフェイスを提供します(最も優先度の高い要素が最上位になります)。 push/pop/top

操作をサポートする任意のランダムアクセスシーケンス、、、およびpriority_queue(egおよび)をインスタンス化するために使用できますヒープを使用して実装されますfront()push_back()pop_back()vectordeque

要素はさらに比較をサポートする必要があります(どの要素の優先度が高く、最初にポップする必要があるかを判断するため)。

スタック 操作の観点からLIFO スタックインターフェイスを提供します(最後に挿入された要素が一番上にあります)。 push/pop/top

操作をサポートする任意のシーケンス、、、およびスタックをインスタンス化するために使用できます(、、、およびback()push_back()pop_back()vectorlistdeque

連想コンテナ:順序付けられていないコレクション
セットする 数学的なセット; セット内の要素を挿入/消去しても、セット内を指すイテレータは無効になりません。集合演算の和集合共通部分、対称差、および包含のテストを提供します。データのタイプは、比較演算子を実装するか、カスタムコンパレータ関数を指定する必要があります。このような比較演算子またはコンパレータ関数は、厳密な弱順序を保証する必要があります。そうでない場合、動作は定義されません。通常、自己平衡二分探索木を使用して実装されます。 <
マルチセット セットと同じですが、重複する要素を許可します(数学的なマルチセット)。
地図 連想配列; あるデータ項目(キー)から別のデータ項目(値)へのマッピングを可能にします。キーのタイプは、比較演算子を実装するか、カスタムコンパレータ機能を指定する必要があります。このような比較演算子またはコンパレータ関数は、厳密な弱順序を保証する必要があります。そうでない場合、動作は定義されません。通常、自己平衡二分探索木を使用して実装されます。 <
マルチマップ マップと同じですが、キーを複製できます。
hash_set
hash_multiset
hash_map
hash_multimap
それぞれset、multiset、map、またはmultimapに似ていますが、ハッシュテーブルを使用して実装されます。キーは順序付けられていませんが、キータイプのハッシュ関数が存在する必要があります。これらのタイプはC++標準から除外されました。同様のコンテナがC++11で標準化されましたが、名前(および)が異なります。 unordered_setunordered_map
他の種類のコンテナ
ビットセット 固定サイズのboolのベクトルに似た一連のビットを格納します。ビット単位の演算を実装し、イテレータがありません。シーケンスではありません。ランダムアクセスを提供します。
valarray 数値使用を目的とした別の配列データ型(特にベクトル行列を表すため)。C ++標準では、この意図された目的のために特定の最適化が可能です。Josuttisによると、valarrayは、「標準が完成するずっと前に[C ++標準]委員会を去った」人々によってひどく設計されており、式テンプレートライブラリが好まれます。[4]この静脈の標準のvalarray部分の提案された書き直しは拒否され、代わりに式テンプレートを使用してそれを実装する許可になりました。[5]

イテレータ

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

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

双方向イテレータをランダムアクセスイテレータのように動作させることができるため、一度に合計10回ステップを進めるだけで、10ステップ進むことができます。ただし、個別のランダムアクセスイテレータを使用すると、効率が向上します。たとえば、ベクトルにはランダムアクセスイテレータがありますが、リストには双方向イテレータしかありません。

イテレータは、STLの一般性を可能にする主要な機能です。たとえば、シーケンスを逆にするアルゴリズムは、双方向イテレータを使用して実装できます。次に、同じ実装をリスト、ベクトル、および両端キューに使用できます。ユーザーが作成したコンテナーは、5つの標準イテレーター・インターフェースの1つを実装するイテレーターを提供するだけでよく、STLで提供されるすべてのアルゴリズムをコンテナーで使用できます。

この一般性には、時には代償が伴います。たとえば、マップやセットなどの関連コンテナでの検索の実行は、コンテナ自体が提供するメンバー関数を呼び出すよりも、イテレータを使用するとはるかに遅くなる可能性があります。これは、連想コンテナのメソッドが、イテレータを使用するアルゴリズムには不透明な内部構造の知識を利用できるためです。

アルゴリズム

STLには、検索や並べ替えなどのアクティビティを実行するための多数のアルゴリズムが用意されており、それぞれが特定のレベルのイテレーターを必要とするように実装されています(したがって、イテレーターによるインターフェイスを提供するすべてのコンテナーで機能します)。二分探索や並べ替えアルゴリズムなどの検索アルゴリズムで、データのタイプに比較演算子を実装するか、カスタムコンパレータ関数を指定する必要があります。このような比較演算子またはコンパレータ関数は、厳密な弱順序を保証する必要があります。これらとは別に、要素の範囲からヒープを作成し、要素の範囲の辞書式順序の順列を生成し、ソートされた範囲をマージし、結合を実行するためのアルゴリズムが提供されますbinary_searchlower_bound<交差ソートされた範囲の 違い。

関数

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

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

批判

C++コンパイラの実装品質

C ++コンパイラの実装品質(QoI)は、STL(および一般的なテンプレートコード)のユーザビリティに大きな影響を与えます。

  • テンプレートに関連するエラーメッセージは非常に長く、解読が難しい傾向があります。この問題は非常に深刻であると考えられているため、 STL関連のエラーメッセージを単純化してきれいに印刷し、理解しやすくするためのツールが数多く作成されています。
  • テンプレートを不注意に使用すると、コードが膨張する可能性があります。[7]これは、STL実装内の特別な手法(たとえば、内部でvoid *コンテナーを使用するなど)およびコンパイラーの最適化手法を改善することで対抗されています。ただし、この症状は、一連の関数を単純に手動でコピーして別のタイプで機能させることに似ており、両方を注意深く適切な手法で回避できます。
  • テンプレートのインスタンス化は、通常、実行時の意思決定を減らすことと引き換えに、コンパイル時間とメモリ使用量を増やすことができます(たとえば、仮想関数を介して)。コンパイラテクノロジが十分に向上するまで、この問題は、注意深いコーディング、特定のイディオムの回避、および適切でない場合やコンパイル時のパフォーマンスが優先される場合のテンプレートの使用を行わないことによって、部分的にしか解決できません。

その他の問題

  • ソースコード内の定数を使用したSTLコンテナーの初期化は、Cから継承されたデータ構造(初期化リストを使用してC ++ 11でアドレス指定)ほど簡単ではありません。
  • STLコンテナは、基本クラスとして使用することを目的としていません(それらのデストラクタは意図的に非仮想です)。コンテナから派生することはよくある間違いです。[8] [9]
  • STLによって実装されるイテレータの概念は、最初は理解するのが難しい場合があります。たとえば、イテレータが指す値が削除されると、イテレータ自体は無効になります。これはエラーの一般的な原因です。STLのほとんどの実装は、より低速なデバッグモードを提供しますが、使用するとそのようなエラーを見つけることができます。同様の問題は、Javaなどの他の言語にも存在します。範囲は、イテレータのより安全で柔軟な代替手段として提案されています。[10]
  • 特定の反復パターンは、STLイテレーターモデルにマップされません。[要出典]たとえば、コールバック列挙APIは、プラットフォームに依存するか利用できないコルーチン[11]を使用せずに、STLモデルに適合させることはできず、C ++ 20まではC++標準の範囲外になります。
  • コンパイラの準拠は、コンテナのメモリ管理に使用されるAllocatorオブジェクトが状態に依存する動作で動作することを保証するものではありません。たとえば、ポータブルライブラリは、そのタイプの異なるアロケータオブジェクトを使用して、異なるプールからメモリをプルするアロケータタイプを定義できません。(Meyers、p。50)(C ++ 11で対処)。
  • アルゴリズムのセットは完全ではありません。たとえば、アルゴリズムはC ++ 11で追加されましたが、省略されました[12][13]copy_if

実装

も参照してください

メモ

  1. ^ Holzner、Steven(2001)。C ++:ブラックブックアリゾナ州スコッツデール:CoriolisGroup。p。648. ISBN 1-57610-777-9STLは、コンテナーイテレーター関数オブジェクト、およびアルゴリズムで構成されています。
  2. ^ Musser、David(2001)。STLチュートリアルおよびリファレンスガイド:標準テンプレートライブラリを使用したC++プログラミングアディソンウェスリーISBN 0-201-37923-6
  3. ^ 軌道、コミュニティでの明度レース(2011年3月5日)。「「STL」と「C++標準ライブラリ」の違いは何ですか?」スタックオーバーフロー2021年10月21日取得
  4. ^ Josuttis、Nicolai M.(1999)。C ++標準ライブラリ:チュートリアルとハンドブックアディソン-ウェスリープロフェッショナル。p。 547
  5. ^ Vandevoorde、David; Josuttis、Nicolai M.(2002)。C ++テンプレート:完全ガイドアディソンウェスリーISBN 0-201-73484-2
  6. ^ ステパノフ、アレクサンダー; リー、メン(1995年10月31日)。「標準テンプレートライブラリ」(PDF)2018年12月16日取得データ構造を操作するライブラリのアルゴリズムテンプレートのほとんどには、範囲を使用するインターフェイスがあります。範囲は、計算の開始と終了を指定するイテレーターのペアです。[...]一般に、範囲[i、j)は、iが指す要素から始まり、jが指す要素までのデータ構造内の要素を指します。範囲[i、j)は、jがiから到達可能である場合にのみ有効です。
  7. ^ エイドリアンストーン。「コード膨張の最小化:テンプレートの過度の特殊化」
  8. ^ マイヤーズ、スコット(2005)。効果的なC++第3版–デザインを改善する55の具体的な方法アディソンウェスリーISBN 0-321-33487-6
  9. ^ サッター、ハーブ; アレキサンドレス、アンドレイ(2004)。C ++コーディング標準:101のルール、ガイドライン、およびベストプラクティスアディソン-ウェスリー。ISBN 0-321-11358-6
  10. ^ アンドレイアレキサンドレスク(2009年5月6日)。「イテレータは行かなければならない」(PDF)BoostCon2009 2011年3月19日取得
  11. ^ マシューウィルソン(2004年2月)。「コールバック列挙APIと入力イテレータの概念」ドブ博士の日記
  12. ^ Bjarne Stroustrup(2000)。C ++プログラミング言語(第3版)。アディソン-ウェスリー。ISBN 0-201-70073-5:p.530 
  13. ^ その他のSTLアルゴリズム(リビジョン2)
  14. ^ ApacheC++標準ライブラリStdcxx.apache.org。2013年7月29日に取得。

参照

外部リンク