C++ For Mathematicians (2006) [eng]

126	C++ for Mathematicians

(d)An operator< for lexicographic sorting of the intervals. That is, [a,b] < [c,d] provided a < c or (a = c and b < d).

(e)An operator<< for output to the screen.

7.2In Exercise 7.1 you created an Interval class. Use that class to investigate the following problem. Let I1,I2,...,In be a collection of random intervals. What is the probability that one of these intervals intersects all of the others?

By random interval we mean an interval whose end points are chosen independently and uniformly from [0,1] (with the understanding that [a,b] = [b,a]).

Write a program that generates n random intervals and then checks to see if one of those intervals meets all of the others. It should repeat this experiment many times and report the frequency with which it meets success.

7.3Write a procedure that finds the median in a list of real numbers. Declare the procedure as

double median(const double* array, long nels);

where array is the list of values and nels is the number of elements in the array.

Warning: Your procedure should not modify the list (hence the use of the keyword const), but should use its values to find the median. Still, a good way to find the middle element(s) is to work with a sorted array. If you wish to use the C++ sort procedure, include these lines in your code:

#include <algorithm> using namespace std;

Note: If the length of the list is even, there is no single middle value, but rather two “middle” values. In this case, take the median to be the average of those two middle values.

7.4Write a program to count the number of primitive Pythagorean triples in which

(a) one of the legs has length k and (b) in which the hypotenuse has length k, for all k with 1 ≤ k ≤ 100.

Chapter 8

Containers

In this chapter we explore a variety of container classes available in C++. The C++ arrays provide little functionality and can be difficult to use. It is easy to make mistakes using arrays: the arrays might not be big enough to hold the data, we might access elements beyond the end of the array, there is no convenient way to enlarge an array after it has been created, and it is easy to forget a delete[] statement for an array that has been dynamically allocated.

In lieu of holding values in arrays, C++ provides the means to create arraylike structures that can change size on demand, unordered collections (sets and multisets), and other useful containers (stacks, queues, double-ended queues, and simple lists). These containers are easy to use.

8.1 Sets

In Chapter 7 we generated primitive Pythagorean triples and collected our results in an array. We then needed to process the array to remove duplicates. Alternatively, with each new triple generated, we could have scanned the array to see if the new triple was already recorded. This, however, increases the processing time and does not solve the problem that we do not know in advance how large to make the array.

The C++ set class behaves much as a finite mathematical set. In a C++ set, all the elements of the set must be the same type. That is, the elements of the set may be all longs or all PTriples; the set cannot contain a mixture of types.

To use sets in your program, you need to include the set header file with the directive #include <set>.

To declare a set one needs to specify the type of element stored in the set. This is done using the syntax set<type> set_name;. For example, to declare a set of integers, use the following statement,

set<long> S;

The variable S is now a set that can hold long integer elements. Any C++ type (either innate or a class you define) can be held in a set with only one proviso: The type must have < and == operators defined.

There are fundamental operations we need to be able to perform on sets such as adding an element to a set, deleting an element from the set, and so on. Here are the

127

128	C++ for Mathematicians

important methods you need to know to use C++ sets. In each case, S and T stand for sets of elements of some type, and e stands for variable of that type. (For example, S and T are sets of longs and e is a long.)

Add an element Use the statement S.insert(e);. This causes a copy of e to be inserted into the set unless, of course, the set already contains this value.

Delete an element Use the statement S.erase(e);. If the set contains the value held by e, that value is removed from the set. If the value is not in the set, nothing changes.

Delete all elements in a set Use the statement S.clear();.

Is an element in the set? Use the method S.count(e). This returns the number of times that e’s value appears in the set. This is either 0 or 1.

How many elements are in this set? The method S.size() returns the cardinality1 of S.

Is a set empty? The method S.empty() returns a bool value: true when S is empty and false otherwise.

Check if two sets are the same The operators == and != work as expected. The expression S==T returns true if S and T contain the same elements.

Copy one set to another The statement S = T; overwrites S with a copy of T.

There are other fundamental operations that one would like to perform on sets including finding the smallest (or largest) element in a set, printing all the elements in a set, and so on. The C++ set type can handle these tasks, but they are more complicated. Before we explain how to do these, we return to Pythagorean triples.

We employ a strategy that is similar to the one we used in Program 7.2. We ask the

