________________________________________

________________________________________________________________________________________________________________________________________________________________

3 ________________________________________
________________________________________________________________________________________________________________________________________________________________

A Tour of the Standard Library
Why waste time learning when ignorance is instantaneous? – Hobbes

Standard libraries — output — strings — input — vectors — range checking — lists — maps — container overview — algorithms — iterators — I/O iterators — traversals and predicates — algorithms using member functions — algorithm overview — complex numbers — vector arithmetic— standard library overview — advice.

3.1 Introduction
No significant program is written in just a bare programming language. First, a set of supporting libraries are developed. These then form the basis for further work. Continuing Chapter 2, this chapter gives a quick tour of key library facilities to give you an idea what can be done using C++ and its standard library. Useful library types, such as s tr in g, v ec to r, st ri ng ve ct or l is t, and m ap are presented as well as the most common ways of using them. Doing this allows me li st ma p, to give better examples and to set better exercises in the following chapters. As in Chapter 2, 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 an understanding of the simplest uses of the most useful library facilities. A more detailed introduction to the standard library is given in §16.1.2. 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, often referred to as GUIs or window systems, for interaction between a user and a program. Similarly, most application development environments provide ‘‘foundation libraries’’ that support corporate or industrial ‘‘standard’’ development and/or execution environments. I do not describe such systems and libraries. The intent is to provide a self-contained description of C++

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

46

A Tour of the Standard Library

Chapter 3

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, but that is left to exercises.

3.2 Hello, world!
The minimal C++ program is
i nt m ai n() { } in t ma in

It defines a function called m ai n, which takes no arguments and does nothing. ma in Every C++ program must have a function named m ai n(). The program starts by executing that ma in function. The i nt value returned by m ai n(), if any, is the program’s return value to ‘‘the system.’’ in t ma in If no value is returned, the system will receive a value indicating successful completion. A nonzero value from m ai n() indicates failure. ma in Typically, a program produces some output. Here is a program that writes out H el lo w or ld He ll o, wo rl d!:
#i nc lu de <i os tr ea m> in cl ud e io st re am i nt m ai n() in t ma in { s td :c ou t << "H el lo w or ld \n st d: co ut He ll o, wo rl d!\ n"; }

The line #i nc lu de <i os tr ea m> instructs the compiler to include the declarations of the standard in cl ud e io st re am stream I/O facilities as found in i os tr ea m. Without these declarations, the expression io st re am
s td :c ou t << "H el lo w or ld \n st d: co ut He ll o, wo rl d!\ n"

would make no sense. The operator << (‘‘put to’’) writes its second argument onto its first. In this case, the string literal "H el lo w or ld \n is written onto the standard output stream s td :c ou t. A He ll o, wo rl d!\ n" st d: co ut string literal is a sequence of characters surrounded by double quotes. In a string literal, the backslash character \ followed by another character denotes a single special character. In this case, \ n is \n the newline character, so that the characters written are H el lo w or ld followed by a newline. He ll o, wo rl d!

3.3 The Standard Library Namespace
The standard library is defined in a namespace (§2.4, §8.2) called s td That is why I wrote st d. s td :c ou t rather than plain c ou t. I was being explicit about using the s ta nd ar d c ou t, rather than st d: co ut co ut st an da rd co ut some other c ou t. co ut Every standard library facility is provided through some standard header similar to <i os tr ea m>. io st re am For example:
#i nc lu de st ri ng in cl ud e<s tr in g> #i nc lu de li st in cl ud e<l is t>

This makes the standard s tr in g and l is t available. To use them, the s td : prefix can be used: st ri ng li st st d:

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

Section 3.3

The Standard Library Namespace

47

s td :s tr in g s = "F ou r l eg s G oo d; t wo l eg s B aa ad st d: st ri ng Fo ur le gs Go od tw o le gs Ba aa d!"; s td :l is t<s td :s tr in g> s lo ga ns st d: li st st d: st ri ng sl og an s;

For simplicity, I will rarely use the s td : prefix explicitly in examples. Neither will I always st d: #i nc lu de the necessary headers explicitly. To compile and run the program fragments here, you in cl ud e must #i nc lu de the appropriate headers (as listed in §3.7.5, §3.8.6, and Chapter 16). In addition, in cl ud e you must either use the s td : prefix or make every name from s td global (§8.2.3). For example: st d: st d
#i nc lu de st ri ng in cl ud e<s tr in g> u si ng n am es pa ce s td us in g na me sp ac e st d; s tr in g s = "I gn or an ce i s b li ss st ri ng Ig no ra nc e is bl is s!"; // make the standard string facilities accessible // make std names available without std:: prefix // ok: string is std::string

It is generally in poor taste to dump every name from a namespace into the global namespace. However, to keep short the program fragments used to illustrate language and library features, I omit repetitive #i nc lu de and s td : qualifications. In this book, I use the standard library almost in cl ud es st d: exclusively, so if a name from the standard library is used, it either is a use of what the standard offers or part of an explanation of how the standard facility might be defined.

3.4 Output
The iostream library defines output for every built-in type. Further, it is easy to define output of a user-defined type. By default, values output to c ou t are converted to a sequence of characters. For co ut example,
v oi d f vo id f() { c ou t << 1 0; co ut 10 }

will place the character 1 followed by the character 0 on the standard output stream. So will
v oi d g vo id g() { i nt i = 1 0; in t 10 c ou t << i co ut i; }

Output of different types can be combined in the obvious way:
v oi d h in t i vo id h(i nt i) { c ou t << "t he v al ue o f i i s "; co ut th e va lu e of is c ou t << i co ut i; c ou t << ´\ n´; co ut \n }

If i has the value 1 0, the output will be 10
t he v al ue o f i i s 1 0 th e va lu e of is 10

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

48

A Tour of the Standard Library

Chapter 3

A character constant is a character enclosed in single quotes. Note that a character constant is output as a character rather than as a numerical value. For example,
v oi d k vo id k() { c ou t << ´a co ut a´; c ou t << ´b co ut b´; c ou t << ´c co ut c´; }

will output a bc ab c. People soon tire of repeating the name of the output stream when outputting several related items. Fortunately, the result of an output expression can itself be used for further output. For example:
v oi d h 2(i nt i vo id h2 in t i) { c ou t << "t he v al ue o f i i s " << i << ´\ n´; co ut th e va lu e of is \n }

This is equivalent to h h(). Streams are explained in more detail in Chapter 21.

3.5 Strings
The standard library provides a s tr in g type to complement the string literals used earlier. The st ri ng s tr in g type provides a variety of useful string operations, such as concatenation. For example: st ri ng
s tr in g s 1 = "H el lo st ri ng s1 He ll o"; s tr in g s 2 = "w or ld st ri ng s2 wo rl d"; v oi d m 1() vo id m1 { s tr in g s 3 = s 1 + ", " + s 2 + "!\ n"; st ri ng s3 s1 s2 \n c ou t << s 3; co ut s3 }

