Unordered Map and Set

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string>
using namespace std;

int main() {
    // Unordered Map
    unordered_map<string, int> wordCount;
    
    wordCount["hello"] = 3;
    wordCount["world"] = 2;
    wordCount["c++"] = 5;
    wordCount["programming"] = 1;
    
    cout << "Unordered Map (Hash Map):" << endl;
    for (const auto& pair : wordCount) {
        cout << pair.first << ": " << pair.second << endl;
    }
    
    // Access
    cout << "\nCount of 'c++': " << wordCount["c++"] << endl;
    
    // Check if key exists
    if (wordCount.find("hello") != wordCount.end()) {
        cout << "'hello' found" << endl;
    }
    
    // Unordered Set
    unordered_set<int> numbers;
    
    numbers.insert(5);
    numbers.insert(2);
    numbers.insert(8);
    numbers.insert(1);
    numbers.insert(5);  // Duplicate ignored
    
    cout << "\nUnordered Set (Hash Set): ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;
    
    // Check if element exists
    if (numbers.find(8) != numbers.end()) {
        cout << "Element 8 found" << endl;
    }
    
    // Size
    cout << "Set size: " << numbers.size() << endl;
    
    // Bucket information (hash table details)
    cout << "\nHash table info:" << endl;
    cout << "Number of buckets: " << numbers.bucket_count() << endl;
    cout << "Load factor: " << numbers.load_factor() << endl;
    
    return 0;
}

Unordered Map (Hash Map):
programming: 1
c++: 5
world: 2
hello: 3

Count of 'c++': 5
'hello' found

Unordered Set (Hash Set): 1 8 2 5
Element 8 found
Set size: 4

Hash table info:
Number of buckets: 8
Load factor: 0.5

This program teaches you how to use Unordered Map and Unordered Set in C++. These containers use hash tables for O(1) average case operations, making them faster than ordered map/set when sorting is not required. They don't maintain sorted order but provide extremely fast lookups.

---

1. What This Program Does

The program demonstrates unordered containers:

• Unordered Map: key-value pairs with hash table
• Unordered Set: unique elements with hash table
• Fast insert, find, and erase operations
• Hash table information (buckets, load factor)

Unordered containers provide O(1) average case performance.

---

2. Header Files Used

1. #include <iostream>

   • Provides cout and cin for input/output operations.

2. #include <unordered_map>

   • Provides unordered_map container class.

3. #include <unordered_set>

   • Provides unordered_set container class.

4. #include <string>

   • Provides string class for string keys.

---

3. Understanding Unordered Containers

Hash Table Concept:

• Uses hash function to map keys to buckets
• O(1) average case operations
• No automatic sorting
• Faster than ordered containers for lookups

Key Features:

• Fast access (O(1) average)
• No sorted order
• Hash-based storage
• Collision handling

---

4. Unordered Map

Declaration:

unordered_map<string, int> wordCount;

Inserting:

wordCount["hello"] = 3; wordCount["world"] = 2;

How it works:

• Key-value pairs stored in hash table
• Fast lookup by key
• No sorted order
• O(1) average insert/find

---

5. Accessing Unordered Map

Using [] Operator:

int count = wordCount["c++"];

Using find():

auto it = wordCount.find("hello"); if (it != wordCount.end()) { // Key found }

How it works:

• [] operator: creates if missing, returns value
• find(): returns iterator, end() if not found
• O(1) average case
• Fast key-based access

---

6. Unordered Set

Declaration:

unordered_set<int> numbers;

Inserting:

numbers.insert(5); numbers.insert(2); numbers.insert(5); // Duplicate ignored

How it works:

• Stores unique elements
• No sorted order
• Fast membership testing
• O(1) average insert/find

---

7. Hash Table Information

Bucket Information:

numbers.bucket_count() // Number of buckets numbers.load_factor() // Average elements per bucket

How it works:

• Buckets: hash table slots
• Load factor: elements/buckets ratio
• Lower load factor = better performance
• Rehashing occurs when load factor high

---

8. When to Use Unordered Containers

Best For:

• Fast lookups (order doesn't matter)
• Hash-based operations
• When sorting not needed
• Performance-critical lookups
• Dictionary-like structures

Example Scenarios:

• Word frequency counting
• Fast membership testing
• Cache implementations
• Symbol tables
• Fast key-value lookups

---

9. Important Considerations

Performance:

• Average case: O(1)
• Worst case: O(n) (hash collisions)
• Faster than map/set for lookups
• Slower for range queries

No Sorting:

• Elements not sorted
• Cannot iterate in sorted order
• Use map/set if sorting needed
• Trade-off: speed vs order

Hash Collisions:

• Multiple keys map to same bucket
• Handled automatically
• Can degrade to O(n) worst case
• Good hash function important

---

10. return 0;

This ends the program successfully.

---

Summary

• Unordered map/set: hash table-based containers, O(1) average case operations.
• No sorted order maintained, faster than ordered containers for lookups.
• Operations: insert(), find(), erase() - all O(1) average.
• Hash collisions can degrade to O(n) worst case.
• Understanding unordered containers enables fast, hash-based data storage.
• Essential when order doesn't matter and fast access is critical.

This program is fundamental for learning hash-based containers, understanding performance trade-offs, and preparing for high-performance data structures in C++ programs.