標準テンプレートライブラリ（STL、標準Tエンプレートライブラリ）という用語は、元々Alexander Stepanov、Meng Lee、AT＆T Bell LaboratoriesおよびHewlett-Packard Research Laboratoriesの他の従業員が90年代前半に開発したインターフェイスとコンポーネントのセットを指します今日ではC ++の標準コンポーネントになったものにかなり多くの人が参加しました）。 さらに、STLライブラリはSGIのプロパティとなり、Boostライブラリセットのコンポーネントとしても含まれました。 最後に、STLライブラリは1998年と2003年のC ++標準（ISO / IEC 14882：1998およびISO / IEC 14882：2003）に入り、その後標準C ++ライブラリのコンポーネントの1つと見なされました。
標準では、STLライブラリのこの部分に名前を付けていませんが、コンパイラ、言語、および文学のどのバージョンを扱うかをソートする際にこの年表を考慮するとよいでしょう-HP STLを標準化に適したサイズに縮小する過程で、一部のアルゴリズムとファンクターがライブラリから外れました。時間の経過とともに何かが追加されます（たとえば、一部のコンテナメソッドのオーバーライドされたプロトタイプのセットを拡張する）。 このテキストでは、標準C ++ライブラリのどの部分を念頭に置いているかを明確にするために、従来の名前STLのみを使用します。
STLの最初の目標（これは、ヘッダーファイルのコメントの時系列から明確に見ることができます）は、配列と比較して通常のコンテナーのより柔軟なモデルを作成し、広く使用されているアルゴリズム（検索、並べ替えなど）を一般化することでした。 しかし、このアイデアは当初の意図よりも実りが多く、大幅に拡張されました。 STLには、ほとんどすべての場合にプログラムコードを大幅に簡素化できる多くの概念とデータ構造が導入されています。 次のカテゴリの概念が導入されています。
- コンテナは、オブジェクトのセットをメモリに保存する方法です。
- イテレータは、コンテナ内の個々のオブジェクトのコンテンツにアクセスする手段です。
- アルゴリズム-コンテナに関する最も標準的な計算手順の決定。
- アダプター-最もよく使用されるインターフェース（スタックやキューなど）を提供するための主要なカテゴリーの適合。
- ファンクター（機能オブジェクト）-他のカテゴリーで使用するためにオブジェクト内の関数を非表示にします。
STLライブラリは非常に広大な領域です。 完全に別の本は、その説明に専念しています。 ここでは、かなり初期レベルの知人、限られたボリューム、および以前に発表された目標に従うため、直感的に明確な例を使用してSTLを使用する手法を検討します。 STL構文は、クラステンプレートや関数テンプレートなどのC ++構文構造の使用に基づいています。 ただし、STL手法をうまく適用するためには、テンプレート手法を深く理解する必要はまったくありません（これは後ほど説明します）。
STLの中心的な概念は、他のすべてがその周りを回っているのですが、コンテナです（これらはコレクションという用語も使用します）。 コンテナは、特定の方法でコンテナにパックされた、同じタイプの特定の数の要素のコレクションです。 クラシックC ++言語で最も単純なプロトタイプコンテナーは配列です。 要素をコンテナにパックする方法によって、コンテナのタイプと、そのようなコンテナ内の要素を操作する機能が決まります。 STLは多くの異なるタイプのコンテナを導入します。主なものは次のとおりです。
- 順次コンテナ-ベクトル（ベクトル）、二重リンクリスト（リスト）、デッキ（デック）;
- 連想コンテナ-セット（セットおよびマルチセット）、ハッシュテーブル（マップおよびマルチマップ）;
- 疑似コンテナ-ビットマスク（ビットセット）、文字列（stringおよびwstring）、配列（valarray）。
単純なものから複雑なものへと移動しながら、主要なものを連続して使用する例を見ていきます。 コンテナの最も単純なタイプはベクターです。 ベクターの近いプロトタイプはC ++配列ですが、ベクターのサイズは、要素の追加（push_back（）メソッド）または削除（pop_back（）メソッドなど）の操作によっていつでも動的に変更できます。 配列については、インデックス操作[n]により、ベクトルの任意の要素を参照できます。 すでに言われたことは、ベクトルに関する最初の表面的な知識の層ですが、従来の配列をどのように使用するかの類似性について作業を開始するには十分です。
#include <iostream> #include <vector> #include <climits> using namespace std; void put( const vector<float>& v ) { cout << "capacity=" << v.capacity() << ", size=" << v.size() << " : "; for( unsigned i = 0; i < v.size(); i++ ) cout << v[ i ] << " "; cout << endl; } vector<float>& operator +=( vector<float>& v, unsigned n ) { float last = v[ v.size() - 1 ]; for( unsigned i = 0; i < n; i++ ) v.push_back( last + i + 1 ); return v; } int main( void ) { float data[] = { 1., 2., 3., 4., 5., 6., 7. }; int n = sizeof( data ) / sizeof( data[ 0 ] ); vector<float> array( data, data + n ); cout << "max_size=" << array.max_size() << " ((INT_MAX+1)/2)=" << ( (unsigned)INT_MAX + 1 ) / 2 << endl; put( array ); put( array += 2 ); put( array += 6 ); }
説明vector <float>（これは、クラスの説明で前述したテンプレートです）は、<b>コードでオブジェクトを宣言します</ b>：vectorfloat 型の要素。 次に、ベクトルクラスのメソッドmax_size（）-一般的なベクトルの最大可能長（実装定数）、サイズ（）-ベクトルの現在のサイズ （要素の数）、容量（）-ベクトルの現在の容量、配置できる要素の最大数現在の場所のベクトルに。 このスニペットを実行すると、次のようになります（詳細は実装によって異なる場合があります）。
$ ./vect1 max_size=1073741823 ((INT_MAX+1)/2)=1073741824 capacity=7, size=7 : 1 2 3 4 5 6 7 capacity=14, size=9 : 1 2 3 4 5 6 7 8 9 capacity=28, size=15 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
ここでは、ベクターのかなり興味深い動作を見ることができます（これはその意味です）：ベクターの次の要素が追加されるとすぐに、その容量は別の要素に十分ではなく、ベクターの新しい配置が行われ、そのために2倍の容量が確保されます（新しい要素の次の追加すぐに新しい移転を必要としませんでした）。
注：再配置中に上記のベクトルの容量が2倍になることは、GCCコンパイラライブラリを実装するための一般的な動作です。 しかし、標準では、実装者の裁量で将来の要素のために正確な予約予約アルゴリズムを残しているため、それを当てにすることはできません。ここでは、画像の定性的な理解のためにのみ説明します（Visual Studioの実装は異なる動作をし、わずかな超過分のみを予約します...これを自分で学習します）。
これまでのところ、コメントなしで、コンテナに要素を配置する操作が要素をコピーするという重要な状況に注意します。これには、a）。要素のタイプのコピーコンストラクターが必要であり、b）。構造要素の場合、これは顕著なコストパフォーマンスにつながります。
したがって、C ++配列に相当するものが得られました。そのサイズ （size（））は、数単位から数百万の要素までの任意の範囲で動的に変化します。 （これは非常に重要です）ベクトルのサイズを増やすことは、現在のサイズを超えてインデックスを作成することではなく、ベクトルの最後に 「プッシュ」（push_back（）メソッド）することで達成されます（対称的に、pop_back（）メソッドは最後の要素をプッシュすることに注意してください）配列からサイズを縮小します（））。 ベクトルのサイズを変更する別の方法は、すぐにresize（）メソッドを目的のサイズに呼び出すことです。 配列とは異なり、ベクターのサイズが動的に変化する可能性があるため、ベクターには2つの異なるインデックスメソッドがあります。 操作 [i]と（i）のメソッド関数です。 それらは異なります ：at（）メソッドはベクターサイズ（）の現在のサイズをチェックし、境界を超えてインデックスを作成すると、 例外をスローします 。 それどころか、インデックス作成操作は境界をチェックしません。これは安全ではありませんが、高速です。 at（）メソッドを使用すると、ベクトルの境界を超えて制御し、論理エラーとして修飾するか、そのようなフラグメントのように必要に応じて現在のコンテナーサイズを調整できます（ここでは実際の操作の2倍のアクセス試行があります）：
int main( void ) { vector<int> nums; for( int i = 0; i < 10; ) { try { nums.at( i ) = i; // vector::at throws an out-of-range i++; } catch( const out_of_range& ) { cout << i << " "; nums.resize( i + 1 ); } } cout << endl << nums.size() << endl; }
$ ./vect7 0 1 2 3 4 5 6 7 8 9 10
C ++ 11標準では、たとえば初期化リストや型推論などの追加の表現力豊かなツールが導入されており、コンテナーでの作業が大幅に簡素化されます（さらに、昔ながらの使い慣れた記述方法も不要になります）。 これは、マトリックスが同時に記述される場合の方法ですa）。 構成（正方形、長方形でも三角形でもよい）、b）。 寸法（3x3）およびc）。 初期化値：
void print( const vector< vector<float> >& m ) { for( auto &row : m ) { for( auto x : row ) cout << x << ' '; cout << endl; } } void trans( vector< vector<float> >& m ) { for( unsigned i = 0; i < m.size(); i++ ) for( unsigned j = i + 1; j < m[ i ].size(); j++ ) { float tmp = m[ i ][ j ]; m[ i ][ j ] = m[ j ][ i ]; m[ j ][ i ] = tmp; } } int main( void ) { vector< vector<float> > matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; print( matrix ); cout << "---------" << endl; trans( matrix ); print( matrix ); }
同時に、ベクトル（正方行列の転置と出力ストリームへの出力）を使用した作業を、擬似配列（インデックス付けのみを使用）として示します。これは本質的にベクトルです（特に、ベクトルによって要素のタイプがどのように決定されるかを示します） C ++ 11標準に従った出力タイプ）：
$ ./vect6 1 2 3 4 5 6 7 8 9 --------- 1 4 7 2 5 8 3 6 9
注：ベクトルについて既に知っているフレームワークでは、返されるサイズ（）の結果の型を （プラットフォーム依存を回避するために）どのように厳密に決定する必要がありますか？ 時々、構文の純度の保護者から、答えはsize_tであるべきであり、この答えは間違っています（特に、多くのプラットフォームでsize_tはunsigned intとして定義されているため）。 ベクトルのsize（）タイプの絶対に厳密な定義を書きたい場合、上記の例の行は次のように書く必要があります。
for( vector<float>::size_type j = i + 1; j < m[ i ].size(); j++ ) { ...
または、次のようにC ++ 11型推論に依存します。
for( auto j = i + 1; j < m[ i ].size(); j++ ) { ...
ここでこの微妙なニュアンスに注意して（考慮に入れて）、不必要に面倒な例を避けるために、それをさらに適用しませんが、ディメンションについては単に符号なしにします。
PS興味のある人は、検証とさらなる実験のためのすべてのコード例のアーカイブ（前の部分とこの部分、およびすべての後続の部分）をここまたはここで取得して、これらすべてを手動で叩かないようにすることができます。