Sets and Maps

Lecture 6: The Set and Map Classes

CS 106B: Programming Abstractions

Fall 2025, Stanford University Computer Science Department

Lecturer: Chris Gregg, Head CA: Yasmine Alonso

Announcements

• On Monday, we will cover algorithmic analysis, otherwise known as Big O notation. We’ll talk about it a bit today, too, but not in great detail.
• If you have OAE exam accomodations, please submit this form before Thursday, 10/9 at 11:59PM so we can guarantee that we’ll be able to support you for the midterm exam.

Code for today:

• SetsAndMaps
• CountUniqueWords
• TallyWords

the break statement

• In C++ loops, you can use the break statement, which may be useful.

• The break statement immediately exits a loop (one level only), and allows you to write constructs like this:

#include "simpio.h"
int main() {
    while (true) {
        int num = getInteger("Please enter a number between 1 and 10: ");
        if (num >= 1 && num <= 10) {
            cout << "Thank you! Your number is " << num << endl;
            break;
        }
    }
    return 0;
}

• Don’t abuse break – there are cases where you could have a while (or for) statement that doesn’t need it, e.g.,

#include "simpio.h"
int main() {
    int num = 0;
    while (num < 1 || num > 10) {
        num = getInteger("Please enter a number between 1 and 10: ");
    }
    cout << "Thank you, your number is " << num << endl;
    return 0;
}

Sets and Maps

• Today we are going to discuss two new collections: sets and maps.
• A set is a collection of elements with no duplicates:
• A map is a collection of key / value pairs, and the key is useed to find the value. In python, we call this collection a dict.

Sets

• A set is a collection of elements with no duplicates. Sets have (at least) the following operations (and they are fast):
  • add(value): adds a value to a set, and ignores if the set already contains the value
  • contains(value): returns true if the set contains the value, false otherwise.
  • remove(value): removes the value from the set. Does nothing if the value is not in the set.
  • size(): returns the number of elements in the set
  • isEmpty(): returns true if the set is empty, false otherwise.
  • Sets have other useful functions, and you should check the [Set] documentation to see them.
• Sets do not have indexes!

Sets: simple example

Set<string> friends;
friends.add("celeste");
friends.add("yasmine");
friends.add("chris");
friends.add("julie");
cout << boolalpha << friends.contains("voldemort") << 
     << noboolalpha << endl;
for(string person : friends) {
    cout << person << endl;
}

Output:

false
celeste
chris
julie
yasmine

• Notice – the output from the for loop is alphabetical! Sets keep their values sorted.

Looping over a Set

for(type currElem : set) {
    // process elements one at a time
}

• You can’t use an index-based for loop, becuase Sets do not have indexes!

for(int i=0; i < set.size(); i++) {
    // does not work, no index!
    cout << set[i];
}

Types of Sets

• There are actually two types of sets in the Stanford library:
  • Set
    • Iteration over the elements is in sorted order
    • Really fast access times! O(log n) per retrieval – we will learn about this next week!
    • Sets are implemented using a “binary search tree”
  • HashSet
    • Iteration over the elements is not in a useful order (it is jumbled)
    • Really, ridiculously fast!
    • O(1) per retrieval (again, we will learn what this means next time!)

Set Operands

• Sets can be compared, combined, etc.
  • s1 == s2
true if the sets contain exactly the same elements
  • s1 != s2
true if the sets don’t contain the exact same elements
  • s1 + s2
    returns the union of s1 and s2 (i.e., all elements in both)
  • s1 * s2
    returns the intersection of s1 and s2 (i.e., only the elements in both sets)
  • s1 - s2
    returns the difference of s1 and s2 (the elements in s1 but not in s2)

Counting Unique Words

• Let’s write a program to count the unique words in a file

Maps

• A map is a collection of pairs (k, v), sometimes called key/value pairs, where v can be found quickly if you know k.
• Other terms you may hear for a map are dictionary or associative array.
• A map is a generalization of an array, where the “indexes” don’t need to be integers:

Using Maps

• A map allows you to get from one half of a pair to the other.

  • E.g., to store an association from "Jenny" to "867-5309":

    //  key         value
    m["Jenny"] = "867-5309"; // or:
    m.put("Jenny", "867-5309");
    

  • To get Jenny’s number:

    string ph = m["Jenny"] // or
    string ph = m.get("Jenny")
    cout << ph << endl;
    

    Output:

    867-5309
    

Maps are Everywhere

• Wikipedia: the key is the title, the value is the article:

Creating Maps

• A Stanford Map requires two parameters: one for keys, one for values:

  // maps from string keys to integer values
  Map<string, int> votes;
  
  // maps from string keys to Vector<string> values
  Map<string, Vector<string>> friendMap; 
  

Map Functions

• The following functions are part of the Map class:
  • m.clear() : removes all key/value pairs from the map
  • m.containsKey(key) : returns true if the map contains a value for the given key
  • m[key]
m.get(key) : returns the value mapped to the given key; m[key] only: if key is not in the map, adds it with the default value (e.g., 0 or ""); m.get(key) only: if key is not in the map, returns the default value for the value type, but does not add it to the map.
  • m.isEmpty() : returns true if the map contains no key/value pairs (size 0)
  • m.keys() : returns a Vector copy of all keys in the map
  • m[key] = value
m.put(key, value) : adds a mapping from the given key to the given value; if the key already exists, replaces its value with the given one
  • m.remove(key) : removes any existing mapping for the given key (ignored if the key doesn’t exist in the map)
  • m.size() : returns the number of key/value pairs in the map
  • m.toString() : returns a string such as “{a:90, d:60, c:70}”
  • m.values() : returns a Vector copy of all the values in the map

Map Example

Map<string, string> wiki;

// adds name / text pair to dataset
wiki.put("Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo", articleHTML);

// returns corresponding articleHTML
cout << wiki.get("Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo");

// removes the article
wiki.remove("Carbon dioxide in Earth's atmosphere");

Types of Maps

• There are actually two types of maps in the Stanford library:
  • Map
    • Iteration over the elements is in sorted order
    • Really fast access times! O(log n) per retrieval – we will learn about this next week!
    • Maps are implemented using a “binary search tree”
  • HashMap
    • Iteration over the elements is not in a useful order (it is jumbled)
    • Really, ridiculously fast!
    • O(1) per retrieval (again, we will learn what this means next time!)

Map Example: Tallying Votes

// tally votes:
// (M)ilk, (S)tokes, (R)ogers
string allVotes = "MMMRMSSMSSMMMMMRRMMMMRRRMMM";

Map<char, int> voteTally;
for (char v : allVotes) {
    voteTally[v]++;
}

// loop over the map
for (char initial : voteTally) {
    int numVotes = voteTally[initial];
    cout << initial << ": " << numVotes << " votes" << endl;
}

• Why does voteTally[v]++; work? It turns out that when you access a Map’s value, you get back a reference! Therefore, updating it here allows it to update inside the map. Cool!
• It is equivalent to the following:

  int& currentTotal = voteTally[v];
  currentTotal++; // update inside the map
  

• Notice how we looped over the map – we only get the keys, and have to manually ask for each value from the key.

Tallying Words

• Let’s write a program to tally how many of each word is in a file