📄 chap08.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<!--
This document was converted from RTF source:
By rtftohtml 4.19
See http://www.sunpack.com/RTF
Filename:C:\TEMP\TicV2\html\TicV2.rtf
Application Directory:C:\TOOLS\RTF2HTML\
Subject:
Author:Bruce Eckel
Operator:Bruce Eckel
Document Comments:
Version Comments:
Comments:
Keywords:
Translation Date:09/26/2001
Translation Time:08:32:30
Translation Platform:Win32
Number of Output files:19
This File:C:\TEMP\TicV2\html\Chap08.htm
SplitDepth=1
SkipNavPanel=1
SkipLeadingToc=1
SkipTrailingToc=1
GenContents=1
GenFrames=1
GenIndex=1
-->
<HEAD lang="en"><META http-equiv="Content-Type" content="text/html">
<TITLE>8: STL Algorithms</TITLE>
</HEAD>
<BODY BGCOLOR="#FFFFFF"><DIV ALIGN="CENTER">
<a href="http://www.MindView.net">
<img src="mindview.gif" alt="MindView Inc." BORDER = "0"></a>
<CENTER>
<FONT FACE="Verdana, Tahoma, Arial, Helvetica, Sans" size = "-1">
[ <a href="README.txt">Viewing Hints</a> ]
[ <a href="RevisionHistory.htm">Revision History</a> ]
[ <a href="http://www.mindview.net/Books/TICPP/ThinkingInCPP2e.html">Book Home Page</a> ]
[ <a href="http://www.mindview.net/Etc/MailingList.html">Free Newsletter</a> ] <br>
[ <a href="http://www.mindview.net/Seminars">Seminars</a> ]
[ <a href="http://www.mindview.net/CDs">Seminars on CD ROM</a> ]
[ <a href="http://www.mindview.net/Services">Consulting</a> ]
</FONT>
<H2><FONT FACE="Verdana, Tahoma, Arial, Helvetica, Sans">
Thinking in C++, 2nd edition, Volume 2<br>
<small>Revision 4.0</small></FONT></H2>
<H3><FONT FACE="Verdana, Tahoma, Arial, Helvetica, Sans">
by Bruce Eckel & Chuck Allison<br>©2001 MindView, Inc.</FONT></H3>
<FONT FACE="Verdana, Tahoma, Arial, Helvetica, Sans" size = "-1">
[ <a href="Chap07.htm">Previous Chapter</a> ]
[ <a href="SimpCont.htm">Short TOC</a> ]
[ <a href="Contents.htm">Table of Contents</a> ]
[ <a href="DocIdx.htm">Index</a> ]
[ <a href="Part3.htm">Next Chapter</a> ]
</FONT>
</CENTER>
</P></DIV><A NAME="_Toc519042058"></A><A NAME="Heading247"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H1 ALIGN="LEFT">
8: STL Algorithms<A NAME="STLAlgorithmsChapter"></A></H1></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Verdana" SIZE=4>The other half of the STL is the
algorithms, which are templatized functions designed to work with the containers
(or, as you will see, anything that can behave like a container, including
arrays<B> </B>and <B>string</B> objects).</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The STL was originally designed around
the algorithms. The goal was that you use algorithms for almost every piece of
code that you write. In this sense it was a bit of an experiment, and only time
will tell how well it works. The real test will be in how easy or difficult it
is for the average programmer to adapt. At the end of this chapter you’ll
be able to decide for yourself whether you find the algorithms addictive or too
confusing to remember. If you’re like me, you’ll resist them at
first but then tend to use them more and more.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Before you make your judgment, however,
there’s one other thing to consider. The STL algorithms provide a
<I>vocabulary</I> with which to describe solutions. That is, once you become
familiar with the algorithms you’ll have a new set of words with which to
discuss what you’re doing, and these words are at a higher level than what
you’ve had before. You don’t have to say “this loop moves
through and assigns from here to there ... oh, I see, it’s copying!”
Instead, you say <B>copy( )</B>. This is the kind of thing we’ve been
doing in computer programming from the beginning – creating more dense
ways to express <I>what</I> we’re doing and spending less time saying
<I>how</I> we’re doing it. Whether the STL algorithms and <I>generic
programming </I>are a great success in accomplishing this remains to be seen,
but that is certainly the
objective.</FONT><A NAME="_Toc519042059"></A><BR></P></DIV>
<A NAME="Heading248"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H2 ALIGN="LEFT">
Function objects</H2></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">A concept that is used heavily in the STL
algorithms is the <I>function object</I>, which was introduced in the previous
chapter. A function object has an overloaded <B>operator( )</B>, and the
result is that a template function can’t tell whether you’ve handed
it a pointer to a function or an object that has an <B>operator( )</B>; all
the template function knows is that it can attach an argument list to the object
<I>as if</I> it were a pointer to a function:</FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C08:FuncObject.cpp</font>
<font color=#009900>// Simple function objects</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
#include <iostream>
<font color=#0000ff>using</font> <font color=#0000ff>namespace</font> std;
<font color=#0000ff>template</font><<font color=#0000ff>class</font> UnaryFunc, <font color=#0000ff>class</font> T>
<font color=#0000ff>void</font> callFunc(T& x, UnaryFunc f) {
f(x);
}
<font color=#0000ff>void</font> g(<font color=#0000ff>int</font>& x) {
x = 47;
}
<font color=#0000ff>struct</font> UFunc {
<font color=#0000ff>void</font> <font color=#0000ff>operator</font>()(<font color=#0000ff>int</font>& x) {
x = 48;
}
};
<font color=#0000ff>int</font> main() {
<font color=#0000ff>int</font> y = 0;
callFunc(y, g);
cout << y << endl;
y = 0;
callFunc(y, UFunc());
cout << y << endl;
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The template <B>callFunc( )</B> says
“give me an <B>f</B> and an <B>x</B>, and I’ll write the code
<B>f(x)</B>.” In <B>main( )</B>, you can see that it doesn’t
matter if <B>f</B> is a pointer to a function (as in the case of
<B>g( )</B>), or if it’s a function object (which is created as a
temporary object by the expression <B>UFunc( )</B>). Notice you can only
accomplish this genericity with a template function; a non-template function is
too particular about its argument types to allow such a thing. The STL
algorithms use this flexibility to take either a function pointer or a function
object, but you’ll usually find that creating a function object is more
powerful and flexible.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The function object is actually a
variation on the theme of a <I>callback</I>, which is described in the design
patterns chapter. A callback allows you to vary the behavior of a function or
object by passing, as an argument, a way to execute some other piece of code.
Here, we are handing <B>callFunc( )</B> a pointer to a function or a
function object.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The following descriptions of function
objects should not only make that topic clear, but also give you an introduction
to the way the STL algorithms work.</FONT><A NAME="_Toc519042060"></A><BR></P></DIV>
<A NAME="Heading249"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H3 ALIGN="LEFT">
Classification of function objects</H3></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Just as the STL classifies iterators
(based on their capabilities), it also classifies function objects based on the
number of arguments that their <B>operator( )</B> takes and the kind of
value returned by that operator (of course, this is also true for function
pointers when you treat them as function objects). The classification of
function objects in the STL is based on whether the <B>operator( )</B>
takes zero, one or two arguments, and if it returns a <B>bool</B> or
non-<B>bool</B> value.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia"><B>Generator</B>: Takes no arguments, and
returns a value of the desired type. A <B>RandomNumberGenerator</B> is a special
case.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia"><B>UnaryFunction</B>: Takes a single
argument of any type and returns a value which may be of a different
type.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia"><B>BinaryFunction</B>: Takes two
arguments of any two types and returns a value of any type.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">A special case of the unary and binary
functions is the <I>predicate</I>, which simply means a function that returns a
<B>bool</B>. A predicate is a function you use to make a<B>
true</B>/<B>false</B> decision.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia"><B>Predicate</B>: This can also be called
a <B>UnaryPredicate</B>. It takes a single argument of any type and returns a
<B>bool</B>.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia"><B>BinaryPredicate</B>: Takes two
arguments of any two types and returns a <B>bool</B>.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia"><B>StrictWeakOrdering</B>: A binary
predicate that says that if you have two objects and neither one is less than
the other, they can be regarded as equivalent to each other.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">In addition, there are sometimes
qualifications on object types that are passed to an algorithm. These
qualifications are given in the template argument type identifier
name:</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia"><B>LessThanComparable</B>: A class that
has a less-than <B>operator<</B>.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia"><B>Assignable</B>: A class that has an
assignment <B>operator=</B> for its own type.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia"><B>EqualityComparable</B>: A class that
has an equivalence <B>operator==</B> for its own
type.</FONT><A NAME="_Toc519042061"></A><BR></P></DIV>
<A NAME="Heading250"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H3 ALIGN="LEFT">
Automatic creation of function objects</H3></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The STL has, in the header file
<B><functional></B>, a set of templates that will automatically create
function objects for you. These generated function objects are admittedly
simple, but the goal is to provide very basic functionality that will allow you
to compose more complicated function objects, and in many situations this is all
you’ll need. Also, you’ll see that there are some <I>function object
adapters</I> that allow you to take the simple function objects and make them
slightly more complicated.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Here are the templates that generate
function objects, along with the expressions that they effect.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><TABLE BORDER>
<TR VALIGN="TOP">
<TH WIDTH=68 COLSPAN=1 ROWSPAN=1 VALIGN="TOP">
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Name</FONT><BR></P></DIV>
</TH>
<TH WIDTH=76 COLSPAN=1 ROWSPAN=1 VALIGN="TOP">
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Type</FONT><BR></P></DIV>
</TH>
<TH WIDTH=166 COLSPAN=1 ROWSPAN=1 VALIGN="TOP">
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Result produced by generated function
object</FONT><BR></P></DIV>
</TH>
</TR>
<TR VALIGN="TOP">
<TD>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">plus</FONT><BR></P></DIV>
</TD>
<TD>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">BinaryFunction</FONT><BR></P></DIV>
</TD>
<TD>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">arg1 + arg2</FONT><BR></P></DIV>
</TD>
</TR>
<TR VALIGN="TOP">
<TD>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">minus</FONT><BR></P></DIV>
</TD>
<TD>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">BinaryFunction</FONT><BR></P></DIV>
</TD>
<TD>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">arg1 - arg2</FONT><BR></P></DIV>
</TD>
</TR>
<TR VALIGN="TOP">
<TD>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">multiplies</FONT><BR></P></DIV>
</TD>
<TD>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">BinaryFunction</FONT><BR></P></DIV>
</TD>
<TD>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">arg1 * arg2</FONT><BR></P></DIV>
</TD>
</TR>
<TR VALIGN="TOP">
<TD>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">divides</FONT><BR></P></DIV>
</TD>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -