chap02.htm.kbk
来自「c++设计思想」· KBK 代码 · 共 1,047 行 · 第 1/5 页
KBK
1,047 行
this can be true it
turns out that understanding the STL more deeply is important to gain the full
power of the library. This chapter and the next probe into the STL containers
and
algorithms.</FONT><A NAME="_Toc312374160"></A><A NAME="_Toc305593281"></A><A NAME="_Toc305628753"></A><A NAME="_Toc312374088"></A><A NAME="_Toc375545199"></A><A NAME="_Toc408018396"></A><A NAME="_Toc519042010"></A><BR></P></DIV>
<A NAME="Heading189"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H2 ALIGN="LEFT">
Containers and iterators</H2></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">If you don’t know how many objects
you’re going to need to solve a particular problem, or how long they will
last, you also don’t know how to store those objects. How can you know how
much space to create? You can’t, since that information isn’t known
until run time.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The solution to most problems in
object-oriented design seems flippant: you create another type of object. For
the storage problem, the new type of object holds other objects, or pointers to
objects. Of course, you can do the same thing with an array, but there’s
more. This new type of object, which is typically referred to in C++ as a
<I>container</I> (also called a <I>collection</I> in some languages), will
expand itself whenever necessary to accommodate everything you place inside it.
So you don’t need to know how many objects you’re going to hold in a
collection. You just create a collection object and let it take care of the
details.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Fortunately, a good OOP language comes
with a set of containers as part of the package. In C++, it’s the Standard
Template Library (STL). In some libraries, a generic container is considered
good enough for all needs, and in others (C++ in particular) the library has
different types of containers for different needs: a vector for consistent
access to all elements, and a linked list for consistent insertion at all
elements, for example, so you can choose the particular type that fits your
needs. These may include sets, queues, hash tables, trees, stacks,
etc.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">All containers have some way to put
things in and get things out. The way that you place something into a container
is fairly obvious. There’s a function called “push” or
“add” or a similar name. Fetching things out of a container is not
always as apparent; if it’s an array-like entity such as a vector, you
might be able to use an indexing operator or function. But in many situations
this doesn’t make sense. Also, a single-selection function is restrictive.
What if you want to manipulate or compare a group of elements in the
container?</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The solution is an <I>iterator</I>, which
is an object whose job is to select the elements within a container and present
them to the user of the iterator. As a class, it also provides a level of
abstraction. This abstraction can be used to separate the details of the
container from the code that’s accessing that container. The container,
via the iterator, is abstracted to be simply a sequence. The iterator allows you
to traverse that sequence without worrying about the underlying structure
– that is, whether it’s a vector, a linked list, a stack or
something else. This gives you the flexibility to easily change the underlying
data structure without disturbing the code in your program. </FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">From the design standpoint, all you
really want is a sequence that can be manipulated to solve your problem. If a
single type of sequence satisfied all of your needs, there’d be no reason
to have different kinds. There are two reasons that you need a choice of
containers. First, containers provide different types of interfaces and external
behavior. A stack has a different interface and behavior than that of a queue,
which is different than that of a set or a list. One of these might provide a
more flexible solution to your problem than the other. Second, different
containers have different efficiencies for certain operations. The best example
is a vector and a list. Both are simple sequences that can have identical
interfaces and external behaviors. But certain operations can have radically
different costs. Randomly accessing elements in a vector is a constant-time
operation; it takes the same amount of time regardless of the element you
select. However, in a linked list it is expensive to move through the list to
randomly select an element, and it takes longer to find an element if it is
further down the list. On the other hand, if you want to insert an element in
the middle of a sequence, it’s much cheaper in a list than in a vector.
These and other operations have different efficiencies depending upon the
underlying structure of the sequence. In the design phase, you might start with
a list and, when tuning for performance, change to a vector. Because of the
abstraction via iterators, you can change from one to the other with minimal
impact on your code.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">In the end, remember that a container is
only a storage cabinet to put objects in. If that cabinet solves all of your
needs, it doesn’t really matter <I>how</I> it is implemented (a basic
concept with most types of objects). If you’re working in a programming
environment that has built-in overhead due to other factors, then the cost
difference between a vector and a linked list might not matter. You might need
only one type of sequence. You can even imagine the “perfect”
container abstraction, which can automatically change its underlying
implementation according to the way it is
used.</FONT><A NAME="_Toc519042011"></A><BR></P></DIV>
<A NAME="Heading190"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H3 ALIGN="LEFT">
STL reference documentation</H3></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">You will notice that this chapter does
not contain exhaustive documentation describing each of the member functions in
each STL container. Although I describe the member functions that I use,
I’ve left the full descriptions to others: there are at least two very
good on-line sources of STL documentation in HTML format that you can keep
resident on your computer and view with a Web browser whenever you need to look
something up. The first is the Dinkumware library (which covers the entire
Standard C and C++ library) mentioned at the beginning of this book section
(page XXX). The second is the freely-downloadable SGI STL and documentation,
freely downloadable at http://www.sgi.com/Technology/STL/. These should provide
complete references when you’re writing code. In addition, the STL books
listed in Appendix XX will provide you with other
resources.</FONT><A NAME="_Toc519042012"></A><BR></P></DIV>
<A NAME="Heading191"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H2 ALIGN="LEFT">
The Standard Template Library
<BR><A NAME="Index491"></A><A NAME="Index492"></A><A NAME="Index493"></A><A NAME="Index494"></A></H2></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The C++
STL</FONT><A NAME="fnB19" HREF="#fn19">[19]</A><A NAME="Index495"></A><A NAME="Index496"></A><FONT FACE="Georgia">
is a powerful library intended to satisfy the vast bulk of your needs for
containers and algorithms, but in a completely portable fashion. This means that
not only are your programs easier to port to other platforms, but that your
knowledge itself does not depend on the libraries provided by a particular
compiler vendor (and the STL is likely to be more tested and scrutinized than a
particular vendor’s library). Thus, it will benefit you greatly to look
first to the STL for containers and algorithms, <I>before</I> looking at
vendor-specific solutions.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">A fundamental principle of software
design is that <I>all problems can be simplified by introducing an extra level
of indirection</I>. This simplicity is achieved in the STL using
<I>iterators</I> to perform operations on a data structure while knowing as
little as possible about that structure, thus producing data structure
independence. With the STL, this means that any operation that can be performed
on an array of objects can also be performed on an STL container of objects and
vice versa. The STL containers work just as easily with built-in types as they
do with user-defined types. If you learn the library, it will work on
everything.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The drawback to this independence is that
you’ll have to take a little time at first getting used to the way things
are done in the STL. However, the STL uses a consistent pattern, so once you fit
your mind around it, it doesn’t change from one STL tool to
another.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Consider an example using the STL
<B>set</B> <A NAME="Index497"></A><A NAME="Index498"></A>class. A set will allow
only one of each object value to be inserted into itself. Here is a simple
<B>set</B> created to work with <B>int</B>s by providing <B>int</B> as the
template argument to <B>set</B>:</FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:Intset.cpp</font>
<font color=#009900>// Simple use of STL set</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
#include <set>
#include <iostream>
<font color=#0000ff>using</font> <font color=#0000ff>namespace</font> std;
<font color=#0000ff>int</font> main() {
set<<font color=#0000ff>int</font>> intset;
<font color=#0000ff>for</font>(<font color=#0000ff>int</font> i = 0; i < 25; i++)
<font color=#0000ff>for</font>(<font color=#0000ff>int</font> j = 0; j < 10; j++)
<font color=#009900>// Try to insert multiple copies:</font>
intset.insert(j);
<font color=#009900>// Print to output:</font>
copy(intset.begin(), intset.end(),
ostream_iterator<<font color=#0000ff>int</font>>(cout, <font color=#004488>"\n"</font>));
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The <B>insert( )</B> member does all
the work: it tries putting the new element in and rejects it if it’s
already there. Very often the activities involved in using a set are simply
insertion and a test to see whether it contains the element. You can also form a
union, intersection, or difference of sets, and test to see if one set is a
subset of another.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">In this example, the values 0 - 9 are
inserted into the set 25 times, and the results are printed out to show that
only one of each of the values is actually retained in the set.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The <B>copy( )</B> function is
actually the instantiation of an STL template function, of which there are many.
These template functions are generally referred to as “the STL
Algorithms” and will be the subject of the following chapter. However,
several of the algorithms are so useful that they will be introduced in this
chapter. Here, <B>copy( ) </B>shows the use of iterators. The <B>set</B>
member functions <B>begin( )</B> and <B>end( )</B> produce iterators
as their return values. These are used by <B>copy( )</B> as beginning and
ending points for its operation, which is simply to move between the boundaries
established by the iterators and copy the elements to the third argument, which
is also an iterator, but in this case, a special type created for iostreams.
This places <B>int</B> objects on <B>cout</B> and separates them with a
newline.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Because of its genericity,
<B>copy( )</B> is certainly not restricted to printing on a stream. It can
be used in virtually any situation: it needs only three iterators to talk to.
All of the algorithms follow the form of <B>copy( )</B> and simply
manipulate iterators (the use of iterators is the “extra level of
indirection”).</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Now consider taking the form of
<B>Intset.cpp</B> and reshaping it to display a list of the words used in a
document. The solution becomes remarkably simple.</FONT><BR></P></DIV>
<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#009900>//: C07:WordSet.cpp</font>
<font color=#009900>//{L} ../TestSuite/Test</font>
#include <font color=#004488>"..</font><font color=#004488>/require.h"</font>
#include <string>
#include <fstream>
#include <iostream>
#include <set>
<font color=#0000ff>using</font> <font color=#0000ff>namespace</font> std;
<font color=#0000ff>void</font> wordSet(<font color=#0000ff>char</font>* fileName) {
ifstream source(fileName);
assure(source, fileName);
string word;
set<string> words;
<font color=#0000ff>while</font>(source >> word)
words.insert(word);
copy(words.begin(), words.end(),
ostream_iterator<string>(cout, <font color=#004488>"\n"</font>));
cout << <font color=#004488>"Number of unique words:"</font>
<< words.size() << endl;
}
<font color=#0000ff>int</font> main(<font color=#0000ff>int</font> argc, <font color=#0000ff>char</font>* argv[]) {
<font color=#0000ff>if</font>(argc > 1)
wordSet(argv[1]);
<font color=#0000ff>else</font>
wordSet(<font color=#004488>"WordSet.cpp"</font>);
} <font color=#009900>///:~</font></PRE></FONT></BLOCKQUOTE>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The only substantive difference here is
that <B>string</B> is used instead of <B>int</B>. The words are pulled from a
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?