C++ For Mathematicians (2006) [eng]

146	C++ for Mathematicians

Program 8.6: A program to demonstrate the use of lists.

1#include <iostream>

2#include <list>

3using namespace std;

4

5/// A procedure to print a list to cout

6void print_list(const list<long>& L) {

7list<long>::const_iterator Li;

8for (Li = L.begin(); Li != L.end(); Li++) {

9cout << *Li << " ";

10}

11cout << endl;

12}

13

14/// Check if an integer is even (to illustrate remove_if)

15bool is_even(long n) {

16return (n%2 == 0);

17}

18

19/// A main to illustrate various list operations

20int main() {

21list<long> L;

22L.insert(L.begin(),4);

23L.insert(L.end(),15);

24L.insert(L.begin(),7);

25L.push_front(24);

26L.push_back(5);

27L.push_front(99);

28

29list<long>::iterator Li;

30Li = L.begin();

31	Li++;	// Focus on 2nd element in	the list
32	L.insert(Li,0);	// Inserts in front of 2nd	element
33

34cout << "Here is the list: ";

35print_list(L);

36cout << "The first element of the list is: " << L.front() << endl;

37cout << "The last element of the list is: " << L.back() << endl;

38cout << "The list contains " << L.size() << " elements" << endl;

39

40L.sort();

41cout << "And now sorted: ";

42print_list(L);

43

44L.pop_back();

45L.pop_front();

46cout << "First and last deleted: ";

47print_list(L);

48

49L.remove_if(is_even);

50cout << "Even values deleted: ";

51print_list(L);

52return 0;

53}

Containers

147

The first procedure in this program is used to print a list to the computer’s screen. We pass the list as a reference variable because this is more efficient (hence the & on line 6). Had we passed the list by value, a new copy of the list would have been created and that’s a waste of time and memory.

Because this procedure does not modify the list, we certify that with the keyword const on line 6.

The next step is to declare an iterator for the list and use that to report each value held in the list. Here’s the problem. An iterator can be used to modify list values. If the C++ compiler sees you working with an iterator for the argument L it worries that you might change the elements held in the list. Suppose we had declared Li in the usual way:

list<long>::iterator Li;

If we then focus Li on an element of L (e.g., with Li = L.begin();) then the compiler gets upset because we now have the ability to modify L.

So, instead of using a “full power” iterator, we instead declare Li to be a “read only” iterator—an iterator that can learn the values held in the list, but cannot modify them. Such an iterator is known as a const_iterator and it is declared like this (see also line 7):

list<long>::const_iterator Li;

Now the compiler can stop worrying that we might modify L in this procedure. The rest of the print_list procedure is straightforward.

(Aside: We could have defined an operator<< to send lists to the computer’s screen. Then we could write statements like this: cout << L;.)

The is_even procedure on lines 15–17 is used to illustrate remove_if later in the program (line 50).

The main procedure appears on line 20 and begins by declaring L to be a list of integers. We first insert 4 at the beginning of the list, then 15 at the end, and then 7 at the beginning. The list now stands at (7,4,15).

Next we insert 24 at the beginning, 5 at the end, and 99 at the beginning. Now the list is (99,24,7,4,15,5).

On lines 30–31 we focus Li on the second element of the list (which holds the value 24). The statement L.insert(Li,0); inserts the value 0 in front of 24; now the list holds (99,0,24,7,4,15,5).

Lines 34–38 are self-explanatory.

Line 40 sorts the list; it now holds (0,4,5,7,15,24,99).

On lines 44–45 we delete the first and last elements of the list. Now the list holds (4,5,7,15,24).

On line 49 we delete all elements that evaluate to true when processed by the is_even procedure. This reduces the list to (5,7,15).

Here is the output from the program.

148	C++ for Mathematicians

Here is the list: 99 0 24 7 4 15 5

The first element of the list is: 99

The last element of the list is: 5

The list contains 7 elements

And now sorted: 0 4 5 7 15 24 99

First and last deleted: 4 5 7 15 24

Even values deleted: 5 7 15

8.7.2 Stacks

A stack is a container that holds elements in a linear structure. New elements can be added only at one end of the stack (called the top of the stack). The only element that can be deleted is the one at the top of the stack, and it is also the only one that is visible.

Before declaring a stack variable, use the directive #include <stack>. Now to declare a stack of, say, double values, use a declaration like this:

stack<double> S;

There are four methods you need to know to work with stacks.

Check if the stack is empty The empty() method returns true if the stack contains no elements.

Add an element to the top of a stack Use the push method: S.push(x);.

Learn the value held at the top of the stack Use S.top(). You may also use the top method to modify the topmost value, as in S.top()=M_PI;.

Remove the top value held in the stack The statement S.pop(); removes the top element from the stack.

8.7.3 Queues

A queue is a container that holds elements in a linear structure. New elements are added only at one end of the queue (called the back). The only element that can be removed from the queue (and the only one whose value is visible) is at the opposite end of the queue (called the front).

To use queues in your program, use the directive #include <queue>. Declare your queue like this:

queue<long> Q;

Here is what you need to know to use queues.

