cout << "map::operator[] lookups: "

<<clock() - ticks << endl; ticks = clock();

for(int i = 0; i < 100; i++) for(int j = 0; j < 1000; j++)

hm[j];

cout << "hash_map::operator[] lookups: "

<<clock() - ticks << endl;

ticks = clock();

for(int i = 0; i < 100; i++) for(int j = 0; j < 1000; j++)

m.find(j);

cout << "map::find() lookups: "

<<clock() - ticks << endl; ticks = clock();

for(int i = 0; i < 100; i++) for(int j = 0; j < 1000; j++)

hm.find(j);

cout << "hash_map::find() lookups: "

<<clock() - ticks << endl;

}///:~

The performance test I ran showed a speed improvement of roughly 4:1 for the hash_map over the map in all operations (and as expected, find( ) is slightly faster than operator[ ] for lookups for both types of map). If a profiler shows a bottleneck in your map, you should consider a hash_map.

Summary

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 should have enough now that you can look up further information in the other resources). My 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.

The fact that I could not escape from introducing some of the STL algorithms in this chapter suggests how useful they can be. In the next chapter you’ll get a much more focused look at the algorithms.

Chapter 15: Multiple Inheritance

259

Exercises

1.Create a set<char>, then 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, and whether there are any letters in the alphabet that are not used in that particular file.

2.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 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.

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

4.Modify WordCount.cpp so that it uses a multimap instead of a map.

5.Create a generator that produces random int values between 0 and 20. Use this to fill a multiset<int>. Count the occurrences of each value, following the example given in MultiSetWordCount.cpp.

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

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

8.Modify Progvals.h and ProgVals.cpp so that they expect leading hyphens to distinguish command-line arguments.

9.Create a second version of Progvals.h and ProgVals.cpp that uses a set instead of a map to manage single-character flags on the command line (such as -a -b -c etc) and also allows the characters to be ganged up behind a single hyphen (such as -abc).

10.Use a stack<int> and build a Fibonacci sequence on the stack. 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.

11.Open a text file whose name is provided on the command line. Read the file a word at a time (hint: use >>) and use a multiset<string> to create a word count for each word.

12.Modify BankTeller.cpp so that the policy that decides when a teller is added or removed is encapsulated inside a class.

13.Create two classes A and B (feel free to choose more interesting names). Create a multimap<A, B> and fill it with key-value pairs, ensuring that there are some duplicate keys. Use equal_range( ) to discover and print a

Chapter 15: Multiple Inheritance

260

range of objects with duplicate keys. Note you may have to add some functions in A and/or B to make this program work.

14.Perform the above exercise for a multiset<A>.

15.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, then pull the elements out to show they are in the proper order.

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

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

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

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

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

21.Create a template that implements a singly-linked list called SList. Provide a default constructor, begin( ) and end( ) functions (thus you must create the appropriate nested iterator), insert( ), erase( ) and a destructor.

22.(More challenging) Create a little command language. Each command can simply print its name and its arguments, but you may also want to make it perform other activities like run programs. The commands will be read from a file that you pass as an command-line argument, or from standard input if no file is given. Each command is on a single line, and lines beginning with ‘#’ are comments. A line begins with the one-word command itself, followed by any number of arguments. Commands and arguments are separated by spaces. Use a map that maps string objects (the name of the command) to object pointers. The object pointers point to objects of a base class Command that has a virtual execute(string args) function, where args contains all the arguments for that command (execute( ) will parse its own arguments from args). Each different type of command is represented by a class that is inherited from Command.

23.Add features to the above exercise so that you can have labels, if-then statements, and the ability to jump program execution to a label.

Chapter 15: Multiple Inheritance

261