<HTML>
<HEAD>
<TITLE>Scalar-Producing Algorithms</TITLE>
<LINK REL=StyleSheet HREF="../rw.css" TYPE="text/css" TITLE="Apache stdcxx Stylesheet"></HEAD>
<BODY BGCOLOR=#FFFFFF>
<A HREF="13-5.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="13-7.html"><IMG SRC="images/bnext.gif" WIDTH=25 HEIGHT=21 ALT="Next file" BORDER=O></A><DIV CLASS="DOCUMENTNAME"><B>Apache C++ Standard Library User's Guide</B></DIV>
<H2>13.6 Scalar-Producing Algorithms</H2>
<A NAME="idx323"><!></A>
<P>The next category of algorithms reduces an entire sequence to a single scalar value. Remember that two of these algorithms, <SAMP>std::accumulate()</SAMP> and <SAMP>std::inner_product()</SAMP>, are declared in the <SAMP>&lt;numeric</SAMP>&gt; header file, not the <SAMP>&lt;algorithm</SAMP>&gt; header file as are the other generic algorithms.</P>
<BLOCKQUOTE><HR><B>
NOTE -- The example functions described in the following sections are in the file alg5.cpp.
</B><HR></BLOCKQUOTE>
<A NAME="1361"><H3>13.6.1 Count the Number of Elements That Satisfy a Condition</H3></A>
<A NAME="idx324"><!></A>
<P>The algorithms <SAMP>std::count()</SAMP> and <SAMP>std::count_if()</SAMP> 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 <SAMP>std::count()</SAMP> function itself yields no value. </P>
<P>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.</P>

<UL><PRE>
namespace std {
  iterator_traits&lt;InputIterator&gt;::distance_type
  count(InputIterator first, InputIterator last, const T&amp; value);

  iterator_traits&lt;InputIterator&gt;::distance_type
  count_if(InputIterator first, InputIterator last,
           Predicate pred);

  void count(InputIterator first, InputIterator last,
             const T&amp;, Size&amp;);
  void count_if(InputIterator first, InputIterator last,
                Predicate, Size&amp;);
}
</PRE></UL>
<P>The example code fragment illustrates the use of the older form of these algorithms. The call on <SAMP>std::count()</SAMP> counts the number of occurrences of the letter <SAMP>e</SAMP> in a sample string, while the invocation of <SAMP>std::count_if()</SAMP> counts the number of vowels.</P>

<A NAME="idx325"><!></A>
<UL><PRE>
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 &lt;&lt; "There are " &lt;&lt; eCount
            &lt;&lt; " letter e's " &lt;&lt; std::endl
            &lt;&lt; "and " &lt;&lt; vowelCount &lt;&lt; " vowels in the text:"
            &lt;&lt; text &lt;&lt; std::endl;
}
</PRE></UL>
<P>Note that if your compiler does not support partial specialization, you don't have the form of the <SAMP>std::count()</SAMP> 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.</P>
<A NAME="1362"><H3>13.6.2 Reduce Sequence to a Single Value</H3></A>
<A NAME="idx326"><!></A>
<P>The result generated by the <SAMP>std::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>operator+</SAMP>, but this can be replaced by any binary function. An initial value or <I>identity</I> must be provided. This value is returned for empty sequences, and is otherwise used as the left argument for the first calculation. </P>

<UL><PRE>
namespace std {
  ContainerType accumulate(InputIterator first, 
                           InputIterator last, 
                           ContainerType initial 
                           [, BinaryFunction ]);
}
</PRE></UL>
<P>The example program illustrates the use of <SAMP>std::accumulate()</SAMP> to produce the sum and product of a <B><I><A HREF="../stdlibref/vector.html">vector</A></I></B> of <SAMP>int</SAMP> values. In the first case the identity is zero, and the default <SAMP>operator+()</SAMP> is used. In the second invocation, the identity is <SAMP>1</SAMP>, and the multiplication operator named <I>times</I> is explicitly passed as the fourth argument:</P>

<A NAME="idx327"><!></A>
<UL><PRE>
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&lt;int&gt;());

  std::cout &lt;&lt; "The sum of the first five integers is "
            &lt;&lt; sum &lt;&lt; std::endl;
  std::cout &lt;&lt; "The product is " &lt;&lt; product &lt;&lt; std::endl;

  // second example, with different types for initial value
  std::list&lt;int&gt; nums;
  nums = std::accumulate(numbers, numbers+5, nums, intReplicate);
}

std::list&lt;int&gt;&amp; intReplicate(std::list&lt;int&gt;&amp; nums, int n)
// add sequence n to 1 to end of list
{
  while (n) nums.push_back(n--);
  return nums;
}
</PRE></UL>
<P>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 <SAMP>std::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 <B><I><A HREF="../stdlibref/list.html">list</A></I></B> and an <SAMP>int</SAMP> value, and repeatedly inserts values into the <B><I>list</I></B>. The values inserted represent a decreasing sequence from the argument down to <SAMP>1</SAMP>. For the example input, the same <B><I><A HREF="../stdlibref/vector.html">vector</A></I></B> as in the first example, the resulting <B><I>list</I></B> contains the <SAMP>15</SAMP> values <SAMP>1 2 1 3 2 1 4 3 2 1 5 4 3 2 1</SAMP>.</P>
<A NAME="1363"><H3>13.6.3 Generalized Inner Product</H3></A>
<A NAME="idx328"><!></A>
<P>Assume we have two sequences of <SAMP>n</SAMP> elements each: <SAMP>a1, a2, ... an</SAMP> and <SAMP>b1, b2, ... bn</SAMP><I>.</I> The <I>inner product</I> of the sequences is the sum of the parallel products, that is, the value <SAMP>a1 * b1 + a2 * b2 + ... + an * bn</SAMP>. 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:</P>

