C++ STL Maps and Sets Explained — Usage, Internals and Pitfalls

#include <iostream>
#include <map>
#include <string>
#include <vector>

int main() {
    // Imagine processing a stream of words from a document.
    // We want a live frequency count, always sorted alphabetically.
    std::vector<std::string> words = {
        "apple", "banana", "apple", "cherry",
        "banana", "apple", "date", "cherry"
    };

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

    for (const std::string& word : words) {
        // [] inserts 0 if key is absent, then we increment.
        // This is intentional here — we WANT upsert behaviour.
        wordFrequency[word]++;
    }

    std::cout << "--- Full frequency table (sorted automatically) ---\n";
    for (const auto& [word, count] : wordFrequency) {
        // Structured bindings (C++17) make this clean to read.
        std::cout << word << ": " << count << "\n";
    }

    // Range query: find all words from 'b' up to (not including) 'e'
    std::cout << "\n--- Words in range [b, e) ---\n";
    auto rangeStart = wordFrequency.lower_bound("b"); // first key >= "b"
    auto rangeEnd   = wordFrequency.lower_bound("e"); // first key >= "e"

    for (auto it = rangeStart; it != rangeEnd; ++it) {
        std::cout << it->first << ": " << it->second << "\n";
    }

    // Safe lookup — find() does NOT insert if key is missing.
    std::string target = "elderberry";
    auto searchResult = wordFrequency.find(target);
    if (searchResult == wordFrequency.end()) {
        // .end() is the sentinel meaning "not found" — never dereference it.
        std::cout << "\n'" << target << "' was not found in the document.\n";
    }

    return 0;
}

#include <iostream>
#include <set>
#include <string>
#include <vector>

int main() {
    // Real scenario: a web server logs every IP that hits a page.
    // We want to know unique visitors and support fast blocklist checks.
    std::vector<std::string> accessLog = {
        "192.168.1.10", "10.0.0.5", "192.168.1.10",
        "172.16.0.3",  "10.0.0.5",  "192.168.1.99",
        "172.16.0.3",  "10.0.0.1"
    };

    std::set<std::string> uniqueVisitors;

    for (const std::string& ip : accessLog) {
        // insert() silently ignores duplicates — no if-check needed.
        // It returns a pair<iterator, bool>; the bool is true if actually inserted.
        auto [it, wasInserted] = uniqueVisitors.insert(ip);
        if (wasInserted) {
            std::cout << "New visitor: " << ip << "\n";
        }
    }

    std::cout << "\nTotal unique visitors: " << uniqueVisitors.size() << "\n";

    // Sorted iteration — free, because set is always ordered.
    std::cout << "\n--- All unique IPs (sorted) ---\n";
    for (const std::string& ip : uniqueVisitors) {
        std::cout << ip << "\n";
    }

    // Fast membership test — O(log n), not O(n) like a vector search.
    std::string suspiciousIp = "172.16.0.3";
    if (uniqueVisitors.count(suspiciousIp) > 0) {
        // .count() on a set returns 0 or 1 — sets can't hold duplicates.
        std::cout << "\nAlert: suspicious IP " << suspiciousIp << " accessed the page.\n";
    }

    // Range query: all IPs from "172" up to "192" (exclusive)
    std::cout << "\n--- IPs in range [172..., 192...) ---\n";
    auto low = uniqueVisitors.lower_bound("172");
    auto high = uniqueVisitors.lower_bound("192");
    for (auto it = low; it != high; ++it) {
        std::cout << *it << "\n";
    }

    return 0;
}

#include <iostream>
#include <set>
#include <string>

struct Task {
    int         priority;  // lower number = higher urgency
    std::string name;

    // Overloading operator< lets std::set work without extra setup.
    // Primary sort: by priority. Secondary: by name (breaks ties).
    bool operator<(const Task& other) const {
        if (priority != other.priority) {
            return priority < other.priority; // lower number first
        }
        return name < other.name; // alphabetical tiebreak
    }
};

int main() {
    // A task scheduler that always keeps tasks sorted by urgency.
    // std::set is perfect here: no duplicates, always ordered.
    std::set<Task> taskQueue;

    taskQueue.insert({3, "Send weekly report"});
    taskQueue.insert({1, "Fix production crash"});
    taskQueue.insert({2, "Review pull request"});
    taskQueue.insert({1, "Page on-call engineer"});  // same priority as crash fix
    taskQueue.insert({2, "Review pull request"});    // exact duplicate — silently ignored

    std::cout << "--- Tasks in priority order ---\n";
    for (const Task& task : taskQueue) {
        std::cout << "[P" << task.priority << "] " << task.name << "\n";
    }

    // Show that the duplicate was rejected
    std::cout << "\nTotal tasks in queue: " << taskQueue.size()
              << " (duplicate was silently dropped)\n";

    // Find the most urgent task without removing it
    const Task& mostUrgent = *taskQueue.begin();
    std::cout << "\nMost urgent task: [P" << mostUrgent.priority
              << "] " << mostUrgent.name << "\n";

    return 0;
}

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

int main() {
    // Inserting the same data into both containers to show the ordering difference.
    std::map<std::string, int>           orderedScores;   // red-black tree
    std::unordered_map<std::string, int> hashedScores;    // hash table

    std::vector<std::pair<std::string,int>> data = {
        {"Charlie", 88}, {"Alice", 95}, {"Bob", 72},
        {"Diana", 91},   {"Eve", 85}
    };

    for (const auto& [name, score] : data) {
        orderedScores[name]  = score;
        hashedScores[name]   = score;
    }

    // std::map always iterates in sorted key order.
    std::cout << "--- std::map (sorted by name) ---\n";
    for (const auto& [name, score] : orderedScores) {
        std::cout << name << ": " << score << "\n";
    }

    // std::unordered_map iterates in unpredictable bucket order.
    std::cout << "\n--- std::unordered_map (insertion order NOT preserved) ---\n";
    for (const auto& [name, score] : hashedScores) {
        std::cout << name << ": " << score << "\n";
    }

    // Range query: names starting with 'A' through 'C' (inclusive)
    // This is trivially efficient on std::map.
    // On unordered_map you'd have to scan every element.
    std::cout << "\n--- std::map range query: names in [A, D) ---\n";
    auto start = orderedScores.lower_bound("A");
    auto end   = orderedScores.lower_bound("D");
    for (auto it = start; it != end; ++it) {
        std::cout << it->first << ": " << it->second << "\n";
    }

    return 0;
}