The next category of algorithms reduces an entire sequence to a single scalar value. Remember that two of these algorithms, std::accumulate() and std::inner_product(), are declared in the <numeric> header file, not the <algorithm> header file as are the other generic algorithms.
NOTE -- The example functions described in the following sections are in the file alg5.cpp.
The algorithms std::count() and std::count_if() are used to discover the number of elements that match a given value or that satisfy a given predicate, respectively. Each algorithm comes in two forms. The newer form returns the number of matches found, while the older one takes as argument a reference to a counting value, typically an integer, and increments this value. In the latter case the std::count() function itself yields no value.
The newer form of these functions is currently mandated by the standard. The older form is retained for two reasons: first, for backward compatibility, since older versions of the standard contained it; and second, because the newer form requires that a compiler support partial specialization, which most (but not all) compilers now do.
namespace std {
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&);
}
The example code fragment illustrates the use of the older form of these algorithms. The call on std::count() counts the number of occurrences of the letter e in a sample string, while the invocation of std::count_if() counts the number of vowels.
void count_example()
// illustrates the use of the count algorithm
// see alg5.cpp for complete source code
{
int eCount = 0;
int vowelCount = 0;
char *text = "Now is the time to begin";
std::count(text, text + strlen(text), 'e', eCount);
std::count_if(text, text + strlen(text), isVowel, vowelCount);
std::cout << "There are " << eCount
<< " letter e's " << std::endl
<< "and " << vowelCount << " vowels in the text:"
<< text << std::endl;
}
Note that if your compiler does not support partial specialization, you don't have the form of the std::count() algorithms that return the sum as a function result, but only the form that adds to the last argument in its parameter list, which is passed by reference. This means successive calls on these functions can be used to produce a cumulative sum. This also means that you must initialize the variable passed to this last argument location prior to calling one of these algorithms.
The result generated by the std::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, operator+, but this can be replaced by any binary function. An initial value or identity must be provided. This value is returned for empty sequences, and is otherwise used as the left argument for the first calculation.
namespace std {
ContainerType accumulate(InputIterator first,
InputIterator last,
ContainerType initial
[, BinaryFunction ]);
}
The example program illustrates the use of std::accumulate() to produce the sum and product of a vector of int 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()
// illustrates the use of the accumulate algorithm
// see alg5.cpp for complete source code
{
int numbers[] = {1, 2, 3, 4, 5};
// first example, simple accumulation
int sum = std::accumulate(numbers, numbers + 5, 0);
int product =
std::accumulate(numbers, numbers + 5, 1,
std::times<int>());
std::cout << "The sum of the first five integers is "
<< sum << std::endl;
std::cout << "The product is " << product << std::endl;
// second example, with different types for initial value
std::list<int> nums;
nums = std::accumulate(numbers, numbers+5, nums, intReplicate);
}
std::list<int>& intReplicate(std::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 is required to match the container type. This is illustrated in the example program by the invocation of std::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 int 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 C++ Standard Library includes the following algorithm for computing an inner product:
namespace std {
ContainerType inner_product
(InputIterator first1, InputIterator last1,
InputIterator first2, ContainerType initialValue
[ , BinaryFunction add, BinaryFunction times ]);
}
The first three arguments to the std::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 std::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 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()
// illustrates the use of the inner_product algorithm
// see alg5.cpp for complete source code
{
int a[] = {4, 3, -2};
int b[] = {7, 3, 2};
// example 1, a simple inner product
int in1 = std::inner_product(a, a+3, b, 0);
std::cout << "Inner product is " << in1 << std::endl;
// example 2, user defined operations
bool anyequal = std::inner_product(a, a+3, b, true,
std::logical_or<bool>(), std::equal_to<int>());
std::cout << "any equal? " << anyequal << std::endl;
}
The std::equal() algorithm tests two sequences for pairwises equality. By using an alternative binary predicate, it can also be used for a wide variety of other pair-wise tests of parallel sequences, such as a pairwise test that returns a boolean result. The std::mismatch() algorithm gives the location of elements that fail that test (Section 13.3.7).
The arguments of the std::equal() algorithm are simple input iterators:
namespace std {
bool equal(InputIterator first, InputIterator last,
InputIterator first2 [, BinaryPredicate]);
}
The std::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 std::greater_equal() function; in this fashion, true is 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()
// illustrates the use of the equal algorithm
// see alg5.cpp for complete source code
{
int a[] = {4, 5, 3};
int b[] = {4, 3, 3};
int c[] = {4, 5, 3};
std::cout << "a = b is: " << std::equal(a, a+3, b) << std::endl;
std::cout << "a = c is: " << std::equal(a, a+3, c) << std::endl;
std::cout << "a pair-wise greater-equal b is: "
<< std::equal(a, a+3, b, std::greater_equal<int>())
<< std::endl;
}
A lexical comparison is commonly used to determine the dictionary order of words. In this procedure, the elements or characters of two sequences are compared in pair-wise fashion. As long as characters within a pair match, the algorithm advances to the next pair. When characters within a pair fail to match, the earlier character determines the smaller word. For example, everybody is smaller than everything, since the b in the former word alphabetically precedes the t in the latter. Should one or the other sequence terminate before the other, the terminated sequence is considered the smaller. For example, every precedes both everybody and everything, but comes after eve. Finally, if both sequences terminate at the same time and pair-wise characters match in all cases, the two words are considered equal.
The std::lexicographical_compare() algorithm implements the concept of lexical comparison, returning true if the first sequence is smaller than the second, and false otherwise. The algorithm is generalized to any sequence. Thus, the std::lexicographical_compare() algorithm can be used with arrays, strings, vectors, lists, or any other data structures of the C++ Standard Library.
namespace std {
bool lexicographical_compare
(InputIterator first1, InputIterator last1,
InputIterator first2, InputIterator last2
[, BinaryFunction ] );
}
Unlike most other algorithms that take two sequences as argument, the std::lexicographical_compare() algorithm uses a first and a past-end iterator for both sequences. A variation on the algorithm also takes a fifth argument, which is the binary function used to compare corresponding elements from the two sequences.
The example program illustrates the std::lexicographical_compare() algorithm in use with character sequences, and arrays of integer values.
void lexicographical_compare_example()
// illustrates the use of the lexicographical_compare algorithm
// see alg5.cpp for complete source code
{
char *wordOne = "everything";
char *wordTwo = "everybody";
std::cout << "compare everybody to everything "
<< std::lexicographical_compare(wordTwo,
wordTwo + std::strlen(wordTwo),
wordOne,
wordOne + std::strlen(wordOne))
<< std::endl;
int a[] = {3, 4, 5, 2};
int b[] = {3, 4, 5};
int c[] = {3, 5};
std::cout << "compare a to b:"
<< std::lexicographical_compare(a, a+4, b, b+3)
<< std::endl;
std::cout << "compare a to c:"
<< std::lexicographical_compare(a, a+4, c, c+2)
<< std::endl;
}