DOC PREVIEW
Stanford CS 106B - Implementing Maps

This preview shows page 1-2-17-18-19-35-36 out of 36 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Chapter 12Implementing MapsYea, from the table of my memoryI’ll wipe away all trivial fond records— Shakespeare, Hamlet, 1602Objectives•To understand the technique of hashing and how it applies to maps.• To appreciate that pointers to functions can be interpreted as data values in C++.• To be able to use function pointers in the implementation of callback and mappingfunctions.Implementing Maps – 412 –One of the most useful data structures introduced in Chapter 4 was the Map class, whichprovides an association between keys and values. The primary goal of this chapter is toshow you how maps can be implemented extremely efficiently using a particularly cleverrepresentation called a hash table. Before doing so, however, it makes sense to start witha less efficient implementation that is not nearly so clever just to make sure that youunderstand what is involved in implementing the map.h interface. The following sectiondefines an array-based implementation for the Map class. The rest of the chapter thenlooks at various strategies for improving on that simple design.12.1 An array-based implementation of the map interfaceFigure 12-1 shows a slightly simplified implementation of the map.h interface, whichleaves out three features of the library version of the interface: deep copying, selectionusing square brackets, and the ability to iterate over the keys in a map. Even in its currentform, however, the interface is quite useful, and it makes sense to investigate possibleimplementations of the fundamental operations before extending the interface.When you are trying to learn how a particular data structure operates, it is often helpfulto start with a specific example, understand how that example works, and then generalizefrom that example to get a sense of how the abstraction works as a whole. Suppose, forexample, that you have been asked to implement (as you will be in exercise 1 at the endof this chapter) a program that translates Roman numerals into integers. As part of thatprogram, you will need some way of encoding the following translation table:I → 1V → 5X → 10L → 50C → 100D → 500M → 1000Figure 12-1 Preliminary version of the map.h interface/* * File: map.h * ----------- * This interface exports a slightly simplified version of the Map * template class. */#ifndef _map_h#define _map_h#include "genlib.h"/* * Class: Map * ---------- * This interface defines a class template that stores a collection * of key-value pairs. The keys are always strings, but the values * can be of any type. This interface defines the value type using * the template facility in C++, which makes it possible to specify * the value type in angle brackets, as in Map<int> or Map<string>. */Implementing Maps – 413 –template <typename ValueType>class Map {public:/* * Constructor: Map * Usage: Map<int> map; * -------------------- * The constructor initializes a new empty map. */ Map();/* * Destructor: ~Map * Usage: delete mp; * ----------------- * The destructor frees any heap storage associated with this map. */ ~Map();/* * Method: size * Usage: nEntries = map.size(); * ----------------------------- * This method returns the number of entries in this map. */ int size();/* * Method: isEmpty * Usage: if (map.isEmpty())... * ---------------------------- * This method returns true if this map contains no entries, * false otherwise. */ bool isEmpty();/* * Method: clear * Usage: map.clear(); * ------------------- * This method removes all entries from this map. */ void clear();Implementing Maps – 414 –/* * Method: put * Usage: map.put(key, value); * --------------------------- * This method associates key with value in this map. Any value * previously associated with this key is replaced by the new one. */ void put(string key, ValueType value);/* * Method: get * Usage: value = map.get(key); * ---------------------------- * If key is found in this map, this method returns the associated * value. If key is not found, the get mathod raises an error. * Clients can use the containsKey method to verify the presence * of a key in the map before attempting to get its value. */ ValueType get(string key);/* * Method: containsKey * Usage: if (map.containsKey(key))... * ----------------------------------- * Returns true if there is an entry for key in this map, * false otherwise. */ bool containsKey(string key);/* * Method: remove * Usage: map.remove(key); * ----------------------- * This method removes any entry for key from this map. * If there is no entry for the key, the map is unchanged. */ void remove(string key);private:#include "mappriv.h"};#include "mapimpl.cpp"#endifImplementing Maps – 415 –Given your experience with the classes in Chapter 4, the idea of using a map shouldspring immediately to mind whenever you see a translation table that maps strings tosome other value. To set up such a map, you would need the following code:Map<int> romanNumerals;romanNumerals.put("I", 1);romanNumerals.put("V", 5);romanNumerals.put("X", 10);romanNumerals.put("L", 50);romanNumerals.put("C", 100);romanNumerals.put("D", 500);romanNumerals.put("M", 1000);The simplest strategy for representing this data structure is to store each key/value pairin an array. As with most of the implementations you’ve seen since Chapter 9, that arrayneeds to be dynamic so that it can expand if the number of keys grows beyond the initialallocation. The mappriv.h file for the array-based implementation of the Map classappears in Figure 12-2, which contains the structure definitions and instance variablesnecessary to represent this information. The code for the array-based representation ofthe Map class appears in Figure 12-3.Figure 12-2 Contents of the private section of map.h for the array-based representation/* * File: mappriv.h * --------------- * This file contains the private section of the map.h interface * for the array-based map. *//* * Type: keyValuePairT * ------------------- * This type represents a key-value pair. This implementation of * the Map class stores these entries in an array. */ struct keyValuePairT { string key; ValueType value; };/* Constants */ static const int INITIAL_CAPACITY = 100;/* Instance variables */ keyValuePairT *array; /* A dynamic array of key/value pairs */ int capacity; /* The allocated size of the array */ int count; /* The current number of entries *//* Private function


View Full Document

Stanford CS 106B - Implementing Maps

Download Implementing Maps
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Implementing Maps and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Implementing Maps 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?