C++ Unordered Map and Set Explained — How They Work, When to Use Them, and Hidden Traps

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <vector>

int main() {
    // --- unordered_map: count word frequencies in a document ---
    std::vector<std::string> words = {
        "apple", "banana", "apple", "cherry",
        "banana", "apple", "date", "cherry"
    };

    // Reserve buckets upfront to avoid mid-run rehashing.
    // Rule of thumb: reserve at least as many buckets as you expect elements.
    std::unordered_map<std::string, int> wordCount;
    wordCount.reserve(words.size());

    for (const auto& word : words) {
        // operator[] inserts a zero-initialized value if key is absent,
        // then increments it. Clean idiom for counting.
        wordCount[word]++;
    }

    std::cout << "=== Word Frequencies ===\n";
    for (const auto& [word, count] : wordCount) {
        // Note: iteration order is NOT alphabetical — it's bucket order.
        std::cout << word << ": " << count << "\n";
    }

    // --- unordered_set: fast duplicate detection ---
    std::vector<std::string> emails = {
        "alice@example.com", "bob@example.com",
        "alice@example.com", "carol@example.com"
    };

    std::unordered_set<std::string> seen;
    std::cout << "\n=== Duplicate Emails ===\n";
    for (const auto& email : emails) {
        // insert() returns a pair<iterator, bool>.
        // The bool is false if the element already existed.
        auto [it, inserted] = seen.insert(email);
        if (!inserted) {
            std::cout << "Duplicate found: " << email << "\n";
        }
    }

    // --- Inspecting internal state ---
    std::cout << "\n=== Internal State of wordCount ===\n";
    std::cout << "Bucket count : " << wordCount.bucket_count() << "\n";
    std::cout << "Load factor  : " << wordCount.load_factor() << "\n";
    std::cout << "Max load factor: " << wordCount.max_load_factor() << "\n";

    return 0;
}

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

// A 2D grid coordinate — used in game maps, image processing, pathfinding.
struct GridCell {
    int row;
    int col;

    // The container also needs to know when two keys are EQUAL.
    // Without this, it can't resolve collisions correctly.
    bool operator==(const GridCell& other) const {
        return row == other.row && col == other.col;
    }
};

// Custom hash functor for GridCell.
// We combine the hashes of both fields using the hash_combine pattern.
// This avoids the symmetry problem of plain XOR.
struct GridCellHash {
    std::size_t operator()(const GridCell& cell) const {
        std::size_t rowHash = std::hash<int>{}(cell.row);
        std::size_t colHash = std::hash<int>{}(cell.col);

        // This magic number (0x9e3779b9) is derived from the golden ratio.
        // It spreads bits in a way that minimises clustering in the bucket array.
        // This is the same technique used by Boost and Abseil internally.
        return rowHash ^ (colHash + 0x9e3779b9 + (rowHash << 6) + (rowHash >> 2));
    }
};

int main() {
    // Pass GridCellHash as the third template argument (the hasher).
    // The fourth argument (std::equal_to by default) uses our operator==.
    std::unordered_map<GridCell, std::string, GridCellHash> terrainMap;

    terrainMap[{0, 0}] = "Forest";
    terrainMap[{0, 1}] = "Mountain";
    terrainMap[{1, 0}] = "River";
    terrainMap[{3, 7}] = "Desert";

    // Look up terrain at a specific coordinate — O(1) average.
    GridCell target = {1, 0};
    auto it = terrainMap.find(target);

    if (it != terrainMap.end()) {
        std::cout << "Terrain at (1,0): " << it->second << "\n";
    }

    // Prove that (0,1) and (1,0) are distinct keys — XOR alone would collide here.
    std::cout << "Terrain at (0,1): " << terrainMap[{0, 1}] << "\n";
    std::cout << "Total cells mapped: " << terrainMap.size() << "\n";

    return 0;
}

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

// Helper to time a block of code in microseconds.
auto timeIt(auto&& fn) {
    auto start = std::chrono::high_resolution_clock::now();
    fn();
    auto end = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
}

int main() {
    const int NUM_PLAYERS = 100'000;
    std::mt19937 rng(42); // Fixed seed for reproducibility.
    std::uniform_int_distribution<int> scoreDist(1, 1'000'000);

    // Build player ID -> score maps.
    std::map<int, int>           orderedLeaderboard;
    std::unordered_map<int, int> fastLeaderboard;
    fastLeaderboard.reserve(NUM_PLAYERS);

    // --- Insertion timing ---
    auto orderedInsertTime = timeIt([&]() {
        for (int id = 0; id < NUM_PLAYERS; ++id)
            orderedLeaderboard[id] = scoreDist(rng);
    });

    rng.seed(42); // Reset so both maps get identical data.
    auto unorderedInsertTime = timeIt([&]() {
        for (int id = 0; id < NUM_PLAYERS; ++id)
            fastLeaderboard[id] = scoreDist(rng);
    });

    // --- Lookup timing: 100k random lookups ---
    std::uniform_int_distribution<int> idDist(0, NUM_PLAYERS - 1);
    volatile int sink = 0; // Prevent the compiler from optimising the loop away.

    auto orderedLookupTime = timeIt([&]() {
        for (int i = 0; i < NUM_PLAYERS; ++i)
            sink += orderedLeaderboard[idDist(rng)];
    });

    auto unorderedLookupTime = timeIt([&]() {
        for (int i = 0; i < NUM_PLAYERS; ++i)
            sink += fastLeaderboard[idDist(rng)];
    });

    std::cout << "=== Insertion (100k elements) ===\n";
    std::cout << "std::map        : " << orderedInsertTime   << " us\n";
    std::cout << "std::unordered_map: " << unorderedInsertTime << " us\n";

    std::cout << "\n=== Lookup (100k random) ===\n";
    std::cout << "std::map        : " << orderedLookupTime   << " us\n";
    std::cout << "std::unordered_map: " << unorderedLookupTime << " us\n";

    // std::map shines here: iterate in ascending player ID order — free with map.
    std::cout << "\n=== Top 3 Players by ID (ordered iteration — only map can do this) ===\n";
    int count = 0;
    for (const auto& [id, score] : orderedLeaderboard) {
        std::cout << "Player " << id << " -> Score: " << score << "\n";
        if (++count == 3) break;
    }

    return 0;
}