Lecture 4/17: Sets and Maps


April 17, 2020

📂Associated files

Lecture 6: The Set and Map Classes

CS 106B: Programming Abstractions

Spring 2020, Stanford University Computer Science Department

Lecturers: Chris Gregg and Julie Zelenski

An image of a set, with a box around many circles, each with a letter inside, and an image of a map, with many circles, each with an individual arrow to another circle.


Slide 2

Announcements


Slide 3

Sets and Maps


Slide 4

Sets

A set with many words, including "the", "if", "to", "by", but not "be". The image has set.contains("to"), which returns "true", and set.contains("be"), which returns false


Slide 5

Sets: simple example

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

Output:

false
chris
julie
nick

Slide 6

Looping over a Set

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

Slide 7

Types of Sets


Slide 8

Set Operands


Slide 9

Counting Unique Words


Slide 10

Maps


Slide 11

Using Maps


Slide 12

Maps are Everywhere

Two wikipedia articles, "Yosemite National Park" and "Mariana Trench"


Slide 13

Creating Maps


Slide 14

Map Functions


Slide 15

Map Example

Map<string, string> wiki;

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

// returns corresponding articleHTML
cout << wiki.get("Yosemite National Park");

// removes the article
wiki.remove("Britain in the E.U.");

A Wikipedia article showing a moth named after Donald Trump, called "Neopalpa Donaldtrumpi", because the moth has a shock of yellow hair

A Wikipedia article about Yosemite National Park

A Wikipedia article about the removal of Great Britain from the U.K.


Slide 16

Types of Maps


Slide 17

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;
}

Slide 18

Tallying Words

The Qt Creator logo