Exercise 6
| About | Files | Solutions |
|---|---|---|
| Template functions, containers, algorithms. | exercise6.tar.gz | sol-exercise6.tar.gz |
- "Counting sort" is an efficient sorting method if the elements that are to be sorted are integral values in a limited range. You count the number of occurrences of each value and then output each value the correct number of times.
Example: sort {6, 3, 6, 2, –1, 3}. The number of occurrences becomes {1, 0, 0, 1, 2, 0, 0, 2} (one –1, no 0, no 1, one 2, two 3, no 4, no 5, two 6).
Implement the functioncsortin csorttest.cc. Sort some million values in the range [1, 1000] and compare the execution time forcsortwith that ofstd::sort.csortshould be better. Sort some thousand values in the range [–10 000 000, +10 000 000] and compare again. - Write a class
SequenceGeneratorto be used in generate.cc. Deduce from the program text what the class should look like. - Write a program that reads a number of text files, whose names are given on the command line, and prints the 20 most common words in the files along with the total number of occurrences in all files. You may assume that there are only letters and whitespace in the files. Give an error message if a file cannot be opened.
- The first part of
TagRemoverfrom lab 3 can be implemented using the standard algorithm std::copy_if, by using stream iterators<char> and a stateful functor that returnsfalsewhen inside a tag andtrueotherwise. The algorithmstd::copy_ifiterates over an iterator range, calling its predicate with each element but only copies the elements for which the predicate returns true. The filetagremover_alg.cccontains a skeleton and a simple test. Implement a functor so that it removes tags when used with std::copy_if.
Note that as the tagremover now operates directly on streams, it does not need any state except from in the functor, and thus can be implemented as a free function.