# 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

```cpp
unordered_map<KeyType, ValueType> mp;
```

Example:

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

Storage (order is not guaranteed):

```plaintext
"Bob"   → 25
"Alice" → 20
```

---

## 🔹 Common Operations & Complexity

| Operation | Code Example | Avg Time | Worst Time |
| --- | --- | --- | --- |
| Insert | `mp[key] = value;` or `mp.insert({key,value});` | O(1) | O(n) |
| Access (by key) | `mp[key]` | O(1) | O(n) |
| Search | `mp.find(key)` | O(1) | O(n) |
| Erase | `mp.erase(key)` | O(1) | O(n) |
| Size | `mp.size()` | O(1) | O(1) |
| Iterate | `for (auto &p: mp) ...` | O(n) | O(n) |

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

---

## 🔹 Example

```cpp
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

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

---

## 🔹 Iteration

```cpp
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`

| Feature | `map` (Red-Black Tree) | `unordered_map` (Hash Table) |
| --- | --- | --- |
| Order of keys | Sorted | No order |
| Lookup/Insert/Erase | O(log n) | O(1) average, O(n) worst |
| Use case | Need ordering, ranges | Just need fast lookups |
| Memory | Lower | Higher (hash overhead) |

---

## 🔹 Typical LeetCode Use Cases

* **Two Sum** (store number → index for O(n) solution).
    
* **Counting frequency** of elements.
    
    ```cpp
    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.
    

---