Chapter 14

Maps & Other Collections

Vectors and arrays are brilliant when you want to look up data by its position — the third enemy, the fifth high score, the tile at row 4, column 7. But a lot of real-world data isn't organized by position. You want the score for the player named "Ada." You want the damage value for the "fire_sword" weapon. For these jobs, indexing by number is clumsy. What you actually want is to look things up by name.

This chapter is about collections that let you do exactly that, plus a handful of other specialist containers the C++ standard library provides.

In this chapter, we will:

std::map

A std::map is a collection of key-value pairs. You use the key to find the value — like a dictionary where the word is the key and the definition is the value. Maps live in the <map> header:

#include <map>

std::map<std::string, int> scores;

scores["Ada"]   = 100;
scores["Grace"] = 85;
scores["Linus"] = 70;

std::cout << scores["Ada"] << std::endl;   // 100

The [] Trap

If you use [] to look up a key that doesn't exist, the map quietly creates an entry for that key with a default value. For an int, that's 0:

int mysteryScore = scores["Grace"];   // Grace didn't exist — now she does, with score 0
std::cout << scores.size() << std::endl;   // 2!

The safer way to check before reading is contains():

if (scores.contains("Grace")) {
    std::cout << scores["Grace"] << std::endl;
} else {
    std::cout << "No score for Grace." << std::endl;
}

Iterating Over a Map

// Traditional — entry.first is the key, entry.second is the value:
for (const auto& entry : scores) {
    std::cout << entry.first << ": " << entry.second << std::endl;
}

// Structured bindings (C++17, preferred):
for (const auto& [name, score] : scores) {
    std::cout << name << ": " << score << std::endl;
}

When you iterate a std::map, entries always come out in sorted key order. In this case, Ada, Grace, Linus — alphabetical order.

Removing Entries and find()

scores.erase("Linus");

// find() returns an iterator, or end() if not found:
auto it = scores.find("Ada");
if (it != scores.end()) {
    std::cout << it->first << " has a score of " << it->second << std::endl;
}

std::unordered_map

std::unordered_map is a hash map that gives you constant-time lookup on average, regardless of how big the map gets. The trade-off is that entries aren't in any particular order. The API is almost identical to std::map:

#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores["Ada"] = 100;

if (scores.contains("Ada")) {
    std::cout << scores["Ada"] << std::endl;   // 100
}

Reach for std::map when you want sorted iteration. Reach for std::unordered_map when you don't care about ordering and want faster lookups.

std::set and std::unordered_set

A set is a collection of unique values. std::set keeps values sorted; std::unordered_set doesn't. They live in <set> and <unordered_set>:

#include <set>

std::set<std::string> unlockedLevels;

unlockedLevels.insert("forest");
unlockedLevels.insert("desert");
unlockedLevels.insert("forest");   // Already there — ignored

std::cout << unlockedLevels.size() << std::endl;   // 2

if (unlockedLevels.contains("desert")) {
    std::cout << "Desert is unlocked!" << std::endl;
}

Useful game patterns for sets: which levels are unlocked, which achievements are earned, which keys are currently held down. Any time the answer is "yes or no, with no duplicates allowed."

std::queue and std::stack

A queue is first-in, first-out (FIFO). Things come out in the order they went in:

#include <queue>

std::queue<std::string> eventQueue;

eventQueue.push("PlayerJumped");
eventQueue.push("EnemySpawned");
eventQueue.push("ScoreIncreased");

while (!eventQueue.empty()) {
    std::cout << eventQueue.front() << std::endl;
    eventQueue.pop();
}
// Output: PlayerJumped, EnemySpawned, ScoreIncreased

A stack is last-in, first-out (LIFO). The most recent thing added is the first thing to come back out:

#include <stack>

std::stack<std::string> undoStack;

undoStack.push("PlaceWall");
undoStack.push("MoveEnemy");
undoStack.push("DeleteTile");

while (!undoStack.empty()) {
    std::cout << "Undoing: " << undoStack.top() << std::endl;
    undoStack.pop();
}
// Output: DeleteTile, MoveEnemy, PlaceWall

std::pair and std::tuple

A std::pair holds exactly two values of potentially different types:

std::pair<std::string, int> namedScore = {"Ada", 100};
std::cout << namedScore.first << ": " << namedScore.second << std::endl;

A std::tuple is the more general version — any number of values, any types:

#include <tuple>

std::tuple<std::string, int, float> playerData = {"Ada", 100, 0.75f};

std::cout << std::get<0>(playerData) << std::endl;   // "Ada"
std::cout << std::get<1>(playerData) << std::endl;   // 100

Structured Bindings

C++17 introduced structured bindings, which let you unpack a pair or tuple into named variables:

auto [name, score] = namedScore;
std::cout << name << ": " << score << std::endl;

// Especially useful when iterating over a map:
for (const auto& [name, score] : scores) {
    std::cout << name << ": " << score << std::endl;
}

std::deque

A std::deque (pronounced "deck") is a double-ended queue. It supports fast insertion and removal at both the front and the back — something a std::vector doesn't support efficiently at the front:

#include <deque>

std::deque<int> recentScores;

recentScores.push_back(100);
recentScores.push_back(85);
recentScores.push_front(150);   // Insert at the front — cheap!

// recentScores is now {150, 100, 85}

A replay system that records the last thirty seconds of gameplay naturally fits a deque — new frames push onto the back, old frames pop off the front. For most game work, std::vector is still your default.

Choosing the Right Collection

AI Exercise

"I'm a C++ beginner. I've just learned about std::vector, std::array, std::map, std::unordered_map, std::set, std::unordered_set, std::queue, std::stack, std::pair, std::tuple, and std::deque. For each of the following four game systems, recommend the collection (or combination of collections) I should use to implement it, and explain your reasoning in one or two sentences. (1) An inventory that maps item names to quantities, displayed alphabetically in the UI. (2) A system that tracks which enemy types the player has encountered at least once, used only to answer yes-or-no questions like 'has the player seen a goblin yet?'. (3) A list of the player's last ten actions, where the newest action is at the front and the oldest falls off the end. (4) A tile map for a level that's exactly 40 tiles wide and 25 tiles tall, where each tile is an integer. Finally, sketch the C++ declaration (just the type) for each system."

Notice what the prompt is doing. It names the specific collections you know so the AI doesn't wander off into unfamiliar territory. And it gives four concrete systems where the right answer depends on the details — "alphabetically," "yes-or-no," "newest at the front," and "exactly 40 by 25." Evaluate whether the AI picks up on those clues.

Summary

You now have the full standard-library toolkit of collections. Vectors and arrays for ordered sequences. Maps and unordered maps for key-value lookup. Sets for unique collections. Queues and stacks for ordered processing. Pairs and tuples for grouping a few values. Deques for double-ended access. And structured bindings for unpacking them cleanly.

With this toolkit plus the concepts from earlier chapters, you now have everything you need to write almost any self-contained game system. What you're missing is how to organize it all — how to model a Player, Enemy, Bullet, and Tile each as first-class things rather than piles of variables. That's what object-oriented programming is for, and it's what the rest of this act is built on.