std::map / std::unordered_map

// std::map — Key must satisfy LessThanComparable (operator< or custom Compare)
template<
    class Key,
    class T,
    class Compare   = std::less<Key>,                              // C++98
    class Allocator = std::allocator<std::pair<const Key, T>>
> class map;

// std::unordered_map — Key must satisfy Hash and EqualityComparable
template<
    class Key,
    class T,
    class Hash      = std::hash<Key>,                             // C++11
    class KeyEqual  = std::equal_to<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>
> class unordered_map;

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

std::map<std::string, std::vector<int>> m;

// --- insert(value) --------------------------------------------------------
// C++98. Inserts only if key is absent. Returns {iterator, bool}.
// The pair is constructed before the call, even if the key already exists —
// a wasted construction if key is present.
auto [it1, ok1] = m.insert({"alpha", {1, 2, 3}});  // C++17 structured bindings
// ok1 == true  → inserted; ok1 == false → key existed, nothing changed.

// --- emplace(args...) ------------------------------------------------------
// C++11. Constructs in-place from forwarded arguments. Avoids one copy vs.
// insert(). Still constructs the value before checking key existence.
auto [it2, ok2] = m.emplace("beta", std::vector<int>{4, 5});

// --- try_emplace(key, args...) --------------------------------------------
// C++17. Constructs the VALUE in-place ONLY if the key is absent. If the
// key already exists, the arguments are left untouched — no move, no copy,
// no construction+destruction cycle. Strictly preferable over operator[] or
// emplace for conditional insertion with expensive or move-only values.
auto [it3, ok3] = m.try_emplace("gamma", std::initializer_list<int>{6, 7});
m.try_emplace("gamma", std::initializer_list<int>{99});  // key exists → {6,7} kept, {99} never built

// --- insert_or_assign(key, val) -------------------------------------------
// C++17. Always assigns the value, whether the key is new or not.
// Returns {iterator, bool}: bool is true if inserted, false if assigned.
// Semantically equivalent to operator[] + assignment, but works on rvalues
// and does not require DefaultConstructible.
auto [it4, ok4] = m.insert_or_assign("alpha", std::vector<int>{10, 11});
// ok4 == false → "alpha" existed and was overwritten

// --- operator[] -----------------------------------------------------------
// C++98. Default-constructs the value if key is absent, THEN returns a ref.
// Never use for existence checks — it mutates the map unconditionally.
m["delta"].push_back(42);  // ok: intentional default-init + modify pattern

#include <map>
#include <string>

std::map<std::string, int> scores{
    {"Alice", 95}, {"Bob", 87}, {"Carol", 72}
};

// --- find(key) --- C++98 ---------------------------------------------------
// Returns an iterator to the element, or end() if not found.
// Prefer this when you need the iterator (to modify the value, erase, etc.).
if (auto it = scores.find("Alice"); it != scores.end()) {   // C++17 init-if
    std::cout << it->second << '\n';   // 95
}

// --- count(key) --- C++98 --------------------------------------------------
// Returns 0 or 1 for std::map (always unique keys).
// Exists primarily for multimap compatibility. Avoid in new code.
bool exists = scores.count("Bob") > 0;  // C++98 idiom

// --- contains(key) --- C++20 -----------------------------------------------
// Returns bool directly. Clearer intent than count() > 0. No insertion.
if (scores.contains("Carol")) { ... }   // C++20 — preferred existence check

// --- lower_bound / upper_bound --- C++98 -----------------------------------
// lower_bound(k): first element with key >= k
// upper_bound(k): first element with key >  k
// Both return end() if no such element exists.
auto lo = scores.lower_bound("Bob");    // → "Bob" entry
auto hi = scores.upper_bound("Bob");    // → "Carol" entry (first after "Bob")

// Iterate the closed interval ["Bob", "Carol"]:
for (auto it = scores.lower_bound("Bob"); it != scores.upper_bound("Carol"); ++it) {
    std::cout << it->first << ": " << it->second << '\n';
}

// --- equal_range(key) --- C++98 --------------------------------------------
// Returns std::pair{lower_bound(key), upper_bound(key)} in one call.
// For std::map the range contains at most one element. Most useful for multimap.
auto [beg, end] = scores.equal_range("Alice");  // C++17 structured bindings
for (auto it = beg; it != end; ++it) {
    std::cout << it->second << '\n';   // 95
}

#include <map>
#include <string>

std::map<int, std::string> m{{1,"one"},{2,"two"},{3,"three"}};

