STLアルゴリズム

lower_bound と upper_bound は組み込みの二分探索関数です。

lower_bound - 対数時間で、指定された値 k 以上の、ソートされた配列内の最小の要素を見つける関数です。
配列の境界と k の値を引数として受け取ります。
見つかった要素にイテレータを返します。そのような要素が存在しない場合は配列の最後 (含まれていない) にイテレータを返します。
詳細については、ドキュメントをご覧ください。

upper_bound - ソートされた配列内で対数時間で、指定された値 k より厳密に大きい最小の要素を見つける関数です。
配列の境界と k の値を引数として受け取ります。
見つかった要素にイテレータを返します。そのような要素が存在しない場合は配列の最後 (含まれていない) にイテレータを返します。
詳細については、ドキュメントをご覧ください。

上記のランダム アクセス コレクションには反復子がないため、セットまたはマルチセットでこれらの関数を使用すると、対数時間では機能しないことを明確にする価値があります。
ただし、これらのコレクションには対応する組み込みメソッドがあります (つまり、「ドットを介して」メソッドを使用する必要があります)。

例:
  ベクトル a = { 0, 1, 3, 5, 7 }; ベクトル::反復子それ; it = lower_bound(a.begin(), a.end(), 4); // *それ == 5 it = lower_bound(a.begin(), a.end(), 5); // *それ == 5 it = lower_bound(a.begin(), a.end(), 8); // それ == a.end() it = upper_bound(a.begin(), a.end(), 4); // *それ == 5 it = upper_bound(a.begin(), a.end(), 5); // *それ == 7 it = upper_bound(a.begin(), a.end(), -1); // *それ == 0 // イテレータを減算することで、見つかった要素のインデックスを取得できます int ind = lower_bound(a.begin(), a.end(), 4) - a.begin(); // インド == 3 // セットや同様のコレクションには関数の代わりにメソッドを使用する必要があります set s{ 1, 3, 5 }; set::iterator sit; 座る = s. lower_bound(3); // *座る == 3 座る = s.upper_bound(3); // *座る == 5  

unique - 同一の連続要素のすべてのシーケンスを線形時間で 1 つに圧縮する関数。
引数として、圧縮を適用する必要がある配列の境界が渡されます。
反復子は、配列の新しい末尾 (両端を含まない) に返されます。新しい end の後で古い end の前にある要素には、未定義の値があるため注意が必要です。
詳しくはドキュメントをご覧ください。

ベクトルでこの関数を使用している場合は、返された結果を使用してサイズを変更すると便利です (詳細は後述)。

例:
  ベクトル a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 }; ユニーク (a.begin(), a.end()); // a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?] // unique 関数を使用すると便利です // 座標圧縮の補助配列 = { 235, 10, 41, 10, 41, 41, 235, 500, 500}; sort(a.begin(), a.end()); // a = [10, 10, 41, 41, 41, 235, 235, 500, 500] a.resize(unique(a.begin(), a.end()) - a.begin()); // a = [10, 41, 235, 500]  

merge - 2 つのソートされた配列をマージする関数。つまり、線形時間で、最初と 2 番目の配列の要素で構成されるソートされた配列を取得します。
これは 5 つの引数を取ります。各配列の 2 つの境界と、宛先 (結果の配列の要素が配置される場所) の左境界です。
詳細については、ドキュメントをご覧ください。

例: // ソース配列はソートする必要があります ベクトル a = { 1, 3, 5, 7 }; ベクトル b = { 2, 4, 6 }; // 宛先には十分な大きさが必要です ベクトル c(7); merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1、2、3、4、5、6、7] // 要素は繰り返し可能 a = {1, 2, 4, 4}; b = { 2, 3, 3, 3, 4, 4 }; c.resize(10); merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]  この関数は、マージソートのコンテキストで非常に便利です。

nth_element は、配列内の n 番目の要素をソート順に線形時間で検索できる関数です。
この関数は、配列の左端、ソートされた順序で値を見つける位置への反復子、および配列の右端を取得します。
関数を適用した後、必要な値はイテレータで示された場所に配置され、残りの値はカオス的な順序を取得しますが、n 番目の左側にはそれ以下の値が存在します。同じく右へ。つまり、この関数は要素の本来の順序を壊すものであると理解して
ください。 詳細については、ドキュメント (https://www.cplusplus.com/reference/algorithm/nth_element/) をご覧ください。

例： ベクトル a = { 4, 0, 3, 9, 2, 1, 8, 5, 6, 7 }; // インデックス 4 の要素を検索します // 引数の順序に注意してください nth_element(a.begin(), a.begin() + 4, a.end()); // a = [#, #, #, #, 4, $, $, $, $, $] // ここで # <= 4 および 4 <= $  

長さ n の順列は、番号 1、2、...、n の繰り返しのない順序付けられたコレクションです。たとえば、[3, 1, 2] と [5, 4, 3, 2, 1] は順列ですが、[1, 2, 1, 3] と [1, 2, 4] は順列ではありません。

長さ n のすべての順列を反復処理する必要があるという事実にタスクが縮小された場合、「next_permutation」と呼ばれる C++ の便利なメカニズムを使用できます。

詳細についてはドキュメントを参照してください。ただし、要点は、この関数が渡された配列を変更することです。辞書式順序での後続の順列 (一般的に明確であり、その名前) に。

next_permutation を使用するには、アルゴリズム ライブラリを含める必要があります (つまり、プログラムの先頭に #include <algorithm> を記述します)。

例: vector arr; arr = { 1, 2, 3 }; // 配列は [1, 2, 3] です next_permutation(arr.begin(), arr.end()); // 配列全体を関数に渡す // 配列は [1, 3, 2] になりました arr = { 2, 3, 1 }; // 配列は [2, 3, 1] です next_permutation(arr.begin(), arr.end()); // 配列全体を関数に渡す // 配列は [3, 1, 2] になりました next_permutation(arr.begin() + 1, arr.begin() + 3); // 配列の一部に関数を適用することは可能ですが、実際にはほとんど必要ありません // 配列は [3, 2, 1] になりました
この場合、関数は、次の順列が生成された場合は true であり、次の順列が存在しなかった場合は false であるブール値の戻り値を持ちます (辞書順で最大の順列が関数に渡される場合)。
これにより、関数をループで使用できるようになり、すべての順列を一度に反復処理できるようになります。順列には正式には 1 から n までの数値が含まれますが、0-indexing により、実際には、0 から n - 1 までの数値の順列を使用する方が便利なことがよくあります。しかし幸いなことに、これによってコードに追加のオーバーレイが発生することはありません。 next_permutation 関数は、インデックスが 0 の順列に適合しています (配列内の重複要素にも対応していますが、詳細は自分で調べることができます)。

一般に、すべての順列を繰り返すコードは次のようになります。 intn; // 順列サイズ vectorperm(n); // perm は「順列」の略です。つまり、 "順列" for (int i = 0; i < n; i++) perm[i] = 私; // 初期順列 0, 1, ..., n - 1 を初期化します する { // ループ内で現在の順列を処理します while (next_permutation(perm.begin(), perm.end())); // 次の順列がない場合は、ループを終了します

このコードは O(n! * f(n)) で実行されます。ここで、f(n) は 1 つの特定の順列を処理するのにかかる時間です。