Assignment 2

1) A split Algorithm

Splitting a string apart into substrings separated by spaces (or other characters) is a common and useful operation. Write a template function named split which splits an std::string into substrings, and stores them into a collection of the caller's choice. The prototype for split should be:

template <class OutputIterator> void split(const std::string& s, OutputIterator oi);

The reason for using the output iterator approach, rather than returning a vector or list of words, is to make the algorithm more general; it will work with any container. An example of use would be:

std::string test("A Tale of Two Cities");
list<std::string> words;

which should print the following words (and put them into the list as well):


Notes: The algorithm should work for any kind of Output Iterator. Multiple consecutive spaces should be treated the same as a single space. Use standard algorithms wherever possible in the implementation. For extra credit (1pt), make split() take an extra argument indicating the character to split on, and have it default to a space.

2) A Cross Reference Generator

Using appropriate containers and algorithms, write a program to generate a cross reference table of words in an input file. The input will be a file containing lines of text, such as:

It was the best of times, it was the worst of times,
it was the age of wisdom, it was the age of foolishness,
it was the epoc of belief, it was the epoc of incredulity,

From this input, generate a cross reference listing each unique word which appears in the input in default string comparison order, one per line. After each word, list the line number(s) on which it appears (the first line being line 1). For example,

It: 1 2
age: 2 2
best: 1
belief: 3

Notes: Words are defined as nonspace characters separated by one or more spaces. The split algorithm should be useful in implementing the cross reference generator. You may find it helpful to first implement a simple word count program, similar to the one outlined in the notes on map. Then, evolve that code into a cross reference generator. You will probably want to combine at least a couple of containers in this program; remember that you can create containers of containers if necessary.