Unordered Map: Container, C++

Unordered Map Container in C++: Usage and Operations

In C++, the unordered_map container is part of the Standard Template Library (STL). It is a dynamic collection that stores key-value pairs, where each key is unique. An unordered_map is implemented using a hash table, ensuring that insertions, deletions, and lookups occur in average constant-time complexity. This makes unordered_map an ideal choice when you need to maintain a collection of key-value pairs with fast access, and when the order of elements doesn't matter.

In this guide, we will explore everything about the unordered_map container, including how to construct unordered maps, perform common operations, and effectively utilize its capabilities in C++.

---

Table of Contents

1. Introduction to Unordered Map in C++
2. Different Ways to Construct an Unordered Map
3. Common Operations on Unordered Map
   • insert()
   • erase()
   • find()
   • count()
   • size()
   • empty()
   • clear()
   • operator[]
4. Working with Custom Data Types
5. Iterators in Unordered Maps
6. Summary and Best Practices

---

1. Introduction to Unordered Map in C++

An unordered_map in C++ is a container that stores key-value pairs, where each key is unique. It is designed for fast retrieval and manipulation of data, making it suitable for scenarios where the order of elements is not important.

Key Features:

• Key-Value Pairs: Each element in an unordered_map is a pair consisting of a key and a value.
• Unique Keys: Each key in the unordered_map must be unique. If a key is inserted again, the existing value will be updated.
• Fast Access: Average constant-time complexity for insertions, deletions, and lookups, due to its hash table-based implementation.
• No Order: Elements are not stored in any specific order, which can make operations faster compared to ordered containers like map.

When to Use:

• Use unordered_map when you need to store key-value pairs and require fast access without caring about the order.
• If you need elements to be in a sorted order, consider using map instead.

---

2. Different Ways to Construct an Unordered Map

You can create an unordered_map in several ways, depending on your requirements.

2.1 Default Constructor

The default constructor creates an empty unordered_map.

unordered_map<int, string> um;

This creates an empty unordered_map that maps integers to strings, which can be populated later.

2.2 Constructor with Initializer List

You can initialize an unordered_map directly with a list of key-value pairs.

unordered_map<int, string> um = {{1, "one"}, {2, "two"}, {3, "three"}};

This creates an unordered_map containing the key-value pairs 1 -> "one", 2 -> "two", and 3 -> "three".

2.3 Constructor with Another Unordered Map

You can create an unordered_map by copying elements from another unordered_map.

unordered_map<int, string> um1 = {{1, "one"}, {2, "two"}};
unordered_map<int, string> um2(um1);  // Initializes um2 as a copy of um1

2.4 Constructor with Another Container

You can create an unordered_map by copying elements from another container, such as a vector of pairs.

vector<pair<int, string>> v = {{1, "one"}, {2, "two"}, {3, "three"}};
unordered_map<int, string> um(v.begin(), v.end());  // Initializes an unordered_map using iterators from a vector

2.5 Assignment Operator

The assignment operator allows you to copy elements from one unordered_map to another.

unordered_map<int, string> um1 = {{1, "one"}, {2, "two"}};
unordered_map<int, string> um2;
um2 = um1;  // Now um2 contains the same key-value pairs as um1

The assignment operator performs a deep copy, meaning the key-value pairs of um1 are fully copied into um2.

---

3. Common Operations on Unordered Map

3.1 insert()

The insert() function adds a key-value pair to the unordered_map. If the key already exists, the value will be updated.

Syntax:

• Insert a single key-value pair:

  um.insert({key, value});

• Insert multiple key-value pairs using an initializer list:

  um.insert({{key1, value1}, {key2, value2}, ...});

• Insert key-value pairs from another container:

  um.insert(container.begin(), container.end());

Example:

unordered_map<int, string> um;

// Insert a single key-value pair
um.insert({1, "one"});  // Inserts 1 -> "one"
um.insert({2, "two"});  // Inserts 2 -> "two"
um.insert({3, "three"});  // Inserts 3 -> "three"

// Insert multiple key-value pairs
um.insert({{4, "four"}, {5, "five"}, {6, "six"}});  // Inserts 4 -> "four", 5 -> "five", and 6 -> "six"

// Insert key-value pairs from another container
vector<pair<int, string>> v = {{7, "seven"}, {8, "eight"}, {9, "nine"}};
um.insert(v.begin(), v.end());  // Inserts 7 -> "seven", 8 -> "eight", and 9 -> "nine"

After these operations, the unordered_map will contain the key-value pairs: {1 -> "one", 2 -> "two", 3 -> "three", 4 -> "four", 5 -> "five", 6 -> "six", 7 -> "seven", 8 -> "eight", 9 -> "nine"}.

3.2 erase()

The erase() function removes a key-value pair from the unordered_map.

Syntax:

• Erase a single key-value pair:

  um.erase(key);

• Erase a key-value pair using an iterator:

  um.erase(iterator);

• Erase a range of key-value pairs:

  um.erase(start_iterator, end_iterator);

Example:

unordered_map<int, string> um = {{1, "one"}, {2, "two"}, {3, "three"}, {4, "four"}, {5, "five"}};

// Erase a single key-value pair
um.erase(2);  // Removes 2 -> "two"

