Obtaining the Source
The next category of algorithms are those that reduce an entire sequence to a single scalar value.
Remember that two of these algorithms, accumulate() and inner_product(), are declared in the numeric header file, not the algorithm header file as are the other generic algorithms.
The algorithms count() and count_if() are used to discover the number of elements that match a given value or that satisfy a given predicate, respectively. Both take as argument a reference to a counting value (typically an integer), and increment this value. Note that the count is passed as a by-reference argument, and is not returned as the value of the function. The count() function itself yields no value.
void count (InputIterator first, InputIterator last,
const T&, Size &);
void count_if (InputIterator first, InputIterator last,
Predicate, Size &);
The Resulting Count
The example code fragment illustrates the use of these algorithms. The call on count() will count the number of occurrences of the letter e in a sample string, while the invocation of count_if() will count the number of vowels.
void count_example ()
// illustrate the use of the count algorithm
{
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;
}
The result generated by the accumulate() algorithm is the value produced by placing a binary operator between each element of a sequence, and evaluating the result. By default the operator is the addition operator, +, however this can be replaced by any binary function. An initial value (an identity) must be provided. This value is returned for empty sequences, and is otherwise used as the left argument for the first calculation.
ContainerType accumulate (InputIterator first, InputIterator last,
ContainerType initial [, BinaryFunction ] );
The example program illustrates the use of accumulate() to produce the sum and product of a vector of integer values. In the first case the identity is zero, and the default operator + is used. In the second invocation the identity is 1, and the multiplication operator (named times) is explicitly passed as the fourth argument.
void accumulate_example ()
// illustrate the use of the accumulate algorithm
{
int numbers[] = {1, 2, 3, 4, 5};
// first example, simple accumulation
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;// second example, with different types for initial value
list<int> nums;
nums = accumulate (numbers, numbers+5, nums, intReplicate);
}list<int>& intReplicate (list<int>& nums, int n)
// add sequence n to 1 to end of list
{
while (n) nums.push_back(n--);
return nums;
}
Neither the identity value nor the result of the binary function are required to match the container type. This is illustrated in the example program by the invocation of accumulate() shown in the second example above. Here the identity is an empty list. The function (shown after the example program) takes as argument a list and an integer value, and repeatedly inserts values into the list. The values inserted represent a decreasing sequence from the argument down to 1. For the example input (the same vector as in the first example), the resulting list contains the 15 values 1 2 1 3 2 1 4 3 2 1 5 4 3 2 1.
Assume we have two sequences of n elements each; a1, a2, ... an and b1, b2, ... bn. The inner product of the sequences is the sum of the parallel products, that is the value a1 * b1 + a2 * b2 + ... + an * bn. Inner products occur in a number of scientific calculations. For example, the inner product of a row times a column is the heart of the traditional matrix multiplication algorithm. A generalized inner product uses the same structure, but permits the addition and multiplication operators to be replaced by arbitrary binary functions. The standard library includes the following algorithm for computing an inner product:
ContainerType inner_product
(InputIterator first1, InputIterator last1,
InputIterator first2, ContainerType initialValue
[ , BinaryFunction add, BinaryFunction times ] );
The first three arguments to the inner_product() algorithm define the two input sequences. The second sequence is specified only by the beginning iterator, and is assumed to contain at least as many elements as the first sequence. The next argument is an initial value, or identity, used for the summation operator. This is similar to the identity used in the accumulate() algorithm. In the generalized inner product function the last two arguments are the binary functions that are used in place of the addition operator, and in place of the multiplication operator, respectively.
In the example program the second invocation illustrates the use of alternative functions as arguments. The multiplication is replaced by an equality test, while the addition is replaced by a logical or. The result is true if any of the pairs are equal, and false otherwise. Using an and in place of the or would have resulted in a test which was true only if all pairs were equal; in effect the same as the equal() algorithm described in the next section.
void inner_product_example ()
// illustrate the use of the inner_product algorithm
{
int a[] = {4, 3, -2};
int b[] = {7, 3, 2};
// example 1, a simple inner product
int in1 = inner_product(a, a+3, b, 0);
cout << "Inner product is " << in1 << endl;
// example 2, user defined operations
bool anyequal = inner_product(a, a+3, b, true,
logical_or<bool>(), equal_to<int>());
cout << "any equal? " << anyequal << endl;
}
The equal() algorithm tests two sequences for pairwise equality. By using an alternative binary predicate, it can also be used for a wide variety of other pair-wise tests of parallel sequences. The arguments are simple input iterators:
bool equal (InputIterator first, InputIterator last,
InputIterator first2 [, BinaryPredicate] );
Equal and Mismatch
The equal() algorithm assumes, but does not verify, that the second sequence contains at least as many elements as the first. A true result is generated if all values test equal to their corresponding element. The alternative version of the algorithm substitutes an arbitrary boolean function for the equality test, and returns true if all pair-wise elements satisfy the predicate. In the sample program this is illustrated by replacing the predicate with the greater_equal() function, and in this fashion true will be returned only if all values in the first sequence are greater than or equal to their corresponding value in the second sequence.
void equal_example ()
// illustrate the use of the equal algorithm
{
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;
}
A lexical comparison of two sequences can be described by noting the features of the most common example, namely the comparision of two words for the purposes of placing them in "dictionary order." When comparing two words, the elements (that is, the characters) of the two sequences are compared in a pair-wise fashion. As long as they match, the algorithm advances to the next character. If two corresponding characters fail to match, the earlier character determines the smaller word. So, for example, everybody is smaller than everything, since the b in the former word alphabetically precedes the t in the latter word. Should one or the other sequence terminate before the other, than the terminated sequence is consider to be smaller than the other. So, for example, every precedes both everybody and everything, but comes after eve. Finally, if both sequences terminate at the same time, and, in all cases, pair-wise characters match, then the two words are considered to be equal.
The lexicographical_compare() algorithm implements this idea, returning true if the first sequence is smaller than the second, and false otherwise. The algorithm has been generalized to any sequence. Thus the lexicographical_comare() algorithm can be used with arrays, strings, vectors, lists, or any of the other data structures used in the standard library.
bool lexicographical_compare
(InputIterator first1, InputIterator last1,
InputInterator first2, InputIterator last2 [, BinaryFunction ] );
Unlike most of the other algorithms that take two sequences as an argument, the
lexicographical_compare() algorithm, uses a first and past-end iterator for both sequences. A variation on the algorithm takes a fifth argument, which is the binary function used to compare the corresponding elements from the two sequences.The example program illustrates the use of this algorithm with character sequences, and with arrays of integer values.
void lexicographical_compare_example() // illustrate the use of the lexicographical_compare algorithm { 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; }