次に説明するアルゴリズムのカテゴリは、シーケンス全体を単一のスカラー値に還元します。accumulate() と inner_product() の 2 つのアルゴリズムは、その他の汎用アルゴリズムのような algorithm ヘッダーファイルではなく、numeric ヘッダーファイルに宣言されることに注意してください。
注 : 以降の節で説明する関数例は、alg5.cpp ファイルにあります。
アルゴリズム count() および count_if() は、それぞれ特定の値に一致する、または特定の述語に一致する要素数を検出するために使用されます。どちらのアルゴリズムにも 2 つの書式があります。新しい書式は、検出された一致の数を返しますが、旧書式はカウント値 (一般に整数) を引数として参照し、この値を増分します。後者の場合、count() 関数そのものは値を算出しません。
これらの関数の新しい書式は、現在標準に指定されています。旧書式は、次の 2 つの理由から保持されています。1 つは、下位互換性のためです。これは旧版の標準には旧書式が使用されているためです。もう 1 つは、まだまれですが、新書式では一部の特殊化をコンパイラがサポートする必要があるためです。
iterator_traits<InputIterator>::distance_type
count (InputIterator first, InputIterator last, const T& value);
iterator_traits<InputIterator>::distance_type
count_if (InputIterator first, InputIterator last, Predicate pred);
void count (InputIterator first, InputIterator last,
const T&, Size &);
void count_if (InputIterator first, InputIterator last,
Predicate, Size &);
このコード例の断片は、これらのアルゴリズムの旧書式の使用方法を説明しています。count() の呼び出しにより、サンプル文字列内の文字 e の発生回数がカウントされ、count_if() の呼び出しにより母音の数がカウントされます。
void count_example ()
// count アルゴリズムの使用方法を説明する
// 完全なソースコードについては alg5.cpp を参照
{
int eCount = 0;
int vowelCount = 0;
char * text = "Now is the time to begin";
count (text, text + strlen(text), 'e', eCount);
count_if (text, text + strlen(text), isVowel, vowelCount);
cout << "There are " << eCount << " letter e's " << endl
<< "and " << vowelCount << " vowels in the text:"
<< text << endl;
}
使用するコンパイラで一部の特殊化がサポートされない場合は、count() アルゴリズムの書式は関数の結果として和を返さず、そのパラメタリストに、参照によって受け渡される最後の引数を追加するだけであることに注意してください。つまり、これらの関数を連続的に呼び出すことによって、累計を生成することができます。これはまた、アルゴリズムを呼び出す前に、この最後の引数位置に渡される変数を初期化する必要があることを意味しています。
accumulate() アルゴリズムにより生成される結果は、シーケンスの各要素の間に 2 項演算子を置き、その結果を評価して得られる値です。デフォルトの演算子は加算演算子 + ですが、これは 2 項関数で置き換えることができます。初期値または識別が設定される必要があります。この値は、空のシーケンスに返されるか、または最初の演算の左辺の引数として使用されます。
ContainerType accumulate (InputIterator first, InputIterator last,
ContainerType initial [, BinaryFunction ] );
プログラム例で、accumulate() を使用して integer 値の vector の和と積を生成する方法を説明します。最初の例では、識別はゼロで、デフォルトの演算子 + が使用されます。第 2 の例では、識別は 1 で、times という乗算演算子が第 4 の引数として明示的に渡されます。
void accumulate_example ()
// accumulate アルゴリズムの使用方法を説明する
// 完全なソースコードについては alg5.cpp を参照
{
int numbers[] = {1, 2, 3, 4, 5};
// 最初の例は単純累積である
int sum = accumulate (numbers, numbers + 5, 0);
int product =
accumulate (numbers, numbers + 5, 1, times<int>());
cout << "The sum of the first five integers is " << sum << endl;
cout << "The product is " << product << endl;
// 第 2 の例では、初期値に異なる型を使用する
list<int> nums;
nums = accumulate (numbers, numbers+5, nums, intReplicate);
}
list<int>& intReplicate (list<int>& nums, int n)
// シーケンス n 〜 1 をリストの終わりに追加する
{
while (n) nums.push_back(n--);
return nums;
}
コンテナ型の照合には、識別の値も 2 項関数の結果も必要ありません。これを、上記の第 2 のプログラム例に示した accumulate() の呼び出しにより説明します。ここでは、識別は空のリストです。プログラム例の後に示す関数は、引数として list と integer 値を取り、値を繰り返し list に挿入します。挿入される値は、引数から 1 への減少シーケンスです。最初の例と同じ vector の入力例では、結果の list には 1 2 1 3 2 1 4 3 2 1 5 4 3 2 1 の 15 の値が含まれます。
それぞれ a1, a2, ... an と b1, b2, ... bn の n 個の要素からなる 2 つのシーケンスがあるとします。シーケンスの内積は、並列積の和、すなわち値 a1 * b1 + a2 * b2 + ... + an * bn です。内積は、多くの数理計算で発生します。たとえば、行×列の内積は、従来の行列乗算アルゴリズムの核心となるものです。一般内積も構造は同じですが、加算演算子と乗算演算子を任意の 2 項関数と置き換えることができます。標準 C++ ライブラリには、内積の計算のための次のアルゴリズムがあります。
ContainerType inner_product
(InputIterator first1, InputIterator last1,
InputIterator first2, ContainerType initialValue
[ , BinaryFunction add, BinaryFunction times ] );
inner_product() アルゴリズムの最初の 3 つの引数は、2 つの入力シーケンスを定義しています。第 2 のシーケンスは、開始反復子だけによって指定され、最初のシーケンスと同じかそれ以上の要素を含むものと想定されています。次の引数は初期値、すなわち総和演算子に使用される識別です。これは、accumulate() アルゴリズムに使用される識別と同じです。一般内積関数では、最後の 2 つの引数は、それぞれ加算演算子と乗算演算子の代わりに使用される 2 項関数です。
プログラム例では、第 2 の呼び出しが引数としての代替関数の使用方法を説明しています。乗算が等価テストに置き換えられ、加算は論理 or に置き換えられています。いずれかの対が等価であれば結果は真となり、そうでなければ偽となります。or の代わりに and を使用すると、すべての対が等価の場合に限り、結果は真になります。これは、次の節で説明する equal() アルゴリズムと事実上同じものです。
void inner_product_example ()
// inner_product アルゴリズムの使用方法を説明する
// 完全なソースコードについては alg5.cpp を参照
{
int a[] = {4, 3, -2};
int b[] = {7, 3, 2};
// 例 1、単純内積
int in1 = inner_product(a, a+3, b, 0);
cout << "Inner product is " << in1 << endl;
// 例 2、ユーザー定義の演算子
bool anyequal = inner_product(a, a+3, b, true,
logical_or<bool>(), equal_to<int>());
cout << "any equal? " << anyequal << endl;
}
equal() アルゴリズムは、2 つのシーケンスの等価性をテストします。代替 2 項述語を使用することによって、ブール型の結果を返す対テストなど、並列シーケンスの他の対テストにもこのアルゴリズムを広範に使用することができます。mismatch() アルゴリズムは、テストに失敗した要素を検出します (13.3.7 節を参照)。
equal() アルゴリズムの引数は、単純な入力反復子です。
bool equal (InputIterator first, InputIterator last,
InputIterator first2 [, BinaryPredicate] );
equal() アルゴリズムでは、第 2 のシーケンスに、最初のシーケンスと同じかそれ以上の要素が含まれていることが想定されていますが、確認はされません。すべての値が対応する要素と等しければ、true の結果が生成されます。このアルゴリズムの代替バージョンは、等価テストの代わりに任意のブール型の関数を使用し、すべての対要素が述語に一致すれば true を返します。プログラム例では、述語を greater_equal() 関数に置き換えてこれを説明しています。この場合、最初のシーケンス内のすべての値が 第2のシーケンスの対応する値より大きいか等しい場合に限り、true が返されます。
void equal_example ()
// equal アルゴリズムの使用方法を説明する
// 完全なソースコードについては alg5.cpp を参照
{
int a[] = {4, 5, 3};
int b[] = {4, 3, 3};
int c[] = {4, 5, 3};
cout << "a = b is: " << equal(a, a+3, b) << endl;
cout << "a = c is: " << equal(a, a+3, c) << endl;
cout << "a pair-wise greater-equal b is: "
<< equal(a, a+3, b, greater_equal<int>()) << endl;
}
字句比較は、普通は語句の辞書式順序を決定するために使用されます。この手順では、2 つのシーケンスの要素または文字が対ごとに比較されます。対の文字が一致していれば、アルゴリズムは次の対に進みます。対の文字が不一致の場合、辞書式順序が先である文字が小さいワードを決定します。たとえば、everybody と everything を比較する場合、前の語句の b は後の語句の t よりもアルファベット順が先なので、everybody は everything より小さいことになります。あるシーケンスが他のシーケンスより早く終わる場合、終了した方がより小さいシーケンスとみなされます。たとえば、every は everybody や everything よりも順序が先ですが、eve よりも順序が後です。最後に、シーケンスが同時に終了し、対の文字がすべて一致する場合、2 つの語句は等価であるとみなされます。
lexicographical_compare() アルゴリズムは、字句比較の概念を実装し、最初のシーケンスが第 2 のシーケンスより小さいと true を返し、そうでない場合は false を返します。このアルゴリズムはどのシーケンスにも一般化されます。したがって、lexicographical_compare() アルゴリズムは、配列、string、vector、list、標準 C++ ライブラリのその他のデータ構造体に使用することができます。
bool lexicographical_compare (InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2 [, BinaryFunction ] );
引数に 2 つのシーケンスを使用する他の大部分のアルゴリズムと異なり、lexicographical_compare() アルゴリズムは両方のシーケンスに始まりと終了の反復子を使用します。このアルゴリズムのバリエーションでは、5 番目の引数が使用されます。これは、2 つのシーケンスの対応する要素の比較に使用される 2 項関数です。
次のプログラム例は、文字シーケンスと整数値の配列を使用して lexicographical_compare() アルゴリズムの使用方法を説明しています。
void lexicographical_compare_example()
// lexicographical_compare アルゴリズムの使用方法を説明する
// 完全なソースコードについては alg5.cpp を参照
{
char * wordOne = "everything";
char * wordTwo = "everybody";
cout << "compare everybody to everything " <<
lexicographical_compare(wordTwo, wordTwo + strlen(wordTwo),
wordOne, wordOne + strlen(wordOne)) << endl;
int a[] = {3, 4, 5, 2};
int b[] = {3, 4, 5};
int c[] = {3, 5};
cout << "compare a to b:" <<
lexicographical_compare(a, a+4, b, b+3) << endl;
cout << "compare a to c:" <<
lexicographical_compare(a, a+4, c, c+2) << endl;
}