You’ll need to be able to work with groups or collections of items. A game that only has one character with one quest and with one shop that sells one item isn’t going to be very fun. You have choices and this episode continues more than a week long exploration of collection types available. You’ll learn when to use each type of collection and why. Up today is the dictionary. I’ll explain what dictionaries are and then give you some guidance on when to use them.
Let’s say that you wanted to map some strings to numeric values. You could use a dictionary and declare it like this. This assumes the dictionary class is actually called a map.
map<string, int> numericValues;
You can then use your map to add a value like this:
numericValues[“mega”] = 1000000;
This will add a new entry with the key “mega” and the value 1,000,000 or one million.
Depending on how you declare you dictionary, you can store different types. It will always associate the keys with the values. Dictionaries are very efficient at looking up values as long as you know the key. Listen to the full episode or you can read the full transcript below.
Transcript
A dictionary is sometimes called an associative array because it associates or relates one value with another. The first value is called the key and the second value is just called the value. This collection type is commonly called a dictionary because it works just like real dictionaries. A dictionary associates words with their meanings. You can look up the words quickly and then find the meaning or maybe multiple meanings that match the word.
If all you know is a meaning and have no idea which word that meaning belongs to, then a dictionary is not very useful. The only way to find a meaning for an unknown word is to start at page one and read each meaning one by one.
This is why dictionaries in programming refer to the first value as the key. Without the key, the dictionary might as well be locked.
When you declare a dictionary, you need to specify the types of the keys and the values that the dictionary will hold. These types can be the same. If you want a program that can look up a word and find its meaning, then you’ll want to use a dictionary of type string and string. The word is the key and is a string. And the meaning is the value and is also a string. That would give you the ability to map a word to a single meaning. You might be able to squeeze multiple meanings into a single string value but then you’ll have to come up with some way to separate the meanings from each other.
A better way to declare a dictionary that maps words to one or more meanings for each word would be to declare the dictionary to be of type string and a list of strings. In this case, the type of the key is a string and the type of the value is a list of strings.
I hope you’re starting to see the power of these collection types. You can combine them in interesting ways like this. I’ll explain how dictionaries work right after this message from our sponsor.
( Message from Sponsor )
Dictionaries normally use another collection type internally called a pair. This just acts as a container that holds the key and the value and it allows the dictionary to work with both as if they were a single class. If you declare your dictionary to use a pointer to the second value type instead of the type itself, then you can store null values for the value.
A dictionary without the second value at all and that uses just the key is sometimes called a set. Think of this as if a real dictionary had no meanings and was just a collection of the words themselves. And a dictionary with both keys and values is sometimes called a map.
Languages like C++ have another version of a set and a map called a multiset and a multimap. The difference between them is that the multi versions allow multiple items to be added that have the same key.
One big question is how are dictionaries implemented? What actually makes them work? This depends on your language but you already know two of the most common ways that a dictionary can be implemented.
The first implementation strategy uses a binary tree to arrange the keys. This gives an order to the items added to the dictionary. That order may or may not be exposed to you to take advantage of.
The second implementation uses a hash table to store and retrieve the keys.
In both of these implementations, what actually gets stored in either the tree or the hash table is the item itself for a set and a pair for the map. If your language doesn’t have the concept of a set, then it will probably just have a map which it will likely call a dictionary. You may not have a choice as to how your dictionary stores items.
The C++ language uses binary trees to implement the set, multiset, map, and multimap. And it declares four more types that use hash tables. These are called an unordered_set, unordered_multiset, unordered_map, and unordered_multimap. Naming the hash table implementations to begin with unordered highlights the unordered nature of hash tables.