// --- Rename a key (the classic node-handle use case) ----------------------
auto node = m.extract(2);       // removes node from m; no allocation or copy
// node.key() returns a non-const reference — mutation is legal here
node.key() = 42;
m.insert(std::move(node));      // spliced back in; no allocation or copy
// m is now: {1:"one", 3:"three", 42:"two"}

// --- Transfer nodes between maps ------------------------------------------
std::map<int, std::string> src{{10,"a"},{20,"b"},{30,"c"}};
std::map<int, std::string> dst{{20,"X"}};

// insert() with a node_type returns an insert_return_type {position, inserted, node}
auto result = dst.insert(src.extract(10));   // 10 not in dst → inserted
// result.inserted == true; result.node is empty

auto result2 = dst.insert(src.extract(20));  // 20 already in dst → not inserted
// result2.inserted == false; result2.node holds the extracted {20,"b"} — not lost!

// --- merge() ---------------------------------------------------------------
// C++17. Moves all nodes from src whose keys are not in dst. Conflicting nodes
// stay in src. No allocations or value copies occur.
std::map<int,std::string> a{{1,"a"},{2,"b"}};
std::map<int,std::string> b{{2,"X"},{3,"c"}};
a.merge(b);
// a → {1:"a", 2:"b", 3:"c"}   (3 transferred)
// b → {2:"X"}                  (2 stayed — conflict)

#include <map>
#include <string>
#include <string_view>

// Without heterogeneous lookup — constructs a temporary std::string each call
std::map<std::string, int> m1{{"hello", 1}};
m1.find("hello");           // constructs std::string("hello") — C++98

// With heterogeneous lookup — zero allocation
std::map<std::string, int, std::less<>> m2{{"hello", 1}};  // C++14
std::string_view sv = "hello";
m2.find(sv);                // no std::string constructed — C++14
m2.contains(sv);            // C++20 + C++14 transparent comparator
m2.lower_bound("he");       // C++14 transparent — string_view or const char* accepted

#include <map>
#include <string>
#include <cctype>
#include <algorithm>

struct CaseInsensitiveLess {
    // is_transparent opts-in to heterogeneous lookup in std::map
    using is_transparent = void;

    bool operator()(std::string_view a, std::string_view b) const noexcept {
        return std::lexicographical_compare(
            a.begin(), a.end(),
            b.begin(), b.end(),
            [](unsigned char x, unsigned char y) {
                return std::tolower(x) < std::tolower(y);
            }
        );
    }
};

std::map<std::string, int, CaseInsensitiveLess> m;
m["Hello"] = 1;
m.find("HELLO");   // finds "Hello" — no new std::string constructed
m.find("hello");   // same element

#include <unordered_map>
#include <string>
#include <string_view>

struct SvHash {
    using is_transparent = void;
    size_t operator()(std::string_view sv) const noexcept {
        return std::hash<std::string_view>{}(sv);
    }
    size_t operator()(const std::string& s) const noexcept {
        return std::hash<std::string_view>{}(s);
    }
};

struct SvEqual {
    using is_transparent = void;
    bool operator()(std::string_view a, std::string_view b) const noexcept {
        return a == b;
    }
};

// C++20: both Hash and KeyEqual must have is_transparent
std::unordered_map<std::string, int, SvHash, SvEqual> um;
um["world"] = 42;

std::string_view sv = "world";
um.find(sv);        // zero allocation — C++20
um.contains(sv);    // zero allocation — C++20

#include <unordered_map>
#include <functional>

struct Point { int x, y; };

// Specialise std::hash in namespace std for seamless integration
namespace std {
    template<>
    struct hash<Point> {
        size_t operator()(const Point& p) const noexcept {
            // Boost-style hash_combine using the golden ratio constant 0x9e3779b9
            size_t h = std::hash<int>{}(p.x);
            h ^= std::hash<int>{}(p.y) + 0x9e3779b9 + (h << 6) + (h >> 2);
            return h;
        }
    };
}

std::unordered_map<Point, double> distances;
distances[{0, 0}] = 0.0;
distances[{3, 4}] = 5.0;

struct PointHash {
    size_t operator()(const Point& p) const noexcept {
        size_t h = std::hash<int>{}(p.x);
        h ^= std::hash<int>{}(p.y) + 0x9e3779b9 + (h << 6) + (h >> 2);
        return h;
    }
};

struct PointEqual {
    bool operator()(const Point& a, const Point& b) const noexcept {
        return a.x == b.x && a.y == b.y;
    }
};

