chap04.htm.kbk
来自「c++设计思想」· KBK 代码 · 共 1,135 行 · 第 1/5 页
KBK
1,135 行
measureTime(Traversal<DF>(), deq, count);
measureTime(Traversal<LF>(), lst, count);
measureTime(Swap<VF>(), vec, count);
measureTime(Swap<DF>(), deq, count);
measureTime(Swap<LF>(), lst, count);
measureTime(RemoveMiddle<VF>(), vec, count);
measureTime(RemoveMiddle<DF>(), deq, count);
measureTime(RemoveMiddle<LF>(), lst, count);
vec.resize(vec.size() * 10); <font color=#009900>// Make it bigger</font>
measureTime(RemoveBack<VF>(), vec, count);
measureTime(RemoveBack<DF>(), deq, count);
measureTime(RemoveBack<LF>(), lst, count);
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">This example makes heavy use of templates
to eliminate redundancy, save space, guarantee identical code and improve
clarity. Each test is represented by a class that is templatized on the
container it will operate on. The test itself is inside the
<B>operator( )</B> which, in each case, takes a reference to the container
and a repeat count – this count is not always used exactly as it is, but
sometimes increased or decreased to prevent the test from being too short or too
long. The repeat count is just a factor, and all tests are compared using the
same value.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Each test class also has a member
function that returns its name, so that it can easily be printed. You might
think that this should be accomplished using run-time type identification, but
since the actual name of the class involves a template expansion, this turns out
to be the more direct approach.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The <B>measureTime( )</B> function
template takes as its first template argument the operation that it’s
going to test – which is itself a class template selected from the group
defined previously in the listing. The template argument <B>Op</B> will not only
contain the name of the class, but also (decorated into it) the type of the
container it’s working with. The RTTI <B>typeid( )</B> operation
allows the name of the class to be extracted as a <B>char*</B>, which can then
be used to create a <B>string</B> called <B>id</B>. This <B>string</B> can be
searched using <B>string::find( )</B> to look for <B>deque</B>, <B>list</B>
or <B>vector</B>. The <B>bool</B> variable that corresponds to the matching
<B>string</B> becomes <B>true</B>, and this is used to properly initialize the
<B>string</B> <B>cont</B> so the container name can be accurately printed, along
with the test name.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Once the type of test and the container
being tested has been printed out, the actual test is quite simple. The Standard
C library function <B>clock( )</B> is used to capture the starting and
ending CPU ticks (this is typically more fine-grained than trying to measure
seconds). Since <B>f</B> is an object of type <B>Op</B>, which is a class that
has an <B>operator( )</B>, the line:</FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE>f(c, count);</PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">is actually calling the
<B>operator( )</B> for the object <B>f</B>.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">In <B>main( )</B>, you can see that
each different type of test is run on each type of container, except for the
containers that don’t support the particular operation being tested (these
are commented out).</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">When you run the program, you’ll
get comparative performance numbers for your particular compiler and your
particular operating system and platform. Although this is only intended to give
you a feel for the various performance features relative to the other sequences,
it is not a bad way to get a quick-and-dirty idea of the behavior of your
library, and also to compare one library with
another.</FONT><A NAME="_Toc519042034"></A><BR></P></DIV>
<A NAME="Heading222"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H2 ALIGN="LEFT">
set</H2></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The <B>set</B> produces a container that
will accept only one of each thing you place in it; it also sorts the elements
(sorting isn’t intrinsic to the conceptual definition of a set, but the
STL <B>set</B> stores its elements in a balanced binary tree to provide rapid
lookups, thus producing sorted results when you traverse it). The first two
examples in this chapter used <B>set</B>s.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Consider the problem of creating an index
for a book. You might like to start with all the words in the book, but you only
want one instance of each word and you want them sorted. Of course, a <B>set</B>
is perfect for this, and solves the problem effortlessly. However, there’s
also the problem of punctuation and any other non-alpha characters, which must
be stripped off to generate proper words. One solution to this problem is to use
the Standard C library function <B>strtok( )</B>, which produces tokens (in
our case, words) given a set of delimiters to strip out:</FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:WordList.cpp</font>
<font color=#009900>// Display a list of words used in a document</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
#include <font color=#004488>"..</font><font color=#004488>/require.h"</font>
#include <string>
#include <cstring>
#include <set>
#include <iostream>
#include <fstream>
<font color=#0000ff>using</font> <font color=#0000ff>namespace</font> std;
<font color=#0000ff>const</font> <font color=#0000ff>char</font>* delimiters =
<font color=#004488>" \t;()\"</font><>:{}[]+-=&*#.,/\\~";
<font color=#0000ff>int</font> main(<font color=#0000ff>int</font> argc, <font color=#0000ff>char</font>* argv[]) {
<font color=#0000ff>char</font>* fname = <font color=#004488>"WordList.cpp"</font>;
<font color=#0000ff>if</font>(argc > 1) fname = argv[1];
ifstream in(fname);
assure(in, fname);
set<string> wordlist;
string line;
<font color=#0000ff>while</font>(getline(in, line)) {
<font color=#009900>// Capture individual words:</font>
<font color=#0000ff>char</font>* s = <font color=#009900>// Cast probably won’t crash:</font>
strtok((<font color=#0000ff>char</font>*)line.c_str(), delimiters);
<font color=#0000ff>while</font>(s) {
<font color=#009900>// Automatic type conversion:</font>
wordlist.insert(s);
s = strtok(0, delimiters);
}
}
<font color=#009900>// Output results:</font>
copy(wordlist.begin(), wordlist.end(),
ostream_iterator<string>(cout, <font color=#004488>"\n"</font>));
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia"><B>strtok( )
<A NAME="Index499"></A><A NAME="Index500"></A></B>takes the starting address of
a character buffer (the first argument) and looks for delimiters (the second
argument). It replaces the delimiter with a zero, and returns the address of the
beginning of the token. If you call it subsequent times with a first argument of
zero it will continue extracting tokens from the rest of the string until it
finds the end. In this case, the delimiters are those that delimit the keywords
and identifiers of C++, so it extracts these keywords and identifiers. Each word
is turned into a <B>string</B> and placed into the <B>wordlist</B> vector, which
eventually contains the whole file, broken up into words.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">You don’t have to use a <B>set</B>
just to get a sorted sequence. You can use the <B>sort( )</B> function
(along with a multitude of other functions in the STL) on different STL
containers. However, it’s likely that <B>set</B> will be
faster.</FONT><A NAME="_Toc519042035"></A><BR></P></DIV>
<A NAME="Heading223"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H3 ALIGN="LEFT">
Eliminating strtok( )</H3></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Some programmers consider
<B>strtok( )</B> to be the poorest design in the Standard C library because
it uses a <B>static</B> buffer to hold its data between function calls. This
means:</FONT><BR></P></DIV>
<OL>
<LI><FONT FACE="Verdana"> </FONT><FONT FACE="Georgia">You can’t use
<B>strtok( ) </B>in two places at the same
time.</FONT><LI><FONT FACE="Verdana"> </FONT><FONT FACE="Georgia">You
can’t use <B>strtok( ) </B>in a multithreaded
program.</FONT><LI><FONT FACE="Verdana"> </FONT><FONT FACE="Georgia">You
can’t use <B>strtok( )</B> in a library that might be used in a
multithreaded
program.</FONT><LI><FONT FACE="Verdana"><B> </B></FONT><FONT FACE="Georgia"><B>strtok( )</B>
modifies the input sequence, which can produce unexpected side
effects.</FONT><LI><FONT FACE="Verdana"><B> </B></FONT><FONT FACE="Georgia"><B>strtok( )</B>
depends on reading in “lines”, which means you need a buffer big
enough for the longest line. This produces both wastefully-sized buffers, and
lines longer than the “longest” line. This can also introduce
security holes. (Notice that the buffer size problem was eliminated in
<B>WordList.cpp</B> by using <B>string</B> input, but this required a cast so
that <B>strtok( )</B> could modify the data in the string – a
dangerous approach for general-purpose
programming).</FONT></OL><DIV ALIGN="LEFT"><P><FONT FACE="Georgia">For all these
reasons it seems like a good idea to find an alternative for
<B>strtok( )</B>. The following example will use an
<B>istreambuf_iterator</B> (introduced earlier) to move the characters from one
place (which happens to be an <B>istream</B>) to another (which happens to be a
<B>string</B>), depending on whether the Standard C library function
<B>isalpha( )</B> is true:</FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:WordList2.cpp</font>
<font color=#009900>// Eliminating strtok() from Wordlist.cpp</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
<font color=#009900>//{-g++295} </font>
#include <font color=#004488>"..</font><font color=#004488>/require.h"</font>
#include <string>
#include <cstring>
#include <set>
#include <iostream>
#include <fstream>
#include <iterator>
<font color=#0000ff>using</font> <font color=#0000ff>namespace</font> std;
<font color=#0000ff>int</font> main(<font color=#0000ff>int</font> argc, <font color=#0000ff>char</font>* argv[]) {
<font color=#0000ff>char</font>* fname = <font color=#004488>"WordList2.cpp"</font>;
<font color=#0000ff>if</font>(argc > 1) fname = argv[1];
ifstream in(fname);
assure(in, fname);
istreambuf_iterator<<font color=#0000ff>char</font>> p(in), end;
set<string> wordlist;
<font color=#0000ff>while</font> (p != end) {
string word;
insert_iterator<string>
ii(word, word.begin());
<font color=#009900>// Find the first alpha character:</font>
<font color=#0000ff>while</font>(!isalpha(*p) && p != end)
p++;
<font color=#009900>// Copy until the first non-alpha character:</font>
<font color=#0000ff>while</font> (isalpha(*p) && p != end)
*ii++ = *p++;
<font color=#0000ff>if</font> (word.size() != 0)
wordlist.insert(word);
}
<font color=#009900>// Output results:</font>
copy(wordlist.begin(), wordlist.end(),
ostream_iterator<string>(cout, <font color=#004488>"\n"</font>));
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">This example was suggested by Nathan
Myers, who invented the <B>istreambuf_iterator</B> and its relatives. This
iterator extracts information character-by-character from a stream. Although the
<B>istreambuf_iterator </B>template argument might suggest to you that you could
extract, for example, <B>int</B>s instead of <B>char</B>, that’s not the
case. The argument must be of some character type – a regular <B>char</B>
or a wide character.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">After the file is open, an
<B>istreambuf_iterator</B> called <B>p</B> is attached to the <B>istream</B> so
characters can be extracted from it. The <B>set<string></B> called
<B>wordlist</B> will be used to hold the resulting words.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The <B>while</B> loop reads words until
the end of the input stream is found. This is detected using the default
constructor for <B>istreambuf_iterator</B> which produces the past-the-end
iterator object <B>end</B>. Thus, if you want to test to make sure you’re
not at the end of the stream, you simply say <B>p != end</B>.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The second type of iterator that’s
used here is the <B>insert_iterator</B>, which creates an iterator that knows
how to insert objects into a container. Here, the “container” is the
<B>string</B> called <B>word</B> which, for the purposes of
<B>insert_iterator</B>, behaves like a container. The constructor for
<B>insert_iterator</B> requires the container and an iterator indicating where
it should start inserting the characters. You could also use a
<B>back_insert_iterator</B>, which requires that the container have a
<B>push_back( )</B> (<B>string</B> does).</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">After the <B>while</B> loop sets
everything up, it begins by looking for the first alpha character, incrementing
<B>start</B> until that character is found. Then it copies characters from one
iterator to the other, stopping when a non-alpha character is found. Each
<B>word</B>, assuming it is non-empty, is added to
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?