没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
4
A Tour of C++: Containers and Algorithms
Why waste time learning
when ignorance is instantaneous?
– Hobbes
• Libraries
Standard Library Overview; The Standard-library Headers and Namespace
• Strings
• Stream I/O
Output; Input;
ssttrr ii nngg I/O; I/O of User-defined Types
• Containers
vv eeccttoorr; ll ii sstt; mmaapp; uunnoorrddeerreedd__mmaapp; Container Overview
• Algorithms
Use of Iterators; Iterator Types; Stream Iterators; Predicates; Algorithm Overview;
Container Algorithms
• Advice
4.1 Libraries [tour3.lib]
No significant program is written in just a bare programming language. First, a set of sup-
porting libraries is developed. These then form the basis for further work. Most programs
are tedious to write in the bare language, whereas just about any task can be rendered sim-
ple by the use of good libraries.
Continuing from Chapter 2 and Chapter 3, this chapter and the next give a quick tour
of key standard-library facilities. The assumption is that you have programmed before. If
not, please consider reading a textbook, such as Programming: Principles and Practice
using C++ [Stroustrup, 2009], before continuing here. Even if you have programmed
The C++ Programming Language, 4th edition ©2013 by Pearson Education, Inc. Reproduced in draft form with the permission of the publisher.
D R A F T
94 A Tour of C++: Containers and Algorithms Chapter 4
before, the libraries you used or the applications you wrote may be very different from the
style of C++ presented here. If you find this ‘‘lightning tour’’ confusing, another approach
could be to skip to the more systematic and bottom up language presentation starting in
Chapter 6. Similarly, a more systematic description of the standard library starts in Chap-
ter 30.
I very briefly present useful standard-library types, such as
ssttrr ii nngg, oossttrreeaamm, vv eeccttoorr, mmaapp
(this chapter), uunniiqquuee__ppttrr, tthhrreeaadd, rreeggee xx, and ccoommppllee xx (Chapter 5), as well as the most com-
mon ways of using them. Doing this allows me to give better examples in the following
chapters. As in Chapter 2 and Chapter 3, you are strongly encouraged not to be distracted
or discouraged by an incomplete understanding of details. The purpose of this chapter is
to give you a taste of what is to come and to convey a basic understanding of the most use-
ful library facilities.
The standard library facilities described in this book are part of every complete C++
implementation. In addition to the standard C++ library, most implementations offer
‘‘graphical user interface’’ systems (GUIs), Web interfaces, database interfaces, etc. Simi-
larly, most application development environments provide ‘‘foundation libraries’’ for cor-
porate or industrial ‘‘standard’’ dev elopment and/or execution environments. Here, I do
not describe such systems and libraries. The intent is to provide a self-contained descrip-
tion of C++ as defined by the standard and to keep the examples portable, except where
specifically noted. Naturally, a programmer is encouraged to explore the more extensive
facilities available on most systems.
4.1.1 Standard-library Overview [tour3.post]
The facilities provided by the standard library can be classified like this:
[1] Basic run-time language support (e.g., for allocation and run-time type informa-
tion); see §30.3.
[2] The C standard library (with very minor modifications to minimize violations of
the type system); see Chapter 41.
[3] Strings and I/O streams (with support for international character sets and local-
ization); see Chapter 35, Chapter 37, and Chapter 38. I/O streams is an extensi-
ble framework to which users can add their own streams, buffering strategies,
and character sets.
[4] A framework of containers (such as
vv eeccttoorr, ll ii sstt, and mmaapp) and algorithms (such as
fifinndd(()), ssoorr tt(()), and mmeerrggee(())); see §4.4, §4.5 ,Chapter 31, Chapter 32, and Chapter 33.
This framework, conventionally called the STL [Stepanov,1994], is extensible so
that users can easily add their own containers and algorithms.
[5] Support for numerical computation (such as standard mathematical functions,
complex numbers, vectors with arithmetic operations, and random number gen-
erators); see §3.2.1.1 and Chapter 39.
[6] Support for regular expression matching; see §5.5 and Chapter 36.
[7] Support for concurrent processing, including
tthhrreeaadds and ll oocc kks; see §5.3 and
Chapter 40. The concurrency support is foundational so that users can add sup-
port for new models of concurrency as libraries.
The C++ Programming Language, 4th edition ©2013 by Pearson Education, Inc. Reproduced in draft form with the permission of the publisher.
D R A F T
Section 4.1.1 Standard-library Overview 95
[8] Utilities to support template metaprogramming (e.g., type traits; §5.4.2, §28.2.4,
§34.7), STL-style generic programming (e.g.,
ppaaiirr; §5.4.3, §34.2.4.1), and gen-
eral programming (e.g.,
cclloocc kk; §5.4.1, §34.6).
[9] ‘‘Smart pointers’’ for resource management (e.g.,
uunniiqquuee__ppttrr and sshhaarreedd__ppttrr;
§5.2.1, §34.3) and an interface to garbage collectors (§34.8).
[10] Special-purpose containers, such as
aarrrr aayy (§34.2.1), bbiittsseett (§34.2.2), and ttuuppllee
(§34.2.4.2).
The main criterion for including a class in the library was that it would somehow be used
by almost every C++ programmer (both novices and experts), that it could be provided in
a general form that did not add significant overhead compared to a simpler version of the
same facility, and that simple uses should be easy to learn (relative to the inherent com-
plexity of the task performed). Essentially, the C++ standard library provides the most
common fundamental data structures together with the fundamental algorithms used on
them.
4.1.2 The Standard-library Headers and Namespace [tour3.name]
Every standard library facility is provided through some standard header. For example:
##iinncclluuddee<<ssttrr ii nngg>>
##iinncclluuddee<<lliisstt>>
This makes the standard ssttrr ii nngg and ll ii sstt available.
The standard library is defined in a namespace (§2.4.2, §14.3.1) called
ssttdd. To use
standard library facilities, the
ssttdd:::: prefix can be used:
ssttdd::::ssttrr ii nnggss{{""FFoouurrlleeggssGGoooodd;;ttwwoolleeggssBBaaaaaadd!!""}};;
ssttdd::::lliisstt<<ssttdd::::ssttrr ii nngg>>ssllooggaannss{{""WWaarriissppeeaaccee"",,""FFrreeeeddoommiissSSllaavveerryy"",,""IIggnnoorraanncceei
issSSttrreennggtthh""}};;
For simplicity, I will rarely use the ssttdd:::: prefix explicitly in examples. Neither will I
always
##iinncclluuddee the necessary headers explicitly. To compile and run the program frag-
ments here, you must
##iinncclluuddee the appropriate headers (as listed in §4.4.5, §4.5.5, and
§30.2) and make the names they declare accessible. For example:
##iinncclluuddee<<ssttrr ii nngg>>//// make the standard string facilities accessible
uussiinngg nnaammeessppaaccee ssttdd;;//// make std names available without std:: prefix
ssttrr ii nnggss{{""CC++++iissaaggeenneerraall−−ppuurrppoosseepprrooggrraammmmiinnggllaanngguuaaggee""}};;//// ok: string is std::string
It is generally in poor taste to dump every name from a namespace into the global
namespace. However, in this book, I use the standard library almost exclusively and it is
good to know what it offers.
Here is a table of selected standard-library headers, all supplying declarations in
namespace
ssttdd:
The C++ Programming Language, 4th edition ©2013 by Pearson Education, Inc. Reproduced in draft form with the permission of the publisher.
D R A F T
96 A Tour of C++: Containers and Algorithms Chapter 4
Selected Standard Library Headers
<<aallggoorr ii tthhmm>>ccooppyy(()), fifinndd(()), ssoorr tt(()) §32.2 §iso.25
<<aarrrr aayy>>aarrrraayy §34.2.1 §iso.23.3.2
<<ccmmaatthh>> ssqqrrtt(()), ppoo ww(()) §39.3 §iso.26.8
<<ccoommppllee xx>>ccoommpplleexx, ssqqrr tt(()), ppoo ww(()) §39.4 §iso.26.8
<<ffssttrreeaamm>> ffssttrreeaamm, ii ffssttrreeaamm, ooffssttrreeaamm §37.2.1 §iso.27.9.1
<<ffuuttuurree>> ffuuttuurree, pprroommiissee §5.3.5 §iso.30.6
<<iioossttrreeaamm>> ii ssttrreeaamm, oossttrreeaamm, cciinn, ccoouutt §37.1 §iso.27.4
<<iitteerr aattoorr>>bbaacckk__iinnsseerrtteerr(()), rree vveerrssee__iitteerraattoorr, bbeeggiinn(()) §33.2 §iso.24.3
<<lliimmiittss>> nnuummeerriicc__lliimmiittss §39.2 §iso.18.3
<<lliisstt>> ll ii sstt §31.4.2 §iso.23.3.5
<<mmaapp>> mmaapp, mm uullttiimmaapp §31.4.3 §iso.23.4.4
<<mmeemmoorr yy>>uunniiqquuee__ppttrr, sshhaarreedd__ppttrr, aallllooccaattoorr §5.2.1 §iso.20.6
<<mm uutteexx>>mmuutteexx, ttiimmeedd__mm uutteexx, rreeccuurrssiivv ee__mmuutteexx §40.6.1 §iso.30.4
<<rreeggee xx>>rreeggeexx, ssmmaattcchh Chapter 36 §iso.28.8
<<sseett>> sseett, mm uullttiisseett §31.4.3 §iso.23.4.6
<<ssssttrreeaamm>> ii ssttrrssttrreeaamm, oossttrrssttrreeaamm §37.2.2 §iso.27.8
<<ssttrr ii nngg>>ssttrriinngg, bbaassiicc__ssttrr ii nngg Chapter 35 §iso.21.3
<<tthhrreeaadd>> tthhrreeaadd §5.3.1 §iso.30.3
<<uunnoorrddeerreedd__mmaapp>> uunnoorrddeerreedd__mmaapp, uunnoorrddeerreedd__mm uullttiimmaapp §31.4.3.2 §iso.23.5.4
<<uuttiilliittyy>> mmoovvee(()), ss wwaapp(()), ppaaiirr §34.9 §iso.20.1
<<vv aallaarrrraayy>>vvaallaarrrraayy, sslliiccee, ggsslliiccee §39.5 §iso.26.6
<<vv eeccttoorr>>vveeccttoorr §31.2 §iso.23.3.6
This listing is far from complete, see §30.2 for more information.
4.2 Strings [tour3.string]
The standard library provides a
ssttrr ii nngg type to complement the string literals. The ssttrr ii nngg
type provides a variety of useful string operations, such as concatenation. For example:
ssttrr ii nnggccoommppoossee((ccoonnssttssttrriinngg&&nnaammee,,ccoonnssttssttrriinngg&&ddoommaaiinn))
{{
rreettuurr nnnnaammee++’’@@’’ ++ddoommaaiinn;;
}}
aauuttoo aaddddrr ==ccoommppoossee((""ddmmrr"",,""bbeellll−−l
laabbss..ccoomm""));;
Here, aaddddrr is initialized to the character sequence ddmmrr@@bbeellll−−llaabbss ..ccoomm. ‘‘Addition’’ of
strings means concatenation. You can concatenate a
ssttrr ii nngg, a string literal, a C-style string,
or a character to a
ssttrr ii nngg. The standard ssttrr ii nngg has a move constructor so returning even long
ssttrr ii nnggs by value is efficient (§3.3.2).
In many applications, the most common form of concatenation is adding something to
the end of a
ssttrr ii nngg. This is directly supported by the ++== operation. For example:
The C++ Programming Language, 4th edition ©2013 by Pearson Education, Inc. Reproduced in draft form with the permission of the publisher.
D R A F T
Section 4.2 Strings 97
vv ooiiddmm22((ssttrriinngg&&ss11,,ssttrriinngg&&ss22))
{{
ss11 ==ss11++’’\\nn’’;;//// append newline
ss22 ++==’’\\nn’’;;//// append newline
}}
The two ways of adding to the end of a ssttrr ii nngg are semantically equivalent, but I prefer the
latter because it is more explicit about what it does, more concise, and possibly more effi-
ciently implemented.
A
ssttrr ii nngg is mutable. In addition to == and ++==, subscripting (using [[]]) and substring opera-
tions are supported. The standard-library
ssttrr ii nngg is described in Chapter 35. Among other
useful features, it provides the ability to manipulate substrings. For example:
ssttrr ii nnggnnaammee==""NNiieellssSSttrroouussttrruupp"";;
vv ooiiddmm33(())
{{
ssttrr ii nnggss==nnaammee..ssuubbssttrr((66,,1100));;//// s = "Stroustr up"
nnaammee ..rreeppllaaccee((00,,55,,""nniicchhoollaass""));;//// name becomes "nicholas Stroustrup"
nnaammee[[00]] ==’
’NN’’;;//// name becomes "Nicholas Stroustrup"
}}
The ssuubbssttrr(()) operation returns a ssttrr ii nngg that is a copy of the substring indicated by its argu-
ments. The first argument is an index into the
ssttrr ii nngg (a position), and the second argument
is the length of the desired substring. Since indexing starts from
00, ss gets the value SSttrroouuss--
ttrr uupp
.
The
rreeppllaaccee(()) operation replaces a substring with a value. In this case, the substring
starting at
00 with length 55 is NNiieellss; it is replaced by NNiicchhoollaass. Thus, the final value of nnaammee
is NNiicchhoollaass SSttrroouussttrruupp. Note that the replacement string need not be the same size as the
substring that it is replacing.
Naturally,
ssttrr ii nnggs can be compared against each other and against string literals. For
example:
ssttrr ii nnggiinnccaannttaattiioonn;;
vv ooiiddrreessppoonndd((ccoonnssttssttrriinngg&&aannsswweerr))
{{
ii ff ((aannsswweerr====iinnccaannttaattiioonn)){{
//// perfor m magic
}}
eellssee ii ff((aannsswweerr====""yyeess"")){{
//// ...
}}
//// ...
}}
The ssttrr ii nngg library is described in Chapter 35. The most common techniques for imple-
menting
ssttrr ii nngg are presented in the SSttrr ii nngg example (§19.3).
The C++ Programming Language, 4th edition ©2013 by Pearson Education, Inc. Reproduced in draft form with the permission of the publisher.
D R A F T
剩余25页未读,继续阅读
资源评论
- sjyyxl2013-10-21只有其中一章,可以看这里 http://download.csdn.net/detail/godghdai/5975259。
- puma88882013-11-08可惜只有第四章。
- panjunye20072013-11-08不是完整的。
- donglailai2013-06-10写的不错,最终要的是包含11的内容。哪里有完整的资料?
herald1qaz
- 粉丝: 0
- 资源: 5
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功