In today's insightful lesson, we will delve into a cornerstone of C++'s data structure ecosystem, the std::unordered_map. Building upon our understanding of std::unordered_set from previous lessons, this session introduces you to the std::unordered_map, a powerful structure that stores key-value pairs. This setup makes the std::unordered_map an ideal choice when swift data access through keys is necessary.

std::unordered_maps utilize the principle of hashing, which enables constant time complexity for several core operations, thereby enhancing their efficiency. By the end of this lesson, you will have gained practical knowledge of creating, manipulating, and understanding the workings of std::unordered_maps, including their implementation and complexity in handling data with the C++ syntax.

Before we commence, let's formally define an std::unordered_map. An std::unordered_map in the world of C++ is a collection that stores key-value pairs grouped by a hash code computed from the key. This means that std::unordered_maps ensure each key is unique and efficiently manage these pairs. std::unordered_maps do not guarantee any specific order for the stored pairs; the order can change over time.

std::unordered_maps function using the principle of hashing. Here, a key is rendered to a hash code by a hash function, and this numeric code identifies the storage location for the key-value pair. Let's visualize a simple creation of an std::unordered_map:

C++
Copy to clipboard
1#include <iostream>
2#include <unordered_map>
3#include <string>
4
5int main() {
6    // Creating the unordered_map
7    std::unordered_map<int, std::string> unordered_map;
8
9    // Adding key-value pairs to the unordered_map
10    unordered_map[1] = "John";
11    unordered_map[2] = "Mike";
12    unordered_map[3] = "Emma";
13
14    // Displaying the contents of the unordered_map
15    std::cout << "unordered_map: " << std::endl;
16    for (const auto& pair : unordered_map) {
17        std::cout << pair.first << ": " << pair.second << std::endl;
18    }
19
20    return 0;
21}

In the above code snippet, we have created an std::unordered_map that maps an int key to a std::string value. We then add three key-value pairs and iterate over the std::unordered_map to print the contents to the console using std::cout.

In std::unordered_maps, hashing takes center stage where the keys are hashed. This hashed value helps us determine where to store the corresponding data.

This mechanism of hashing is what gives the std::unordered_map its name. But the question that arises is: why is hashing important? Through hashing, it becomes possible to achieve constant time complexity, O(1), for retrieving and storing operations in ideal scenarios. This means that std::unordered_maps provide extremely swift data access and insertion functionality — an advantage unrivaled by other data structures.

One thing to note is that due to the hashing mechanism, a std::unordered_map might experience what is known as a hash collision. To handle collisions, C++ implements separate chaining or open addressing strategies to ensure that operations remain efficient.

std::unordered_maps demonstrate an impressive O(1) average time complexity for basic operations — both insertion (setting values) and retrieval. Derived from the concept of hashing, the key's hash code is used directly to store and retrieve elements, eliminating the need for scanning or searching. This gives the std::unordered_map a substantial edge in efficiency.

While it offers efficient time complexity operations, by using a std::unordered_map, we need to be mindful of space complexity as well. The space usage for a std::unordered_map can grow to O(n), where n is the number of elements in the std::unordered_map.

We extend our earlier std::unordered_map example to exhibit these operations:

C++
Copy to clipboard
1#include <iostream>
2#include <unordered_map>
3#include <string>
4
5int main() {
6    std::unordered_map<int, std::string> unordered_map;
7
8    // Adding elements (set operation)
9    unordered_map[1] = "John";
10    unordered_map[2] = "Mike";
11    unordered_map[3] = "Emma";
12
13    // Retrieving an element
14    std::cout << "Element with key 1: " << unordered_map[1] << std::endl;
15    // Output: Element with key 1: John
16
17    // Removing an element
18    unordered_map.erase(2);
19
20    std::cout << "unordered_map after removal operation:" << std::endl;
21    for (const auto& pair : unordered_map) {
22        std::cout << pair.first << ": " << pair.second << std::endl;
23    }
24    // Output: unordered_map after removal operation: 1: John, 3: Emma
25
26    return 0;
27}

Here, we use key indexing to retrieve the value mapped to the provided key and the erase() method to delete the designated key-value pair. It's important to note that erase() does not return a value indicating success or failure; you might want to check if the key exists beforehand if necessary.

Throughout this lesson, you've deepened your understanding of std::unordered_map, exploring its structure and implementation. We've seen the utilization of hashing, which enables std::unordered_map to access elements with remarkable speed. By examining how std::unordered_map handles data and space complexity, you've laid a solid foundation for approaching large datasets in C++.

As you progress further, applying your theoretical knowledge in practical settings is crucial. The upcoming exercises offer an opportunity to put your learnings to use, strengthen your understanding, and prepare you for tackling various coding problems and programming challenges with greater confidence. Let's get started!