chap03.htm.kbk
来自「c++设计思想」· KBK 代码 · 共 616 行 · 第 1/3 页
KBK
616 行
argument; the latter initializes each element using the default
copy-constructor.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">However, in the more general case you
won’t know how many objects you’ll need. If <B>vector</B>
reallocations are slowing things down, you can change sequence containers. You
could use a <B>list</B>, but<B> </B>as you’ll see, the <B>deque</B> allows
speedy insertions at either end of the sequence, and never needs to copy or
destroy objects as it expands its storage. The <B>deque</B> also allows random
access with <B>operator[ ]</B>, but it’s not quite as fast as
<B>vector</B>’s <B>operator[</B> <B>]</B>. So in the case where
you’re creating all your objects in one part of the program and randomly
accessing them in another, you may find yourself filling a <B>deque</B>, then
creating a <B>vector</B> from the <B>deque</B> and using the <B>vector</B> for
rapid indexing. Of course, you don’t want to program this way habitually,
just be aware of these issues (avoid premature optimization).</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">There is a darker side to
<B>vector</B>’s reallocation of memory, however. Because <B>vector</B>
keeps its objects in a nice, neat array (allowing, for one thing, maximally-fast
random access), the iterators used by <B>vector</B> are generally just pointers.
This is a good thing – of all the sequence containers, these pointers
allow the fastest selection and manipulation. However, consider what happens
when you’re holding onto an iterator (i.e. a pointer) and then you add the
one additional object that causes the <B>vector</B> to reallocate storage and
move it elsewhere. Your pointer is now pointing off into
nowhere:</FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:VectorCoreDump.cpp</font>
<font color=#009900>// How to break a program using a vector</font>
<font color=#009900>//{-msc}</font>
<font color=#009900>//{-bor}</font>
<font color=#009900>//{-g++3}</font>
#include <vector>
#include <iostream>
<font color=#0000ff>using</font> <font color=#0000ff>namespace</font> std;
<font color=#0000ff>int</font> main() {
vector<<font color=#0000ff>int</font>> vi(10, 0);
ostream_iterator<<font color=#0000ff>int</font>> out(cout, <font color=#004488>" "</font>);
copy(vi.begin(), vi.end(), out);
vector<<font color=#0000ff>int</font>>::iterator i = vi.begin();
cout << <font color=#004488>"\n i: "</font> << <font color=#0000ff>long</font>(i) << endl;
*i = 47;
copy(vi.begin(), vi.end(), out);
<font color=#009900>// Force it to move memory (could also just add</font>
<font color=#009900>// enough objects):</font>
vi.resize(vi.capacity() + 1);
<font color=#009900>// Now i points to wrong memory:</font>
cout << <font color=#004488>"\n i: "</font> << <font color=#0000ff>long</font>(i) << endl;
cout << <font color=#004488>"vi.begin(): "</font> << <font color=#0000ff>long</font>(vi.begin());
*i = 48; <font color=#009900>// Access violation</font>
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">If your program is breaking mysteriously,
look for places where you hold onto an iterator while adding more objects to a
<B>vector</B>. You’ll need to get a new iterator after adding elements, or
use <B>operator[ ] </B>instead for element selections. If you combine the above
observation with the awareness of the potential expense of adding new objects to
a <B>vector</B>, you may conclude that the safest way to use one is to fill it
up all at once (ideally, knowing first how many objects you’ll need) and
then just use it (without adding more objects) elsewhere in the program. This is
the way <B>vector</B> has been used in the book up to this
point.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">You may observe that using <B>vector
</B>as the “basic” container in the earlier chapters of this book
may not be the best choice in all cases. This is a fundamental issue in
containers, and in data structures in general: the “best” choice
varies according to the way the container is used. The reason <B>vector</B> has
been the “best” choice up until now is that it looks a lot like an
array, and was thus familiar and easy for you to adopt. But from now on
it’s also worth thinking about other issues when choosing
containers.</FONT><A NAME="_Toc519042024"></A><BR></P></DIV>
<A NAME="Heading211"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H3 ALIGN="LEFT">
Inserting and erasing elements</H3></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The <B>vector</B> is most efficient
if:</FONT><BR></P></DIV>
<OL>
<LI><FONT FACE="Verdana"> </FONT><FONT FACE="Georgia">You <B>reserve( )</B>
the correct amount of storage at the beginning so the <B>vector</B> never has to
reallocate.</FONT><LI><FONT FACE="Verdana"> </FONT><FONT FACE="Georgia">You only
add and remove elements from the back
end.</FONT></OL><DIV ALIGN="LEFT"><P><FONT FACE="Georgia">It is possible to insert
and erase elements from the middle of a <B>vector</B> using an iterator, but the
following program demonstrates what a bad idea it is:</FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:VectorInsertAndErase.cpp</font>
<font color=#009900>// Erasing an element from a vector</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
#include <font color=#004488>"Noisy.h"</font>
#include <iostream>
#include <vector>
#include <algorithm>
<font color=#0000ff>using</font> <font color=#0000ff>namespace</font> std;
<font color=#0000ff>int</font> main() {
vector<Noisy> v;
v.reserve(11);
cout << <font color=#004488>"11 spaces have been reserved"</font> << endl;
generate_n(back_inserter(v), 10, NoisyGen());
ostream_iterator<Noisy> out(cout, <font color=#004488>" "</font>);
cout << endl;
copy(v.begin(), v.end(), out);
cout << <font color=#004488>"Inserting an element:"</font> << endl;
vector<Noisy>::iterator it =
v.begin() + v.size() / 2; <font color=#009900>// Middle</font>
v.insert(it, Noisy());
cout << endl;
copy(v.begin(), v.end(), out);
cout << <font color=#004488>"\nErasing an element:"</font> << endl;
<font color=#009900>// Cannot use the previous value of it:</font>
it = v.begin() + v.size() / 2;
v.erase(it);
cout << endl;
copy(v.begin(), v.end(), out);
cout << endl;
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">When you run the program you’ll see
that the call to <B>reserve( )</B> really does only allocate storage
– no constructors are called. The <B>generate_n( )</B> call is pretty
busy: each call to <B>NoisyGen::operator( )</B> results in a construction,
a copy-construction (into the <B>vector</B>) and a destruction of the temporary.
But when an object is inserted into the <B>vector</B> in the middle, it must
shove everything down to maintain the linear array and – since there is
enough space – it does this with the assignment operator (if the argument
of <B>reserve( )</B> is 10 instead of eleven then it would have to
reallocate storage). When an object is erased from the <B>vector</B>, the
assignment operator is once again used to move everything up to cover the place
that is being erased (notice that this requires that the assignment operator
properly cleans up the lvalue). Lastly, the object on the end of the array is
deleted.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">You can imagine how enormous the overhead
can become if objects are inserted and removed from the middle of a
<B>vector</B> if the number of elements is large and the objects are
complicated. It’s obviously a practice to
avoid.</FONT><A NAME="_Toc519042025"></A><BR></P></DIV>
<A NAME="Heading212"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H2 ALIGN="LEFT">
deque</H2></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The <B>deque</B> (double-ended-queue,
pronounced “deck”) is the basic sequence container optimized for
adding and removing elements from either end. It also allows for reasonably fast
random access – it has an <B>operator[ ]</B> like <B>vector</B>. However,
it does not have <B>vector</B>’s constraint of keeping everything in a
single sequential block of memory. Instead, <B>deque</B> uses multiple blocks of
sequential storage (keeping track of all the blocks and their order in a mapping
structure). For this reason the overhead for a <B>deque</B> to add or remove
elements at either end is very low. In addition, it never needs to copy and
destroy contained objects during a new storage allocation (like <B>vector</B>
does) so it is far more efficient than <B>vector</B> if you are adding an
unknown quantity of objects. This means that <B>vector</B> is the best choice
only if you have a pretty good idea of how many objects you need. In addition,
many of the programs shown earlier in this book that use <B>vector</B> and
<B>push_back( )</B> might be more efficient with a <B>deque</B>. The
interface to <B>deque</B> is only slightly different from a <B>vector</B> (deque
has a <B>push_front( )</B> and <B>pop_front( )</B> while <B>vector</B>
does not, for example) so converting code from using <B>vector</B> to using
<B>deque</B> is almost trivial. Consider <B>StringVector.cpp</B>, which can be
changed to use <B>deque</B> by replacing the word “vector” with
“deque” everywhere. The following program adds parallel <B>deque</B>
operations to the <B>vector</B> operations in <B>StringVector.cpp</B>, and
performs timing comparisons:</FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:StringDeque.cpp</font>
<font color=#009900>// Converted from StringVector.cpp</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
#include <font color=#004488>"..</font><font color=#004488>/require.h"</font>
#include <string>
#include <deque>
#include <vector>
#include <fstream>
#include <iostream>
#include <iterator>
#include <sstream>
#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>char</font>* fname = <font color=#004488>"StringDeque.cpp"</font>;
<font color=#0000ff>if</font>(argc > 1) fname = argv[1];
ifstream in(fname);
assure(in, fname);
vector<string> vstrings;
deque<string> dstrings;
string line;
<font color=#009900>// Time reading into vector:</font>
clock_t ticks = clock();
<font color=#0000ff>while</font>(getline(in, line))
vstrings.push_back(line);
ticks = clock() - ticks;
cout << <font color=#004488>"Read into vector: "</font> << ticks << endl;
<font color=#009900>// Repeat for deque:</font>
ifstream in2(fname);
assure(in2, fname);
ticks = clock();
<font color=#0000ff>while</font>(getline(in2, line))
dstrings.push_back(line);
ticks = clock() - ticks;
cout << <font color=#004488>"Read into deque: "</font> << ticks << endl;
<font color=#009900>// Now compare indexing:</font>
ticks = clock();
<font color=#0000ff>for</font>(<font color=#0000ff>int</font> i = 0; i < vstrings.size(); i++) {
ostringstream ss;
ss << i;
vstrings[i] = ss.str() + <font color=#004488>": "</font> + vstrings[i];
}
ticks = clock() - ticks;
cout << <fo⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?