√

user to input N. We then generate all pairs of integers (m,n) with 1 ≤ m,n ≤ N. We use these to generate primitive Pythagorean triples. We examine each triple to see if c ≤ N; if so, we add it to a set S. In the end, we print all the elements of the set. The difficult part of the program is printing the set! Here is the code; the explanation follows.

1The container classes in the Standard Template Library have size() methods that report the number of elements held in the container. The value returned by size() method has type size t which is often an unsigned value. Consequently, if you compare the return value from size() to, say, a long integer value, the compiler may issue a warning or an error. To fix this problem, you may need to convert the result of the size() method to a long value. Fortunately, this is simple. Replace X.size() with long(X.size()) and all should be well.

Containers	129

Program 8.1: A program to find Pythagorean triples using sets.

1#include "PTriple.h"

2#include <set>

3
4	int main() {
5	set<PTriple> S;	// Set to hold the PTriples we find
6

7// Ask the user for N

8cout << "Please enter N (upper bound on triples) --> ";

9long N;

10cin >> N;

11if (N <= 0) return 0; // Nothing to do when N isn’t positive

12

13// We only need to run the constructor arguments up to the square

14// root of N.

15long rootN = long (sqrt(double(N)) );

16

17// Run through possibilities and if appropriate, add to the set S.

18for (int k=1; k<=rootN; k++) {

19for (int j=1; j<=rootN; j++) {

20PTriple P(j,k);

21if (P.getC() <= N)

22S.insert(P);

23}

24}

25
26	// Print out the elements of the set
27	set<PTriple>::iterator si;	// Iterator for S

28for (si = S.begin(); si != S.end() ; si++) {

29cout << *si << endl;

30}

31

32return 0;

33}

We begin by declaring a set S (line 5) whose job is to hold the triples we find.

√

Lines 8–11 ask the user for N and line 15 calculates N .

Lines 18–24 step through all values of m,n and use these to generate primitive Pythagorean triples. If the triple’s hypotenuse is no greater than N (line 21) then we add it to the set (line 22).

The last part of the program (lines 27–30) prints the set S to the computer’s screen. To do this, we need an object called an iterator (explained next).

At the end of the program, we do not need to delete the set S. The set is designed to release the memory it consumes when the procedure in which it was declared terminates.

130	C++ for Mathematicians

8.2 Set iterators

To access the 8th element of an array a is easy; we just type a[7]. (Remember that the first element of the array is a[0].) However, there is no method to access the 8th element of a set. When programmers built the C++ set class, they chose a design that would make the insertion, deletion, and element-query operations as efficient as possible. These requirements are incompatible with rapid access to the nth element for arbitrary n.

Nonetheless, it is necessary for users to be able to access the elements held in a set. To do so, they can fetch the elements sequentially using an object called an iterator.

A set iterator is an object that refers to elements of a set. The iterator specifies a “current” element of the set. There are three important operations set iterators can perform:

(a)They can report the value at the “current” location,

(b)They can advance to the next element in the set, and

(c)They can step back to the previous element of the set.

An iterator for a set is declared with a statement like this:

set<long>::iterator si;

This declares si to be an iterator for sets that contain long integers. The declaration does not give si any particular value; it is not ready to report on elements of a set.

C++ set objects include a method named begin(). This method returns an iterator to the first (i.e., smallest) element of the set. So, if S is a set of long integers, we can initialize si with a statement like this:

si = S.begin();

Note that si is not a long integer; it is an iterator. Hence a statement of the form cout << si does not print the smallest element of the set. To access the value that the iterator considers to be current, we use this syntax: *si. (The * operator is designed specifically to mimic the dereferencing notation used by pointers.) Therefore, the following code does what it says.

set<long> S; set<long>::iterator si;

....

if (!S.empty()) { si = S.begin();

cout << "The smallest element in S is " << *si << endl;

}

else {

cout << "The set S is empty" << endl;

}

Containers

131

We push an iterator forward and backward using the increment ++ and decrement -- operators, respectively. That is, the statement si++ (or ++si) advances the iterator to the next element of a set and si-- (or --si) moves the operator back one step.

We need to take care that we don’t run past the end of the set or rewind before its beginning. The set class provides the methods begin() and end() for this purpose.

