chap03.htm.kbk
来自「c++设计思想」· KBK 代码 · 共 616 行 · 第 1/3 页
KBK
616 行
<B>deque</B> support <B>push_front( )</B> and <B>pop_front( )</B>,
<B>vector</B> does not, so the only member functions that work with all three
are <B>push_back( )</B> and <B>pop_back( )</B>.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The naming of the member function
<B>swap( )</B> is a little confusing, since there’s also a non-member
<B>swap( )</B> algorithm that switches two elements of a container. The
member <B>swap( )</B>, however, swaps <I>everything</I> in one container
for another (if the containers hold the same type), effectively swapping the
containers themselves. There’s also a non-member version of this
function.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The following sections on the sequence
containers discuss the particulars of each type of
container.</FONT><A NAME="_Toc519042022"></A><BR></P></DIV>
<A NAME="Heading209"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H2 ALIGN="LEFT">
vector</H2></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The <B>vector</B> is intentionally made
to look like a souped-up array, since it has array-style indexing but also can
expand dynamically. <B>vector</B> is so fundamentally useful that it was
introduced in a very primitive way early in this book, and used quite regularly
in previous examples. This section will give a more in-depth look at
<B>vector</B>.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">To achieve maximally-fast indexing and
iteration, the <B>vector</B> maintains its storage as a single contiguous array
of objects. This is a critical point to observe in understanding the behavior of
<B>vector</B>. It means that indexing and iteration are lighting-fast, being
basically the same as indexing and iterating over an array of objects. But it
also means that inserting an object anywhere but at the end (that is, appending)
is not really an acceptable operation for a <B>vector</B>. It also means that
when a <B>vector</B> runs out of pre-allocated storage, in order to maintain its
contiguous array it must allocate a whole new (larger) chunk of storage
elsewhere and copy the objects to the new storage. This has a number of
unpleasant side effects.</FONT><A NAME="_Toc519042023"></A><BR></P></DIV>
<A NAME="Heading210"></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">A <B>vector </B>starts by grabbing a
block of storage, as if it’s taking a guess at how many objects you plan
to put in it. As long as you don’t try to put in more objects than can be
held in the initial block of storage, everything is very rapid and efficient
(note that if you <I>do </I>know how many objects to expect, you can
pre-allocate storage using <B>reserve( )</B>). But eventually you will put
in one too many objects and, unbeknownst to you, the <B>vector </B>responds
by:</FONT><BR></P></DIV>
<OL>
<LI><FONT FACE="Verdana"> </FONT><FONT FACE="Georgia">Allocating a new, bigger
piece of
storage</FONT><LI><FONT FACE="Verdana"> </FONT><FONT FACE="Georgia">Copying all
the objects from the old storage to the new (using the
copy-constructor)</FONT><LI><FONT FACE="Verdana"> </FONT><FONT FACE="Georgia">Destroying
all the old objects (the destructor is called for each
one)</FONT><LI><FONT FACE="Verdana"> </FONT><FONT FACE="Georgia">Releasing the
old memory</FONT></OL><DIV ALIGN="LEFT"><P><FONT FACE="Georgia">For complex
objects, this copy-construction and destruction can end up being very expensive
if you overfill your vector a lot. To see what happens when you’re filling
a <B>vector</B>, here is a class that prints out information about its
creations, destructions, assignments and copy-constructions:</FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:Noisy.h</font>
<font color=#009900>// A class to track various object activities</font>
#ifndef NOISY_H
#define NOISY_H
#include <iostream>
<font color=#0000ff>class</font> Noisy {
<font color=#0000ff>static</font> <font color=#0000ff>long</font> create, assign, copycons, destroy;
<font color=#0000ff>long</font> id;
<font color=#0000ff>public</font>:
Noisy() : id(create++) {
std::cout << <font color=#004488>"d["</font> << id << <font color=#004488>"]"</font>;
}
Noisy(<font color=#0000ff>const</font> Noisy& rv) : id(rv.id) {
std::cout << <font color=#004488>"c["</font> << id << <font color=#004488>"]"</font>;
copycons++;
}
Noisy& <font color=#0000ff>operator</font>=(<font color=#0000ff>const</font> Noisy& rv) {
std::cout << <font color=#004488>"("</font> << id << <font color=#004488>")=["</font> <<
rv.id << <font color=#004488>"]"</font>;
id = rv.id;
assign++;
<font color=#0000ff>return</font> *<font color=#0000ff>this</font>;
}
<font color=#0000ff>friend</font> <font color=#0000ff>bool</font>
<font color=#0000ff>operator</font><(<font color=#0000ff>const</font> Noisy& lv, <font color=#0000ff>const</font> Noisy& rv) {
<font color=#0000ff>return</font> lv.id < rv.id;
}
<font color=#0000ff>friend</font> <font color=#0000ff>bool</font>
<font color=#0000ff>operator</font>==(<font color=#0000ff>const</font> Noisy& lv, <font color=#0000ff>const</font> Noisy& rv) {
<font color=#0000ff>return</font> lv.id == rv.id;
}
~Noisy() {
std::cout << <font color=#004488>"~["</font> << id << <font color=#004488>"]"</font>;
destroy++;
}
<font color=#0000ff>friend</font> std::ostream&
<font color=#0000ff>operator</font><<(std::ostream& os, <font color=#0000ff>const</font> Noisy& n) {
<font color=#0000ff>return</font> os << n.id;
}
<font color=#0000ff>friend</font> <font color=#0000ff>class</font> NoisyReport;
};
<font color=#0000ff>struct</font> NoisyGen {
Noisy <font color=#0000ff>operator</font>()() { <font color=#0000ff>return</font> Noisy(); }
};
<font color=#009900>// A singleton. Will automatically report the</font>
<font color=#009900>// statistics as the program terminates:</font>
<font color=#0000ff>class</font> NoisyReport {
<font color=#0000ff>static</font> NoisyReport nr;
NoisyReport() {} <font color=#009900>// Private constructor</font>
<font color=#0000ff>public</font>:
~NoisyReport() {
std::cout << <font color=#004488>"\n-------------------\n"</font>
<< <font color=#004488>"Noisy creations: "</font> << Noisy::create
<< <font color=#004488>"\nCopy-Constructions: "</font>
<< Noisy::copycons
<< <font color=#004488>"\nAssignments: "</font> << Noisy::assign
<< <font color=#004488>"\nDestructions: "</font> << Noisy::destroy
<< std::endl;
}
};
<font color=#009900>// Because of these this file can only be used</font>
<font color=#009900>// in simple test situations. Move them to a </font>
<font color=#009900>// .cpp file for more complex programs:</font>
<font color=#0000ff>long</font> Noisy::create = 0, Noisy::assign = 0,
Noisy::copycons = 0, Noisy::destroy = 0;
NoisyReport NoisyReport::nr;
#endif <font color=#009900>// NOISY_H ///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Each <B>Noisy</B> object has its own
identifier, and there are <B>static</B> variables to keep track of all the
creations, assignments (using <B>operator=</B>), copy-constructions and
destructions. The <B>id</B> is initialized using the <B>create</B> counter
inside the default constructor; the copy-constructor and assignment operator
take their <B>id</B> values from the rvalue. Of course, with <B>operator=</B>
the lvalue is already an initialized object so the old value of <B>id</B> is
printed before it is overwritten with the <B>id</B> from the
rvalue.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">In order to support certain operations
like sorting and searching (which are used implicitly by some of the
containers), <B>Noisy</B> must have an <B>operator<</B> and
<B>operator==</B>. These simply compare the <B>id</B> values. The
<B>operator<<</B> for <B>ostream</B> follows the standard form and simply
prints the <B>id</B>.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia"><B>NoisyGen</B> produces a function
object (since it has an <B>operator( )</B>) that is used to automatically
generate <B>Noisy</B> objects during testing.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia"><B>NoisyReport</B> is a type of class
called a <I>singleton</I>, which is a “design pattern” (these are
covered more fully in Chapter XX). Here, the goal is to make sure there is one
and only one <B>NoisyReport</B> object, because it is responsible for printing
out the results at program termination. It has a <B>private</B> constructor so
no one else can make a <B>NoisyReport</B> object, and a single static instance
of <B>NoisyReport</B> called <B>nr</B>. The only executable statements are in
the destructor, which is called as the program exits and the static destructors
are called; this destructor prints out the statistics captured by the
<B>static</B> variables in <B>Noisy</B>.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The one snag to this header file is the
inclusion of the definitions for the <B>static</B>s at the end. If you include
this header in more than one place in your project, you’ll get
multiple-definition errors at link time. Of course, you can put the
<B>static</B> definitions in a separate<B> cpp</B> file and link it in, but that
is less convenient, and since <B>Noisy</B> is just intended for quick-and-dirty
experiments the header file should be reasonable for most
situations.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Using <B>Noisy.h</B>, the following
program will show the behaviors that occur when a <B>vector</B> overflows its
currently allocated storage:</FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:VectorOverflow.cpp</font>
<font color=#009900>// Shows the copy-construction and destruction</font>
<font color=#009900>// That occurs when a vector must reallocate</font>
<font color=#009900>// (It maintains a linear array of elements)</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
#include <font color=#004488>"Noisy.h"</font>
#include <vector>
#include <iostream>
#include <string>
#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]);
vector<Noisy> vn;
Noisy n;
<font color=#0000ff>for</font>(<font color=#0000ff>int</font> i = 0; i < size; i++)
vn.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">You can either use the default value of
1000, or use your own value by putting it on the command-line.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">When you run this program, you’ll
see a single default constructor call (for <B>n</B>), then a lot of
copy-constructor calls, then some destructor calls, then some more
copy-constructor calls, and so on. When the vector runs out of space in the
linear array of bytes it has allocated, it must (to maintain all the objects in
a linear array, which is an essential part of its job) get a bigger piece of
storage and move everything over, copying first and then destroying the old
objects. You can imagine that if you store a lot of large and complex objects,
this process could rapidly become prohibitive.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">There are two solutions to this problem.
The nicest one requires that you know beforehand how many objects you’re
going to make. In that case you can use <B>reserve( )</B> to tell the
vector how much storage to pre-allocate, thus eliminating all the copies and
destructions and making everything very fast (especially random access to the
objects with <B>operator[ ]</B>). Note that the use of <B>reserve( )</B> is
different from using the <B>vector</B> constructor with an integral first
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?