To check if the queue is empty Q.empty() returns true if the queue is empty and false otherwise.

To add an element to the back of the queue Q.push(e) inserts the value in e to the end of the queue.

Containers

149

To see the value at the front of the queue Q.front() gives the value held at the head of the queue.

To delete the value at the front of the queue Use the statement Q.pop();.

It is also possible to look (and modify) the last element in the queue with the back() method, but this is not in the spirit of queues. The usual mode of operation with queues is to insert values at the back of the queue and not deal with them again until they emerge at the front.

8.7.4 Deques

A deque is a double-ended queue (hence its name). It is a container that holds elements in a linear structure. New elements can be inserted or deleted at either end. It is possible to access (and modify) any element of a deque quickly using array notation (e.g., D[4]). These containers incorporate features of stacks, queues, and vectors.

To use a deque in your program, use the directive #include <deque> and declare your variables like this:

deque<long> D;

Here are the most important things you can do with a deque.

Add elements To add a value to the back use D.push_back(e); and to add a value to the front use D.push_front(e);. The “front” of the deque is considered its beginning and the “back” is its end.

Delete elements The methods pop_front() and pop_back() delete the first and last elements of the deque, respectively.

Inspecting and modifying elements The methods front() and back() can be used to get the first/last values in the deque, and to modify those values. A statement such as D.front()=34; changes the first element’s value to 34. Of course, these methods require that the deque be nonempty.

Alternatively, one can use square brackets to get or to modify any value held in a deque. Index 0 always refers to the first (front) element of the deque. Index D.size()-1 is used for the last. To change the second entry in a deque, one would use a statement like this: D[1]=86;. As with arrays and vectors, it is important not to give an out-of-range index.

Deques support iterators (declared like this: deque<long>::iterator Di;), but it is easier to use square brackets to work with individual entries.

Here is a short program to illustrate the use of deques; its output follows.

150	C++ for Mathematicians

Program 8.7: A program to illustrate the deque container.

1#include <iostream>

2#include <deque>

3using namespace std;

4

5int main() {

6deque<long> D;

7

8D.push_back(17);

9D.push_back(23);

10D.push_front(-9);

11D.push_front(5);

12

13 D[1] = 0;

14

15cout << "The first element of the deque is " << D.front() << endl;

16cout << "The last element of the deque is " << D.back() << endl;

17cout << "Here is the entire structure: " ;

18for (long k=0; k<D.size(); k++) {

19cout << D[k] << " " ;

20}

21cout << endl;

22
23	return 0;
24	}

	The first element of the deque is	5
	The last element of the deque is 23
	Here is the entire structure: 5 0	17 23

8.7.5 Priority queues

A priority_queue is a container that holds its elements in a treelike structure. The elements must be comparable via the < operation. Elements can be inserted at any time but only the largest is visible and deletable.

To use a priority_queue include the <queue> header and declare your variable like this:

priority_queue<long> PQ;

The relevant operations for a priority_queue are these.

Adding a value Use PQ.push(e);.

Getting the largest value held Use PQ.top().

Deleting the largest value held Use PQ.pop();.

A short program to illustrate these concepts, and its output, follow.

Containers

151

Program 8.8: Demonstrating the use of the priority queue container.

1#include <iostream>

2#include <queue>

3using namespace std;

4

5int main() {

6priority_queue<long> PQ;

7

8PQ.push(5);

9PQ.push(12);

10PQ.push(0);

11PQ.push(-7);

12

13cout << "The elements we pushed into the priority_queue are ";

14while (!PQ.empty()) {

15cout << PQ.top() << " ";

16PQ.pop();

17}

18cout << endl;

19return 0;

20}

	The elements we pushed into the priority_queue are 12 5 0 -7

8.8Exercises

8.1In mathematics, the elements of a set can themselves be sets. Show how to

declare a set of sets of integers in C++ and write a short program that creates

the set	{	1,2,3	}	,	{	4,5	}	,	{	6	.
											}

8.2Write a procedure to print a set of long integers to the screen. The elements of the set should be enclosed between curly braces and separated by commas. (Be sure that the last element of the set is not followed by a comma.) The output should resemble these examples:

{1,2,3}

{-1}

{0,1}

{}

8.3Suppose we wish to use sets of complex numbers in a program. As a test, we create this simple program:

#include <complex> #include <set> using namespace std;

int main() {

152	C++ for Mathematicians

complex<double> z(2.,3.); set< complex<double> > A; A.insert(z);

return 0;

}

This program creates a complex number z = 2 + 3i and a set of complex numbers A into which we insert z. Unfortunately, the computer fails to compile this code and, instead, prints out a long stream of error messages that includes a complaint that there is

no match for const std::complex<double>& < const std::complex<double>&’ operator

What is wrong and how can we fix this?

8.4 Let a1,a2,a3,... be the sequence of numbers defined recursively by

a1 = 1 and an = ∑ ad .

d|n,d<n

These are the values calculated by Program 8.5 (page 143).

Prove that an is the number of ordered factorizations of n. That is, the number of ways to write n = f1 f2 ··· ft where the fi are integers with fi > 1. For example, a6 = 3 because the ordered factorizations of 6 are

