8. Map

---

// ── ABOUT ────────────────────────────────────────────────────────
// Stores key-value pairs, UNIQUE keys, sorted by key (ascending)
// insert / find / erase / access → O(log n)
 
// ── CREATE & INSERT ──────────────────────────────────────────────
map<int, string> m;
m[1] = "abc";                            // O(log n) → insert or overwrite
m[5] = "ded";
m[3] = "efd";
m[5] = "sof";                            // overwrites existing key
m.insert({2, "omm"});                    // insert pair
 
// ── ITERATE ──────────────────────────────────────────────────────
for (auto &pair : m)
    cout << pair.first << " " << pair.second << " | ";
// always in sorted key order: 1 2 3 5
 
// ── FIND ─────────────────────────────────────────────────────────
auto f = m.find(5);                      // O(log n) → returns iterator
if (f == m.end())
    cout << "not found";
else
    cout << f->first << " = " << f->second;
 
// ── ACCESS ───────────────────────────────────────────────────────
cout << m[5];                            // O(log n) → "sof"
cout << m[-1];                           // WARNING: creates key -1 with default value!
                                         // use find() if you're not sure key exists
 
// ── ERASE ────────────────────────────────────────────────────────
m.erase(3);                              // by key   O(log n)
auto er = m.find(3);
m.erase(er);                             // by iterator
 
// ── SIZE ─────────────────────────────────────────────────────────
cout << m.size();                        // O(1)
 
// ── SUMMARY ──────────────────────────────────────────────────────
// set  → unique keys only
// map  → unique keys, each with a value
// both ordered → O(log n)
// unordered variants → O(1) average

---