Here, s 3 is initialized to the character sequence s3
H el lo w or ld He ll o, wo rl d!

followed by a newline. Addition of strings means concatenation. You can add strings, string literals, and characters to a string. In many applications, the most common form of concatenation is adding something to the end of a string. This is directly supported by the += operation. For example:
v oi d m 2(s tr in g& s 1, s tr in g& s 2) vo id m2 st ri ng s1 st ri ng s2 { s 1 = s 1 + ´\ n´; // append newline s1 s1 \n s 2 += ´\ n´; s2 \n // append newline }

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

Section 3.5

Strings

49

The two ways of adding to the end of a string are semantically equivalent, but I prefer the latter because it is more concise and likely to be more efficiently implemented. Naturally, s tr in gs can be compared against each other and against string literals. For example: st ri ng
s tr in g i nc an ta ti on st ri ng in ca nt at io n; v oi d r es po nd co ns t s tr in g& a ns we r) vo id re sp on d(c on st st ri ng an sw er { i f (a ns we r == i nc an ta ti on { if an sw er in ca nt at io n) // perform magic } e ls e i f (a ns we r == "y es { el se if an sw er ye s") // ... } // ... }

The standard library string class is described in Chapter 20. Among other useful features, it provides the ability to manipulate substrings. For example:
s tr in g n am e = "N ie ls S tr ou st ru p"; st ri ng na me Ni el s St ro us tr up v oi d m 3() vo id m3 { s tr in g s = n am e.s ub st r(6 10 ; st ri ng na me su bs tr 6,1 0) n am e.r ep la ce 0,5 Ni ch ol as ; na me re pl ac e(0 5,"N ic ho la s") }

// s = "Stroustrup" // name becomes "Nicholas Stroustrup"

The s ub st r() operation returns a string that is a copy of the substring indicated by its arguments. su bs tr The first argument is an index into the string (a position), and the second argument is the length of the desired substring. Since indexing starts from 0 s gets the value S tr ou st ru p. 0, St ro us tr up The r ep la ce operation replaces a substring with a value. In this case, the substring starting at re pl ac e() 0 with length 5 is N ie ls it is replaced by N ic ho la s. Thus, the final value of n am e is N ic ho la s Ni el s; Ni ch ol as na me Ni ch ol as S tr ou st ru p. Note that the replacement string need not be the same size as the substring that it is St ro us tr up replacing. 3.5.1 C-Style Strings A C-style string is a zero-terminated array of characters (§5.2.2). As shown, we can easily enter a C-style string into a s tr in g. To call functions that take C-style strings, we need to be able to extract st ri ng the value of a s tr in g in the form of a C-style string. The c _s tr st ri ng c_ st r() function does that (§20.3.7). For na me pr in tf example, we can print the n am e using the C output function p ri nt f() (§21.8) like this:
v oi d f vo id f() { p ri nt f("n am e: %s \n na me c_ st r()); pr in tf na me s\ n",n am e.c _s tr }

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

50

A Tour of the Standard Library

Chapter 3

3.6 Input
The standard library offers i st re am for input. Like o st re am i st re am deal with character string is tr ea ms os tr ea ms, is tr ea ms representations of built-in types and can easily be extended to cope with user-defined types. The operator >> (‘‘get from’’) is used as an input operator; c in is the standard input stream. ci n The type of the right-hand operand of >> determines what input is accepted and what is the target of the input operation. For example,
v oi d f vo id f() { i nt i in t i; c in >> i // read an integer into i ci n i; d ou bl e d do ub le d; c in >> d // read a double-precision, floating-point number into d ci n d; }

reads a number, such as 1 23 4, from the standard input into the integer variable i and a floating12 34 point number, such as 1 2.3 4e 5, into the double-precision, floating-point variable d 12 34 e5 d. Here is an example that performs inch-to-centimeter and centimeter-to-inch conversions. You input a number followed by a character indicating the unit: centimeters or inches. The program then outputs the corresponding value in the other unit:
i nt m ai n() in t ma in { c on st f lo at f ac to r = 2 54 // 1 inch equals 2.54 cm co ns t fl oa t fa ct or 2.5 4; f lo at x i n, c m; fl oa t x, in cm c ha r c h = 0 ch ar ch 0; c ou t << "e nt er l en gt h: "; co ut en te r le ng th c in >> x ci n x; c in >> c h; ci n ch // read a floating-point number // read a suffix

s wi tc h (c h) { sw it ch ch c as e ´i ca se i´: // inch in = x in x; c m = x fa ct or cm x*f ac to r; b re ak br ea k; c as e ´c ca se c´: // cm i n = x fa ct or in x/f ac to r; cm = x cm x; br ea k; b re ak d ef au lt de fa ul t: in = cm = 0 in cm 0; b re ak br ea k; } c ou t << i n << " i n = " << c m << " c m\ n"; co ut in in cm cm \n }

The switch-statement tests a value against a set of constants. The break-statements are used to exit

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

Section 3.6

Input

51

the switch-statement. The case constants must be distinct. If the value tested does not match any of them, the d ef au lt is chosen. The programmer need not provide a d ef au lt de fa ul t de fa ul t. Often, we want to read a sequence of characters. A convenient way of doing that is to read into a s tr in g. For example: st ri ng
i nt m ai n() in t ma in { s tr in g s tr st ri ng st r; c ou t << "P le as e e nt er y ou r n am e\ n"; co ut Pl ea se en te r yo ur na me \n c in >> s tr ci n st r; c ou t << "H el lo " << s tr << "!\ n"; co ut He ll o, st r \n }

If you type in
E ri c Er ic

the response is
H el lo E ri c! He ll o, Er ic

By default, a whitespace character (§5.2.2) such as a space terminates the read, so if you enter
E ri c B lo od ax e Er ic Bl oo da xe

pretending to be the ill-fated king of York, the response is still
H el lo E ri c! He ll o, Er ic

You can read a whole line using the g et li ne function. For example: ge tl in e()
i nt m ai n() in t ma in { s tr in g s tr st ri ng st r; c ou t << "P le as e e nt er y ou r n am e\ n"; co ut Pl ea se en te r yo ur na me \n g et li ne ci n,s tr ; ge tl in e(c in st r) c ou t << "H el lo " << s tr << "!\ n"; co ut He ll o, st r \n }

With this program, the input
E ri c B lo od ax e Er ic Bl oo da xe

yields the desired output:
H el lo E ri c B lo od ax e! He ll o, Er ic Bl oo da xe

The standard strings have the nice property of expanding to hold what you put in them, so if you enter a couple of megabytes of semicolons, the program will echo pages of semicolons back at you – unless your machine or operating system runs out of some critical resource first.

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

52

A Tour of the Standard Library

Chapter 3

3.7 Containers
Much computing involves creating collections of various forms of objects and then manipulating such collections. Reading characters into a string and printing out the string is a simple example. A class with the main purpose of holding objects is commonly called a container. Providing suitable containers for a given task and supporting them with useful fundamental operations are important steps in the construction of any program. To illustrate the standard library’s most useful containers, consider a simple program for keeping names and telephone numbers. This is the kind of program for which different approaches appear ‘‘simple and obvious’’ to people of different backgrounds. 3.7.1 Vector For many C programmers, a built-in array of (name,number) pairs would seem to be a suitable starting point:
s tr uc t E nt ry { st ru ct En tr y s tr in g n am e; st ri ng na me i nt n um be r; in t nu mb er }; E nt ry p ho ne _b oo k[1 00 0]; En tr y ph on e_ bo ok 10 00 v oi d p ri nt _e nt ry in t i vo id pr in t_ en tr y(i nt i) // simple use { c ou t << p ho ne _b oo k[i na me << ´ ´ << p ho ne _b oo k[i nu mb er << ´\ n´; co ut ph on e_ bo ok i].n am e ph on e_ bo ok i].n um be r \n }

However, a built-in array has a fixed size. If we choose a large size, we waste space; if we choose a smaller size, the array will overflow. In either case, we will have to write low-level memorymanagement code. The standard library provides a v ec to r (§16.3) that takes care of that: ve ct or
v ec to r<E nt ry p ho ne _b oo k(1 00 0); ve ct or En tr y> ph on e_ bo ok 10 00 v oi d p ri nt _e nt ry in t i vo id pr in t_ en tr y(i nt i) // simple use, exactly as for array { c ou t << p ho ne _b oo k[i na me << ´ ´ << p ho ne _b oo k[i nu mb er << ´\ n´; co ut ph on e_ bo ok i].n am e ph on e_ bo ok i].n um be r \n } v oi d a dd _e nt ri es in t n // increase size by n vo id ad d_ en tr ie s(i nt n) { p ho ne _b oo k.r es iz e(p ho ne _b oo k.s iz e()+n ; ph on e_ bo ok re si ze ph on e_ bo ok si ze n) }

The v ec to r member function s iz e() gives the number of elements. ve ct or si ze Note the use of parentheses in the definition of p ho ne _b oo k. We made a single object of type ph on e_ bo ok v ec to r<E nt ry and supplied its initial size as an initializer. This is very different from declaring a ve ct or En tr y> built-in array:
v ec to r<E nt ry b oo k(1 00 0); ve ct or En tr y> bo ok 10 00 v ec to r<E nt ry b oo ks 10 00 ; ve ct or En tr y> bo ok s[1 00 0] // vector of 1000 elements // 1000 empty vectors

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

Section 3.7.1

Vector

53

If you make the mistake of using [] where you meant () when declaring a v ec to r, your compiler ve ct or will almost certainly catch the mistake and issue an error message when you try to use the v ec to r. ve ct or A v ec to r is a single object that can be assigned. For example: ve ct or
v oi d f ve ct or En tr y>& v vo id f(v ec to r<E nt ry v) { v ec to r<E nt ry v 2 = p ho ne _b oo k; ve ct or En tr y> v2 ph on e_ bo ok v = v 2; v2 // ... }

Assigning a v ec to r involves copying its elements. Thus, after the initialization and assignment in ve ct or f f(), v and v 2 each holds a separate copy of every E nt ry in the phone book. When a v ec to r holds v2 En tr y ve ct or many elements, such innocent-looking assignments and initializations can be prohibitively expensive. Where copying is undesirable, references or pointers should be used. 3.7.2 Range Checking The standard library v ec to r does not provide range checking by default (§16.3.3). For example: ve ct or
v oi d f vo id f() { i nt i = p ho ne _b oo k[1 00 1].n um be r; // 1001 is out of range in t ph on e_ bo ok 10 01 nu mb er // ... }

The initialization is likely to place some random value in i rather than giving an error. This is undesirable, so I will use a simple range-checking adaptation of v ec to r, called V ec in the following ve ct or Ve c, chapters. A V ec is like a v ec to r, except that it throws an exception of type o ut _o f_ ra ng e if a subVe c ve ct or ou t_ of _r an ge script is out of range. Techniques for implementing types such as V ec and for using exceptions effectively are disVe c cussed in §11.12, §8.3, Chapter 14, and Appendix E. However, the definition here is sufficient for the examples in this book:
t em pl at e<c la ss T c la ss V ec : p ub li c v ec to r<T { te mp la te cl as s T> cl as s Ve c pu bl ic ve ct or T> p ub li c: pu bl ic V ec Ve c() : v ec to r<T ve ct or T>() { } V ec in t s : v ec to r<T s) { } Ve c(i nt s) ve ct or T>(s T o pe ra to r[](i nt i { r et ur n a t(i ; } T& op er at or in t i) re tu rn at i) c on st T o pe ra to r[](i nt i c on st { r et ur n a t(i ; } co ns t T& op er at or in t i) co ns t re tu rn at i) }; // range-checked // range-checked

The a t() operation is a v ec to r subscript operation that throws an exception of type o ut _o f_ ra ng e at ve ct or ou t_ of _r an ge if its argument is out of the v ec to r’s range (§16.3.3). If necessary, it is possible to prevent access to ve ct or the v ec to r<T base; see §15.3.2. ve ct or T> Returning to the problem of keeping names and telephone numbers, we can now use a V ec to Ve c ensure that out-of-range accesses are caught. For example:
V ec En tr y> p ho ne _b oo k(1 00 0); Ve c<E nt ry ph on e_ bo ok 10 00

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

54

A Tour of the Standard Library
v oi d p ri nt _e nt ry in t i vo id pr in t_ en tr y(i nt i) // simple use, exactly as for vector { c ou t << p ho ne _b oo k[i na me << ´ ´ << p ho ne _b oo k[i nu mb er << ´\ n´; co ut ph on e_ bo ok i].n am e ph on e_ bo ok i].n um be r \n }

Chapter 3

An out-of-range access will throw an exception that the user can catch. For example:
v oi d f vo id f() { t ry { tr y

f or (i nt i = 0 i 10 00 0; i fo r in t 0; i<1 00 00 i++) p ri nt _e nt ry i); pr in t_ en tr y(i } c at ch (o ut _o f_ ra ng e) { ca tc h ou t_ of _r an ge c ou t << "r an ge e rr or \n co ut ra ng e er ro r\ n"; }

}

The exception will be thrown, and then caught, when p ho ne _b oo k[i is tried with i 10 00 ph on e_ bo ok i] i==1 00 0. If the user doesn’t catch this kind of exception, the program will terminate in a well-defined manner rather than proceeding or failing in an undefined manner. One way to minimize surprises from exceptions is to use a m ai n() with a try-block as its body: ma in
i nt m ai n() in t ma in t ry { tr y // your code } c at ch (o ut _o f_ ra ng e) { ca tc h ou t_ of _r an ge c er r << "r an ge e rr or \n ce rr ra ng e er ro r\ n"; } c at ch (...) { ca tc h c er r << "u nk no wn e xc ep ti on t hr ow n\ n"; ce rr un kn ow n ex ce pt io n th ro wn \n }

This provides default exception handlers so that if we fail to catch some exception, an error message is printed on the standard error-diagnostic output stream c er r (§21.2.1). ce rr 3.7.3 List Insertion and deletion of phone book entries could be common. Therefore, a list could be more appropriate than a vector for representing a simple phone book. For example:
l is t<E nt ry p ho ne _b oo k; li st En tr y> ph on e_ bo ok

When we use a list, we tend not to access elements using subscripting the way we commonly do for vectors. Instead, we might search the list looking for an element with a given value. To do this, we take advantage of the fact that a l is t is a sequence as described in §3.8: li st
v oi d p ri nt _e nt ry co ns t s tr in g& s vo id pr in t_ en tr y(c on st st ri ng s) { t yp ed ef l is t<E nt ry :c on st _i te ra to r L I; ty pe de f li st En tr y>: co ns t_ it er at or LI

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

Section 3.7.3
f or (L I i = p ho ne _b oo k.b eg in ; i != p ho ne _b oo k.e nd ; ++i { fo r LI ph on e_ bo ok be gi n() ph on e_ bo ok en d() i) c on st E nt ry e = *i // reference used as shorthand co ns t En tr y& i; i f (s == e na me { if s e.n am e) c ou t << e na me << ´ ´ << e nu mb er << ´\ n´; co ut e.n am e e.n um be r \n r et ur n; re tu rn } } }

List

55

The search for s starts at the beginning of the list and proceeds until either s is found or the end is reached. Every standard library container provides the functions b eg in and e nd be gi n() en d(), which return an iterator to the first and to one-past-the-last element, respectively (§16.3.2). Given an iterator i i, ++i advances i to refer to the next element. Given an iterator i the element it refers to is *i i i, i. A user need not know the exact type of the iterator for a standard container. That iterator type is part of the definition of the container and can be referred to by name. When we don’t need to modify an element of the container, c on st _i te ra to r is the type we want. Otherwise, we use the plain co ns t_ it er at or i te ra to r type (§16.3.1). it er at or Adding elements to a l is t and removing elements from a l is t is easy: li st li st
v oi d f co ns t E nt ry e l is t<E nt ry :i te ra to r i l is t<E nt ry :i te ra to r p vo id f(c on st En tr y& e, li st En tr y>: it er at or i, li st En tr y>: it er at or p) { p ho ne _b oo k.p us h_ fr on t(e ; ph on e_ bo ok pu sh _f ro nt e) // add at beginning p ho ne _b oo k.p us h_ ba ck e); ph on e_ bo ok pu sh _b ac k(e // add at end p ho ne _b oo k.i ns er t(i e); ph on e_ bo ok in se rt i,e // add before the element referred to by ‘i’ p ho ne _b oo k.e ra se p); ph on e_ bo ok er as e(p } // remove the element referred to by ‘p’

For a more complete description of i ns er t() and e ra se , see §16.3.6. in se rt er as e() 3.7.4 Map Writing code to look up a name in a list of (name,number) pairs is really quite tedious. In addition, a linear search is quite inefficient for all but the shortest lists. Other data structures directly support insertion, deletion, and searching based on values. In particular, the standard library provides the m ap type (§17.4.1). A m ap is a container of pairs of values. For example: ma p ma p
m ap st ri ng in t> p ho ne _b oo k; ma p<s tr in g,i nt ph on e_ bo ok

In other contexts, a m ap is known as an associative array or a dictionary. ma p When indexed by a value of its first type (called the key) a m ap returns the corresponding value ma p of the second type (called the value or the mapped type). For example:
v oi d p ri nt _e nt ry co ns t s tr in g& s vo id pr in t_ en tr y(c on st st ri ng s) { i f (i nt i = p ho ne _b oo k[s c ou t << s << ´ ´ << i << ´\ n´; if in t ph on e_ bo ok s]) co ut \n }

If no match was found for the key s a default value is returned from the p ho ne _b oo k. The default s, ph on e_ bo ok value for an integer type in a m ap is 0 Here, I assume that 0 isn’t a valid telephone number. ma p 0.

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

56

A Tour of the Standard Library

Chapter 3

3.7.5 Standard Containers A m ap a l is t, and a v ec to r can each be used to represent a phone book. However, each has ma p, li st ve ct or strengths and weaknesses. For example, subscripting a v ec to r is cheap and easy. On the other ve ct or hand, inserting an element between two elements tends to be expensive. A l is t has exactly the li st opposite properties. A m ap resembles a l is t of (key,value) pairs except that it is optimized for findma p li st ing values based on keys. The standard library provides some of the most general and useful container types to allow the programmer to select a container that best serves the needs of an application: _________________________________________________________________ ________________________________________________________________ Standard Container Summary _________________________________________________________________ _   v ec to r< T> ve ct or <T > A variable-sized vector (§16.3)   li st <T > A doubly-linked list (§17.2.2)   l is t< T> qu eu e< T> A queue (§17.3.2)   q ue ue <T >   s ta ck <T > st ac k< T> A stack (§17.3.1)   d eq ue <T > de qu e< T> A double-ended queue (§17.2.3)   p ri or it y_ qu eu e< T> pr io ri ty _q ue ue <T > A queue sorted by value (§17.3.3)   se t< T> A set (§17.4.3)   s et <T > mu lt is et <T > A set in which a value can occur many times (§17.4.4)   m ul ti se t< T>   m ap <k ey ,v al > ma p< ke y, va l> An associative array (§17.4.1) ________________________________________________________________ m ul ti ma p< ke y, va l> mu lt im ap <k ey ,v al > A map in which a key can occur many times (§17.4.2)  _  The standard containers are presented in §16.2, §16.3, and Chapter 17. The containers are defined in namespace s td and presented in headers <v ec to r>, <l is t>, <m ap etc. (§16.2). st d ve ct or li st ma p>, The standard containers and their basic operations are designed to be similar from a notational point of view. Furthermore, the meanings of the operations are equivalent for the various containers. In general, basic operations apply to every kind of container. For example, p us h_ ba ck pu sh _b ac k() can be used (reasonably efficiently) to add elements to the end of a v ec to r as well as for a l is t, and ve ct or li st every container has a s iz e() member function that returns its number of elements. si ze This notational and semantic uniformity enables programmers to provide new container types that can be used in a very similar manner to the standard ones. The range-checked vector, V ec Ve c (§3.7.2), is an example of that. Chapter 17 demonstrates how a h as h_ ma p can be added to the ha sh _m ap framework. The uniformity of container interfaces also allows us to specify algorithms independently of individual container types.

3.8 Algorithms
A data structure, such as a list or a vector, is not very useful on its own. To use one, we need operations for basic access such as adding and removing elements. Furthermore, we rarely just store objects in a container. We sort them, print them, extract subsets, remove elements, search for objects, etc. Consequently, the standard library provides the most common algorithms for containers in addition to providing the most common container types. For example, the following sorts a v ec to r and places a copy of each unique v ec to r element on a l is t: ve ct or ve ct or li st

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

Section 3.8

Algorithms

57

v oi d f ve ct or En tr y>& v e, l is t<E nt ry vo id f(v ec to r<E nt ry ve li st En tr y>& l e) le { s or t(v e.b eg in ,v e.e nd so rt ve be gi n() ve en d()); u ni qu e_ co py ve be gi n(),v e.e nd ,l e.b eg in un iq ue _c op y(v e.b eg in ve en d() le be gi n()); }

The standard algorithms are described in Chapter 18. They are expressed in terms of sequences of elements (§2.7.2). A sequence is represented by a pair of iterators specifying the first element and the one-beyond-the-last element. In the example, s or t() sorts the sequence from v e.b eg in so rt ve be gi n() to v e.e nd ve en d() – which just happens to be all the elements of a v ec to r. For writing, you need only to ve ct or specify the first element to be written. If more than one element is written, the elements following that initial element will be overwritten. If we wanted to add the new elements to the end of a container, we could have written:
v oi d f ve ct or En tr y>& v e, l is t<E nt ry vo id f(v ec to r<E nt ry ve li st En tr y>& l e) le { s or t(v e.b eg in ,v e.e nd so rt ve be gi n() ve en d()); u ni qu e_ co py ve be gi n(),v e.e nd ,b ac k_ in se rt er le ; un iq ue _c op y(v e.b eg in ve en d() ba ck _i ns er te r(l e)) }

// append to le

A b ac k_ in se rt er ba ck _i ns er te r() adds elements at the end of a container, extending the container to make room for them (§19.2.4). Thus, the standard containers plus b ac k_ in se rt er ba ck _i ns er te r()s eliminate the need to use error-prone, explicit C-style memory management using r ea ll oc re al lo c() (§16.3.5). Forgetting to use a b ac k_ in se rt er when appending can lead to errors. For example: ba ck _i ns er te r()
v oi d f ve ct or En tr y>& v e, l is t<E nt ry vo id f(v ec to r<E nt ry ve li st En tr y>& l e) le { c op y(v e.b eg in ,v e.e nd ,l e); co py ve be gi n() ve en d() le // error: le not an iterator c op y(v e.b eg in ,v e.e nd ,l e.e nd co py ve be gi n() ve en d() le en d()); // bad: writes beyond the end c op y(v e.b eg in ,v e.e nd ,l e.b eg in co py ve be gi n() ve en d() le be gi n()); // overwrite elements }

3.8.1 Use of Iterators When you first encounter a container, a few iterators referring to useful elements can be obtained; b eg in be gi n() and e nd en d() are the best examples of this. In addition, many algorithms return iterators. For example, the standard algorithm f in d looks for a value in a sequence and returns an iterator to fi nd the element found. Using f in d, we can count the number of occurrences of a character in a s tr in g: fi nd st ri ng
i nt c ou nt co ns t s tr in g& s c ha r c in t co un t(c on st st ri ng s, ch ar c) // count occurrences of c in s { i nt n = 0 in t 0; s tr in g::c on st _i te ra to r i = f in d(s be gi n(),s en d(),c ; st ri ng co ns t_ it er at or fi nd s.b eg in s.e nd c) w hi le (i != s en d()) { wh il e i s.e nd ++n n; i = f in d(i 1,s en d(),c ; fi nd i+1 s.e nd c) } r et ur n n re tu rn n; }

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

58

A Tour of the Standard Library

Chapter 3

The f in d algorithm returns an iterator to the first occurrence of a value in a sequence or the onefi nd past-the-end iterator. Consider what happens for a simple call of c ou nt co un t:
v oi d f vo id f() { s tr in g m = "M ar y h ad a l it tl e l am b"; st ri ng Ma ry ha d li tt le la mb i nt a _c ou nt = c ou nt m,´a ; in t a_ co un t co un t(m a´) }

The first call to f in d() finds the ´a in M ar y. Thus, the iterator points to that character and not to fi nd a´ Ma ry s en d(), so we enter the loop. In the loop, we start the search at i 1; that is, we start one past s.e nd i+1 where we found the ´a We then loop finding the other three ´a a´. a´s. That done, f in d() reaches fi nd the end and returns s en d() so that the condition i s.e nd fails and we exit the loop. s.e nd i!=s en d() That call of c ou nt could be graphically represented like this: co un t()

Ma

r

y

had

a

l

i

t

t

l

e

l

amb

..... . . . . . . .....

The arrows indicate the initial, intermediate, and final values of the iterator i i. Naturally, the f in d algorithm will work equivalently on every standard container. Consefi nd quently, we could generalize the c ou nt function in the same way: co un t()
t em pl at e<c la ss C c la ss T i nt c ou nt co ns t C v T v al te mp la te cl as s C, cl as s T> in t co un t(c on st C& v, va l) { t yp en am e C :c on st _i te ra to r i = f in d(v be gi n(),v en d(),v al ; // "typename"; see §C.13.5 ty pe na me C: co ns t_ it er at or fi nd v.b eg in v.e nd va l) i nt n = 0 in t 0; w hi le (i != v en d()) { wh il e i v.e nd ++n n; ++i // skip past the element we just found i; i = f in d(i v.e nd ,v al ; fi nd i,v en d() va l) } r et ur n n re tu rn n; }

This works, so we can say:
v oi d f li st co mp le x>& l c, v ec to r<s tr in g>& v s, s tr in g s vo id f(l is t<c om pl ex lc ve ct or st ri ng vs st ri ng s) { i nt i 1 = c ou nt lc co mp le x(1 3)); in t i1 co un t(l c,c om pl ex 1,3 i nt i 2 = c ou nt vs Di og en es ; in t i2 co un t(v s,"D io ge ne s") i nt i 3 = c ou nt s,´x ; in t i3 co un t(s x´) }

However, we don’t have to define a c ou nt template. Counting occurrences of an element is so genco un t erally useful that the standard library provides that algorithm. To be fully general, the standard library c ou nt takes a sequence as its argument, rather than a container, so we would say: co un t

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

Section 3.8.1

Use of Iterators

59

v oi d f li st co mp le x>& l c, v ec to r<s tr in g>& v s, s tr in g s vo id f(l is t<c om pl ex lc ve ct or st ri ng vs st ri ng s) { i nt i 1 = c ou nt lc be gi n(),l c.e nd ,c om pl ex 1,3 ; in t i1 co un t(l c.b eg in lc en d() co mp le x(1 3)) i nt i 2 = c ou nt vs be gi n(),v s.e nd ,"D io ge ne s"); in t i2 co un t(v s.b eg in vs en d() Di og en es i nt i 3 = c ou nt s.b eg in ,s en d(),´x ; in t i3 co un t(s be gi n() s.e nd x´) }

The use of a sequence allows us to use c ou nt for a built-in array and also to count parts of a conco un t tainer. For example:
v oi d g ch ar c s[], i nt s z) vo id g(c ha r cs in t sz { i nt i 1 = c ou nt cs 0],&c s[s z],´z ; in t i1 co un t(&c s[0 cs sz z´) i nt i 2 = c ou nt cs 0],&c s[s z/2 ,´z ; in t i2 co un t(&c s[0 cs sz 2] z´) }

// ’z’s in array // ’z’s in first half of array

3.8.2 Iterator Types What are iterators really? Any particular iterator is an object of some type. There are, however, many different iterator types because an iterator needs to hold the information necessary for doing its job for a particular container type. These iterator types can be as different as the containers and the specialized needs they serve. For example, a v ec to r’s iterator is most likely an ordinary pointer ve ct or because a pointer is quite a reasonable way of referring to an element of a v ec to r: ve ct or iterator: p

vector:

P

i

e

t

He

i

n

Alternatively, a v ec to r iterator could be implemented as a pointer to the v ec to r plus an index: ve ct or ve ct or iterator: (start == p, position == 3)
.............

vector:

P

i

e

t

He

i

n

Using such an iterator would allow range checking (§19.3). A list iterator must be something more complicated than a simple pointer to an element because an element of a list in general does not know where the next element of that list is. Thus, a list iterator might be a pointer to a link:

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

60

A Tour of the Standard Library

Chapter 3

iterator:

p

list:

link

link

link

link

...

elements:

P

i

e

t

What is common for all iterators is their semantics and the naming of their operations. For example, applying ++ to any iterator yields an iterator that refers to the next element. Similarly, * yields the element to which the iterator refers. In fact, any object that obeys a few simple rules like these is an iterator (§19.2.1). Furthermore, users rarely need to know the type of a specific iterator; each container ‘‘knows’’ its iterator types and makes them available under the conventional names i te ra it er at or and c on st _i te ra to r. For example, l is t<E nt ry :i te ra to r is the general iterator type for to r co ns t_ it er at or li st En tr y>: it er at or l is t<E nt ry I rarely have to worry about the details of how that type is defined. li st En tr y>. 3.8.3 Iterators and I/O Iterators are a general and useful concept for dealing with sequences of elements in containers. However, containers are not the only place where we find sequences of elements. For example, an input stream produces a sequence of values and we write a sequence of values to an output stream. Consequently, the notion of iterators can be usefully applied to input and output. To make an o st re am _i te ra to r, we need to specify which stream will be used and the type of os tr ea m_ it er at or objects written to it. For example, we can define an iterator that refers to the standard output stream, c ou t: co ut
o st re am _i te ra to r<s tr in g> o o(c ou t); os tr ea m_ it er at or st ri ng oo co ut

The effect of assigning to *o o is to write the assigned value to c ou t. For example: oo co ut
i nt m ai n() in t ma in { *o o = "H el lo "; oo He ll o, ++o o; oo *o o = "w or ld \n oo wo rl d!\ n"; }

// meaning cout << "Hello, " // meaning cout << "world!\n"

This is yet another way of writing the canonical message to standard output. The ++o o is done to oo mimic writing into an array through a pointer. This way wouldn’t be my first choice for that simple task, but the utility of treating output as a write-only container will soon be obvious – if it isn’t already. Similarly, an i st re am _i te ra to r is something that allows us to treat an input stream as a readis tr ea m_ it er at or only container. Again, we must specify the stream to be used and the type of values expected:
i st re am _i te ra to r<s tr in g> i i(c in ; is tr ea m_ it er at or st ri ng ii ci n)

Because input iterators invariably appear in pairs representing a sequence, we must provide an

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

Section 3.8.3

Iterators and I/O

61

i st re am _i te ra to r to indicate the end of input. This is the default i st re am _i te ra to r: is tr ea m_ it er at or is tr ea m_ it er at or
i st re am _i te ra to r<s tr in g> e os is tr ea m_ it er at or st ri ng eo s;

We could now read H el lo w or ld from input and write it out again like this: He ll o, wo rl d!
i nt m ai n() in t ma in { s tr in g s 1 = *i i; st ri ng s1 ii ++i i; ii s tr in g s 2 = *i i; st ri ng s2 ii c ou t << s 1 << ´ ´ << s 2 << ´\ n´; co ut s1 s2 \n }

Actually, i st re am _i te ra to rs and o st re am _i te ra to rs are not meant to be used directly. Instead, they is tr ea m_ it er at or os tr ea m_ it er at or are typically provided as arguments to algorithms. For example, we can write a simple program to read a file, sort the words read, eliminate duplicates, and write the result to another file:
i nt m ai n() in t ma in { s tr in g f ro m, t o; st ri ng fr om to c in >> f ro m >> t o; ci n fr om to i fs tr ea m i s(f ro m.c _s tr if st re am is fr om c_ st r()); i st re am _i te ra to r<s tr in g> i i(i s); is tr ea m_ it er at or st ri ng ii is i st re am _i te ra to r<s tr in g> e os is tr ea m_ it er at or st ri ng eo s; v ec to r<s tr in g> b ii eo s); ve ct or st ri ng b(i i,e os s or t(b be gi n(),b en d()); so rt b.b eg in b.e nd o fs tr ea m o s(t o.c _s tr of st re am os to c_ st r()); o st re am _i te ra to r<s tr in g> o o(o s,"\ n"); os tr ea m_ it er at or st ri ng oo os \n u ni qu e_ co py b.b eg in ,b en d(),o o); un iq ue _c op y(b be gi n() b.e nd oo r et ur n !i s.e of re tu rn is eo f() || !o s; os }

// get source and target file names // input stream (c_str(); see §3.5.1 and §20.3.7) // input iterator for stream // input sentinel // b is a vector initialized from input // sort the buffer // output stream // output iterator for stream // copy buffer to output, // discard replicated values // return error state (§3.2, §21.3.3)

An i fs tr ea m is an i st re am that can be attached to a file, and an o fs tr ea m is an o st re am that can be if st re am is tr ea m of st re am os tr ea m attached to a file. The o st re am _i te ra to r’s second argument is used to delimit output values. os tr ea m_ it er at or 3.8.4 Traversals and Predicates Iterators allow us to write loops to iterate through a sequence. However, writing loops can be tedious, so the standard library provides ways for a function to be called for each element of a sequence. Consider writing a program that reads words from input and records the frequency of their occurrence. The obvious representation of the strings and their associated frequencies is a m ap ma p:
m ap st ri ng in t> h is to gr am ma p<s tr in g,i nt hi st og ra m;

The obvious action to be taken for each string to record its frequency is:

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

62

A Tour of the Standard Library

Chapter 3

v oi d r ec or d(c on st s tr in g& s vo id re co rd co ns t st ri ng s) { h is to gr am s]++; hi st og ra m[s // record frequency of ‘‘s’’ }

Once the input has been read, we would like to output the data we have gathered. The m ap consists ma p of a sequence of (string,int) pairs. Consequently, we would like to call
v oi d p ri nt co ns t p ai r<c on st s tr in g,i nt vo id pr in t(c on st pa ir co ns t st ri ng in t>& r r) { c ou t << r fi rs t << ´ ´ << r se co nd << ´\ n´; co ut r.f ir st r.s ec on d \n }

for each element in the map (the first element of a p ai r is called f ir st and the second element is pa ir fi rs t, called s ec on d). The first element of the p ai r is a c on st s tr in g rather than a plain s tr in g because all se co nd pa ir co ns t st ri ng st ri ng m ap keys are constants. ma p Thus, the main program becomes:
i nt m ai n() in t ma in { i st re am _i te ra to r<s tr in g> i i(c in ; is tr ea m_ it er at or st ri ng ii ci n) i st re am _i te ra to r<s tr in g> e os is tr ea m_ it er at or st ri ng eo s; f or _e ac h(i i,e os re co rd ; fo r_ ea ch ii eo s,r ec or d) f or _e ac h(h is to gr am be gi n(),h is to gr am en d(),p ri nt ; fo r_ ea ch hi st og ra m.b eg in hi st og ra m.e nd pr in t) }

Note that we don’t need to sort the m ap to get the output in order. A m ap keeps its elements ma p ma p ordered so that an iteration traverses the m ap in (increasing) order. ma p Many programming tasks involve looking for something in a container rather than simply doing something to every element. For example, the f in d algorithm (§18.5.2) provides a convenient way fi nd of looking for a specific value. A more general variant of this idea looks for an element that fulfills a specific requirement. For example, we might want to search a m ap for the first value larger than ma p 4 2. A m ap allows us to access its elements as a sequence of (key,value) pairs, so we can search a 42 ma p m ap st ri ng in t>’s sequence for a p ai r<c on st s tr in g,i nt where the i nt is greater than 4 2: ma p<s tr in g,i nt pa ir co ns t st ri ng in t> in t 42
b oo l g t_ 42 co ns t p ai r<c on st s tr in g,i nt bo ol gt _4 2(c on st pa ir co ns t st ri ng in t>& r r) { r et ur n r se co nd 42 re tu rn r.s ec on d>4 2; } v oi d f ma p<s tr in g,i nt m vo id f(m ap st ri ng in t>& m) { t yp ed ef m ap st ri ng in t>::c on st _i te ra to r M I; ty pe de f ma p<s tr in g,i nt co ns t_ it er at or MI M I i = f in d_ if m.b eg in ,m en d(),g t_ 42 ; MI fi nd _i f(m be gi n() m.e nd gt _4 2) // ... }

Alternatively, we could count the number of words with a frequency higher than 42:

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

Section 3.8.4

Traversals and Predicates

63

v oi d g co ns t m ap st ri ng in t>& m vo id g(c on st ma p<s tr in g,i nt m) { i nt c 42 = c ou nt _i f(m be gi n(),m en d(),g t_ 42 ; in t c4 2 co un t_ if m.b eg in m.e nd gt _4 2) // ... }

A function, such as g t_ 42 gt _4 2(), that is used to control the algorithm is called a predicate. A predicate is called for each element and returns a Boolean value, which the algorithm uses to perform its intended action. For example, f in d_ if fi nd _i f() searches until its predicate returns t ru e to indicate that an tr ue element of interest has been found. Similarly, c ou nt _i f() counts the number of times its predicate co un t_ if is t ru e. tr ue The standard library provides a few useful predicates and some templates that are useful for creating more (§18.4.2). 3.8.5 Algorithms Using Member Functions Many algorithms apply a function to elements of a sequence. For example, in §3.8.4
f or _e ac h(i i,e os re co rd ; fo r_ ea ch ii eo s,r ec or d)

calls r ec or d() for each string read from input. re co rd Often, we deal with containers of pointers and we really would like to call a member function of the object pointed to, rather than a global function on the pointer. For example, we might want to call the member function S ha pe :d ra w() for each element of a l is t<S ha pe Sh ap e: dr aw li st Sh ap e*>. To handle this specific example, we simply write a nonmember function that invokes the member function. For example:
v oi d d ra w(S ha pe p vo id dr aw Sh ap e* p) { p dr aw ; p->d ra w() } v oi d f li st Sh ap e*>& s h) vo id f(l is t<S ha pe sh { f or _e ac h(s h.b eg in ,s h.e nd ,d ra w); fo r_ ea ch sh be gi n() sh en d() dr aw }

By generalizing this technique, we can write the example like this:
v oi d g li st Sh ap e*>& s h) vo id g(l is t<S ha pe sh { f or _e ac h(s h.b eg in ,s h.e nd ,m em _f un Sh ap e::d ra w)); fo r_ ea ch sh be gi n() sh en d() me m_ fu n(&S ha pe dr aw }

The standard library m em _f un template (§18.4.4.2) takes a pointer to a member function (§15.5) me m_ fu n() as its argument and produces something that can be called for a pointer to the member’s class. The result of m em _f un Sh ap e::d ra w) takes a S ha pe me m_ fu n(&S ha pe dr aw Sh ap e* argument and returns whatever S ha pe :d ra w() returns. Sh ap e: dr aw The m em _f un me m_ fu n() mechanism is important because it allows the standard algorithms to be used for containers of polymorphic objects.

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

64

A Tour of the Standard Library

Chapter 3

3.8.6 Standard Library Algorithms What is an algorithm? A general definition of an algorithm is ‘‘a finite set of rules which gives a sequence of operations for solving a specific set of problems [and] has five important features: Finiteness ... Definiteness ... Input ... Output ... Effectiveness’’ [Knuth,1968,§1.1]. In the context of the C++ standard library, an algorithm is a set of templates operating on sequences of elements. The standard library provides dozens of algorithms. The algorithms are defined in namespace s td and presented in the <a lg or it hm header. Here are a few I have found particularly useful: st d al go ri th m> _ _____________________________________________________________________  Selected Standard Algorithms _ _____________________________________________________________________ _ _____________________________________________________________________  f or _e ac h( )  fo r_ ea ch () Invoke function for each element (§18.5.1)   fi nd () Find first occurrence of arguments (§18.5.2)  f in d( )  fi nd _i f( ) Find first match of predicate (§18.5.2)  f in d_ if ()   c ou nt ()  co un t( ) Count occurrences of element (§18.5.3)  c ou nt _i f( )  co un t_ if () Count matches of predicate (§18.5.3)  r ep la ce ()  re pl ac e( ) Replace element with new value (§18.6.4)   re pl ac e_ if () Replace element that matches predicate with new value (§18.6.4)   r ep la ce _i f( ) co py () Copy elements (§18.6.1)  c op y( )   u ni qu e_ co py ()  un iq ue _c op y( ) Copy elements that are not duplicates (§18.6.1)  s or t( )  so rt () Sort elements (§18.7.1)  e qu al _r an ge ()  eq ua l_ ra ng e( ) Find all elements with equivalent values (§18.7.2)   Merge sorted sequences (§18.7.3) _me rg e( ) _____________________________________________________________________  m er ge () These algorithms, and many more (see Chapter 18), can be applied to elements of containers, s tr in gs, and built-in arrays. st ri ng

3.9 Math
Like C, C++ wasn’t designed primarily with numerical computation in mind. However, a lot of numerical work is done in C++, and the standard library reflects that. 3.9.1 Complex Numbers The standard library supports a family of complex number types along the lines of the c om pl ex co mp le x class described in §2.5.2. To support complex numbers where the scalars are single-precision, floating-point numbers (f lo at double precision numbers (d ou bl es), etc., the standard library c om fl oa ts), do ub le co mp le x is a template: pl ex
t em pl at e<c la ss s ca la r> c la ss c om pl ex { te mp la te cl as s sc al ar cl as s co mp le x p ub li c: pu bl ic c om pl ex sc al ar r e, s ca la r i m); co mp le x(s ca la r re sc al ar im // ... };

The usual arithmetic operations and the most common mathematical functions are supported for complex numbers. For example:

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

Section 3.9.1

Complex Numbers

65

// standard exponentiation function from <complex>: t em pl at e<c la ss C c om pl ex C> p ow co ns t c om pl ex C>&, i nt ; te mp la te cl as s C> co mp le x<C po w(c on st co mp le x<C in t) v oi d f co mp le x<f lo at f l, c om pl ex do ub le d b) vo id f(c om pl ex fl oa t> fl co mp le x<d ou bl e> db { c om pl ex lo ng d ou bl e> l d = f l+s qr t(d b); co mp le x<l on g do ub le ld fl sq rt db d b += f l*3 db fl 3; f l = p ow 1/f l,2 ; fl po w(1 fl 2) // ... }

For more details, see §22.5. 3.9.2 Vector Arithmetic The v ec to r described in §3.7.1 was designed to be a general mechanism for holding values, to be ve ct or flexible, and to fit into the architecture of containers, iterators, and algorithms. However, it does not support mathematical vector operations. Adding such operations to v ec to r would be easy, but ve ct or its generality and flexibility precludes optimizations that are often considered essential for serious numerical work. Consequently, the standard library provides a vector, called v al ar ra y, that is less va la rr ay general and more amenable to optimization for numerical computation:
t em pl at e<c la ss T c la ss v al ar ra y { te mp la te cl as s T> cl as s va la rr ay // ... T o pe ra to r[](s iz e_ t); T& op er at or si ze _t // ... };

The type s iz e_ t is the unsigned integer type that the implementation uses for array indices. si ze _t The usual arithmetic operations and the most common mathematical functions are supported for v al ar ra ys. For example: va la rr ay
// standard absolute value function from <valarray>: t em pl at e<c la ss T v al ar ra y<T a bs co ns t v al ar ra y<T te mp la te cl as s T> va la rr ay T> ab s(c on st va la rr ay T>&); v oi d f va la rr ay do ub le vo id f(v al ar ra y<d ou bl e>& a 1, v al ar ra y<d ou bl e>& a 2) a1 va la rr ay do ub le a2 { v al ar ra y<d ou bl e> a = a 1*3 14 a2 a1 va la rr ay do ub le a1 3.1 4+a 2/a 1; a 2 += a 1*3 14 a2 a1 3.1 4; a = a bs a); ab s(a d ou bl e d = a 2[7 ; do ub le a2 7] // ... }

For more details, see §22.4. 3.9.3 Basic Numeric Support Naturally, the standard library contains the most common mathematical functions – such as l og lo g(), p ow po w(), and c os – for floating-point types; see §22.3. In addition, classes that describe the propco s() erties of built-in types – such as the maximum exponent of a f lo at – are provided; see §22.2. fl oa t

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.

66

A Tour of the Standard Library

Chapter 3

3.10 Standard Library Facilities
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 information); see §16.1.3. [2] The C standard library (with very minor modifications to minimize violations of the type system); see §16.1.2. [3] Strings and I/O streams (with support for international character sets and localization); see Chapter 20 and Chapter 21. [4] A framework of containers (such as v ec to r, l is t, and m ap and algorithms using containers ve ct or li st ma p) (such as general traversals, sorts, and merges); see Chapter 16, Chapter 17, Chapter 18, and Chapter 19. [5] Support for numerical computation (complex numbers plus vectors with arithmetic operations, BLAS-like and generalized slices, and semantics designed to ease optimization); see Chapter 22. 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. Essentially, the C++ standard library provides the most common fundamental data structures together with the fundamental algorithms used on them. Every algorithm works with every container without the use of conversions. This framework, conventionally called the STL [Stepanov,1994], is extensible in the sense that users can easily provide containers and algorithms in addition to the ones provided as part of the standard and have these work directly with the standard containers and algorithms.

3.11 Advice
[1] Don’t reinvent the wheel; use libraries. [2] Don’t believe in magic; understand what your libraries do, how they do it, and at what cost they do it. [3] When you have a choice, prefer the standard library to other libraries. [4] Do not think that the standard library is ideal for everything. [5] Remember to #i nc lu de the headers for the facilities you use; §3.3. in cl ud e [6] Remember that standard library facilities are defined in namespace s td §3.3. st d; [7] Use s tr in g rather than c ha r*; §3.5, §3.6. st ri ng ch ar [8] If in doubt use a range-checked vector (such as V ec §3.7.2. Ve c); [9] Prefer v ec to r<T l is t<T and m ap ke y,v al ue to T ve ct or T>, li st T>, ma p<k ey va lu e> T[]; §3.7.1, §3.7.3, §3.7.4. [10] When adding elements to a container, use p us h_ ba ck or b ac k_ in se rt er pu sh _b ac k() ba ck _i ns er te r(); §3.7.3, §3.8. [11] Use p us h_ ba ck on a v ec to r rather than r ea ll oc on an array; §3.8. pu sh _b ac k() ve ct or re al lo c() [12] Catch common exceptions in m ai n(); §3.7.2. ma in

The C++ Programming Language, Special Edition by Bjarne Stroustrup. Copyright ©2000 by AT&T. Published by Addison Wesley, Inc. ISBN 0-201-70073-5. All rights reserved.