In this lesson, we will explore the concept and practical application of HashMaps in C++. HashMaps, known as unordered_map in C++, are a powerful and efficient data structure used for storing key-value pairs. You will learn how to utilize unordered_map to count the frequency of elements in a collection, understand the underlying mechanics, and analyze the time and space efficiency of this approach. This lesson includes a step-by-step demonstration with detailed code examples and a discussion on the practical applications of using HashMaps for counting occurrences in various contexts.

We begin in a library, where we want to count book copies. With a small collection, we might be able to tally each one manually. However, as the collection grows, this approach becomes cumbersome and inefficient. A more efficient method uses a HashMap, known as unordered_map in C++.

For a quick illustration, consider this list of colors:

C++
Copy to clipboard
1#include <vector>
2#include <string>
3
4std::vector<std::string> colors = {"red", "blue", "red", "green", "blue", "blue"};

If we count manually, red appears twice, blue appears thrice, and green appears once. We can employ HashMaps for a more efficient counting process.

Simple yet powerful, HashMaps allow us to store and retrieve data using keys. The unique colors in our list act as keys, and the count of each color becomes its corresponding value. Let's demonstrate how we can count elements in our colors list using a C++ unordered_map:

C++
Copy to clipboard
1#include <iostream>
2#include <unordered_map>
3#include <vector>
4#include <string>
5
6int main() {
7    std::vector<std::string> colors = {"red", "blue", "red", "green", "blue", "blue"};
8    std::unordered_map<std::string, int> color_map;
9
10    // Start the loop to iterate over each color
11    for (const auto& color : colors) {
12
13        // If the color is present in our unordered_map, increment its value by 1
14        if (color_map.find(color) != color_map.end()) {
15            color_map[color] += 1;
16        } else {
17            // If the color isn't present, it means we're encountering this color in our list for the first time.
18            // In this case, we add it to our unordered_map and set its value to 1
19            color_map[color] = 1;
20        }
21    }
22
23    // Print our unordered_map with counts
24    for (const auto& pair : color_map) {
25        std::cout << pair.first << ": " << pair.second << std::endl;
26    }
27
28    return 0;
29}

When the above code executes, it displays the counts for each color:

Copy to clipboard
1red: 2
2blue: 3
3green: 1

Here's how we created an unordered_map to count our elements:

We began with an empty unordered_map. Then, we went through our list, and for every occurring element, we simply incremented its value in the unordered_map. If the element was not already in the unordered_map, it would be added with a default value of 0, which is then incremented to 1.

Default values in C++ for integral types (such as int) are 0, meaning that when we access a key in an unordered_map that does not yet exist, it is automatically added with a value of 0. Therefore, our optimized code can be simplified without the need for explicit presence checks.

Here's the optimized code:

C++
Copy to clipboard
1#include <iostream>
2#include <unordered_map>
3#include <vector>
4#include <string>
5
6int main() {
7    std::vector<std::string> colors = {"red", "blue", "red", "green", "blue", "blue"};
8    std::unordered_map<std::string, int> color_map;
9
10    // Iterate over each color and increase its count
11    for (const auto& color : colors) {
12        color_map[color] += 1;
13    }
14
15    // Print our unordered_map with counts
16    for (const auto& pair : color_map) {
17        std::cout << pair.first << ": " << pair.second << std::endl;
18    }
19
20    return 0;
21}

This optimized approach leverages the default value of 0 for int types in C++ unordered_map, eliminating the need for conditional checks and streamlining the logic. Consequently, the code efficiently counts the colors in our list, showcasing how efficient counting can be even as the list size increases!

The time complexity of our approach is O(n), where n is the number of elements in our list. This is because we iterate over our list exactly once, performing constant-time operations for each element. Here is why:

• Accesses to the unordered_map (both setting a value and getting a value) in C++ are typically O(1), constant-time operations.
• The for loop iterates over each element in the list exactly once, so it is an O(n) operation.

The total time complexity, therefore, remains O(n) because the time taken is directly proportional to the number of items in the list. As the size of the list increases, the time taken scales linearly, making this approach efficient for larger collections.

It is also worth noting that the space complexity of this approach is O(k), where k is the number of unique elements in the list. In the worst-case scenario, where all elements are unique, the space complexity would be O(n).

In conclusion, using HashMaps or unordered_map for counting is a time-efficient approach, especially when working with large datasets.

This approach can be applied to larger lists, strings, and nested collections to count elements. Counting is a ubiquitous task in areas like data analysis and natural language processing. You can employ this concept to count the frequency of words in sentences, characters in strings, or items in shopping lists.

Now, let's solidify the concept of counting occurrences using HashMaps with hands-on exercises. The core of this lesson has shown you how unordered_map can be used for efficient element counting. They are beneficial for enhancing code performance and organization!