STLコンポーネントアルゴリズム

STL は、OOP と従来のプログラミングの両方で使用できる多数のテンプレートクラスと関数を提供します。 STL の約 50 個のアルゴリズムはすべて完全に汎用的であり、特定のデータ型に依存しません。次のサブセクションでは、3 つの基本的な STL コンポーネントについて説明します。

1) イテレータはコンテナ内のオブジェクトにアクセスする方法を提供します。たとえば、反復子のペアを使用して、リストまたはベクトル内のオブジェクトの範囲を指定できます。イテレータはポインタのようなものです。実際、C++ ポインタもイテレータの一種です。ただし、イテレータは、operator*() やその他のポインタのような演算子のメソッドを定義するクラスのオブジェクトになることもできます。

2) コンテナは、テンプレートクラスのメソッドとして提供されるリスト、ベクター、デキューなどのデータ構造です。コンテナ内のデータにアクセスするには、コンテナクラスによってエクスポートされた反復子を使用します。

3) アルゴリズムは、コンテナ内のデータを操作するために使用されるテンプレート関数です。たとえば、STL はベクトル内のデータをソートするために sort() を使用し、リスト内のオブジェクトを検索するために find() を使用します。関数自体は、操作するデータの構造や型に依存しないため、単純な配列から非常に複雑なコンテナーまで、あらゆるデータ構造で使用できます。

関数と関数オブジェクト

STL では、関数はアルゴリズムと呼ばれ、標準の C ライブラリ関数よりも汎用的です。 STL アルゴリズムは、operator() 関数をオーバーロードすることによってテンプレートクラスまたはテンプレート関数として実装されます。これらのクラスは、コンテナー内のデータに対してさまざまな操作を実行する関数オブジェクトを作成するために使用されます。次のセクションでは、関数と関数オブジェクトの使用方法について説明します。

関数とアサーション

多くの場合、コンテナ内のデータに対してユーザー定義の操作を実行する必要があります。たとえば、コンテナー内のすべてのオブジェクトを反復処理して、独自の関数にコールバックできるようにする STL アルゴリズムが必要な場合があります。例えば

#include <iostream.h>  
 #include <stdlib.h> // random()、srandom() が必要 
 #include <time.h> // time() が必要 
 #include <vector> // ベクトルが必要 
 #include <algorithm> // for_each() が必要 
 
 #define VSIZE 24 // ベクトルのサイズ 
 vector< long > v(VSIZE); // ベクトルオブジェクト 
 
 // 関数のプロトタイプ 
 voidを初期化します( long &ri);
 void表示( const  長い&ri);
 bool isMinus(定数  long &ri); // 述語関数 
 
 intメイン()
 {
 srandom( time(NULL) ); // シード乱数ジェネレータ 
 
 for_each(v.begin(), v.end(), initialize); //通常の関数を呼び出す 
 cout << "符号付き長整数のベクトル" << endl;
 for_each(v.begin(), v.end(), show);
 cout << 終了; 
 
 // 述語関数を使用して負の値をカウントする 
 //  
整数カウント = 0;
ベクトル< long >::イテレータ p;
 p = find_if(v.begin(), v.end(), isMinus); //アサーション関数を呼び出す 
 while (p != v.end()) {
カウント++;
 p = find_if(p + 1, v.end(), isMinus);
 }
 cout << "値の数: " << VSIZE << endl;
 cout << "負の値: " << count << endl; 
 
 0を返します。
 } 
 
 // ri を符号付き整数値に設定する 
 void初期化( long &ri)
 {
 ri = ( ランダム() - (RAND_MAX / 2) );
 // ri = ランダム();  
 } 
 
 // riの値を表示 
 void表示( const  長い&ri)
 {
 cout << ri << " " ;
 } 
 
 // ri が 0 より小さい場合は true を返します 
 bool isMinus(定数 長い&ri)
 {
戻り値(ri < 0);
 }

いわゆるアサーション関数は、bool 値を返す関数です。

関数オブジェクト

STL アルゴリズムにコールバック関数を渡すだけでなく、より複雑な操作を実行するためにクラスオブジェクトを渡す必要がある場合もあります。このようなオブジェクトは関数オブジェクトと呼ばれます。実際、関数オブジェクトはクラスですが、コールバック関数と同じようにコールバックできます。たとえば、関数オブジェクトは、for_each() または find_if() 関数によって呼び出されるたびに統計を保持できます。関数オブジェクトは、operator()() をオーバーロードすることによって実装されます。 TanyClass が operator()() を定義している場合は、次のように使用できます。

 TAnyClass オブジェクト; // オブジェクトの構築 
 object(); // TAnyClass::operator()() 関数を呼び出す 
 for_each(v.begin(), v.end(), オブジェクト);

