Assignment #7

Implement the Map class template two different ways. Part of the first 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[].

Two Implementations

Implementation #1 stores the pairs of items in a vector, in no particular order. So searching the map will be done with a sequential search. Implementation #2 uses a singly-linked list of pairs, in no particular order. Again, Big-Oh efficiency is not an issue. You can see examples of how to implement linked lists by look at the queue or stack code online. You may nest the Node class, or leave it as a top-level class. You must implement the Big-Three (copy constructor, operator=, destructor) for this version of the map.

The Map Template Interface

Here is the interface along with the data representation for version #1 (version #2 has a different data representation, but same public 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 ) { }
    };


      // Data representation varies in two implementations
    vector<Pair> items;
};

operator[] Semantics

Both versions of operator[] 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 with both versions of the map using assign7.cpp. Since you may not change assign7.cpp, you will need to use the trick discussed in class to enable separate compilation of templates under Visual C++.