Mapping Functions and Iterators Notes | EduRev

: Mapping Functions and Iterators Notes | EduRev

 Page 1


Mapping Functions 
and Iterators 
Eric Roberts 
CS 106B 
May 8, 2009 
Page 2


Mapping Functions 
and Iterators 
Eric Roberts 
CS 106B 
May 8, 2009 
Where Are We Now? 
• In our last episode, we implemented the generic Map class 
based on the idea of a hash table. 
• Our implementation had all of the features of the library 
version of Map with the exception of 
– There was no support for associative array selection 
– There was no support for iterating through the keys in a map. 
• The game plan for today is to 
– Implement associate array selection by defining the [] operator 
– Implement mapping functions 
– Describe iterator strategies 
Page 3


Mapping Functions 
and Iterators 
Eric Roberts 
CS 106B 
May 8, 2009 
Where Are We Now? 
• In our last episode, we implemented the generic Map class 
based on the idea of a hash table. 
• Our implementation had all of the features of the library 
version of Map with the exception of 
– There was no support for associative array selection 
– There was no support for iterating through the keys in a map. 
• The game plan for today is to 
– Implement associate array selection by defining the [] operator 
– Implement mapping functions 
– Describe iterator strategies 
/* 
 * Method: operator[] 
 * Usage: map[key] = newValue; 
 * --------------------------- 
 * This method overloads [] to access values from this 
 * map by key.  The argument inside the brackets is the key (a 
 * string).  This allows the client to use notation of an 
 * "associative-array" to get/set the value associated with a key. 
 * If the key is already present in the map, this function returns 
 * a reference to its associated value.  Because this function 
 * returns the value by reference, it allows in-place modification 
 * of the value. 
 */ 
 
    ValueType & operator[](string key); 
 
Interface Entry for the [] Operator 
Page 4


Mapping Functions 
and Iterators 
Eric Roberts 
CS 106B 
May 8, 2009 
Where Are We Now? 
• In our last episode, we implemented the generic Map class 
based on the idea of a hash table. 
• Our implementation had all of the features of the library 
version of Map with the exception of 
– There was no support for associative array selection 
– There was no support for iterating through the keys in a map. 
• The game plan for today is to 
– Implement associate array selection by defining the [] operator 
– Implement mapping functions 
– Describe iterator strategies 
/* 
 * Method: operator[] 
 * Usage: map[key] = newValue; 
 * --------------------------- 
 * This method overloads [] to access values from this 
 * map by key.  The argument inside the brackets is the key (a 
 * string).  This allows the client to use notation of an 
 * "associative-array" to get/set the value associated with a key. 
 * If the key is already present in the map, this function returns 
 * a reference to its associated value.  Because this function 
 * returns the value by reference, it allows in-place modification 
 * of the value. 
 */ 
 
    ValueType & operator[](string key); 
 
Interface Entry for the [] Operator 
/* 
 * Implementation notes: operator [] 
 * --------------------------------- 
 * This method looks very much like put except that it doesn't 
 * store a new value and returns the position in the cell by 
 * reference. 
 */ 
 
template <typename ValueType> 
ValueType & Map<ValueType>::operator[](string key) { 
    int index = hash(key) % nBuckets; 
    cellT *cell = findCell(buckets[index], key); 
    if (cell == NULL) { 
        cell = new cellT; 
        cell->key = key; 
        cell->link = buckets[index]; 
        buckets[index] = cell; 
        nEntries++; 
    } 
    return cell->value; 
} 
Implementation of the [] Operator 
Page 5


Mapping Functions 
and Iterators 
Eric Roberts 
CS 106B 
May 8, 2009 
Where Are We Now? 
• In our last episode, we implemented the generic Map class 
based on the idea of a hash table. 
• Our implementation had all of the features of the library 
version of Map with the exception of 
– There was no support for associative array selection 
– There was no support for iterating through the keys in a map. 
• The game plan for today is to 
– Implement associate array selection by defining the [] operator 
– Implement mapping functions 
– Describe iterator strategies 
/* 
 * Method: operator[] 
 * Usage: map[key] = newValue; 
 * --------------------------- 
 * This method overloads [] to access values from this 
 * map by key.  The argument inside the brackets is the key (a 
 * string).  This allows the client to use notation of an 
 * "associative-array" to get/set the value associated with a key. 
 * If the key is already present in the map, this function returns 
 * a reference to its associated value.  Because this function 
 * returns the value by reference, it allows in-place modification 
 * of the value. 
 */ 
 
    ValueType & operator[](string key); 
 
Interface Entry for the [] Operator 
/* 
 * Implementation notes: operator [] 
 * --------------------------------- 
 * This method looks very much like put except that it doesn't 
 * store a new value and returns the position in the cell by 
 * reference. 
 */ 
 
template <typename ValueType> 
ValueType & Map<ValueType>::operator[](string key) { 
    int index = hash(key) % nBuckets; 
    cellT *cell = findCell(buckets[index], key); 
    if (cell == NULL) { 
        cell = new cellT; 
        cell->key = key; 
        cell->link = buckets[index]; 
        buckets[index] = cell; 
        nEntries++; 
    } 
    return cell->value; 
} 
Implementation of the [] Operator 
Functions as Data 
• Up to this point in CS106, we’ve thought of functions as part 
of the control structure and as completely separate from the 
data structure. 
• That view, however, is limiting and does not reflect what goes 
on inside the machine.  One of the foundational ideas of 
modern computing—usually attributed to John von Neumann 
although there are other valid claims to the idea—is that code 
is stored in the same memory as data.  This concept is called 
the stored programming model. 
• If you go on to take CS 107, you will learn a little about how 
code is represented inside the computer.  The details of that 
representation, however, are not important for the moment.  
What is important is that every C++ function lives somewhere 
in memory and therefore has an address.  It is at least possible 
therefore to refer to a function in the data structure by storing 
its address as a pointer value. 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!