📄 sca_1926.htm
字号:
<HTML><HEAD><TITLE>Scalar-Producing Algorithms</TITLE></HEAD>
<BODY>
<A HREF="ug.htm"><IMG SRC="images/banner.gif"></A>
<P><STRONG>Click on the banner to return to the user guide home page.</STRONG></P>
<P>©Copyright 1996 Rogue Wave Software</P>
<H2>Scalar-Producing Algorithms</H2>
<A HREF="sidebar.htm#sidebar66"><IMG SRC="images/note.gif" BORDER=0> <STRONG>Obtaining the Source</STRONG></A>
<P>The next category of algorithms are those that reduce an entire sequence to a single scalar value.</P>
<P>Remember that two of these algorithms, <SAMP>accumulate()</SAMP> and <SAMP>inner_product(),</SAMP> are declared in the <SAMP>numeric</SAMP> header file, not the <SAMP>algorithm</SAMP> header file as are the other generic algorithms.</P>
<A NAME="countthenumberofelementsthatsatisfyacondition"><H3>Count the Number of Elements that Satisfy a Condition</H3></A>
<P>The algorithms <SAMP>count()</SAMP> and <SAMP>count_if()</SAMP> 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 <I>not</I> returned as the value of the function. The <SAMP>count()</SAMP> function itself yields no value.</P>
<PRE>void count (InputIterator first, InputIterator last,
const T&, Size &);
void count_if (InputIterator first, InputIterator last,
Predicate, Size &);
</PRE>
<A HREF="sidebar.htm#sidebar67"><IMG SRC="images/note.gif" BORDER=0> <STRONG>The Resulting Count</STRONG></A>
<P>The example code fragment illustrates the use of these algorithms. The call on <SAMP>count()</SAMP> will count the number of occurrences of the letter <SAMP>e</SAMP> in a sample string, while the invocation of <SAMP>count_if()</SAMP> will count the number of vowels.</P>
<PRE>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;
}</PRE>
<A NAME="reducesequencetoasinglevalue"><H3>Reduce Sequence to a Single Value</H3></A>
<P>The result generated by the <SAMP>accumulate()</SAMP> 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, <SAMP>+</SAMP>, 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. </P>
<PRE>ContainerType accumulate (InputIterator first, InputIterator last,
ContainerType initial [, BinaryFunction ] );</PRE>
<!--ASQ-1 The style "teletype gap" is not associated; its content follows: --><P>The example program illustrates the use of <SAMP>accumulate()</SAMP> to produce the sum and product of a vector of integer values. In the first case the identity is zero, and the default operator <SAMP>+</SAMP> is used. In the second invocation the identity is 1, and the multiplication operator (named <B><I>times</I></B>) is explicitly passed as the fourth argument.</P>
<PRE><I>void accumulate_example ()</I>
<I>// illustrate the use of the accumulate algorithm</I>
<I>{</I>
<I> int numbers[] = {1, 2, 3, 4, 5};</I></PRE>
<!--ASQ-1 The style "teletype gap" is not associated; its content follows: --><PRE><I>// first example, simple accumulation</I>
<I> int sum = accumulate (numbers, numbers + 5, 0);</I>
<I> int product = </I>
<I> accumulate (numbers, numbers + 5, 1, times<int>());</I></PRE><!--ASQ-1 The style "teletype gap" is not associated; its content follows: --><PRE><I> cout << "The sum of the first five integers is " << sum << endl;</I>
<I> cout << "The product is " << product << endl;</I></PRE><!--ASQ-1 The style "teletype gap" is not associated; its content follows: --><PRE><I>// second example, with different types for initial value</I>
<I> list<int> nums;</I>
<I> nums = accumulate (numbers, numbers+5, nums, intReplicate);</I>
<I>}</I></PRE><!--ASQ-1 The style "teletype gap" is not associated; its content follows: --><PRE>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;
}
</PRE><P>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 <SAMP>accumulate()</SAMP> 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.</P>
<A NAME="generalizedinnerproduct"><H3>Generalized Inner Product</H3></A>
<P>Assume we have two sequences of <I>n</I> elements each; <I>a1, a2, ... an</I> and <I>b1, b2, ... bn.</I> The <I>inner product</I> of the sequences is the sum of the parallel products, that is the value <I>a1 * b1 + a2 * b2 + ... + an * bn</I>. 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:</P>
<PRE>ContainerType inner_product
(InputIterator first1, InputIterator last1,
InputIterator first2, ContainerType initialValue
[ , BinaryFunction add, BinaryFunction times ] );
</PRE>
<P>The first three arguments to the <SAMP>inner_product()</SAMP> 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 <SAMP>accumulate()</SAMP> 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.</P>
<P>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 <I>or</I>. The result is true if any of the pairs are equal, and false otherwise. Using an <I>and</I> in place of the <I>or</I> would have resulted in a test which was true only if <I>all</I> pairs were equal; in effect the same as the <SAMP>equal()</SAMP> algorithm described in the next section.</P>
<PRE>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;
}
</PRE>
<A NAME="testtwosequencesforpairwiseequality"><H3>Test Two Sequences for Pairwise Equality</H3></A>
<P>The<SAMP> equal()</SAMP> 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:</P>
<PRE>bool equal (InputIterator first, InputIterator last,
InputIterator first2 [, BinaryPredicate] );
</PRE>
<A HREF="sidebar.htm#sidebar68"><IMG SRC="images/note.gif" BORDER=0> <STRONG>Equal and Mismatch</STRONG></A>
<P>The <SAMP>equal()</SAMP> algorithm assumes, but does not verify, that the second sequence contains at least as many elements as the first. A <SAMP>true</SAMP> 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 <SAMP>true</SAMP> if all pair-wise elements satisfy the predicate. In the sample program this is illustrated by replacing the predicate with the <SAMP>greater_equal()</SAMP> function, and in this fashion <SAMP>true</SAMP> will be returned only if all values in the first sequence are greater than or equal to their corresponding value in the second sequence.</P>
<PRE>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;
}</PRE>
<A NAME="lexicalcomparison"><H3>Lexical Comparison </H3></A>
<P>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, <samp>everybody</samp> is smaller than <samp>everything</samp>, since the <samp>b</samp> in the former word alphabetically precedes the <samp>t</samp> 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, <samp>every</samp> precedes both <samp>everybody</samp> and <samp>everything</samp>, but comes after <samp>eve</samp>. 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.</P>
<P>The <samp>lexicographical_compare()</samp> algorithm implements this idea, returning <samp>true</samp> if the first sequence is smaller than the second, and <samp>false</samp> otherwise. The algorithm has been generalized to any sequence. Thus the <samp>lexicographical_comare()</samp> algorithm can be used with arrays, strings, vectors, lists, or any of the other data structures used in the standard library.</P>
<PRE>
bool lexicographical_compare
(InputIterator first1, InputIterator last1,
InputInterator first2, InputIterator last2 [, BinaryFunction ] );
</PRE>
<P>Unlike most of the other algorithms that take two sequences as an argument, the <pre>lexicographical_compare()</samp> algorithm, uses a first and past-end iterator for <em>both</em> 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.</P>
<P>The example program illustrates the use of this algorithm with character sequences, and with arrays of integer values.</P>
<PRE>
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;
}
</PRE>
<HR>
<A HREF="rem_8388.htm"><IMG SRC="images/prev.gif"></A> <A HREF="booktoc.htm"><IMG SRC="images/toc.gif"></A> <A HREF="seq_4302.htm"><IMG SRC="images/next.gif"></A></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -