C++ unordered_map

---

Introduction

In C++, std::unordered_map is an associative container in the C++ Standard Library that stores key-value pairs using a hash table. Unlike std::map, which stores its elements in sorted order, an unordered_map does not guarantee any specific order of elements. It provides constant-time average complexity (O(1)) for insertions, deletions, and lookups on average due to its underlying hash-based implementation.

---

Syntax

The syntax to declare an unordered_map is:

Copy Codestd::unordered_map<KeyType, ValueType> unordered_map_name;

Where:

• KeyType: The type of the key (e.g., int, std::string).
• ValueType: The type of the value associated with each key.

You can also specify a custom hash function and comparison function:

Copy Codestd::unordered_map<KeyType, ValueType, Hash, Compare> unordered_map_name;

Where:

• Hash: A function object or function that defines how the keys should be hashed.
• Compare: A custom comparison function for keys (though it's not commonly required, as unordered_map uses a default comparator for equality checking).

---

Declaring and Initializing an Unordered Map

Example 1: Basic Unordered Map Declaration

Copy Code#include <iostream>
#include <unordered_map>

int main() {
    // Declare an unordered map with int keys and string values
    std::unordered_map<int, std::string> umap;

    // Insert elements into the unordered map
    umap[1] = "Apple";
    umap[2] = "Banana";
    umap[3] = "Cherry";
    umap[4] = "Date";

    // Displaying the elements of the unordered map
    for (const auto& pair : umap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

Output:

Copy Code1: Apple
2: Banana
3: Cherry
4: Date

Note: The order in which the elements are displayed is not guaranteed because unordered_map does not maintain any specific order.

---

Operations on Unordered Maps

1. Insert Elements

You can insert elements into an unordered_map using either the bracket operator [] or the insert() method.

• Using [] operator:

  Copy Codeumap[5] = "Elderberry";  // Insert element with key 5 and value "Elderberry"
  

• Using insert() method:

  Copy Codeumap.insert({6, "Fig"});  // Insert key 6 with value "Fig"
  

2. Find Elements

You can search for an element in the unordered map using the find() method. This returns an iterator to the element with the given key or unordered_map::end() if the key is not found.

Copy Codeauto it = umap.find(3);  // Search for the key 3
if (it != umap.end()) {
    std::cout << "Found: " << it->first << " => " << it->second << std::endl;
} else {
    std::cout << "Key not found!" << std::endl;
}

3. Erase Elements

You can remove an element by key or by iterator.

• Remove by key:

  Copy Codeumap.erase(2);  // Removes the element with key 2
  

• Remove by iterator:

  Copy Codeauto it = umap.find(3);
  umap.erase(it);  // Removes the element pointed to by the iterator
  

4. Count Elements

You can check whether a key exists in the unordered map using the count() method. Since each key can only appear once in an unordered_map, this method will return either 1 (if the key exists) or 0 (if the key doesn't exist).

Copy Codestd::cout << "Count of key 2: " << umap.count(2) << std::endl;  // Output: 1
std::cout << "Count of key 5: " << umap.count(5) << std::endl;  // Output: 1
std::cout << "Count of key 10: " << umap.count(10) << std::endl;  // Output: 0

5. Size and Emptiness

You can check the size of the unordered map and whether it is empty using the size() and empty() methods:

Copy Codestd::cout << "Size of unordered map: " << umap.size() << std::endl;
std::cout << "Is unordered map empty? " << (umap.empty() ? "Yes" : "No") << std::endl;

6. Clear the Unordered Map

You can remove all elements from the unordered map using the clear() method:

Copy Codeumap.clear();  // Removes all elements from the unordered map

---

Iterating Over an Unordered Map

You can iterate over the elements of an unordered map using an iterator or a range-based for loop:

Example 1: Using Iterator

Copy Codefor (auto it = umap.begin(); it != umap.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

Example 2: Using Range-Based For Loop

Copy Codefor (const auto& pair : umap) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

---

Custom Hash Function

In the unordered_map, the keys are hashed to determine their positions in the container. By default, unordered_map uses the hash function provided in the standard library for built-in types such as int, std::string, etc. However, you can define your own hash function if you're using custom types as keys.

Example: Custom Hash Function

Suppose you have a custom class Person and want to use it as a key in an unordered map.

Copy Code#include <iostream>
#include <unordered_map>
#include <string>

class Person {
public:
    std::string name;
    int age;

    Person(std::string name, int age) : name(name), age(age) {}

    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

struct PersonHash {
    size_t operator()(const Person& p) const {
        return std::hash<std::string>()(p.name) ^ std::hash<int>()(p.age);  // Combine hashes of name and age
    }
};

int main() {
    std::unordered_map<Person, std::string, PersonHash> umap;

    umap[Person("Alice", 30)] = "Engineer";
    umap[Person("Bob", 25)] = "Designer";

    for (const auto& pair : umap) {
        std::cout << pair.first.name << " (" << pair.first.age << "): " << pair.second << std::endl;
    }

    return 0;
}

Output:

Copy CodeAlice (30): Engineer
Bob (25): Designer

---

Advantages of Using std::unordered_map

1. Fast Lookups: unordered_map provides average O(1) time complexity for search, insert, and delete operations, making it efficient for large datasets.
2. No Order: Since it does not maintain any order, it is ideal for scenarios where you do not need the elements to be in any specific order, but only need fast access to them by key.
3. Efficient Memory Usage: The hash table implementation is efficient in terms of memory usage and access times.
4. Custom Hashing: You can define custom hash functions for user-defined types, making unordered_map very flexible.

---

When to Use std::unordered_map

Use std::unordered_map when:

• You need fast access to elements by key and don’t care about the order of the elements.
• You are working with a large dataset and need to ensure that insertion, search, and deletion operations are done in average constant time (O(1)).
• You are dealing with custom key types and want to provide a custom hash function.

---

---