std::unordered_map<Point, double, PointHash, PointEqual> dist2;

std::unordered_map<std::string, int> freq;
freq.reserve(50'000);           // pre-allocates buckets; prevents rehashing during bulk insert
freq.max_load_factor(0.5f);     // rehash when load > 0.5; lower = fewer collisions, more memory
                                // default max_load_factor is 1.0

#include <flat_map>   // C++23

// Construction from existing sorted data — O(n), no sorting needed
// Mark with std::sorted_unique to skip the sort step
std::vector<int>         keys   = {1, 3, 5, 7, 10};
std::vector<std::string> values = {"one","three","five","seven","ten"};

std::flat_map<int, std::string> fm(
    std::sorted_unique,          // C++23: assert data is already sorted+unique
    std::move(keys),
    std::move(values)
);

// Lookup is identical to std::map
auto it = fm.find(5);            // O(log n) binary search over contiguous keys
fm.contains(7);                  // C++20 + C++23

// Batch insertion is efficient; random one-at-a-time insertion is not
fm.insert(fm.end(), {12, "twelve"});  // hint at end() for amortized O(1) when appending

// Underlying containers are accessible
auto& ks = fm.keys();            // const ref to the sorted key vector
auto& vs = fm.values();          // const ref to the value vector

// WRONG — iterator i is invalidated by insert
auto i = fm.find(3);
fm[15] = "fifteen";    // insertion shifts everything; i is dangling
std::cout << i->second;  // undefined behaviour

// CORRECT — re-look up after mutation
fm[15] = "fifteen";
auto j = fm.find(3);   // safe

// Safe erase-while-iterating for std::map and std::unordered_map:
// erase() returns the next valid iterator in C++11 and later.
for (auto it = m.begin(); it != m.end(); ) {
    if (shouldErase(it->second)) {
        it = m.erase(it);    // C++11: erase returns next iterator
    } else {
        ++it;
    }
}

// For std::flat_map, prefer the erase-remove idiom or rebuild from scratch
// if erasing many elements, since each individual erase is O(n).

#include <map>
#include <string>

std::map<std::string, int> scores{{"Alice", 95}, {"Bob", 87}, {"Carol", 72}};

// Read-only iteration — preferred; avoids accidental modification
for (const auto& [name, score] : scores) {        // C++17
    std::cout << name << ": " << score << '\n';
}

// Mutating values — auto& binds to the pair; v is a ref to pair.second
for (auto& [name, score] : scores) {
    score += 5;   // modifies in-place — correct
}

// Common mistake: auto (by value) silently copies, mutation is a no-op
for (auto [name, score] : scores) {               // copies each pair
    score = 0;    // modifies the copy only — silent no-op on the map
}

// Structured bindings also work with insert/emplace return values
auto [it, inserted] = scores.try_emplace("Dave", 88);  // C++17
if (inserted) {
    std::cout << "Added " << it->first << '\n';
}

// And with equal_range
auto [lo, hi] = scores.equal_range("Bob");
for (auto it = lo; it != hi; ++it) {
    std::cout << it->second << '\n';
}

std::map<std::string, int> m;
if (m["missing"]) { ... }    // "missing" → 0 is now in the map — silent mutation
// Fix: m.contains("missing") in C++20, or m.find("missing") != m.end()

std::flat_map<int, int> fm{{1,10},{2,20},{3,30}};
auto it = fm.find(2);
fm[4] = 40;            // insertion invalidates it
it->second;            // undefined behaviour — it is dangling

// Safe erase-during-iteration for both containers:
for (auto it = m.begin(); it != m.end(); ) {
    it = shouldErase(it->second) ? m.erase(it) : std::next(it);
}

for (auto& [k, v] : m)       { v = 0; }   // modifies values in-place — correct
for (auto  [k, v] : m)       { v = 0; }   // modifies a copy — silent no-op
for (const auto& [k, v] : m) { ... }      // read-only — preferred

// WRONG — only hash is transparent; heterogeneous lookup silently disabled
struct HalfTransparentHash {
    using is_transparent = void;
    size_t operator()(std::string_view sv) const { return std::hash<std::string_view>{}(sv); }
};
// KeyEqual = std::equal_to<std::string> — no is_transparent → heterogeneous lookup disabled

std::unordered_map<std::string, int, HalfTransparentHash> broken;
std::string_view sv = "key";
broken.find(sv);  // still constructs a temporary std::string — no error, no warning