Program #5

Implement the Map class template. Part of the interface is below (you will want to add private helpers). A map, also known as an associative array, stores keys and values. The map may not contain duplicate keys, but it may contain duplicate values. Most of the semantics should be self-explanatory, given the names of the member functions and their parameters. The tricky functions are the two versions of operator[].

The Map Template Interface

Here is the interface:

template <class KeyType, class ValueType>
class Map
{
  public:
      // Return true if empty.
    bool isEmpty( ) const;

      // Return the number of keys currently stored.
    int getSize( ) const;

      // Return a vector that contains all the keys.
    vector<KeyType> getAllKeys( ) const;

      // Make the map empty.
    void makeEmpty( );

      // Add a key and value; if key already present, override value.
    void insert( const KeyType & key, const ValueType & val );

      // Remove a key and its associated value if found; otherwise, do nothing.
    void remove( const KeyType & key );

      // Get the value corresponding to key (see below).
    ValueType & operator[] ( const KeyType & key );
    const ValueType & operator[] ( const KeyType & key ) const;

  private:
    struct Pair
    {
        KeyType   key;
        ValueType value;

        Pair( const KeyType & k = KeyType( ), const ValueType & v = ValueType( ) )
          : key( k ), value( v ) { }
    };

    vector<Pair> items;
};

operator[] Semantics

Both versions return the value corresponding to the key in the map. They differ in their behavior when the key is not found. For the accessor, if the key is not found an exception should be thrown. For the mutator if the key is not found, then you should insert the key with the default value, and then return a reference to the value (since now there is a value in the map).

What to Submit

Submit your source code and a sample run. You must compile with a test program that I will supply next week.

Due Date

This program is due on Thursday, October 14.