As we mentioned, S.begin() returns an iterator for the first element of a set, S. Unfortunately, S.end() does not return an iterator to the last element of the set! Instead, it returns an iterator one step past the end. (This design is consistent with the idea that if an array a contains n elements, then a[n] is one step past the end of the array.) If the set S is empty, S.begin() and S.end() give identical results.

(In addition to begin and end, there is a pair of reverse iterators named rbegin and rend. Invoking S.rbegin() returns an iterator to the last element of the set and S.rend() returns an iterator to a position one step before the first element. These are useful if we want to step through the elements of a set from largest to smallest.)

It is possible to compare iterators with the operators == and !=.

With these ideas in place, here is how to print all the elements of a set to the computer’s screen.

set<long> S; set<long>::iterator si;

....

for (si = S.begin(); si != S.end(); si++) { cout << *si << " ";

}

cout << endl;

This code prints the elements of S on a single line with spaces separating the elements.

Suppose we wish to sum the elements of S. Here is how we can do it.

long sum = 0;

for (si = S.begin(); si != S.end(); si++) { sum += *si;

}

You may not use set iterators to change a value in a set. The expression *si may not appear to the left of an = sign (assignment operator).

Please refer to lines 27–30 of Program 8.1. There we declare an iterator si for sets of Pythagorean triples. We then use it to print (one per line) all the elements of the set S.

Here is how to use iterators to create procedures to check if one set is a subset of another and to compute the union and intersection of sets.2

2The code given here compiles and runs as expected when using the g++ compiler, but not with Microsoft Visual Studio. Here’s why and how to fix the problem.

Explanation: Some iterators are capable of modifying the containers to which they refer (not set, but

132	C++ for Mathematicians

bool subset(const set<long>& A, const set<long>& B) { if (A.empty()) return true;

set<long>::iterator si;

for (si=A.begin(); si!=A.end(); si++) { if (B.count(*si) == 0) return false;

}

return true;

}

void Union(const set<long>& A, const set<long>& B, set<long>& C) { C = A;

set<long>::iterator si;

for (si = B.begin(); si != B.end(); si++) { C.insert(*si);

}

}

void Intersection(const set<long>& A, const set<long>&B, set<long>& C){ C.clear();

set<long>::iterator si;

for (si = A.begin(); si != A.end(); si++) { if (B.count(*si)>0) {

C.insert(*si);

}

}

}

The first procedure checks if A B. The next two procedures set C equal to A B and A ∩ B, respectively.

In all three procedures arguments A and B are declared const set<long>&. This means that A and B are sets of long integers and are passed by reference. Call by reference is important in this instance. The sets might contain tens of thousands of elements. If we used call by value (i.e., if we omitted the &), then the set would be copied and this takes time. By passing a reference, the procedure receives its data instantaneously. The const keyword is an assurance that the code that follows does not alter the sets A or B.

Argument C in the second and third procedures holds the result of the computation. In order for the procedures to modify argument C it must be a reference variable (hence the & is required).

The union and intersection procedures do not return a result; they are both type void. It might be tempting to declare the union procedure like this:

others such as vector and list discussed later in this chapter). If an argument to a procedure is a container and declared to be a const reference, then using an iterator referring to that container could violate the const guarantee (because the iterator might modify the object). The g++ compiler allows us to use set iterators for const objects as there is no danger that the set can be modified through the use of the iterator. Visual Studio, however, takes a stricter approach. It does not allow us to use an iterator that refers to a const container. The solution is use a restricted form of an iterator called a const iterator; we discuss these on pages 145–147.

Solution: To make this code usable in the stricter context of Visual Studio, change all instances of iterator to const iterator.

Containers

133

set<long> Union(const set<long>& A, const set<long>& B);

Inside the procedure, we could build the union in a set named C and conclude with return C;.

Such a procedure would work, but it would be inefficient. The problem is that the return variable would be copied to the calling procedure.

We named the union procedure with a capital letter: Union. Why not name this simply union? The problem we are avoiding is that union is a C++ keyword (not one that is of interest to mathematicians). We cannot name a procedure union, just as we cannot name a procedure if or for. (See Section 15.5.3 if you are curious.)

These procedures work perfectly for sets of long integers, but cannot be used for sets of double numbers. In C++ there is a mechanism to create a procedure schema (called a template) so that one procedure can be used with arguments of many different types. This is explained later (in Chapter 12).

