Maps and Sets

Associative containers store data in a way that allows efficient lookup by key. std::map and std::set use a balanced BST (O(log n) operations); std::unordered_map and std::unordered_set use hash tables (O(1) average). Choose based on whether you need sorted order or maximum lookup speed.

`std::map` — Sorted Key-Value Pairs

cpp

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

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

    // Insert / update
    wordCount["hello"]  = 1;
    wordCount["world"]  = 2;
    wordCount["hello"]  = 5;   // Overwrites

    wordCount.insert({"cpp", 3});
    wordCount.emplace("fun", 4);   // Construct in-place (faster)

    // Access
    cout << wordCount["hello"] << "\n";   // 5
    cout << wordCount.at("cpp") << "\n";  // 3 (throws if not found)

    // Check existence
    if (wordCount.count("missing") == 0) {
        cout << "'missing' not in map\n";
    }

    // C++20: contains()
    cout << wordCount.contains("fun") << "\n";   // 1

    // Iteration — always in sorted key order
    for (const auto& [key, val] : wordCount) {   // C++17 structured binding
        cout << key << ": " << val << "\n";
    }
    // cpp: 3
    // fun: 4
    // hello: 5
    // world: 2

    // Size
    cout << wordCount.size() << "\n";   // 4

    return 0;
}

Finding and Erasing

cpp

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

int main() {
    map<string, double> prices = {
        {"apple",  0.5},
        {"banana", 0.25},
        {"cherry", 1.2},
        {"date",   2.5},
    };

    // find — returns iterator (O(log n))
    auto it = prices.find("banana");
    if (it != prices.end()) {
        cout << "banana costs: " << it->second << "\n";   // 0.25
        it->second = 0.3;   // Modify value through iterator
    }

    // lower_bound / upper_bound
    auto lb = prices.lower_bound("b");   // First key >= "b"
    auto ub = prices.upper_bound("c");   // First key > "c"
    for (auto i = lb; i != ub; ++i) {
        cout << i->first << ": " << i->second << "\n";
    }
    // banana: 0.3
    // cherry: 1.2

    // Erase by key
    prices.erase("date");
    cout << prices.size() << "\n";   // 3

    // Erase by iterator
    prices.erase(prices.begin());   // Removes 'apple' (smallest key)

    return 0;
}

`std::unordered_map` — Hash Table

cpp

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

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

    // Count word frequencies
    string text = "the quick brown fox jumps over the lazy dog the fox";
    istringstream ss(text);
    string word;

    while (ss >> word) {
        freq[word]++;   // operator[] inserts 0 if key is missing
    }

    // Iteration — order is NOT guaranteed
    for (const auto& [w, count] : freq) {
        cout << w << ": " << count << "\n";
    }

    // O(1) average lookup
    cout << "the: " << freq["the"] << "\n";   // 3
    cout << "fox: " << freq["fox"] << "\n";   // 2

    // Load factor and rehashing
    cout << "Load factor: " << freq.load_factor() << "\n";
    freq.reserve(100);   // Hint to avoid rehashing

    return 0;
}

Container	Ordered	Lookup	Insert	Use When
`map`	Yes (sorted)	O(log n)	O(log n)	Need sorted iteration or range queries
`unordered_map`	No	O(1) avg	O(1) avg	Maximum lookup speed, no order needed

Default Value with `operator[]`

map::operator[] inserts a default-constructed value if the key is not found. This is useful but can be a surprise:

cpp

map<string, int> m;
cout << m["new_key"] << "\n";   // 0 (inserted new key with value 0!)
cout << m.size()     << "\n";   // 1

// If you don't want to insert, use find() or contains()
if (m.count("another_key") == 0) {
    cout << "Not found\n";
}

`std::set` — Sorted Unique Elements

cpp

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

int main() {
    set<int> s = {5, 2, 8, 1, 9, 3, 7, 4, 6};

    // Set automatically sorts and deduplicates
    for (int n : s) cout << n << " ";
    cout << "\n";   // 1 2 3 4 5 6 7 8 9

    // Insert
    s.insert(10);
    s.insert(5);    // Duplicate — ignored silently

    // Check membership — O(log n)
    cout << s.count(7) << "\n";   // 1 (found)
    cout << s.count(99) << "\n";  // 0 (not found)
    cout << s.contains(7) << "\n"; // 1 (C++20)

    // Erase
    s.erase(5);
    cout << s.size() << "\n";   // 9

    // Useful: find first element >= value
    auto it = s.lower_bound(6);
    cout << *it << "\n";   // 6

    return 0;
}

`std::unordered_set` — Hash Set