<UL><PRE>
namespace std {
  ContainerType inner_product 
     (InputIterator first1, InputIterator last1,
      InputIterator first2, ContainerType initialValue
      [ , BinaryFunction add, BinaryFunction times ]);
}
</PRE></UL>
<A NAME="idx329"><!></A>
<P>The first three arguments to the <SAMP>std::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 <I>identity</I>, used for the summation operator. This is similar to the identity used in the <SAMP>std::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 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>

<A NAME="idx330"><!></A>
<UL><PRE>
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 &lt;&lt; "Inner product is " &lt;&lt; in1 &lt;&lt; std::endl;

  // example 2, user defined operations
  bool anyequal = std::inner_product(a, a+3, b, true,
                  std::logical_or&lt;bool&gt;(), std::equal_to&lt;int&gt;());
   std::cout &lt;&lt; "any equal? " &lt;&lt; anyequal &lt;&lt; std::endl;
}
</PRE></UL>
<A NAME="1364"><H3>13.6.4 Test Two Sequences for Pairwise Equality</H3></A>
<A NAME="idx331"><!></A>
<P>The<SAMP> std::equal()</SAMP> 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 <SAMP>std::mismatch()</SAMP> algorithm gives the location of elements that fail that test (<A HREF="13-3.html#1337">Section&nbsp;13.3.7</A>).</P>
<P>The arguments of the <SAMP>std::equal()</SAMP> algorithm are simple input <B><I><A HREF="../stdlibref/iterator.html">iterator</A></I></B>s:</P>

<UL><PRE>
namespace std {
  bool equal(InputIterator first, InputIterator last, 
             InputIterator first2 [, BinaryPredicate]);
}
</PRE></UL>
<P>The <SAMP>std::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>std::greater_equal()</SAMP> function; in this fashion, <SAMP>true</SAMP> is returned only if all values in the first sequence are greater than or equal to their corresponding value in the second sequence.</P>

<A NAME="idx332"><!></A>
<UL><PRE>
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 &lt;&lt; "a = b is: " &lt;&lt; std::equal(a, a+3, b) &lt;&lt; std::endl;
  std::cout &lt;&lt; "a = c is: " &lt;&lt; std::equal(a, a+3, c) &lt;&lt; std::endl;
  std::cout &lt;&lt; "a pair-wise greater-equal b is: " 
            &lt;&lt; std::equal(a, a+3, b, std::greater_equal&lt;int&gt;())
            &lt;&lt; std::endl;
}
</PRE></UL>
<A NAME="1365"><H3>13.6.5 Lexical Comparison</H3></A>
<A NAME="idx333"><!></A>
<P>A <I>lexical comparison</I> is commonly used to determine the dictionary order of words. In this procedure, the elements or <I>characters</I> 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, <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. Should one or the other sequence terminate before the other, the terminated sequence is considered the smaller. 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 pair-wise characters match in all cases, the two words are considered equal.</P>
<A NAME="idx334"><!></A>
<P>The <SAMP>std::lexicographical_compare()</SAMP> algorithm implements the concept of lexical comparison, returning <SAMP>true</SAMP> if the first sequence is smaller than the second, and <SAMP>false</SAMP> otherwise. The algorithm is generalized to any sequence. Thus, the <SAMP>std::lexicographical_compare()</SAMP> algorithm can be used with arrays, <B><I><A HREF="../stdlibref/basic-string.html">string</A></I></B>s, <B><I><A HREF="../stdlibref/vector.html">vector</A></I></B>s, <B><I><A HREF="../stdlibref/list.html">list</A></I></B>s, or any other data structures of the C++ Standard Library.</P>

<UL><PRE>
namespace std {
  bool lexicographical_compare 
     (InputIterator first1, InputIterator last1,
      InputIterator first2, InputIterator last2 
      [, BinaryFunction ] );
}
</PRE></UL>
<P>Unlike most other algorithms that take two sequences as argument, the <SAMP>std::lexicographical_compare()</SAMP> algorithm uses a first and a past-end <B><I><A HREF="../stdlibref/iterator.html">iterator</A></I></B> for <I>both</I> 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.</P>
<P>The example program illustrates the <SAMP>std::lexicographical_compare()</SAMP> algorithm in use with character sequences, and arrays of integer values.</P>

<A NAME="idx335"><!></A>
<UL><PRE>
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 &lt;&lt; "compare everybody to everything "
            &lt;&lt; std::lexicographical_compare(wordTwo,
                                wordTwo + std::strlen(wordTwo),
                                wordOne,
                                wordOne + std::strlen(wordOne))
            &lt;&lt; std::endl;

  int a[] = {3, 4, 5, 2};
  int b[] = {3, 4, 5};
  int c[] = {3, 5};

  std::cout &lt;&lt; "compare a to b:"
            &lt;&lt; std::lexicographical_compare(a, a+4, b, b+3)
            &lt;&lt; std::endl;

  std::cout &lt;&lt; "compare a to c:"
            &lt;&lt; std::lexicographical_compare(a, a+4, c, c+2)
            &lt;&lt; std::endl;
}
</PRE></UL>

<BR>
<HR>
<A HREF="13-5.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="13-7.html"><IMG SRC="images/bnext.gif" WIDTH=20 HEIGHT=21 ALT="Next file" BORDER=O></A>

<!-- Google Analytics tracking code -->
<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
    _uacct = "UA-1775151-1";
    urchinTracker();
</script>
<!-- end of Google Analytics tracking code -->

</BODY>
</HTML>