map and set
A vector finds elements by an index like 0, 1, 2. Often, though, you want to look things up by name: how much apples cost, what Ana scored. A std::map is a two-column table: on the left the key, on the right the value, and you use the key to find the value. It needs #include <map>.
1#include <iostream>2#include <map>3#include <string>4 5int main() {6 std::map<std::string, double> prices;7 prices["apple"] = 0.65;8 prices["banana"] = 0.32;9 std::cout << "banana: $" << prices["banana"] << '\n';10 std::cout << prices.size() << " kinds in all\n";11 return 0;12}
banana: $0.32 2 kinds in all
std::map<std::string, double>: the keys are strings and the values are doubles. prices["apple"] = 0.65 stores a value and prices["banana"] reads one. It looks like a vector's square brackets, except a key goes inside them.
Storing and changing
A map can start out with several pairs in curly braces, each written {key, value}. A key has only one value: assigning to it again replaces the old one. Press Step and see stock drawn as key–value pairs:
1#include <iostream>2#include <map>3#include <string>4 5int main() {6 std::map<std::string, int> stock{{"apple", 5}, {"pear", 3}};7 stock["apple"] += 2;8 stock["orange"] = 10;9 std::cout << "apple: " << stock["apple"] << '\n';10 std::cout << stock.size() << " kinds in all\n";11 return 0;12}
apple: 7 3 kinds in all
At stock["orange"] = 10 there is no orange in the table yet, so a new pair is added. At stock["apple"] += 2 apples are already there, so the old value changes.
Sorted by key
A range for goes through a map. Each pass gets one pair: .first is the key, .second the value. Whatever order you put them in, a map always keeps them sorted by key, smallest first. Press Step and watch where each new pair goes:
1#include <iostream>2#include <map>3#include <string>4 5int main() {6 std::map<int, std::string> rooms;7 rooms[305] = "Ana";8 rooms[101] = "Ben";9 rooms[210] = "Cara";10 for (const auto& kv : rooms) {11 std::cout << "Room " << kv.first << ": " << kv.second << '\n';12 }13 return 0;14}
Room 101: Ben Room 210: Cara Room 305: Ana
Each pair has a long type name, so write const auto&. Since C++17 you can also write for (const auto& [room, name] : rooms); this course sticks to C++14 and writes .first and .second.
Note: String keys sort by character codes, so uppercase comes before lowercase. There is also std::unordered_map, which looks things up faster, but goes through them in no fixed order; it can differ from one computer to the next.
The m[key] trap
What happens when you use square brackets with a key that isn't there?
What does this show?
1#include <iostream>2#include <map>3#include <string>4 5int main() {6 std::map<std::string, int> stock{{"apple", 5}};7 std::cout << stock["banana"] << '\n';8 std::cout << stock.size() << '\n';9 return 0;10}
stock["banana"] can't find a banana, so it quietly adds the pair {"banana", 0} and gives you the 0. Now the table has two pairs.
Square brackets add what they can't find. That's handy for counting (the word count below depends on it), but a trap when you only want to check: your table fills up with zeros.
Looking up and erasing
To check whether a key is there without adding it, use one of these:
| You write | What it does |
|---|---|
m.count(key) | 1 if the key is there, 0 if not |
m.find(key) | the pair it found; equals m.end() when there is none |
m.at(key) | reads the value; throws std::out_of_range if the key isn't there |
m.erase(key) | removes the key and its value |
1#include <iostream>2#include <map>3#include <string>4 5int main() {6 std::map<std::string, int> scores{{"Ana", 92}, {"Ben", 78}};7 if (scores.count("Cara") == 0) {8 std::cout << "No Cara\n";9 }10 auto it = scores.find("Ben");11 if (it != scores.end()) {12 std::cout << "Ben: " << it->second << '\n';13 }14 scores.erase("Ben");15 std::cout << scores.size() << " left\n";16 return 0;17}
No Cara Ben: 78 1 left
find gives you an iterator that points at the pair it found; -> reaches a member of the pair it points at, so it->second is the value. Lesson 27 covers iterators. Most of the time count is all you need.
Counting words
Counting is one of the most common jobs for a map. With counts[w]++, the first time w turns up the brackets add a 0 and then it goes up by 1; each later time it goes up by 1 again.
1#include <iostream>2#include <map>3#include <string>4#include <vector>5 6int main() {7 std::vector<std::string> words{"cat", "dog", "cat", "fish", "cat", "dog"};8 std::map<std::string, int> counts;9 for (const auto& w : words) {10 counts[w]++;11 }12 for (const auto& kv : counts) {13 std::cout << kv.first << ": " << kv.second << '\n';14 }15 return 0;16}
cat: 3 dog: 2 fish: 1
Press Step and watch the numbers in counts go up one by one. The words come out in alphabetical order, because a map sorts its keys.
set: no duplicates, always sorted
A std::set (from <set>) has keys and no values. Put the same value in twice and it keeps only one; going through it always goes smallest first:
1#include <iostream>2#include <set>3 4int main() {5 std::set<int> seen;6 seen.insert(42);7 seen.insert(7);8 seen.insert(42);9 seen.insert(19);10 std::cout << seen.size() << " values\n";11 for (int x : seen) {12 std::cout << x << " ";13 }14 std::cout << '\n';15 std::cout << "Is 7 there? " << seen.count(7) << '\n';16 return 0;17}
3 values 7 19 42 Is 7 there? 1
insert puts a value in, count checks for it (1 or 0), and erase removes it. For "drop the duplicates" or "have I seen this before?", use a set.
Practice
Write the code, then press Check. A hint costs nothing; the answer is there when you need it.
How many in the storeroom
✓Finish total_count: go through stock, add up all the counts, and return the sum. main is already written; it shows how many items each storeroom has.
Kitchen: 18 items Office: 35 items
1#include <iostream>2#include <map>3#include <string>4 5int total_count(const std::map<std::string, int>& stock) {6 int total = 0;7 8 return total;9}10 11int main() {12 std::map<std::string, int> kitchen{{"cups", 6}, {"plates", 8}, {"bowls", 4}};13 std::map<std::string, int> office{{"pens", 20}, {"notebooks", 15}};14 std::cout << "Kitchen: " << total_count(kitchen) << " items\n";15 std::cout << "Office: " << total_count(office) << " items\n";16 return 0;17}
How many of each letter
✓Count how many times each letter appears in word, and show them in alphabetical order.
a: 3 b: 1 n: 2
1#include <iostream>2#include <map>3#include <string>4 5int main() {6 std::string word = "banana";7 8 return 0;9}
Fix it: a set has no push_back
✓This program doesn't compile. Fix it so it shows how many different numbers were called: Different numbers: 3.
Different numbers: 3
1#include <iostream>2#include <set>3#include <vector>4 5int main() {6 std::vector<int> calls{110, 120, 110, 119, 120};7 std::set<int> seen;8 for (int c : calls) {9 seen.push_back(c);10 }11 std::cout << "Different numbers: " << seen.size() << '\n';12 return 0;13}
What you learned
std::map<key type, value type>finds values by key and needs#include <map>;m[key] = valuestores or changes one.- Going through a
mapgoes in key order, smallest first; each pair has.first(the key) and.second(the value). m[key]adds a default value (0, an empty string) when the key isn't there: right for counting, a trap for checking.- To check, use
count(1 or 0) orfind(equalsend()when not found);atthrows when not found;eraseremoves. counts[w]++is the classic way to count words.- A
std::setholds values without duplicates, always sorted:insert,count,erase.