It is possible to initialize an iterator with methods other than begin and end. Another useful method is find. If A is a set and e is an element, then A.find(e) returns an iterator for A that is focused on e. However, if e is not in A, then A.find(e) signals its inability to find e in the set by returning A.end(), that is, an iterator that is one step beyond the end of the set.

8.3 Multisets

The directive #include <set> also provides the multiset type. A multiset may contain an element repeatedly. For a set, the count method returns only 0 or 1; for multisets, it returns the multiplicity of the element, and this may be any nonnegative integer.

A multiset iterator is declared in the expected way:

multiset<type>::iterator mi;

If an element appears several times in a set, *mi gives that value repeatedly as mi is increased. Here is an example.

Program 8.2: A program to demonstrate the use of multiset.

1#include <iostream>

2#include <set>

3using namespace std;

4

5int main() {

6multiset<long> A;

7
8	for (int k=1;	k<=5; k++) A.insert(k); //	A <- {1,2,3,4,5}
9	A.insert(3);	// we put an extra 3 into A
10

	134	C++ for Mathematicians
11	cout << "The size of A is " << A.size() << endl;
12
13	// print the set
14	multiset<long>::iterator ai;
15	cout << "The elements of A are: ";
16	for (ai = A.begin(); ai != A.end(); ai++) {
17	cout << *ai << " ";
18	}
19	cout << endl;
20	return 0;
21	}

	The output from this program is this:
	The size of A is 6
	The elements of A are: 1 2 3 3 4 5

8.4 Adjustable arrays via the vector class

Arrays in C++ can be created in two ways. First, we can specify in our program how large the array should be:

long primes[100];

Every time the program is run, the array primes has the same size. Alternatively, the array can be created while the program is running with a size that is determined at that time:

long *primes; long n;

...

primes = new long[n];

...

delete[] primes;

Although this allows the size of an array to be set by the program while it is running, it does not provide all the functionality we might like. For example, if while the program is running we discover that the array is too small, there is no simple way to increase its size. Alternatively, once the array is populated with values, we may discover that we have overestimated its size. There is no simple way to shrink the array down to just the size we need (and thereby release the extra memory). Finally, dynamically allocated arrays should be released with a delete[] statement when they are no longer needed. However, it is easy to forget to do this. For example, a procedure might look like this:

void procedure() { long *list;

...

list = new long[n];

Containers

135

...

if (something_bad) {

cout << "Trouble happens" << endl; return;

}

...

cout << "All’s well that ends well" << endl; delete[] list;

}

If something_bad evaluates to true the procedure ends early. In that case, the procedure never reaches the delete[] statement and the memory allocated to list is never released. We have a memory leak. When an array is passed to another procedure, the procedure that receives the array cannot determine the number of elements the array contains; that information would need to be passed as a separate argument.

C++ provides a remedy to the many woes that plague ordinary arrays: “smart” arrays are called vectors. A vector holds elements of a given type in a list. The elements of the vector are accessed exactly as elements in an array. Before declaring any vector variables, the directive #include <vector> is required. Then, to create a vector of, say, long integers, we can use one of the following,

vector<long> alpha;

vector<long> beta(100); // round parentheses, not square brackets!

The first creates a vector of longs of size zero and the latter creates a vector of longs that (initially) can hold 100 values.

To learn the size of an array, use the size method: for example, beta.size() returns 100 (based on the declaration above).

Because beta has size 100, its 100 elements can be accessed just as an array is: from beta[0] to beta[99]. It is an error to access beta[100] because that would be beyond the capacity of the vector. Unfortunately, this error may happen silently because vectors do not check if the index they are given is in the proper range.3

If the array we declared is not large enough, we can ask it to grow using the resize method.

vector<long> beta(100); beta[99] = 23; beta.resize(110);

beta[100] = -4; // OK; we have space up to beta[109]

The amount of memory a vector uses is not always its size. Often, when a vector is resized, it grabs more memory than you requested. The resizing operation is time consuming if the vector does not have spare capacity. For example, suppose

3The vector class provides a method named at() that may be used in place of the square brackets notation; that is, we can write vec.at(k) in place of vec[k]. The at() procedure checks that its argument is within range. If the index is illegal, then at() signals the error by throwing an exception; this is a concept discussed in Section 15.3.