# 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

Slide 2

# Announcements

- Assignment 1 is due tonight, end-of-day Anywhere on Earth. Assignment 2 coming soon!
- The recorded section video for this week has been posted on Canvas for anyone that wants extra review on the last week and a half of lecture content.

Slide 3

# 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`

.

Slide 4

# 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 documentation to see them.

- Sets
*do not*have indexes!

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
```

- Notice â€“ the output from the for loop is alphabetical! Sets keep their values sorted.

Slide 6

# 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]; }`

Slide 7

# 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"

- Iteration over the elements is in
`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!)

Slide 8

# 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`

)

Slide 9

# Counting Unique Words

- Let's write a program to count the unique words in a file

Slide 10

# 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:

Slide 11

# 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`

- E.g., to store an association from

Slide 12

# Maps are Everywhere

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

Slide 13

# 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 double keys to Vector<int> values Map<string, Vector<string>> friendMap;`

Slide 14

# 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; if`key`

is not in the map,**adds**it with the default value (e.g.,`0`

or`""`

)`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

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.");
```

Slide 16

# 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"

- Iteration over the elements is in
`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!)

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

- 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.

Slide 18

# Tallying Words

- Let's write a program to tally how many of each word is in a file