📄 chap07.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<!--
This document was converted from RTF source:
By rtftohtml 4.19
See http://www.sunpack.com/RTF
Filename:C:\TEMP\TicV2\html\TicV2.rtf
Application Directory:C:\TOOLS\RTF2HTML\
Subject:
Author:Bruce Eckel
Operator:Bruce Eckel
Document Comments:
Version Comments:
Comments:
Keywords:
Translation Date:09/26/2001
Translation Time:08:32:26
Translation Platform:Win32
Number of Output files:19
This File:C:\TEMP\TicV2\html\Chap07.htm
SplitDepth=1
SkipNavPanel=1
SkipLeadingToc=1
SkipTrailingToc=1
GenContents=1
GenFrames=1
GenIndex=1
-->
<HEAD lang="en"><META http-equiv="Content-Type" content="text/html">
<TITLE>7: STL Containers & Iterators</TITLE>
</HEAD>
<BODY BGCOLOR="#FFFFFF"><DIV ALIGN="CENTER">
<a href="http://www.MindView.net">
<img src="mindview.gif" alt="MindView Inc." BORDER = "0"></a>
<CENTER>
<FONT FACE="Verdana, Tahoma, Arial, Helvetica, Sans" size = "-1">
[ <a href="README.txt">Viewing Hints</a> ]
[ <a href="RevisionHistory.htm">Revision History</a> ]
[ <a href="http://www.mindview.net/Books/TICPP/ThinkingInCPP2e.html">Book Home Page</a> ]
[ <a href="http://www.mindview.net/Etc/MailingList.html">Free Newsletter</a> ] <br>
[ <a href="http://www.mindview.net/Seminars">Seminars</a> ]
[ <a href="http://www.mindview.net/CDs">Seminars on CD ROM</a> ]
[ <a href="http://www.mindview.net/Services">Consulting</a> ]
</FONT>
<H2><FONT FACE="Verdana, Tahoma, Arial, Helvetica, Sans">
Thinking in C++, 2nd edition, Volume 2<br>
<small>Revision 4.0</small></FONT></H2>
<H3><FONT FACE="Verdana, Tahoma, Arial, Helvetica, Sans">
by Bruce Eckel & Chuck Allison<br>©2001 MindView, Inc.</FONT></H3>
<FONT FACE="Verdana, Tahoma, Arial, Helvetica, Sans" size = "-1">
[ <a href="Chap06.htm">Previous Chapter</a> ]
[ <a href="SimpCont.htm">Short TOC</a> ]
[ <a href="Contents.htm">Table of Contents</a> ]
[ <a href="DocIdx.htm">Index</a> ]
[ <a href="Chap08.htm">Next Chapter</a> ]
</FONT>
</CENTER>
</P></DIV><A NAME="_Toc519042009"></A><A NAME="Heading188"></A><FONT FACE = "Verdana, Tahoma, Arial, Helvetica, Sans"><H1 ALIGN="LEFT">
7: STL Containers & Iterators<A NAME="STLContainersChapter"></A></H1></FONT>
<DIV ALIGN="LEFT"><P><FONT FACE="Verdana" SIZE=4><I>Container classes </I>are the
solution to a specific kind of code reuse problem. They are building blocks used
to create object-oriented programs – they make the internals of a program
much easier to construct.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">A container class describes an object
that holds other objects. Container classes are so important that they were
considered fundamental to early object-oriented languages. In Smalltalk, for
example, programmers think of the language as the program translator together
with the class library, and a critical part of that library is the container
classes. So it became natural that C++ compiler vendors also include a container
class library. You’ll note that the <B>vector</B> was so useful that it
was introduced in its simplest form very early in this book.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Like many other early C++ libraries,
early container class libraries followed Smalltalk’s <I>object-based
hierarchy</I>, which worked well for Smalltalk, but turned out to be awkward and
difficult to use in C++. Another approach was required.</FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">This chapter attempts to slowly work you
into the concepts of the C++ <I>Standard Template Library </I>(STL), which is a
powerful library of containers (as well as <I>algorithms</I>, but these are
covered in the following chapter). In the past, I have taught that there is a
relatively small subset of elements and ideas that you need to understand in
order to get much of the usefulness from the STL. Although 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
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -