algorithms stl
STLにおけるアルゴリズムとそのタイプの明示的な研究。
経験豊富なOracleSQLインタビューの質問
STLは、イテレータを介してコンテナに作用するさまざまなアルゴリズムをサポートしています。これらのアルゴリズムは、コンテナーに直接ではなくイテレーターに作用するため、あらゆるタイプのイテレーターで使用できます。
STLアルゴリズムが組み込まれているため、時間を大幅に節約でき、信頼性も向上します。また、コードの再利用性も向上します。これらのアルゴリズムは通常、1つの関数呼び出しであり、それらを実装するために網羅的なコードを記述する必要はありません。
=> ここでC ++トレーニングシリーズ全体を探してください。
学習内容：
STLアルゴリズムの種類
STLは、次のタイプのアルゴリズムをサポートします
- 検索アルゴリズム
- ソートアルゴリズム
- 数値アルゴリズム
- 非変換/変更アルゴリズム
- アルゴリズムの変換/変更
- 最小および最大操作
これらの各タイプについては、次の段落で詳しく説明します。
検索と並べ替えのアルゴリズム
STLの主要な検索アルゴリズムは、バイナリ検索です。二分探索アルゴリズムは、ソートされた配列を操作し、配列を半分に分割して要素を検索します。
これは、最初に検索する要素を配列の中央の要素と比較し、次に検索を1に制限することによって行われます。st半分または2nd検索する要素が中央の要素よりも小さいか大きいかに応じて、配列の半分。
二分探索は、最も広く使用されている検索アルゴリズムです。
その一般的な構文は次のとおりです。
binary_search(startaddr, endaddr, key) どこ、
startaddr：配列の最初の要素のアドレス。
endaddr：配列の最後の要素のアドレス。
キー：検索する要素。
STLは、コンテナ内の要素を特定の順序で配置するために使用される「ソート」アルゴリズムを提供します。
ソートアルゴリズムの一般的な構文は次のとおりです。
sort(startAddr, endAddr); どこ、
startAddr：ソートする配列の開始アドレス。
endAddr：ソートされる配列の終了アドレス。
内部的には、STLはクイックソートアルゴリズムを使用して配列をソートします。
バイナリ検索とソートアルゴリズムを示す例を見てみましょう。
#include #include using namespace std; int main() { int testAry() = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 }; int arysize = sizeof(testAry) / sizeof(testAry(0)); sort(testAry, testAry + arysize); cout<<'
Sorted Array is
'; for(int i=0;i 出力：
ソートされた配列は
0 1 2 3 4 5 6 7 8 9
配列でキー= 2が見つかりました
キー= 10が配列に見つかりません
与えられたコードでは、バイナリ検索を使用してキー要素を検索する必要がある配列を提供しています。二分探索にはソートされた配列が必要なため、最初に「sort」アルゴリズムを使用して配列をソートし、次に必要なパラメーターを指定して「binary_search」への関数呼び出しを行います。
最初に、key = 2に対してbinary_searchアルゴリズムを呼び出し、次にkey = 10に対して呼び出します。このように、1回の関数呼び出しで、配列に対してバイナリ検索を実行したり、配列を並べ替えたりすることができます。
数値アルゴリズム
STLのヘッダーには、数値を操作するさまざまな関数が含まれています。これらの関数は、lcds、gcdの検索から、配列、特定の範囲のベクトルなどのコンテナー内の要素の合計の計算まで多岐にわたります。
ここでは、いくつかの重要な機能について例を挙げて説明します。
（i）蓄積する
累積関数の一般的な構文は次のとおりです。
accumulate (first, last, sum); この関数は、変数sumの範囲(first、last)内のすべての要素の合計を返します。上記の構文表記では、firstとlastはコンテナ内の最初と最後の要素のアドレスであり、sumはsum変数の初期値です。
（ii）partial_sum
partial_sum関数の一般的な構文は次のとおりです。
partial_sum(first, last, b) ここに
最初：コンテナの開始要素のアドレス。
Last：コンテナの最後の要素のアドレス。
B：対応する配列要素の部分和が格納される配列。
したがって、partial_sum関数は、対応する配列またはベクトル要素の部分和を計算し、それらを別の配列に格納します。
aが(first、last)の範囲の要素を表し、bが結果の配列の要素を表す場合、partial_sumは次のようになります。
b0 = a0
b1 = a0 + a1
b2 = a0 + a1 + a2…など。
両方を示す例を見てみましょう プログラム内のこれらの関数：
#include #include using namespace std; int main() { int A() = {21,25,64,32}; int sum = 0; int b(4); cout<<'
Result of accumulate function is: '< 出力：
累積関数の結果は次のとおりです。142
配列Aのpartial_sum：21 46110142
上記のプログラムに示されているように、最初に累積関数を使用して要素の合計を計算し、次に関数partial_sumを呼び出して、対応する配列要素の部分合計を計算します。
STLとヘッダーでサポートされているその他のアルゴリズム：
- iota： 開始値の連続する増分で範囲を埋めます。
- 減らす： 順序が狂っていることを除いて、累積と同様です。
- 内部製品： 要素の2つの範囲の内積を計算します。
- neighbor_difference： 範囲内の隣接する要素間の差を計算します。
- inclusive_scan： partial_sumと同様に、i番目の合計にi番目の入力要素が含まれます。
- Exclusive_scan： partial_sumと同様に、i番目の入力要素をi番目の合計から除外します。
非変更アルゴリズム
非変更または非変換アルゴリズムは、操作しているコンテナーの内容を変更しないアルゴリズムです。STLは、多くの非変更アルゴリズムをサポートしています。
それらのいくつかを以下にリストしました：
- カウント： 指定された範囲内の値の数を返します。
- 等しい： 2つの範囲の要素を比較し、ブール値を返します。
- ミスマッチ： 2つのイテレータが比較され、不一致が発生した場合、イテレータのペアを返します。
- 探す： 指定された範囲で指定されたシーケンスを検索します。
- search_n： 指定された範囲でカウント値のシーケンスを検索します。
「カウント」関数と「等しい」関数について詳しく説明しましょう。
count（first、last、value）は、「value」が(first、last)の範囲に出現する回数を返します。
#include #include using namespace std; int main () { int values() = {5,1,6,9,10,1,12,5,5,5,1,8,9,7,46}; int count_5 = count(values, values+15, 5); cout<<'The number of times '5' appears in array= '< 出力：
Windows7用の無料のシステムオプティマイザー
配列に「5」が現れる回数= 4
このコードに示されているように、配列値を定義してから、値の範囲と値5を指定してcount関数を呼び出します。この関数は、値5が範囲内に出現する回数（count）を返します。
「等しい」関数を示す例を見てみましょう。
equal（first1、last1、first2）は、範囲(first1、last1)の要素を、first2が指す最初の要素と比較し、すべての要素が等しい場合はtrueを返し、そうでない場合はfalseを返します。
#include #include using namespace std; int main() { int inputs1() = { 1,2,3,4,5,6,7,8}; int inputs2() = { -1,2,1,2,3,4,6,7,8,9}; if (equal( inputs1 , inputs1+8 , inputs2 )==1) cout<<'Elements in Two ranges are equal'; else cout<<'Elements in two ranges are not equal'; } 出力：
2つの範囲の要素は等しくありません。
上記のコードでは、2つの整数配列を定義し、「equal」関数を使用して対応する要素を比較します。配列の要素は同じではないため、equalはfalseを返します。
アルゴリズムの変更
変更アルゴリズムは、コンテナの実行時にコンテナの内容を変更または変換します。
最も一般的で広く使用されている変更アルゴリズムには、2つの値を交換し、コンテナ内の要素をそれぞれ逆にする「swap」と「reverse」が含まれます。
これらの関数の例を見てみましょう。
#include #include #include #include using namespace std; int main () { vector vec1 = {1,1,2,3,5}; vector vec2 = {2,4,6,8,10}; swap(vec1,vec2); cout<<'Vector 1 : '; for (auto it = vec1.begin(); it < vec1.end(); ++it) cout << *it << ' '; cout< 出力：
ベクトル1：2 4 6 8 10
ベクトル2：1 1 2 3 5
逆ベクトル1：108 6 4 2
逆ベクトル2：5 3 2 1 1
ご覧のとおり、プログラムには2つのベクトルが定義されています。最初にスワップ関数を使用して、vector1とvector2の内容をスワップします。次に、逆関数を使用して各ベクトルの内容を逆にします。
プログラムは、Vector1とVector2の内容を交換した後、および内容を逆にした後に出力します。
最小および最大操作
このカテゴリは、指定された2つの値からそれぞれ最小値と最大値を見つける最小関数と最大関数で構成されます。
これらの関数の一般的な構文は次のとおりです。
max(objecta, objectb); min(objecta, objectb); 「compare_function」または最小/最大値を見つけるために使用される基準を提供するための3番目のパラメーターを提供することもできます。これが提供されていない場合、max関数は比較のために「>」演算子を使用しますが、min関数は「<’ operator for comparison.
プログラムを使ってこれらの機能をデモンストレーションしましょう。
#include #include using namespace std; int main() { int x=4, y=5; cout<<'Max of 4 and 5 : '; cout << max(x,y); cout< 出力：
最大4および5：5
4と5の最小値：4
最大文字列：小さい文字列
最小文字列：長い文字列
上記のプログラムは、最初に数値に、次に文字列にmin関数とmax関数を使用するため、自明です。オプションの「compare_function」を提供しなかったため、min / max関数はそれぞれ「」演算子に作用しました。
結論
これで、STLで使用される主要なアルゴリズムに関するこのチュートリアルは終了です。
以降のチュートリアルでは、コンテナーに関係なく、STLで使用される一般的な関数とともにイテレーターについて詳しく説明します。
=> Easy C ++トレーニングシリーズをお読みください。
推奨読書