cpp

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int main() {
    // Remove duplicates from a vector
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

    unordered_set<int> seen;
    vector<int> unique_v;

    for (int n : v) {
        if (seen.insert(n).second) {   // insert returns {iterator, bool}
            unique_v.push_back(n);     // second = true if newly inserted
        }
    }

    for (int n : unique_v) cout << n << " ";
    cout << "\n";   // 3 1 4 5 9 2 6 (original order preserved)

    // Two-sum problem using unordered_set
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    unordered_set<int> complements;

    for (int n : nums) {
        int complement = target - n;
        if (complements.count(complement)) {
            cout << n << " + " << complement << " = " << target << "\n";  // 7 + 2 = 9
        }
        complements.insert(n);
    }

    return 0;
}

`multimap` and `multiset` — Duplicate Keys

cpp

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

int main() {
    // multimap — multiple values per key
    multimap<string, int> grades;
    grades.emplace("Alice", 90);
    grades.emplace("Alice", 85);
    grades.emplace("Bob",   75);

    // All values for "Alice"
    auto range = grades.equal_range("Alice");
    for (auto it = range.first; it != range.second; ++it) {
        cout << it->first << ": " << it->second << "\n";
    }
    // Alice: 90
    // Alice: 85

    // multiset — allows duplicate elements
    multiset<int> ms = {3, 1, 4, 1, 5, 9, 2, 6};
    for (int n : ms) cout << n << " ";
    cout << "\n";   // 1 1 2 3 4 5 6 9

    cout << ms.count(1) << "\n";   // 2 (two 1s)

    return 0;
}

Practical Example: Inventory System

cpp

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

class Inventory {
    map<string, pair<int, double>> items;  // name → {quantity, price}

public:
    void addStock(const string& name, int qty, double price) {
        if (items.count(name)) {
            items[name].first += qty;   // Update quantity
        } else {
            items[name] = {qty, price};
        }
    }

    bool sell(const string& name, int qty) {
        auto it = items.find(name);
        if (it == items.end() || it->second.first < qty) {
            cout << "Insufficient stock: " << name << "\n";
            return false;
        }
        it->second.first -= qty;
        if (it->second.first == 0) items.erase(it);
        return true;
    }

    double totalValue() const {
        double total = 0;
        for (const auto& [name, info] : items) {
            total += info.first * info.second;
        }
        return total;
    }

    void print() const {
        cout << left << setw(15) << "Item"
             << right << setw(8) << "Qty"
             << setw(10) << "Price"
             << setw(12) << "Value" << "\n";
        cout << string(45, '-') << "\n";

        for (const auto& [name, info] : items) {
            cout << left << setw(15) << name
                 << right << setw(8) << info.first
                 << setw(10) << fixed << setprecision(2) << info.second
                 << setw(12) << info.first * info.second << "\n";
        }
        cout << string(45, '-') << "\n";
        cout << setw(33) << "Total:" << setw(12) << totalValue() << "\n";
    }
};

int main() {
    Inventory inv;
    inv.addStock("Laptop",  10, 45000.0);
    inv.addStock("Mouse",   50, 999.0);
    inv.addStock("Keyboard", 30, 1499.0);
    inv.addStock("Monitor", 5, 18000.0);

    inv.sell("Laptop", 3);
    inv.sell("Mouse",  15);

    inv.print();

    return 0;
}

Summary

map<K,V> — sorted by key, O(log n) operations — use when you need ordered iteration or range queries
unordered_map<K,V> — hash table, O(1) average — use when you need maximum lookup speed
set<T> — sorted unique elements; unordered_set<T> — hash set, O(1) lookup
multimap/multiset — allow multiple values per key or duplicate elements
map::operator[] inserts a default value if the key is not found — use find() to avoid unintended inserts
C++17 structured bindings (const auto& [key, val]) make map iteration clean and readable
emplace and emplace_hint construct elements in-place — faster than insert for complex value types

Next, we'll explore STL algorithms — sort, find, transform, accumulate, and the power of algorithm composition with lambdas.

Maps and Sets

Maps and Sets

std::map — Sorted Key-Value Pairs

Finding and Erasing

std::unordered_map — Hash Table

Default Value with operator[]

std::set — Sorted Unique Elements

std::unordered_set — Hash Set

multimap and multiset — Duplicate Keys

Practical Example: Inventory System

Summary

`std::map` — Sorted Key-Value Pairs

`std::unordered_map` — Hash Table

Default Value with `operator[]`

`std::set` — Sorted Unique Elements

`std::unordered_set` — Hash Set

`multimap` and `multiset` — Duplicate Keys