// Erase using an iterator
auto it = um.find(3);
um.erase(it);  // Removes 3 -> "three"

// Erase a range of key-value pairs
um.insert({{1, "one"}, {2, "two"}, {3, "three"}, {4, "four"}, {5, "five"}});  // Reinsert key-value pairs for demonstration
auto start = um.find(1);
auto end = um.find(4);
um.erase(start, end);  // Removes 1 -> "one", 2 -> "two", and 3 -> "three"

After these operations, the unordered_map will contain: {4 -> "four", 5 -> "five"}.

Warning: Avoid using the range version of erase() with unordered_map, as the concept of a range is not well-defined due to the unordered nature of the container. The order of elements is not guaranteed, which can lead to unexpected results when erasing a range.

3.3 find()

The find() function searches for a key in the unordered_map and returns an iterator to the corresponding key-value pair if found, or end() if not found.

Syntax:

auto it = um.find(key);

Example:

unordered_map<int, string> um = {{1, "one"}, {2, "two"}, {3, "three"}};
auto it = um.find(2);
if (it != um.end()) {
    cout << "Key found: " << it->first << " -> " << it->second << endl;  // Outputs: Key found: 2 -> "two"
} else {
    cout << "Key not found." << endl;
}

3.4 count()

The count() function returns the number of occurrences of a key in the unordered_map. Since unordered_map only allows unique keys, it will return either 0 or 1.

Syntax:

size_t count = um.count(key);

Example:

unordered_map<int, string> um = {{1, "one"}, {2, "two"}, {3, "three"}};
cout << "Count of 2: " << um.count(2) << endl;  // Outputs: Count of 2: 1
cout << "Count of 4: " << um.count(4) << endl;  // Outputs: Count of 4: 0

3.5 size()

The size() function returns the number of key-value pairs in the unordered_map.

Syntax:

size_t size = um.size();

Example:

unordered_map<int, string> um = {{1, "one"}, {2, "two"}, {3, "three"}};
cout << "Size: " << um.size() << endl;  // Outputs: Size: 3

3.6 empty()

The empty() function returns a boolean value indicating whether the unordered_map is empty or not.

Syntax:

bool is_empty = um.empty();

Example:

unordered_map<int, string> um;
cout << "Is empty: " << um.empty() << endl;  // Outputs: Is empty: 1 (true)

3.7 clear()

The clear() function removes all elements from the unordered_map.

Syntax:

um.clear();

Example:

unordered_map<int, string> um = {{1, "one"}, {2, "two"}, {3, "three"}};
um.clear();  // Removes all elements from the unordered_map
cout << "Size after clear: " << um.size() << endl;  // Outputs: Size after clear: 0

3.8 operator[]

The operator[] allows you to access the value corresponding to a key, or insert a new key-value pair if the key does not exist.

Syntax:

um[key] = value;

Example:

unordered_map<int, string> um = {{1, "one"}, {2, "two"}};
um[3] = "three";  // Adds 3 -> "three"
cout << "Key 3: " << um[3] << endl;  // Outputs: Key 3: three

---

4. Working with Custom Data Types

You can also use custom data types as keys in an unordered_map. However, since the container relies on hashing, you need to provide a hash function for the custom key type.

Custom Hash Function

To use a custom data type as a key in unordered_map, you need to define a hash function and a comparison function. Here's how:

#include <iostream>
#include <unordered_map>

using namespace std;

struct Person {
    string name;
    int age;

    // Equality operator for custom comparison
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// Custom hash function for Person
struct PersonHash {
    size_t operator()(const Person& p) const {
        return hash<string>()(p.name) ^ hash<int>()(p.age);
    }
};

int main() {
    unordered_map<Person, string, PersonHash> um;

    Person p1{"Alice", 30};
    Person p2{"Bob", 25};

    um[p1] = "Engineer";
    um[p2] = "Doctor";

    cout << "Alice's profession: " << um[p1] << endl;  // Outputs: Alice's profession: Engineer
    cout << "Bob's profession: " << um[p2] << endl;    // Outputs: Bob's profession: Doctor

    return 0;
}

In this example, Person is a custom key type, and PersonHash is a custom hash function.

---

5. Iterators in Unordered Maps

You can iterate through the elements of an unordered_map using iterators.

unordered_map<int, string> um = {{1, "one"}, {2, "two"}, {3, "three"}};

// Using an iterator to iterate
for (auto it = um.begin(); it != um.end(); ++it) {
    cout << it->first << " -> " << it->second << endl;
}

Alternatively, you can use a range-based for loop:

for (const auto& pair : um) {
    cout << pair.first << " -> " << pair.second << endl;
}

---

6. Summary and Best Practices

• Efficiency: unordered_map provides fast access and modification of elements, typically in constant time.
• Order Doesn't Matter: The order of elements is not guaranteed. If order is important, use map instead.
• Custom Types: You can use custom data types as keys by defining an appropriate hash function and equality operator.
• Avoid Range Operations: Be cautious when using operations that involve ranges, as the unordered nature of the container may lead to unexpected results.

By understanding these fundamental operations and features, you can use unordered_map efficiently in C++ to store and manipulate key-value pairs with optimal performance.