Programming in C++

Exercise Sheet 4

These exercises provide practice with using and defining template functions and classes.

  1. During the lecture we've seen how to use a vector in order to implement a stack: 
    #include <iostream>
#include <vector>
using namespace std;

template <typename Item>
class stack {
	vector<Item> v;
public:
	bool empty() const { return v.size() == 0; }
	void push(const Item & x) { v.push_back(x); }
	void pop() { v.pop_back(); }
	// It takes two...
	      Item & top()       { return v.back(); }
	const Item & top() const { return v.back(); }
};

int main() {
	stack<int> si;

	si.push(1);
	si.push(2);
	si.push(3);

	while (! si.empty()) {
		cout << si.top();
		si.pop();
	}

	return 0;
}
    Now we need to implement a queue, with methods enqueue (add), dequeue (remove), head (gets the item at the head of the queue), tail (gets the last item), and empty. A queue is a collection to which items may be added or removed, such that the item removed is always the first one added (and still there) - so it's FIFO, where stack is LIFO.

    Write a generic queue class based on list and test it.

  2. Write a program that reads words from the standard input and, when the end of input (EOF) is reached, prints out each word once, with a count of the number of times it occurred in the input.

    You will need a map from strings to integers to keep track of the number of occurrences of each word.

    HINT: Because there is as yet no easy way to get all the words in a map, you will also need to maintain a vector or list of all the words seen (but only one of each). (Next session we will cover iterators, which can be used instead.)

  3. Write a new program that reads a series of lines, each comprising a word and an associated number, and then prints out for each word the total sum and average of the associated numbers.

    HINT: You will need a new class to hold the statistics for a word (a pair of two ints? BTW, pair is defined inside utility), and then a map from words to objects of this class.