Unordered Map & Unordered Multimap

In this tutorial, we will explore the unordered_map and unordered_multimap containers in C++. These are part of the Standard Template Library (STL) and are based on hash tables, providing average O(1) lookup times. Understanding these containers is crucial for efficient data management, especially when dealing with large datasets.

Introduction

The unordered_map and unordered_multimap are associative containers that store elements formed by a combination of a key value and a mapped value, following a specific order. Unlike the ordered maps (map and multimap), which maintain elements in a sorted order based on keys, unordered maps do not guarantee any particular order. This makes them highly efficient for operations like insertion, deletion, and lookup, with an average time complexity of O(1).

These containers are particularly useful when you need fast access to data without the overhead of maintaining order. However, they come with trade-offs in terms of memory usage and potential performance degradation in worst-case scenarios.

Core Content

What is an Unordered Map?

An unordered_map is a container that stores elements formed by the combination of a key value and a mapped value, and which allows for fast retrieval of individual elements based on their keys. The order of elements is not guaranteed to be consistent across different runs of the program.

Key Features

• Fast Lookup: Average O(1) time complexity for insertions, deletions, and lookups.
• No Order Guarantee: Elements are stored in a hash table, which does not maintain any particular order.
• Unique Keys: Each key can only appear once in an unordered_map.

Example Code

Let's see how to use an unordered_map:

1#include <iostream>
2#include <unordered_map>
3 
4int main() {
5  std::unordered_map<std::string, int> ageMap;
6 
7  // Inserting elements
8  ageMap["Alice"] = 30;
9  ageMap["Bob"] = 25;
10  ageMap["Charlie"] = 35;
11 
12  // Accessing elements
13  std::cout << "Age of Alice: " << ageMap["Alice"] << std::endl;
14  std::cout << "Age of Bob: " << ageMap["Bob"] << std::endl;
15 
16  // Checking if a key exists
17  if (ageMap.find("Charlie") != ageMap.end()) {
18      std::cout << "Charlie is in the map." << std::endl;
19  }
20 
21  return 0;
22}

Age of Alice: 30
Age of Bob: 25
Charlie is in the map.

What is an Unordered Multimap?

An unordered_multimap is similar to an unordered_map, but it allows for multiple elements with equivalent keys. This means that you can store multiple values associated with the same key.

Key Features

• Fast Lookup: Average O(1) time complexity for insertions, deletions, and lookups.
• No Order Guarantee: Elements are stored in a hash table, which does not maintain any particular order.
• Multiple Values per Key: Each key can appear multiple times in an unordered_multimap.

Example Code

Let's see how to use an unordered_multimap:

1#include <iostream>
2#include <unordered_map>
3 
4int main() {
5  std::unordered_multimap<std::string, int> ageMap;
6 
7  // Inserting elements
8  ageMap.insert({"Alice", 30});
9  ageMap.insert({"Bob", 25});
10  ageMap.insert({"Alice", 31}); // Duplicate key
11 
12  // Accessing elements
13  auto range = ageMap.equal_range("Alice");
14  for (auto it = range.first; it != range.second; ++it) {
15      std::cout << "Age of Alice: " << it->second << std::endl;
16  }
17 
18  return 0;
19}

Age of Alice: 30
Age of Alice: 31

Unordered Map vs. Map

When to Use unordered_map

• You need fast access times for insertions, deletions, and lookups.
• The order of elements is not important.
• Memory usage is a concern but can be traded off for performance.

When to Use map

• You require the elements to be stored in a sorted order.
• You need to perform range queries or operations that rely on ordering.
• Consistent behavior across different runs (e.g., debugging).

Bucket Interface

Both unordered_map and unordered_multimap provide a bucket interface, which allows you to access the underlying hash table structure. This can be useful for advanced operations like rehashing or customizing the load factor.

Example Code

Let's see how to use the bucket interface:

1#include <iostream>
2#include <unordered_map>
3 
4int main() {
5  std::unordered_map<std::string, int> ageMap;
6 
7  // Inserting elements
8  ageMap["Alice"] = 30;
9  ageMap["Bob"] = 25;
10  ageMap["Charlie"] = 35;
11 
12  // Getting the number of buckets
13  std::cout << "Number of buckets: " << ageMap.bucket_count() << std::endl;
14 
15  // Iterating over elements in a specific bucket
16  for (size_t i = 0; i < ageMap.bucket_count(); ++i) {
17      std::cout << "Bucket #" << i << ": ";
18      for (auto it = ageMap.begin(i); it != ageMap.end(i); ++it) {
19          std::cout << "{" << it->first << ", " << it->second << "} ";
20      }
21      std::cout << std::endl;
22  }
23 
24  return 0;
25}

Number of buckets: 8
Bucket #0: 
Bucket #1: {Charlie, 35} 
Bucket #2: 
Bucket #3: {Alice, 30} 
Bucket #4: 
Bucket #5: 
Bucket #6: {Bob, 25} 
Bucket #7:

Practical Example

Let's create a practical example that demonstrates the use of unordered_map and unordered_multimap. We'll build a simple program that manages a collection of books, where each book has a title and multiple authors.

1#include <iostream>
2#include <unordered_map>
3#include <vector>
4 
5int main() {
6  std::unordered_map<std::string, int> bookPages;
7  std::unordered_multimap<std::string, std::string> authorBooks;
8 
9  // Adding books
10  bookPages["The Great Gatsby"] = 180;
11  bookPages["To Kill a Mockingbird"] = 281;
12  bookPages["1984"] = 328;
13 
14  authorBooks.insert({"F. Scott Fitzgerald", "The Great Gatsby"});
15  authorBooks.insert({"Harper Lee", "To Kill a Mockingbird"});
16  authorBooks.insert({"George Orwell", "1984"});
17  authorBooks.insert({"Ernest Hemingway", "The Old Man and the Sea"});
18 
19  // Displaying books by page count
20  std::cout << "Books by page count:" << std::endl;
21  for (const auto& book : bookPages) {
22      std::cout << book.first << ": " << book.second << " pages" << std::endl;
23  }
24 
25  // Displaying books by author
26  std::cout << "
27Books by author:" << std::endl;
28  for (const auto& author : authorBooks) {
29      std::cout << author.first << " wrote: " << author.second << std::endl;
30  }
31 
32  return 0;
33}

Books by page count:
The Great Gatsby: 180 pages
To Kill a Mockingbird: 281 pages
1984: 328 pages

Books by author:
F. Scott Fitzgerald wrote: The Great Gatsby
Harper Lee wrote: To Kill a Mockingbird
George Orwell wrote: 1984
Ernest Hemingway wrote: The Old Man and the Sea

Summary

• unordered_map: Fast lookup, no order guarantee, unique keys.
• unordered_multimap: Fast lookup, no order guarantee, multiple values per key.
• Use unordered_map when fast access is crucial and order is not important.
• Use map when maintaining a sorted order is necessary.

What's Next?

In the next tutorial, we will explore unordered_set and unordered_multiset, which are unordered versions of the set containers. These containers provide similar performance benefits as unordered_map and unordered_multimap but for unique or multiple elements without associated values.

Stay tuned!