STL はいくつかの関数オブジェクトを定義します。これらはテンプレートなので、long などの C/C++ ネイティブデータ型を含むあらゆる型に使用できます。一部の関数オブジェクトには、plus() や multiplies() など、その目的を明確に示す名前が付けられています。同様のメソッド greater() と less-equal() は、2 つの値を比較するために使用されます。

知らせ

ANSI C++ の一部のバージョンでは times() 関数オブジェクトが定義されていますが、GNU C++ では multiplies() という名前が付けられています。使用時にはヘッダーファイル < functional> を含める必要があります。

関数オブジェクトの便利な応用例は、accumulate() アルゴリズムです。この関数はコンテナ内のすべての値の合計を計算します。このような値は単純な型である必要はなく、operator+() をオーバーロードすることでクラスオブジェクトにすることもできることに注意してください。

リスト8. accum.cpp

 #include <iostream.h>  
 #include <numeric> // 累積() が必要 
 #include <vector> // ベクトルが必要 
 #include < functional> // multiplies() (または times()) が必要 
 #定義 MAX 10  
 vector< long > v(MAX); // ベクトルオブジェクト 
 intメイン()
 {
 // 従来のループを使用してベクトルを埋める 
 //  
 ( int i = 0; i < MAX; i++)の場合
ｖ[i] = i + 1;
 // 含まれる値の合計を累積する 
 //  
長い合計 =
累積(v.begin(), v.end(), 0);
 cout << "値の合計 == " << sum << endl;
 // 含まれる値の積を累算する 
 //  
ロング製品 =
 assemble(v.begin(), v.end(), 1, multiplies< long >()); // この行に注意してください 
 cout << "値の積 == " << product << endl;
 0を返します。
 }

コンパイル出力は次のようになります。

 $ g++ accum.cpp
 $ ./a.out
値の合計== 55
値の積== 3628800

『関数オブジェクトを使用するaccumulate()の使用法に注意してください。 accelerate() は内部的にコンテナ内の各オブジェクトと 3 番目の引数を multiplies 関数オブジェクトへの引数として渡し、multiplies(1,v) は積を計算します。 VC でのこれらのテンプレートのソースコードは次のとおりです。

 // テンプレート関数 蓄積 
テンプレート<クラス_II、クラス_Ty>インライン 
 _Ty を累積します (_II _F、_II _L、_Ty _V)
 { (; _F != _L; +++F)の場合
_V = _V + *_F;
戻り値(_V); }
 // テンプレート関数 BINOP で蓄積する 
テンプレート<クラス_II、クラス_Ty、クラス_Bop>インライン 
 _Ty 累積 (_II _F、_II _L、_Ty _V、_Bop _B)
 { (; _F != _L; +++F)の場合
_V = _B(_V、*_F);
戻り値(_V); }
 // テンプレート構造体 binary_function  
テンプレート<クラス_A1、クラス_A2、クラス_R>
構造体バイナリ関数{
 typedef _A1 最初の引数の型;
 typedef _A2 2番目の引数型;
 typedef _R 結果型;
 };
 // テンプレート構造体は乗算します 
テンプレート<クラス_Ty>
構造体乗算: binary_function<_Ty, _Ty, _Ty> {
 _Ty演算子()( const _Ty& _X, const _Ty& _Y) const  
 {戻り値(_X * _Y); }
 };

はじめに: STL がどのように実装されているかを深く理解したい場合、最も良い方法は、簡単なプログラムを書いて、プログラムに含まれるテンプレートソースコードをコピーし、少し整理してみることです。そうすれば、理解できるようになります。したがって、「STL ソースコード分析」のような本を購入する必要はありません。これらの本は時間の無駄になる可能性があります。』

（１）ジェネレータ関数オブジェクト

関数オブジェクトの便利なクラスの 1 つは「ジェネレーター」です。このような関数には独自のメモリがあり、以前の呼び出しの値を記憶することができます。たとえば、乱数生成関数。

通常の C プログラマーは、静的変数またはグローバル変数を使用して、前回の呼び出しの結果を「記憶」します。しかし、これを行うことの欠点は、関数をそのデータから分離できないことです。もう 1 つの欠点は、スレッドの安全性を確保するために TLS が必要になることです。明らかに、クラスを使用して「メモリ」の一部をカプセル化する方が安全で信頼性が高くなります。例を見てみましょう:

リスト9. randfunc.cpp

 #include <iostream.h>  
 #include <stdlib.h> // random()、srandom() が必要 
 #include <time.h> // time() が必要 
 #include <algorithm> // random_shuffle() が必要 
 #include <vector> // ベクトルが必要 
 #include < functional> // ptr_fun() が必要 
使用して 名前空間std;
 // ランダム化するデータ 
 int iarray[10] = {1、2、3、4、5、6、7、8、9、10};
