Thinking In C++. Volume 2: Practical Programming

The goal of this chapter was not just to introduce the STL containers in some considerable depth. (Of course, not every detail could be covered here, but you have enough now that you can look up further information in the other resources.) Our higher hope is that this chapter has made you grasp the incredible power available in the STL and shown you how much faster and more efficient your programming activities can be by using and understanding the STL.

Exercises

             1.             Create a set, open a file (whose name is provided on the command line), and read that file in a char at a time, placing each char in the set. Print the results, and observe the organization. Are there any letters in the alphabet that are not used in that particular file?

        39.             Create three sequences of Noisy objects, a vector, deque, and list. Sort them. Now write a function template to receive the vector and deque sequences as a parameter to sort them and record the sorting time. Write a specialized template function to do the same for list (ensure to call its member sort( ) instead of the generic algorithm). Compare the performance of the different sequence types.

        40.             Write a program to compare the speed of sorting a list using list::sort( ) vs. using std::sort( ) (the STL algorithm version of sort( )).

         41.             Create a generator that produces random int values between 0 and 20 inclusive, and use it to fill a multiset. Count the occurrences of each value, following the example given in MultiSetWordCount.cpp.

        42.             Change StlShape.cpp so that it uses a deque instead of a vector.

        43.             Modify Reversible.cpp so it works with deque and list instead of vector.

        44.             Use a stack and populate it with a Fibonacci sequence. The program’s command line should take the number of Fibonacci elements desired, and you should have a loop that looks at the last two elements on the stack and pushes a new one for every pass through the loop.

        45.             Using only three stacks (source, sorted, and losers), sort a random sequence of numbers by placing the numbers initially on the source stack. Assume the number on the top of the source is the largest, and push it on the sorted stack. Continue to pop the source stack comparing it with the top of the sorted stack. Whichever number is the smallest, pop it from its stack and push it onto the on the losers’ stack. Once the source stack is empty, repeat the process using the loser’s stack as the source stack, and use the source stack as the losers’ stack. The algorithm completes when all the numbers have been placed into the winners’ stack.

        46.             Open a text file whose name is provided on the command line. Read the file a word at a time, and use a multiset to create a word count for each word.

         47.             Modify WordCount.cpp so that it uses insert( ) instead of operator[ ] to insert elements in the map.

        48.             Create a class that has an operator< and an ostream& operator<<. The class should contain a priority number. Create a generator for your class that makes a random priority number. Fill a priority_queue using your generator, and then pull the elements out to show they are in the proper order.

        49.             Rewrite Ring.cpp so it uses a deque instead of a list for its underlying implementation.

        50.             Modify Ring.cpp so that the underlying implementation can be chosen using a template argument. (Let that template argument default to list.)

         51.             Create an iterator class called BitBucket that just absorbs whatever you send to it without writing it anywhere.

        52.             Create a kind of "hangman" game. Create a class that contains a char and a bool to indicate whether that char has been guessed yet. Randomly select a word from a file, and read it into a vector of your new type. Repeatedly ask the user for a character guess, and after each guess, display the characters in the word that have been guessed, and display underscores for the characters that haven’t. Allow a way for the user to guess the whole word. Decrement a value for each guess, and if the user can get the whole word before the value goes to zero, they win.

        53.             Open a file and read it into a single string. Turn the string into a stringstream. Read tokens from the stringstream into a list using a TokenIterator.

        54.             Compare the performance of stack based on whether it is implemented with vector, deque, or list.