Map - std::unordered

S3.0 What This Teaches

The standard library provides two map types. This tutorial covers:

std::unordered_map - O(1) average, hash-based, unordered
std::map - O(log n), tree-based, sorted by key
Inserting and looking up values
The [] operator vs find()
Structured bindings for clean iteration

S3.1 unordered_map vs map

	unordered_map	map
Lookup	O(1) average	O(log n)
Order	Unspecified	Sorted by key
Key requirement	Hashable + equality	Less-than comparable
Use when	Fast lookup matters most	Ordered iteration needed

Default to unordered_map. Switch to map when you need keys in sorted order.

S3.2 Inserting and Looking Up

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

// insert
scores["Alice"] = 95;
scores.insert({"Bob", 87});
scores.emplace("Carol", 92);

// safe lookup with find
auto it = scores.find("Alice");
if (it != scores.end())
    std::cout << it->second << "\n";   // 95

S3.3 The [] Operator vs find()

scores["Dave"];         // inserts "Dave" with default value 0 if not present
scores["Dave"] += 10;   // now 10

// find does NOT insert
auto it = scores.find("Eve");
if (it == scores.end())
    std::cout << "Eve not found\n";

// count: returns 0 or 1 (maps have unique keys)
if (scores.count("Alice"))
    std::cout << "Alice exists\n";

Avoid [] for reads when you are not certain the key exists - it inserts a default-constructed value if missing, silently growing the map. Use find() or count() instead.

S3.4 Iteration

for (const auto& [key, value] : scores)
    std::cout << key << ": " << value << "\n";

// map iterates in sorted key order; unordered_map order is unspecified

The structured binding [key, value] (C++17) unpacks the std::pair<const Key, Value> stored at each position.

S3.5 Example - All Together

// Map - std::unordered_map and std::map.

#include <iostream>
#include <unordered_map>
#include <map>
#include <string>

int main() {
    // word frequency count
    std::unordered_map<std::string, int> freq;
    for (const auto& word : {"the", "cat", "sat", "on", "the", "mat", "the"})
        freq[word]++;

    std::cout << "frequencies:\n";
    for (const auto& [word, count] : freq)
        std::cout << "  " << word << ": " << count << "\n";

    // sorted map for ordered output
    std::map<std::string, int> sorted_freq(freq.begin(), freq.end());
    std::cout << "\nsorted:\n";
    for (const auto& [word, count] : sorted_freq)
        std::cout << "  " << word << ": " << count << "\n";

    sorted_freq.erase("on");
    std::cout << "\nsize after erase: " << sorted_freq.size() << "\n";
    return 0;
}

frequencies:
  the: 3
  mat: 1
  on: 1
  sat: 1
  cat: 1

sorted:
  cat: 1
  mat: 1
  on: 1
  sat: 1
  the: 3

size after erase: 4

Note: unordered_map iteration order varies between runs.

S3.6 Exercise

Exercise

Count the character frequencies of a string using an unordered_map<char, int>. Print the results sorted by frequency (highest first) using a vector of pairs.
Build a phone book using map<std::string, std::string> (name → number). Add, look up, and remove entries, then iterate in alphabetical order.
Use emplace instead of insert or [] to add entries. Confirm it does not overwrite an existing key.

S3.7 Common Mistakes

[] on a const map

const std::unordered_map<std::string, int> m = {{"a", 1}};
m["a"];   // error: [] is not const because it may insert

Use m.at("a") or m.find("a") on const maps.

Assuming insertion order

unordered_map does not preserve insertion order. If you need predictable order use map (sorted) or maintain a separate vector of keys.

Using a non-hashable type as key

struct Point { int x, y; };
std::unordered_map<Point, int> m;   // error: no std::hash for Point

Provide a custom hash or use std::map with a custom comparator.

S3.8 Key Terms

Term	Meaning
unordered_map	Hash-based map; O(1) average lookup; unordered
map	Tree-based map; O(log n) lookup; sorted by key
find(key)	Returns iterator to element or end(); does not insert
operator[]	Inserts default value if key missing; not safe on const map
at(key)	Bounds-checked lookup; throws std::out_of_range if missing
count(key)	Returns 0 or 1 for maps (maps have unique keys)
structured binding	auto& [key, value] unpacks pair into named variables (C++17)