ベクトル< int > v(iarray, iarray + 10);
 // 関数のプロトタイプ 
 voidディスプレイ(ベクトル< int >& vr, const   char *s);
符号なし整数RandInt( const符号なし整数n);
 intメイン()
 {
 srandom( time(NULL) ); // シード乱数ジェネレータ 
 Display(v, "シャッフル前:" );
 pinter_to_unary_function<unsigned int , unsigned int >
 ptr_RandInt = ptr_fun(RandInt); // RandInt() へのポインタ // この行に注意してください 
ランダムシャッフル(v.begin(), v.end(), ptr_RandInt);
 Display(v, "シャッフル後:" );
 0を返します。
 }
 // ベクトル vr の内容を表示 
 voidディスプレイ(ベクトル< int >& vr, const  文字*s)
 {
 cout << endl << s << endl;
コピー(vr.begin(), vr.end(), ostream_iterator< int >(cout, " " ));
 cout << 終了;
 }
 // シーケンス内の次のランダムな値を n を法として返します 
符号なし整数RandInt(符号なし整数nの定数)
 {
ランダム（）%nを返します。
 }

コンパイルと実行結果は次のとおりです。

 $ g++ randfunc.cpp
 $ ./a.out
シャッフル前:
 1 2 3 4 5 6 7 8 9 10
シャッフル後:
 6 7 2 8 3 5 10 1 9 4

まず、次のステートメントでオブジェクトを宣言します。

単項関数へのポインター<unsigned int 、unsigned int >
 ptr_RandInt は ptr_fun(RandInt);

ここでは、STL 単項関数テンプレートを使用して変数 ptr_RandInt を定義し、関数 RandInt() へのアドレスを初期化します。単眼関数は 1 つの引数を受け取り、値を返します。これで、random_shuffle() は次のように呼び出すことができます。

ランダムシャッフル(v.begin(), v.end(), ptr_RandInt);

この例では、ジェネレーターは単に rand() 関数を呼び出します。

定数参照に関するちょっとした問題 (翻訳なし、VC の例の const を削除)

#p#

（２）ジェネレータ関数クラスオブジェクト

次の例は、ジェネレータ関数クラスオブジェクトの使用を示しています。

リスト 10. fiborand.cpp

 #include <iostream.h>  
 #include <algorithm> // random_shuffle() が必要 
 #include <vector> // ベクトルが必要 
 #include < functional> // unary_function が必要 
使用して 名前空間std;
 // ランダム化するデータ 
 int iarray[10] = {1、2、3、4、5、6、7、8、9、10};
ベクトル< int > v(iarray, iarray + 10);
 // 関数プロトタイプ 
 voidディスプレイ(ベクトル< int >& vr, const   char *s);
 // FiboRand テンプレート関数オブジェクトクラス 
テンプレート<クラスArg>
クラスFiboRand :パブリックunary_function<Arg, Arg> {
整数i, j;
 Arg配列[18]
公共：
フィボランド();
引数演算子()( const Arg& arg);
 };
 void main()
 {
 FiboRand< int > fibogen; // ジェネレータオブジェクトを構築 
 cout << "フィボナッチ乱数ジェネレータ" << endl;
 cout << "random_shuffle と関数オブジェクトを使用する" << endl;
 Display(v, "シャッフル前:" );
ランダムシャッフル(v.begin(), v.end(), fibogen);
 Display(v, "シャッフル後:" );
 }
 // ベクトル vr の内容を表示 
 voidディスプレイ(ベクトル< int >& vr, const  文字*s)
 {
 cout << endl << s << endl;
コピー(vr.begin(), vr.end(),
 ostream_iterator< int >(cout, " " ));
 cout << 終了;
 }
 // FiboRand クラスのコンストラクタ 
テンプレート<クラスArg>
 FiboRand<Arg>::FiboRand()
 {
シーケンス[17] = 1;
シーケンス[16] = 2;
 ( int n = 15; n > 0; n—)の場合
シーケンス[n] = シーケンス[n + 1] + シーケンス[n + 2];
私 = 17;
 5;
 }
 // FiboRand クラス関数演算子 
テンプレート<クラスArg>
引数 FiboRand<Arg>::operator()( const Arg& arg)
 {
引数k = シーケンス[i] + シーケンス[j];
シーケンス[i] = k;
私 - ;
 j--;
 i == 0 の場合i = 17;
 j == 0 の場合、j = 17;
 k% 引数を返します。
 }

コンパイルして実行した結果の出力は次のようになります。

 $ g++ フィボランド.cpp
 $ ./a.out
フィボナッチ乱数ジェネレータ
random_shuffleと関数オブジェクトを使用する
シャッフル前:
 1 2 3 4 5 6 7 8 9 10
シャッフル後:
 6 8 5 4 3 7 10 1 9

