Maps and Sets

What you’ll build

A program that reads a short text, counts how often each word appears, and lists the words it has seen, each once. A Map holds a value for each key, and a Set holds values without repeats; both are in std.collections.

A Map

A Map literal is pairs of key: value in braces. map[key] reads a key’s value, and map[key] = value adds the key or gives it a new value. A Map keeps its keys in the order they were added.

Import std.core
Import std.collections

Local capitals = {"France": "Paris", "Japan": "Tokyo"}
capitals["Peru"] = "Lima"
Print(capitals, capitals.Count)
Print(capitals["France"])
Print(capitals.Contains("Peru"), capitals.Contains("Chad"))
capitals.Remove("Peru")
Print(capitals.Keys(), capitals.Values())

{France: Paris, Japan: Tokyo, Peru: Lima} 3
Paris
True False
[France, Japan] [Paris, Tokyo]

A key that isn’t there

map[key] for a key the Map doesn’t have is a bug, and panics. When a key may be missing, Get gives the value or Null, and Get(key, fallback) gives the fallback instead.

Import std.core
Import std.collections
Import std.text

Local capitals = {"France": "Paris", "Japan": "Tokyo"}
Print(capitals.Get("Chad") ?? "not listed")
Print(capitals.Get("Chad", "unknown"))

Local city = capitals.Get("Japan")
If city != Null Then Print("Japan's capital has {city.Length} letters")

not listed
unknown
Japan's capital has 5 letters

After city != Null, the compiler knows city holds a String, so city.Length is allowed.

Counting with a default

A Map made with a default gives it for any key that’s missing, without adding the key. With a default of 0, counts[word] += 1 counts each word, starting from 0 the first time. A For over a Map gives each key with its value.

Import std.core
Import std.collections
Import std.text

Local text = "the cat and the hat and the bat"
Local counts = Map<String, Int>(default: 0)
For word In text.Split(" ")
    counts[word] += 1
End For

For word, count In counts
    Print("{word:<4} {count}")
End For

the  3
cat  1
and  2
hat  1
bat  1

A Map of lists can’t use a shared default, since every key would get the same array. GetOrAdd adds a new value the first time a key is seen instead:

Import std.core
Import std.collections
Import std.text

Local byLength = Map<Int, String[]>()
For word In ["fig", "kiwi", "pear", "plum", "lime", "date", "apple"]
    byLength.GetOrAdd(word.Length, Function() => []).Add(word)
End For
Print(byLength)

{3: [fig], 4: [kiwi, pear, plum, lime, date], 5: [apple]}

A Set

A Set holds each value once. Add gives True when the value is new and False when the Set had it already, and Contains asks whether a value is in it.

Import std.core
Import std.collections
Import std.text

Local seen = Set<String>()
For word In "the cat and the hat and the bat".Split(" ")
    If !seen.Add(word) Then Print("again: {word}")
End For
Print(seen, seen.Count)

again: the
again: and
again: the
{the, cat, and, hat, bat} 5

Combining Sets

Union makes a Set of the values in either Set, Intersect of the values in both, and Difference of the values in the first but not the second. Each makes a new Set, and leaves both as they were. IsSubsetOf asks whether every value of one Set is in the other: the primes aren’t a subset of the odd numbers, since 2 is even.

Import std.core
Import std.collections

Local odds = Set<Int>()
odds.AddAll([1, 3, 5, 7, 9])
Local primes = Set<Int>()
primes.AddAll([2, 3, 5, 7])

Print(odds.Union(primes))
Print(odds.Intersect(primes))
Print(odds.Difference(primes))
Print(primes.IsSubsetOf(odds))

{1, 3, 5, 7, 9, 2}
{3, 5, 7}
{1, 9}
False

A Map’s keys and a Set’s values must be Hashable. Numbers, Strings, Chars, Bools, and Enums are, and so are tuples and arrays of them. Every Class is, unless it defines an == of its own without a Hash, and a Struct can be.

What you learned

• {key: value} makes a Map; map[key] reads and writes, and keys stay in the order added.
• Get gives a key’s value or Null, and Get(key, fallback) a fallback.
• Map<K, V>(default: v) gives v for a missing key, which makes counting easy.
• A Set keeps each value once; Add says whether a value was new.
• Union, Intersect, and Difference make new Sets from two.