次に説明するアルゴリズムのカテゴリは、特定の特性を備えたシーケンス内の要素の検索に使用されます。一般に検索結果は、copy (13.2.2 節を参照)、 partition (13.4.4 節を参照)、in-place merge (13.4.6 節を参照) などの次の操作の引数として使用されます。
注 : 以降の節で説明する関数例は、alg2.cpp ファイル にあります。
この節で説明する検索ルーチンは、検索条件に一致する最初の要素を識別する反復子を返します。一般にこの値は、次のように iterator 変数に保存されます。
list<int>::iterator where; where = find(aList.begin(), aList.end(), 7);
検索条件に一致するすべての要素を検索する場合は、ループを作成する必要があります。このループでは、前の検索で検出された値が最初に提示されます。それ以外の場合は、前の検索で検出された値が再び返されます。結果の値は、新しい検索の開始点となります。たとえば、adjacent_find() プログラム例 (13.3.2 節を参照) の以下のループは、文字列引数内で反復するすべての文字の値を印刷します。
while ((where = adjacent_find(where, stop)) != stop) {
cout << "double " << *where << " in position "
<< where - start << endl;
++where;
}
注 : 標準 C++ ライブラリのすべての検索アルゴリズムは、検索条件に一致する値が見つからない場合は、シーケンスの終端反復子を返します。一般にシーケンスの終端値を間接参照することは不当であるため、検索結果を使用する前にこの条件を確認する必要があります。
検索アルゴリズムの多くは、コンテナ要素型の等価演算子 == の代わりに要素を比較する関数を指定することができる、任意の引数を使用します。アルゴリズムの定義において、標準等価演算子が使用可能な場合は、これらの任意引数を、指定する必要がないことを示す角括弧で囲みます。
2 つのアルゴリズム find() と find_if() は、条件に一致する最初の要素の検索に使用されます。これらのアルゴリズムの宣言は次のとおりです。
InputIterator find_if (InputIterator first, InputIterator last,
Predicate);
InputIterator find (InputIterator first, InputIterator last,
const T&);
アルゴリズム find_if() は、引数として、ブール値を返す任意の関数である述語関数 (3.2 節を参照) を使用します。find_if() アルゴリズムは、述語に一致するシーケンス内の最初の要素を指定する新規の反復子を返します。条件に一致する要素が見つからない場合は、第 2 の引数である終了値の反復子が返されます。結果として得られる値は反復子なので、一致する値を検索するには、間接参照演算子 * を使用する必要があります。これについては、プログラム例で説明します。
アルゴリズムの第 2 の書式である find() は、述語関数を特定の値に置き換え、特定のデータ型に固有の等価演算子 == を使用して、この値に一致するシーケンス内の最初の要素を返します。
注 : アルゴリズム find() および find_if() は、関連する構造体の連続線形検索を実行します。順序付きの set および map データ構造は、より効率的な独自の find() メンバー関数を備えています。このため、set と map には汎用 find() アルゴリズムを使用することはできません。
次のプログラム例は、find() および find_if() の使用方法を説明しています。
void find_test ()
// find アルゴリズムの使用方法を説明する
// 完全ソースコードについては alg2.cpp を参照
{
int vintageYears[] = {1967, 1972, 1974, 1980, 1995};
int * start = vintageYears;
int * stop = start + 5;
int * where = find_if (start, stop, isLeapYear);
if (where != stop)
cout << "first vintage leap year is " << *where << endl;
else
cout << "no vintage leap years" << endl;
where = find(start, stop, 1995);
if (where != stop)
cout << "1995 is position " << where - start
<< " in sequence" << endl;
else
cout "1995 does not occur in sequence" << endl;
adjacent_find() アルゴリズムは、シーケンス内のある要素に隣接する次の要素が等価である最初の要素を検索するために使用されます。 たとえば、シーケンスに値 1 4 2 5 6 6 7 5 が含まれる場合は、このアルゴリズムは最初の 6 の値に対応する反復子を返します。条件を満たす値が見つからない場合は、シーケンスの終端の反復子が返されます。このアルゴリズムの宣言は次のとおりです。
ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last [, BinaryPredicate ] );
最初の 2 つの引数は、テスト対象となるシーケンスを指定します。 任意の 3 番目の引数は、ブール値を返す 2 項関数である 2 項述語である必要があります。 存在する場合は 2 項関数が隣接要素のテストに使用され、存在しない場合は等価演算子 == が使用されます。
プログラム例では隣接文字を探し、テキスト文字列を検索します。以下のテキスト例では、これらの隣接文字は位置 5、7、9、21、37 にあります。同じ位置が繰り返して検出されることを避けるために、ループの増分が必要です。
void adjacent_find_example ()
// adjacent_find 命令の使用方法を説明する
// 完全なソースコードについては alg2.cpp を参照
{
char * text = "The bookkeeper carefully opened the door.";
char * start = text;
char * stop = text + strlen(text);
char * where = start;
cout << "In the text: " << text << endl;
while ((where = adjacent_find(where, stop)) != stop) {
cout << "double " << *where
<< " in position " << where - start << endl;
++where;
}
}
アルゴリズム find_first_of() は、シーケンスから別のシーケンスにも含まれる要素の最初の発生を検索するために使用されます。
ForwardIterator1 find_first_of
(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2
[, BinaryPredicate pred ] );
このアルゴリズムは、[first1,last1) で検出され、[first2,last2) にも含まれる最初の要素を指定する新規の反復子を返します。一致が見つからない場合は、第 2 の引数が返されます。結果として得られる値は反復子なので、一致する値を検索するには間接参照演算子 * を使用する必要があります。これを次のプログラム例で説明します。
void find_test ()
// find アルゴリズムの使用方法を説明する
// 完全なソースコードについては alg2.cpp を参照
{
int vintageYears[] = {1967, 1972, 1974, 1980, 1995};
int requestedYears[] = [1923, 1970, 1980, 1974 };
int * start = vintageYears;
int * stop = start + 5;
int * where = find_first_of (start, stop,
requestedyears,requestedyears+4 );
if (where != stop)
cout << "first requested vintage year is " << *where << endl;
else
cout << "no requested vintage years" << endl;
}
// 出力は 1974 を表す
このアルゴリズムは、2 つのシーケンスを操作する他の多くのアルゴリズムと異なり、最初のシーケンスだけでなく両方のシーケンスに、開始および終了反復子の対を使用することに注意してください。
アルゴリズム equal() および mismatch() と同様に、find_first_of() の代替バージョンは、任意の 2 項述語を使用して 2 つのシーケンスの要素を比較します。
basic_string クラスは、ここに挙げる基本パターンのいくつかの有用な多重定義を含め、find_first_of および find_end アルゴリズムに固有のバージョンを提供します。
アルゴリズム search() および search_n() は、大きなシーケンス内の特定サブシーケンスの開始の検索に使用されます。これを理解するための最も簡単な例として、アルゴリズムを他の用途のために一般化できるとしても、大きな文字列内で特定の部分文字列を検索することがいかに大変かを考えてください。引数は、少なくとも順方向反復子の機能を備えていることが前提となります。
ForwardIterator search (ForwardIterator first1, ForwardIterator last1, ForwardIterator first2, ForwardIterator last2 [, BinaryPredicate ]);
たとえば、文字列 "dreams and aspirations" 内の文字列 "ration" の位置を検索するとします。この問題の解をプログラム例に示します。該当する一致が見つからない場合は、返される値は最初のシーケンスの終了反復子です。
void search_example ()
// search アルゴリズムの使用方法を説明する
// 完全なソースコードについては alg2.cpp を参照
{
char * base = "dreams and aspirations";
char * text = "ration";
char * where = search(base, base + strlen(base),
text, text + strlen(text));
if (*where != '\0')
cout << "substring position: " << where - base << endl;
else
cout << "substring does not occur in text" << endl;
}
このアルゴリズムは、2 つのシーケンスを操作する他の多くのアルゴリズムと異なり、最初のシーケンスだけでなく両方のシーケンスに開始および終了反復子の対を使用することに注意してください。
アルゴリズム equal() および mismatch() と同様に、search() の代替バージョンは、任意の 2 項述語を使用して 2 つのシーケンスの要素を比較します。
検索速度は何によって決定されるのでしょうか。最悪の場合、アルゴリズム search() によって実行される比較の数は、2 つのシーケンス内の要素数の積となります。ただし、特別の例外を除き、このような最悪のケースとなることはほとんどありません。
アルゴリズム find_end() は、大きなシーケンス内の特定サブシーケンスの最後の発生の開始の検索に使用されます。これを理解するための最も簡単な例として、アルゴリズムを他の用途のために一般化できるとしても、大きな文字列内で特定の部分文字列を検索することがいかに大変かを考えてください。引数は、少なくとも順方向反復子の機能を備えていることが前提となります。
ForwardIterator find_end (ForwardIterator first1, ForwardIterator last1, ForwardIterator first2, ForwardIterator last2 [, BinaryPredicate ]);
たとえば、文字列 "The road less traveled" 内の文字列 "le" の最後の発生位置を検索するとします。この問題の解をプログラム例に示します。該当する一致が見つからない場合は、返される値は最初のシーケンスの終了反復子です。
void find_end_example ()
// find_end アルゴリズムの使用方法を説明する
// 完全なソースコードについては alg2.cpp を参照
{
char * base = "The road less traveled";
char * text = "le";
char * where = find(base, base + strlen(base),
text, text + strlen(text));
if (*where != '\0')
cout << "substring position: " << where - base << endl;
else
cout << "substring does not occur in text" << endl;
}
このアルゴリズムは、2 つのシーケンスを操作する他の多くのアルゴリズムと異なり、最初のシーケンスだけでなく両方のシーケンスに開始および終了反復子の対を使用することに注意してください。
アルゴリズム find_first_of() および search() と同様に、find_end() の代替バージョンは、任意の 2 項述語を使用して 2 つのシーケンスの要素を比較します。
検索速度は何によって決定されるのでしょうか。search() の場合と同様、最悪の場合、アルゴリズム find_end() によって実行される比較の数は、2 つのシーケンス内の要素数の積となります。
関数 max() および min() を使用して、最大値と最小値の対を検索することができます。これらの関数は、小なり演算子 < の代わりに使用される比較関数を定義する第 3 の引数を任意で使用することができます。この引数は値であり、反復子ではありません。
template <class T> const T& max(const T& a, const T& b [, Compare ] ); template <class T> const T& min(const T& a, const T& b [, Compare ] );
最大関数と最小関数は、汎用アルゴリズム max_element() および min_element() によってシーケンス全体に一般化されます。これらの関数の引数は、入力反復子です。
ForwardIterator max_element (ForwardIterator first,
ForwardIterator last [, Compare ] );
ForwardIterator min_element (ForwardIterator first,
ForwardIterator last [, Compare ] );
これらのアルゴリズムは、それぞれシーケンス内の最大値または最小値を示す反復子を返します。複数の値が条件に一致する場合は、返される結果は最初に条件を満たす値です。どちらのアルゴリズムも任意で第 3 の引数を使用することができます。この引数は、デフォルトの演算子の代わりに比較演算子として使用される関数です。
プログラム例で、これらのアルゴリズムのいくつかの使用方法を説明します。string の例で、文字列を語句に分割するために使用した関数 split() については、12.3 節を参照してください。関数 randomInteger() については、2.5 節を参照してください。
void max_min_example ()
// アルゴリズム max_element および min_element の使用方法を説明する
// 完全なソースコードについては alg2.cpp を参照
{
// 0 から 99 までの乱数ベクトルを作成する
vector<int> numbers(25);
for (int i = 0; i < 25; i++)
numbers[i] = randomInteger(100);
// 最大値を印刷する
vector<int>::iterator max =
max_element(numbers.begin(), numbers.end());
cout << "largest value was " << * max << endl;
// 文字列の使用例
string text =
"It was the best of times, it was the worst of times.";
list<string> words;
split (text, " .,!:;", words);
cout << "The smallest word is "
<< * min_element(words.begin(), words.end())
<< " and the largest word is "
<< * max_element(words.begin(), words.end())
<< endl;
}
最大および最小アルゴリズムは、標準 C++ ライブラリの提供するすべてのデータ型に使用することができます。ただし、順序付きデータ型である set および map の場合は、構造体の最初または最後の要素として最大値または最小値に容易にアクセスすることができます。
mismatch() という名前から、このアルゴリズムが、2 つのシーケンスが等価であるかどうかを決定する equal() の逆アルゴリズムではないかと考えるかもしれません (13.6.4 節を参照)。しかし、mismatch() アルゴリズムは、2つの並列シーケンスが異なる要素を持つ最初の位置を示す反復子の pair を返すものです。構造体 pair については、9.1 節と 9.2.1 節で説明します。
第 2 のシーケンスは、終了位置を使用せずに開始位置のみで表示されます。第 2 のシーケンスには最初のシーケンスと同数またはそれ以上の要素が含まれると想定されていますが、確認はされません。mismatch() の引数と戻り型は、次のように定義されます。
pair<InputIterator, InputIterator> mismatch
(InputIterator first1, InputIterator last1,
InputIterator first2 [, BinaryPredicate ] );
2 つのシーケンスの要素は、要素ごとに並行して検査されます。不一致、つまり 2 つのシーケンスが異なるポイントが検出されると、2 つの異なる要素の位置を表示する反復子を含む pair が作成されて、返されます。最初のシーケンスが不一致要素の検出前に使い果たされると、最初のシーケンスの終わりの値と第 2 のシーケンスの最後の検査値を含む pair が返されます。第 2 のシーケンスは使い果たされていなくても構いません。
この手順はプログラム例で説明しています。関数 imismatch_test() は、2 つの string 値を引数として使用します。この 2 つの値が辞書式に比較され、その相対的な順序を示すメッセージが印刷されます。これは lexicographic_compare() アルゴリズムによって実行される分析と同様ですが、この関数はブール値を返すだけです。
mismatch() アルゴリズムは、第 2 のシーケンスの長さが最初のシーケンスと同じかそれ以上であると想定しているため、まず 2 つの文字列の長さが比較され、第 2 の文字列が最初の文字列より短い場合は、引数が逆転されます。mismatch() の呼び出し後、結果の pair の要素が構成要素部分に分割されます。次に、これらの部分がテストされ、該当する順序が決定されます。
void mismatch_test (char * a, char * b)
// mismatch アルゴリズムの使用方法を説明する
// 完全なソースコードについては alg2.cpp を参照
{
pair<char *, char *> differPositions(0, 0);
char * aDiffPosition;
char * bDiffPosition;
if (strlen(a) < strlen(b)) {
// 第 2 の文字列の方が長いことを確認する
differPositions = mismatch(a, a + strlen(a), b);
aDiffPosition = differPositions.first;
bDiffPosition = differPositions.second;
}
else {
differPositions = mismatch(b, b + strlen(b), a);
// 次の逆転した順序に注意
aDiffPosition = differPositions.second;
bDiffPosition = differPositions.first;
}
// 結果の値を比較する
cout << "string " << a;
if (*aDiffPosition == *bDiffPosition)
cout << " is equal to ";
else if (*aDiffPosition < *bDiffPosition)
cout << " is less than ";
else
cout << " is greater than ";
cout << b << endl;
}
アルゴリズム mismatch() の第 2 の書式はこれと似ていますが、第 4 の引数として 2 項述語を使用する点が異なります。この 2 項関数は、要素の比較のために == 演算子の代わりに使用されます。