Map, Set & Unordered Containers

Why Look Up by Key Instead of Index?

A vector is great when "the 3rd item" is a meaningful question. But often it isn't — you want to ask "what's Alice's age?" or "is this username already taken?" Doing that with a vector means scanning every element until you find a match: O(n), and it gets slower as the data grows.

The STL's associative containers — map, set, unordered_map, unordered_set — are built exactly for this. They store data so that looking something up by key is dramatically faster than a linear scan.

std::map — Ordered Key-Value Pairs

A map<K, V> stores unique keys of type K, each mapped to a value of type V. You can insert or overwrite with [], exactly like an array but indexed by any comparable type, not just integers.

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> ages;

    ages["Alice"] = 30;
    ages["Bob"] = 25;
    ages["Charlie"] = 35;

    ages["Alice"] = 31; // key exists -> overwrites the value

    for (const auto& [name, age] : ages) { // structured bindings (C++17)
        cout << name << " is " << age << " years old" << endl;
    }

    return 0;
}

Checking for a key with .find()

Using ages["Zoe"] to check whether "Zoe" exists is a trap — if the key isn't there, that syntax silently inserts it with a default value. To check without inserting, use .find().

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> stock = {{"apples", 50}, {"bananas", 30}};

    auto it = stock.find("apples");
    if (it != stock.end()) {
        cout << "Found: " << it->first << " -> " << it->second << endl;
    }

    if (stock.find("mangoes") == stock.end()) {
        cout << "mangoes not in stock" << endl;
    }

    return 0;
}

.find(key) returns an iterator to the matching entry, or .end() if the key doesn't exist — it never modifies the map. Both [] access and .find() run in O(log n) on a map, since the tree is balanced.

std::set — Unique, Sorted Values

A set<T> is like a map with only keys and no values — it stores each distinct element exactly once, always in sorted order. Inserting a duplicate is simply ignored.

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> ids;

    ids.insert(5);
    ids.insert(2);
    ids.insert(5); // duplicate — silently ignored
    ids.insert(8);

    for (int id : ids) cout << id << " "; // prints sorted: 2 5 8
    cout << endl;

    cout << "Contains 5? " << (ids.find(5) != ids.end() ? "yes" : "no") << endl;

    return 0;
}

Use a set whenever you need to guarantee "no duplicates" and don't need to attach any extra data to each element — deduplicating a list of IDs, tracking which nodes you've already visited in a graph, and so on.

unordered_map & unordered_set — Hash-Based Speed

unordered_map and unordered_set store the exact same kind of data as map and set, but internally use a hash table instead of a balanced tree. The trade-off: you lose sorted iteration order, but lookups, inserts, and erases are average O(1) instead of map's O(log n).

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    unordered_map<string, int> wordCount;

    wordCount["cat"]++;
    wordCount["dog"]++;
    wordCount["cat"]++;

    for (const auto& [word, count] : wordCount) {
        cout << word << ": " << count << endl; // order is NOT guaranteed
    }

    return 0;
}

Lesson Summary