chap04.htm.kbk
来自「c++设计思想」· KBK 代码 · 共 1,135 行 · 第 1/5 页
KBK
1,135 行
color=#004488>"vector"</font>);
testSwap<deque<Noisy> >(<font color=#004488>"deque"</font>);
testSwap<list<Noisy> >(<font color=#004488>"list"</font>);
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">When you run this, you’ll discover
that each type of sequence container is able to swap one sequence for another
without any copying or assignments, even if the sequences are of different
sizes. In effect, you’re completely swapping the memory of one object for
another.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The STL algorithms also contain a
<B>swap( )</B>, and when this function is applied to two containers of the
same type, it will use the member <B>swap( )</B> to achieve fast
performance. Consequently, if you apply the <B>sort( )</B> algorithm to a
container of containers, you will find that the performance is very fast –
it turns out that fast sorting of a container of containers was a design goal of
the STL.</FONT><A NAME="_Toc519042032"></A><BR></P></DIV>
<A NAME="Heading220"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H3 ALIGN="LEFT">
Robustness of lists</H3></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">To break a <B>list</B>, you have to work
pretty hard:</FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:ListRobustness.cpp</font>
<font color=#009900>// lists are harder to break</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
#include <list>
#include <iostream>
<font color=#0000ff>using</font> <font color=#0000ff>namespace</font> std;
<font color=#0000ff>int</font> main() {
list<<font color=#0000ff>int</font>> li(100, 0);
list<<font color=#0000ff>int</font>>::iterator i = li.begin();
<font color=#0000ff>for</font>(<font color=#0000ff>int</font> j = 0; j < li.size() / 2; j++)
i++;
<font color=#009900>// Walk the iterator forward as you perform </font>
<font color=#009900>// a lot of insertions in the middle:</font>
<font color=#0000ff>for</font>(<font color=#0000ff>int</font> k = 0; k < 1000; k++)
li.insert(i++, 1); <font color=#009900>// No problem</font>
li.erase(i);
i++;
<font color=#009900>//! *i = 2; // Oops! It's invalid</font>
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">When the link that the iterator <B>i</B>
was pointing to was erased, it was unlinked from the list and thus became
invalid. Trying to move forward to the “next link” from an invalid
link is poorly-formed code. Notice that the operation that broke <B>deque</B> in
<B>DequeCoreDump.cpp</B> is perfectly fine with a
<B>list</B>.</FONT><A NAME="_Toc519042033"></A><BR></P></DIV>
<A NAME="Heading221"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H2 ALIGN="LEFT">
Performance comparison</H2></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">To get a better feel for the differences
between the sequence containers, it’s illuminating to race them against
each other while performing various operations. </FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:SequencePerformance.cpp</font>
<font color=#009900>// Comparing the performance of the basic</font>
<font color=#009900>// sequence containers for various operations</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
#include <vector>
#include <queue>
#include <list>
#include <iostream>
#include <string>
#include <typeinfo>
#include <ctime>
#include <cstdlib>
<font color=#0000ff>using</font> <font color=#0000ff>namespace</font> std;
<font color=#0000ff>class</font> FixedSize {
<font color=#0000ff>int</font> x[20];
<font color=#009900>// Automatic generation of default constructor,</font>
<font color=#009900>// copy-constructor and operator=</font>
} fs;
<font color=#0000ff>template</font><<font color=#0000ff>class</font> Cont>
<font color=#0000ff>struct</font> InsertBack {
<font color=#0000ff>void</font> <font color=#0000ff>operator</font>()(Cont& c, <font color=#0000ff>long</font> count) {
<font color=#0000ff>for</font>(<font color=#0000ff>long</font> i = 0; i < count; i++)
c.push_back(fs);
}
<font color=#0000ff>char</font>* testName() { <font color=#0000ff>return</font> <font color=#004488>"InsertBack"</font>; }
};
<font color=#0000ff>template</font><<font color=#0000ff>class</font> Cont>
<font color=#0000ff>struct</font> InsertFront {
<font color=#0000ff>void</font> <font color=#0000ff>operator</font>()(Cont& c, <font color=#0000ff>long</font> count) {
<font color=#0000ff>long</font> cnt = count * 10;
<font color=#0000ff>for</font>(<font color=#0000ff>long</font> i = 0; i < cnt; i++)
c.push_front(fs);
}
<font color=#0000ff>char</font>* testName() { <font color=#0000ff>return</font> <font color=#004488>"InsertFront"</font>; }
};
<font color=#0000ff>template</font><<font color=#0000ff>class</font> Cont>
<font color=#0000ff>struct</font> InsertMiddle {
<font color=#0000ff>void</font> <font color=#0000ff>operator</font>()(Cont& c, <font color=#0000ff>long</font> count) {
<font color=#0000ff>typename</font> Cont::iterator it;
<font color=#0000ff>long</font> cnt = count / 10;
<font color=#0000ff>for</font>(<font color=#0000ff>long</font> i = 0; i < cnt; i++) {
<font color=#009900>// Must get the iterator every time to keep</font>
<font color=#009900>// from causing an access violation with</font>
<font color=#009900>// vector. Increment it to put it in the</font>
<font color=#009900>// middle of the container:</font>
it = c.begin();
it++;
c.insert(it, fs);
}
}
<font color=#0000ff>char</font>* testName() { <font color=#0000ff>return</font> <font color=#004488>"InsertMiddle"</font>; }
};
<font color=#0000ff>template</font><<font color=#0000ff>class</font> Cont>
<font color=#0000ff>struct</font> RandomAccess { <font color=#009900>// Not for list</font>
<font color=#0000ff>void</font> <font color=#0000ff>operator</font>()(Cont& c, <font color=#0000ff>long</font> count) {
<font color=#0000ff>int</font> sz = c.size();
<font color=#0000ff>long</font> cnt = count * 100;
<font color=#0000ff>for</font>(<font color=#0000ff>long</font> i = 0; i < cnt; i++)
c[rand() % sz];
}
<font color=#0000ff>char</font>* testName() { <font color=#0000ff>return</font> <font color=#004488>"RandomAccess"</font>; }
};
<font color=#0000ff>template</font><<font color=#0000ff>class</font> Cont>
<font color=#0000ff>struct</font> Traversal {
<font color=#0000ff>void</font> <font color=#0000ff>operator</font>()(Cont& c, <font color=#0000ff>long</font> count) {
<font color=#0000ff>long</font> cnt = count / 100;
<font color=#0000ff>for</font>(<font color=#0000ff>long</font> i = 0; i < cnt; i++) {
<font color=#0000ff>typename</font> Cont::iterator it = c.begin(),
end = c.end();
<font color=#0000ff>while</font>(it != end) it++;
}
}
<font color=#0000ff>char</font>* testName() { <font color=#0000ff>return</font> <font color=#004488>"Traversal"</font>; }
};
<font color=#0000ff>template</font><<font color=#0000ff>class</font> Cont>
<font color=#0000ff>struct</font> Swap {
<font color=#0000ff>void</font> <font color=#0000ff>operator</font>()(Cont& c, <font color=#0000ff>long</font> count) {
<font color=#0000ff>int</font> middle = c.size() / 2;
<font color=#0000ff>typename</font> Cont::iterator it = c.begin(),
mid = c.begin();
it++; <font color=#009900>// Put it in the middle</font>
<font color=#0000ff>for</font>(<font color=#0000ff>int</font> x = 0; x < middle + 1; x++)
mid++;
<font color=#0000ff>long</font> cnt = count * 10;
<font color=#0000ff>for</font>(<font color=#0000ff>long</font> i = 0; i < cnt; i++)
swap(*it, *mid);
}
<font color=#0000ff>char</font>* testName() { <font color=#0000ff>return</font> <font color=#004488>"Swap"</font>; }
};
<font color=#0000ff>template</font><<font color=#0000ff>class</font> Cont>
<font color=#0000ff>struct</font> RemoveMiddle {
<font color=#0000ff>void</font> <font color=#0000ff>operator</font>()(Cont& c, <font color=#0000ff>long</font> count) {
<font color=#0000ff>long</font> cnt = count / 10;
<font color=#0000ff>if</font>(cnt > c.size()) {
cout << <font color=#004488>"RemoveMiddle: not enough elements"</font>
<< endl;
<font color=#0000ff>return</font>;
}
<font color=#0000ff>for</font>(<font color=#0000ff>long</font> i = 0; i < cnt; i++) {
<font color=#0000ff>typename</font> Cont::iterator it = c.begin();
it++;
c.erase(it);
}
}
<font color=#0000ff>char</font>* testName() { <font color=#0000ff>return</font> <font color=#004488>"RemoveMiddle"</font>; }
};
<font color=#0000ff>template</font><<font color=#0000ff>class</font> Cont>
<font color=#0000ff>struct</font> RemoveBack {
<font color=#0000ff>void</font> <font color=#0000ff>operator</font>()(Cont& c, <font color=#0000ff>long</font> count) {
<font color=#0000ff>long</font> cnt = count * 10;
<font color=#0000ff>if</font>(cnt > c.size()) {
cout << <font color=#004488>"RemoveBack: not enough elements"</font>
<< endl;
<font color=#0000ff>return</font>;
}
<font color=#0000ff>for</font>(<font color=#0000ff>long</font> i = 0; i < cnt; i++)
c.pop_back();
}
<font color=#0000ff>char</font>* testName() { <font color=#0000ff>return</font> <font color=#004488>"RemoveBack"</font>; }
};
<font color=#0000ff>template</font><<font color=#0000ff>class</font> Op, <font color=#0000ff>class</font> Container>
<font color=#0000ff>void</font> measureTime(Op f, Container& c, <font color=#0000ff>long</font> count){
string id(<font color=#0000ff>typeid</font>(f).name());
<font color=#0000ff>bool</font> Deque = id.find(<font color=#004488>"deque"</font>) != string::npos;
<font color=#0000ff>bool</font> List = id.find(<font color=#004488>"list"</font>) != string::npos;
<font color=#0000ff>bool</font> Vector = id.find(<font color=#004488>"vector"</font>) !=string::npos;
string cont = Deque ? <font color=#004488>"deque"</font> : List ? <font color=#004488>"list"</font>
: Vector? <font color=#004488>"vector"</font> : <font color=#004488>"unknown"</font>;
cout << f.testName() << <font color=#004488>" for "</font> << cont << <font color=#004488>": "</font>;
<font color=#009900>// Standard C library CPU ticks:</font>
clock_t ticks = clock();
f(c, count); <font color=#009900>// Run the test</font>
ticks = clock() - ticks;
cout << ticks << endl;
}
<font color=#0000ff>typedef</font> deque<FixedSize> DF;
<font color=#0000ff>typedef</font> list<FixedSize> LF;
<font color=#0000ff>typedef</font> vector<FixedSize> VF;
<font color=#0000ff>int</font> main(<font color=#0000ff>int</font> argc, <font color=#0000ff>char</font>* argv[]) {
srand(time(0));
<font color=#0000ff>long</font> count = 1000;
<font color=#0000ff>if</font>(argc >= 2) count = atoi(argv[1]);
DF deq;
LF lst;
VF vec, vecres;
vecres.reserve(count); <font color=#009900>// Preallocate storage</font>
measureTime(InsertBack<VF>(), vec, count);
measureTime(InsertBack<VF>(), vecres, count);
measureTime(InsertBack<DF>(), deq, count);
measureTime(InsertBack<LF>(), lst, count);
<font color=#009900>// Can't push_front() with a vector:</font>
<font color=#009900>//! measureTime(InsertFront<VF>(), vec, count);</font>
measureTime(InsertFront<DF>(), deq, count);
measureTime(InsertFront<LF>(), lst, count);
measureTime(InsertMiddle<VF>(), vec, count);
measureTime(InsertMiddle<DF>(), deq, count);
measureTime(InsertMiddle<LF>(), lst, count);
measureTime(RandomAccess<VF>(), vec, count);
measureTime(RandomAccess<DF>(), deq, count);
<font color=#009900>// Can't operator[] with a list:</font>
<font color=#009900>//! measureTime(RandomAccess<LF>(), lst, count);</font>
measureTime(Traversal<VF>(), vec, count);
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?