6 2 × 3 3 × 2.

We have a1 = 1 because the empty product evaluates to 1.

Find another combinatorial description of this sequence.

8.5Create a class to represent integer partitions. Given a nonnegative integer n, a partition of n is a multiset of positive integers whose sum is n; the elements of the multiset are called the parts of the partition.

Name your class Partition and give it the following capabilities:

•A constructor that creates the empty partition of 0.

•An add_part method for adding a part.

•A get_sum method for learning the sum of the parts in the partition (i.e., the number partitioned by this Partition).

•An nparts method that reports the number of parts in the partition.

•A get_parts that returns the parts of the partition in a vector<int> container.

•An operator< to give a total order on the set of integer partitions.

•An operator<< for writing Partition objects to the screen. Choose an attractive output format. For example, the partition {1,1,3,4} of 9 can be written to the screen as 9 = 4+3+1+1.

Containers

153

8.6Use the Partition class that you developed in Exercise 8.5 to create a program that prints out all the partitions of a positive integer n, where n is specified by the user.

8.7Create a procedure to calculate binomial coefficients nk by the following algorithm. When k = 0 or k = n, set nk = 1. Otherwise, use the Pascal’s triangle identity: nk = nk−−11 + n−k 1 . This can be done recursively, but if the recursion is done naively, the same binomial coefficients are recalculated many times. Instead, devise a procedure that never calculates any binomial coefficient more than once.

8.8Write a procedure to convert an array of long integers into a vector<long>.

8.9Sorting vectors. Suppose values is a vector<long> of size 10 and we wish to sort the elements held in values into ascending order. We might consider the statement sort(values, values+10); but that is incorrect (and the compiler generates an error message).

Next we guess that (like a list) vector defines a sort method. So we try values.sort(); but this is also incorrect.

The difficulty with the first approach is that values is an object of type vector<long> and, unlike a C++ array, is not a pointer to the first element. So the expression values+10 is illegal. The difficulty with the second approach is that vector objects do not define a sort method.

How do we sort elements held in a vector?

Hint: In place of pointers to the first and one-past-the-last elements usually required by sort, we can use iterators.

8.10Suppose we have an iterator that refers to an element of a set, and then we delete that element from the set. What can you say about the iterator now?

8.11In light of Exercise 8.10, write a procedure that deletes all odd elements from a set of integers. Such a procedure would be declared such as this:

void delete_odds(set<long>& A);

8.12In many instances we want to perform an action on all the elements of a container. To do this, we typically use an iterator like this:

set<long> A;

...

set<long>::iterator sp;

for (sp = A.begin(); sp != A.end(); ++sp) { // do something with the value *sp

}

Because this structure is so frequent, the Standard Template Library provides a procedure named for_each that acts just as the code above does. The for_each procedure is defined in the algorithm header.

154	C++ for Mathematicians
	A call to for_each looks like this:

for_each(cont.begin(), cont.end(), proc);

Here cont is a container (such as a set or vector) and proc is a procedure that takes a single argument of the same type as cont houses. Furthermore, proc does not have a return value. For example, if cont is a vector<double>, then proc would be declared void proc(double x);.

The statement for_each(cont.begin(),cont.end(),proc); is equivalent to this code:

vector<double>::iterator vi;

for (vi=cont.begin(); vi!=cont.end(); ++vi) { proc(*vi);

}

Use the for_each procedure to create a print_set procedure that prints out a set of long integers to cout. The format of the output should look like this:

{ 1 3 9 }.

8.13A simplicial complex can be defined combinatorially as a finite set S of finite nonempty sets with the property that if A S and 0/ = B A, then B S. The sets in S are called the simplices of the simplicial complex.

For example, this topological simplicial complex

2		4
1	3	5

can be written combinatorially as
1	}	,	{	2	}	,	{	3	}	,	{	4	}	,	{	5	}	, 1,2 ,	{	1,3 ,	2,3 ,	{	2,4 ,	3,4 ,	{	3,5 ,	2,3,4	.
{																		{ }		} {	}		} {	}		} {		}

Create a class called SimplicialComplex that holds such structures. For the sake of efficiency, store only the maximal simplices in the complex. For the example given above, the maximal simplices are {1,2}, {1,3}, {2,3,4}, and {3,5}.

The class should contain a basic constructor (that creates an empty simplicial complex) and a method to add new simplices. The add method should be careful to deal with the following two situations.

•If the new simplex X is already in the simplicial complex do not add it again; we need to check that X is not a subset of one of the maximal simplices in S.

Containers

155

•If the new simplex X is not in S, but contains some of the simplices already in S, then we need to update the set of maximal simplices to include X and to delete those that are proper subsets of X.

The class should also contain a method to check if a given simplex X is a member of the complex.

If you are feeling adventurous, create an erase method to remove simplices from the complex. Of course, when a simplex X is deleted from S, we must also delete all simplices that contain X. We then need to be careful to update our collection of maximal simplices. If we delete the simplex {3,4} from the example in the figure, then we must also delete {2,3,4}. After the deletion, the simplex {2,3} is maximal.