unordered_map in C++

---

🔹 What is unordered_map?

• A key → value container from C++ STL.

• Similar to map, but does NOT store keys in sorted order.

• Keys are stored in buckets using hashing.

• Provides average O(1) lookup, insert, erase (faster than map).

• Order of keys is unpredictable.

👉 Think of it as a hash table implementation of a dictionary.

---

🔹 Syntax

unordered_map<KeyType, ValueType> mp;

Example:

unordered_map<string, int> age;
age["Alice"] = 20;
age["Bob"] = 25;

Storage (order is not guaranteed):

"Bob"   → 25
"Alice" → 20

---

🔹 Common Operations & Complexity

⚠️ Worst-case O(n) happens if many keys land in the same bucket (hash collisions). But in practice, it’s rare.

---

🔹 Example

unordered_map<int, string> mp;
mp[30] = "X";
mp[10] = "Y";
mp[20] = "Z";

// Order is not guaranteed!
// Could print: 20→Z, 30→X, 10→Y

---

🔹 Checking Existence

if (mp.find(20) != mp.end()) {
    cout << "Key 20 found, value = " << mp[20];
}
else {
    cout << "Key 20 not found";
}

---

🔹 Iteration

for (auto &p : mp) {
    cout << p.first << " → " << p.second << endl;
}

⚠️ Unlike map, iteration order is unpredictable (depends on hashing).

---

🔹 Characteristics

1. Unordered → No sorting of keys.

2. Unique keys → Each key is stored only once.

3. Underlying data structure → Hash Table.

4. Fast average operations → O(1).

---

🔹 Advantages (Pros)

✅ Much faster than map for lookups (average O(1)).
✅ Great for frequency counting, existence check, hash-based problems.
✅ Easy syntax like map.

---

🔹 Disadvantages (Cons)

❌ Keys are not stored in order → no range queries, no smallest/largest key.
❌ Slightly more memory usage due to hashing buckets.
❌ Worst-case O(n) time (though rare with good hash functions).
❌ Doesn’t work well with custom complex types unless you define a hash function.

---

🔹 map vs unordered_map

---

🔹 Typical LeetCode Use Cases

• Two Sum (store number → index for O(n) solution).

• Counting frequency of elements.

    unordered_map<int,int> freq;
    for (int x : nums) freq[x]++;
  

• Checking existence in O(1).

• Prefix sums / subarray problems.

• Graph adjacency list (fast access).

---

✅ Summary

• unordered_map = Hash table based key-value store.

• Operations = O(1) average.

• Faster than map if you don’t care about sorting.

• Use in LeetCode most of the time unless the problem needs sorted keys.

---

👉 So:

• Use unordered_map by default for speed.

• Use map if you specifically need sorted keys or range queries.

---