In chapter 4 we will study trees and balanced trees. The standard library has an implementation of balanced (red-black) trees, but these implementations are not directly accessible to programmers. Instead, they are used as internal representations in the container classes set, multiset, map, and multimap. In this lab we will study the map and multimap, which are somewhat more complicated than set and multiset, but substantially more useful. Students completely unfamiliar with these container classes or wishing to review them in more detail than is covered here should see Chapter 7 and Sections 19.6-19.9 of Musser and Saini or Section 17.4 of Stroustrup.

Maps and multimaps store entries, each of which is a pair of the form

        pair< const Key, T >

The declaration for a map looks like

      template < class Key, class T, class Compare = less< Key > > class map

    bool Comp( const Key& lft, const Key& right );

Of course maps (and multimaps) define iterators, and each iterator is in essence a pointer to a pair as defined above. As we will see, this leads to some complicated looking syntax. Iterating through a map looks like the iterations for any other container class, but the operations are implemented internally as an in-order tree traversal.

Enough of the preliminaries; it is time to start doing something. As you work through this lab, refer back to the foregoing discussion to help make sense of what's going on.

1. Copy the files
   • /dept/cs/cs230/www/labs/lab5/student.cpp
   • /dept/cs/cs230/www/labs/lab5/student.h
   • /dept/cs/cs230/www/labs/lab5/main.cpp
   and create a new project which incorporates them.

   Look quickly at student.h and student.cpp. The code there is straightforward. Now look at the main.cpp in light of the following discussion.

2. Inserting: There are two ways to insert into a map and one way to insert into a multimap. The simplest method, which is unique to a map, is through the [] operator. The effect of the line

     students["Stewart"] = StudentRecord( "stewac", "freshman", "12234567890" );
   

   is to enter a StudentRecord into the map using the key "Stewart" (implicitly converted to a string). What really happens using the [] operator is that the underlying tree is searched for a matching string: if it is there, the associated StudentRecord is returned (as a reference); if it is not there, an entry is created at the appropriate place in the tree using the default constructor for StudentRecord. In either case, the returned StudentRecord is replaced by the new record by the assignment statement.

   The other way to insert is with the insert function. There are several flavors of "insert", but the basic one is shown here (see main.cpp). The first thing to do is to create the value (a pair) to be inserted. For a map, the actual insert operation returns a pair, with the "first" being an iterator and "second" being a bool.

   Note: the values stored in any pair can be accessed through the public member variables first and second.

   For a multimap, the insert just returns the iterator. The difference in return types is because maps can not have entries with duplicate keys, so the insert will fail if the key is already in the map.

   Obviously, therefore, maps (and multimaps) define iterators. Each iterator is in essence a pointer to a pair as defined above. As we will see, this leads to some complicated looking syntax. Iterating through a map looks like the iterations for any other container class, but the operations are implemented internally as an in-order tree traversal.

   So, here are two exercises: (a) compile and run the program to see what happens, and then (b) write code at the line in main.cpp labeled C to output the key and associated student record referenced (pointed to, actually) from the result of the insert. Compile and test the resulting program. (To get rid of all the silly looking warnings, set the "Warning level" to "None" under Project/Settings/C++. In general, this is a bad thing to do, but some the reaction of some compilers to the templates warrants it.)

3. The difficult syntax associated with maps can be improved dramatically through the use of typedefs. You can see useful ones at the label D in main.cpp. Note the second typedef in particular: along with every other container class, a map defines a number of types, including a value_type and a variety of iterators. It might be helpful for what follows to move these typedefs to near the top of main.cpp, just after the map header file is included.

4. Find: The find operation can also be implemented in several ways. Unique to the map is the use of the [] operator, as shown at the code labeled E (see discussion above). This use of the operator locates the entry having the given key and returns a reference to the second of the value type pair. Hence, using the "." operator gives access to the associated StudentRecord. As discussed above, if the key was not previously in the map, a new entry is created. The find member function works for both maps and multimaps. It takes only a Key (string in our case) as an argument, and returns an iterator. This iterator "points" to the value type pair if the key is in the map (multimap) and to the end iterator otherwise. It does not create an entry if one matching the key is not found. To find all entries in a map or multimap matching a given key use lower_bound and upper_bound, each of which takes a Key and returns an iterator. The iterator returned by lower_bound indicates the first entry whose key is not less than the target key. The iterator returned by upper_bound is the first entry whose key is greater than the target.

5. Rewrite the lines labeled E to use find and, if not found, to insert entries in the map. Use std::cout statements to indicate exactly what is happening. Compile and test your program.

6. Add a function to main.cpp to print the entire contents of a map. Use the prototype

          void PrintMap( const StudentMap& students )
   

   Be sure to print both the string and StudentRecord for each entry.

7. Write code to use an iterator to run through the current map adding to the grades of each student (member function "add_grades"), using whatever values you wish.

8. The "erase" function takes either a key (string in our example), an iterator, or two iterators (first and last). In the first case, the entry containing the key is removed if it exists (all entries containing the key, in a multimap. The second erase is straightforward. The third erase deletes everyting from first up to but not including last.

9. Write code to erase every entry in the map whose key starts with "S". Make your code as efficient as possible by not iterating from the start of the map. Note: the string type has a subscripting operator []. Your code segment should be as short as possible.

10. Change the map to a multimap (perhaps through the typedefs!) What must change in main.cpp to accommodate this? Write code to add duplicate keys (with different student records) to the multimap.

At the conclusion of this lab, take a moment to review the following:

You have been reintroduced to the map and multimap container classes from the standard library (STL). You have also explored their primary member functions. The main difficulty in compiling code that uses maps and multimaps is that the Key is and must remain a const.

Maps and multimaps use a balanced tree implementation, but this is not apparent from the public interface. The only way a balanced tree implementation could be inferred is from the time-bound requirements on the operations (find, insert and erase must be logarithmic and ordered output must be linear). This is evidence of a good class design: the public interface reflects an intuitive view of how the class is to be used, not how it is implemented.