1. Maps and multimaps have two comparison predicates while other STL containers have only one. Explain the difference.

   ---

   Maps and multimaps have two types of values to worry about, while the other containers have only one. As with all other containers, maps and multimaps have a value_type and an associated value_compare() predicate. Unlike all other containers, however, the map and multimap value type is a pair of types: pair<const Key,T>. The value_compare() predicate is used to define, for example, operator ==().

   Unlike the sequential containers, maps and multimaps also must do a key comparison, for which the value_compare() predicate is inappropriate. The second map and multimap comparison, key_compare() is used to perform key comparisons.

   Note that sets and multisets also have two comparison predicates, but they are actually the same predicate because the value and key types are the same for sets and multisets.

   ---

2. Maps and vectors are similar in the sense that they both provide indexed access to values. Explain under which circumstances you would choose to use a map instead of a vector to provide indexed access to values.

   ---

   There are two circumstances. The first circumstance would be if the index value has non-integer type. Because vectors have only integer indices, a map, which can have indices of any type, would be more appropriate than a vector would be.

   If the indices are integers, the second condition under which it would be better to chose a map over a vector is when the number of values stored is much smaller than the range of index values.

   See Muser and Saini page 165.

   A number of people tried to argue that maps are sorted and vectors are not, but sortedness has no relevance here (besides, what's being sorted are the key values, and it isn't too hard to argue that vectors are sorted too). Some people also tried to argue that reading and writing maps is faster than reading and writing vectors, but that isn't true: either it takes O(log n) to index a map and constant time to index a vector, or it takes the same, constant amount of time to step through a map or a vector.

   ---

3. Describe the map ic_map created by

   map<int, char, less<int> > ic_map;
   ic_map.insert(pair<const int, char>(1, 'a'));
   ic_map.insert(pair<const int, char>(1, 'b'));
   ic_map.insert(pair<const int, char>(2, 'c'));
   

   ---

   After the first insertion, ic_map contains ((1, 'a')). Because the second value being inserted has the same key value as a value already in the ic_map, the second value replaces the duplicated key value. ic_map now contains ((1, 'b')). The third insertion adds a value with a new key, and ic_map finally contains ((1, 'b'), (2, 'c')).

   A couple of people suggested the second value gets merged with the first value, so that ic_map would contain ((1, {a', <, <)', >, >). A few others suggested that the second insert would be rejected because it conflicted with value already in ic_map.

   ---

4. Explain how you would find all values associated with a particular key value in a multimap. For example, how would you find the employee records for all employees named "Smith" in the multimap

   multimap<string, EmpolyeeRecord, less<string> >employees;
   

   ---

   Use equal_range(). A number of people also suggested using count() to find out how many Smiths were in the multimap, but were unclear on how you'd find the first Smith.

   ---

This page last modified on 16 August 2000.