このプログラムは rand_shuffle をまったく異なる方法で使用します。フィボナッチジェネレーターは、以前の「使用」の結果を記憶するクラスにカプセル化されます。この例では、クラス FiboRand は配列と 2 つのインデックス変数 I と j を管理します。

FiboRand クラスは unary_function() テンプレートから継承します。

テンプレート<クラスArg>
クラスFiboRand: public unary_function<Arg, Arg> {...

Arg はユーザー定義のデータ型です。このクラスは、コンストラクターと operator() 関数の 2 つのメンバー関数も定義します。これにより、random_shuffle() アルゴリズムは FiboRand オブジェクトを関数のように「呼び出す」ことができます。

#p#

（３）バインダー関数オブジェクト

バインダーは、別の関数オブジェクト f() とパラメーター値 V を使用して関数オブジェクトを作成します。バインドされた関数オブジェクトはバイナリ関数である必要があります。つまり、2 つのパラメーター A と B を持ちます。 STL のバインダーは次のとおりです。

bind1st() は、値 V を最初の引数 A として受け取る関数オブジェクトを作成します。
bind2nd() は、値 V を 2 番目の引数 B として受け取る関数オブジェクトを作成します。

以下にいくつか例を挙げます。

リスト 11. バインダー.cpp

 #include <iostream.h>  
 #include <アルゴリズム>  
 #include <機能>  
 #include <リスト>  
使用して 名前空間std;
 //データ 
 int iarray[10] = {1、2、3、4、5、6、7、8、9、10};
リスト< int > aList(iarray, iarray + 10);
 intメイン()
 {
整数k = 0;
 count_if(aList.begin(), aList.end(),
 bind1st(より大きい< int >(), 8), k);
 cout << "要素数 < 8 == " << k << endl;
 0を返します。
 }

アルゴリズム count_if() は、特定の条件を満たす要素の数をカウントします。これは、関数オブジェクトとパラメータをオブジェクトにバンドルし、そのオブジェクトをアルゴリズムの 3 番目の引数として渡すことによって行われます。この表現に注目してください:

 bind1st(より大きい< int >(), 8)

この式は、greater<int>() とパラメータ値 8 を関数オブジェクトにバンドルします。 bind1st() が使用されているため、この関数は次の式を計算することと同等になります。

8 > ク

式内の q はコンテナ内のオブジェクトです。したがって、完全な表現は

count_if(aList.begin(), aList.end(),
 bind1st(より大きい< int >(), 8), k);

サイズが 8 以下のすべてのオブジェクトの数を数えます。

（４）関数オブジェクトの否定

否定関数オブジェクトは、別の関数オブジェクトから作成されるオブジェクトです。元の関数が true を返す場合、否定関数オブジェクトは false を返します。否定関数オブジェクトには、not1() と not2() の 2 つがあります。 not1() は単眼関数オブジェクトを受け入れ、not2() は両眼関数オブジェクトを受け入れます。負の関数オブジェクトはバインダーでよく使用されます。たとえば、前のセクションでは、bind1nd を使用して q <= 8 の値を検索しました。

 count_if(aList.begin(), aList.end(),
 bind1st(より大きい< int >(), 8), k);

q>8 のオブジェクトを検索する場合は、bind2st を使用します。次のように書くことができます:

開始 = find_if(aList.begin(), aList.end(),
 not1(bind1nd(より大きい< int >(), 6)));

bind1nd は単項関数を返すため、not1 を使用する必要があります。

概要: 標準テンプレートライブラリ (STL) の使用

多くのプログラマーは依然として標準の C 関数を使用していますが、それはメルセデスを探すのにロバに乗るようなものです。最終的にはそこにたどり着くでしょうが、多くの時間を無駄にしてしまうことになります。

ただし、標準の C 関数 (フォーマットされた出力に sprintf() を使用するなど) を使用すると便利な場合もあります。ただし、C 関数はエラーを報告するために例外メカニズムを使用しないため、新しいデータ型の処理には適していません。さらに、標準の C 関数ではメモリ割り当て技術が使用されることが多く、経験の浅いプログラマーは簡単にバグを記述する可能性があります。。

C++ 標準ライブラリは、データセットを処理するためのより安全で柔軟な方法を提供します。 STL はもともと、HP Labs の Alexander Stepanov と Meng Lee によって開発されました。最近、C++ 標準委員会は STL を採用しましたが、実装ごとに詳細はまだ異なります。

STL の 2 つの主な特徴は、データ構造とアルゴリズムの分離と非オブジェクト指向性です。オブジェクトへのアクセスは、ポインタのような反復子を通じて実現されます。コンテナーは、リンクリストやベクターのようなデータ構造であり、テンプレート形式で提供されます。アルゴリズムは、コンテナー内のデータを操作するために使用される関数テンプレートです。 STL はテンプレートに基づいているため、あらゆるデータ型と構造に使用できます。

【編集者のおすすめ】