part2.htm.kbk
来自「c++设计思想」· KBK 代码 · 共 439 行 · 第 1/2 页
KBK
439 行
efficiency of a <B>deque</B> when adding
objects to the container but the efficiency of a <B>vector</B> when indexing
them. Each of the basic sequence containers (<B>vector</B>, <B>deque</B> and
<B>list</B>) has a two-iterator constructor (indicating the beginning and ending
of the sequence to read from when creating a new object) and an
<B>assign( )</B> member function to read into an existing container, so you
can easily move objects from one sequence container to another.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The following example reads objects into
a <B>deque</B> and then converts to a <B>vector</B>:</FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:DequeConversion.cpp</font>
<font color=#009900>// Reading into a Deque, converting to a vector</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
<font color=#009900>//{-msc}</font>
#include <font color=#004488>"Noisy.h"</font>
#include <deque>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstdlib>
<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>int</font> size = 25;
<font color=#0000ff>if</font>(argc >= 2) size = atoi(argv[1]);
deque<Noisy> d;
generate_n(back_inserter(d), size, NoisyGen());
cout << <font color=#004488>"\n Converting to a vector(1)"</font> << endl;
vector<Noisy> v1(d.begin(), d.end());
cout << <font color=#004488>"\n Converting to a vector(2)"</font> << endl;
vector<Noisy> v2;
v2.reserve(d.size());
v2.assign(d.begin(), d.end());
cout << <font color=#004488>"\n Cleanup"</font> << endl;
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">You can try various sizes, but you should
see that it makes no difference – the objects are simply copy-constructed
into the new <B>vector</B>s. What’s interesting is that <B>v1</B> does not
cause multiple allocations while building the <B>vector</B>, no matter how many
elements you use. You might initially think that you must follow the process
used for <B>v2</B> and preallocate the storage to prevent messy reallocations,
but the constructor used for <B>v1</B> determines the memory need ahead of time
so this is unnecessary.</FONT><A NAME="_Toc519042027"></A><BR></P></DIV>
<A NAME="Heading214"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H3 ALIGN="LEFT">
Cost of overflowing allocated storage</H3></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">It’s illuminating to see what
happens with a <B>deque</B> when it overflows a block of storage, in contrast
with <B>VectorOverflow.cpp</B>:</FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:DequeOverflow.cpp</font>
<font color=#009900>// A deque is much more efficient than a vector</font>
<font color=#009900>// when pushing back a lot of elements, since it</font>
<font color=#009900>// doesn't require copying and destroying.</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
#include <font color=#004488>"Noisy.h"</font>
#include <deque>
#include <cstdlib>
<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>int</font> size = 1000;
<font color=#0000ff>if</font>(argc >= 2) size = atoi(argv[1]);
deque<Noisy> dn;
Noisy n;
<font color=#0000ff>for</font>(<font color=#0000ff>int</font> i = 0; i < size; i++)
dn.push_back(n);
cout << <font color=#004488>"\n cleaning up \n"</font>;
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Here you will never see any destructors
before the words “cleaning up” appear. Since the <B>deque</B>
allocates all its storage in blocks instead of a contiguous array like
<B>vector</B>, it never needs to move existing storage (thus no additional
copy-constructions and destructions occur). It simply allocates a new block. For
the same reason, the <B>deque</B> can just as efficiently add elements to the
<I>beginning</I> of the sequence, since if it runs out of storage it (again)
just allocates a new block for the beginning. Insertions in the middle of a
<B>deque</B>, however, could be even messier than for <B>vector</B> (but not as
costly).</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Because a <B>deque </B>never moves its
storage, a held iterator never becomes invalid when you add new things to either
end of a deque, as it was demonstrated to do with <B>vector</B> (in
<B>VectorCoreDump.cpp</B>). However, it’s still possible (albeit harder)
to do bad things:</FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:DequeCoreDump.cpp</font>
<font color=#009900>// How to break a program using a deque</font>
#include <queue>
#include <iostream>
<font color=#0000ff>using</font> <font color=#0000ff>namespace</font> std;
<font color=#0000ff>int</font> main() {
deque<<font color=#0000ff>int</font>> di(100, 0);
<font color=#009900>// No problem iterating from beginning to end,</font>
<font color=#009900>// even though it spans multiple blocks:</font>
copy(di.begin(), di.end(),
ostream_iterator<<font color=#0000ff>int</font>>(cout, <font color=#004488>" "</font>));
deque<<font color=#0000ff>int</font>>::iterator i = <font color=#009900>// In the middle:</font>
di.begin() + di.size() / 2;;
<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> j = 0; j < 1000; j++) {
cout << j << endl;
di.insert(i++, 1); <font color=#009900>// Eventually breaks</font>
}
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Of course, there are two things here that
you wouldn’t normally do with a <B>deque</B>: first, elements are inserted
in the middle, which <B>deque</B> allows but isn’t designed for. Second,
calling <B>insert( )</B> repeatedly with the same iterator would not
ordinarily cause an access violation, but the iterator is walked forward after
each insertion. I’m guessing it eventually walks off the end of a block,
but I’m not sure what actually causes the problem.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">If you stick to what <B>deque</B> is best
at – insertions and removals from either end, reasonably rapid traversals
and fairly fast random-access using <B>operator[ ]</B> – you’ll be
in good shape.</FONT><A NAME="_Toc519042028"></A><BR></P></DIV>
<A NAME="Heading215"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H3 ALIGN="LEFT">
Checked random-access</H3></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Both <B>vector </B>and <B>deque</B>
provide two ways to perform random access of their elements: the <B>operator[
]</B>, which you’ve seen already, and <B>at( )</B>, which checks the
boundaries of the container that’s being indexed and throws an exception
if you go out of bounds. It does cost more to use
<B>at( )</B>:</FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:IndexingVsAt.cpp</font>
<font color=#009900>// Comparing "at()" to operator[]</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 <vector>
#include <deque>
#include <iostream>
#include <ctime>
<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>long</font> count = 1000;
<font color=#0000ff>int</font> sz = 1000;
<font color=#0000ff>if</font>(argc >= 2) count = atoi(argv[1]);
<font color=#0000ff>if</font>(argc >= 3) sz = atoi(argv[2]);
vector<<font color=#0000ff>int</font>> vi(sz);
clock_t ticks = clock();
<font color=#0000ff>for</font>(<font color=#0000ff>int</font> i1 = 0; i1 < count; i1++)
<font color=#0000ff>for</font>(<font color=#0000ff>int</font> j = 0; j < sz; j++)
vi[j];
cout << <font color=#004488>"vector[] "</font> << clock() - ticks << endl;
ticks = clock();
<font color=#0000ff>for</font>(<font color=#0000ff>int</font> i2 = 0; i2 < count; i2++)
<font color=#0000ff>for</font>(<font color=#0000ff>int</font> j = 0; j < sz; j++)
vi.at(j);
cout << <font color=#004488>"vector::at() "</font> << clock()-ticks <<endl;
deque<<font color=#0000ff>int</font>> di(sz);
ticks = clock();
<font color=#0000ff>for</font>(<font color=#0000ff>int</font> i3 = 0; i3 < count; i3++)
<font color=#0000ff>for</font>(<font color=#0000ff>int</font> j = 0; j < sz; j++)
di[j];
cout << <font color=#004488>"deque[] "</font> << clock() - ticks << endl;
ticks = clock();
<font color=#0000ff>for</font>(<font color=#0000ff>int</font> i4 = 0; i4 < count; i4++)
<font color=#0000ff>for</font>(<font color=#0000ff>int</font> j = 0; j < sz; j++)
di.at(j);
cout << <font color=#004488>"deque::at() "</font> << clock()-ticks <<endl;
<font color=#009900>// Demonstrate at() when you go out of bounds:</font>
<font color=#0000ff>try</font> {
di.at(vi.size() + 1);
} <font color=#0000ff>catch</font>(...) {
cerr << <font color=#004488>"Exception thrown"</font> << endl;
}
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">As you’ll learn in the
exception-handling chapter, different systems may handle the uncaught exception
in different ways, but you’ll know one way or another that something went
wrong with the program when using <B>at( )</B>, whereas it’s possible
to go blundering ahead using <B>operator[
]</B>.</FONT><A NAME="_Toc519042029"></A><BR></P></DIV>
<A NAME="Heading216"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H2 ALIGN="LEFT">
list</H2></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">A <B>list</B> is implemented as a
doubly-linked list and is thus designed for rapid insertion and removal of
elements in the middle of the sequence (whereas for <B>vector</B> and <B>deque
</B>this is a much more costly operation). A list is so slow when randomly
accessing elements that it does not have an <B>operator[ ]</B>. It’s best
used when you’re traversing a sequence, in order, from beginning to end
(or end to beginning) rather than choosing elements randomly from the middle.
Even then the traversal is significantly slower than either a <B>vector </B>or a
<B>deque</B>, but if you aren’t doing a lot of traversals that won’t
be your bottleneck.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Another thing to be aware of with a
<B>list</B> is the memory overhead of each link, which requires a forward and
backward pointer on top of the storage for the actual object. Thus a <B>list</B>
is a better choice when you have larger objects that you’ll be inserting
and removing from the middle of the <B>list</B>. It’s better not to use a
<B>list </B>if you think you might be traversing it a lot, looking for objects,
since the amount of time it takes to get from the beginning of the <B>list</B>
– which is the only place you can start unless you’ve already got an
iterator to somewhere you know is closer to your destination – to the
object of interest is proportional to the number of objects between the
beginning and that object.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The objects in a <B>list </B>never move
after they are created; “moving” a list element means changing the
links, but never copying or assigning the actual objects. This means that a held
iterator never moves when you add new things to a list as it was demonstrated to
do in <B>vector</B>. Here’s an example using the <B>Noisy</B>
class:</FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:ListStability.cpp</font>
<font color=#009900>// Things don't move around in lists</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
#include <font color=#004488>"Noisy.h"</font>
#include <list>
#include <iostream>
#include <algorithm>
<font color=#0000ff>using</font> <font color=#0000ff>namespace</font> std;
<font color=#0000ff>int</font> main() {
list<Noisy> l;
ostream_iterator<Noisy> out(cout, <font color=#004488>" "</font>);
generate_n(back_inserter(l), 25, NoisyGen());
cout << <font color=#004488>"\n Printing the list:"</font> << endl;
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?