In this OpenGenus article, we will look at the various ways of deleting elements in an unordered map in C++.

Table Of Contents-

1. Introduction to C++ STL
2. Background on unordered maps
3. Various ways to delete an element in unordered map in C++
4. Solving a few examples
5. Conclusion

C++ Standard Template Library (STL) provides a powerful and versatile data structure known as unordered_map, which is an implementation of a hash table. It allows fast access to elements using keys. While inserting and accessing elements in an unordered map are straightforward operations, deleting elements can be a bit nuanced. In this article, we will explore various methods to delete elements from an unordered map in C++ STL.

Background on unordered maps:

Before delving into the deletion techniques, let's briefly recap the basics of unordered_map. It is part of the C++ Standard Template Library and falls under the category of associative containers. The key characteristics of unordered_map include:

Fast Retrieval: Elements in an std::unordered_map are stored based on their hash values, which allows for quick retrieval of values associated with specific keys.

Unique Keys: Keys in an std::unordered_map are unique, ensuring that each key is associated with only one value.

Dynamic Sizing: The container dynamically resizes itself to accommodate the number of elements, providing efficiency in terms of memory usage.

Given these characteristics, deleting elements from an std::unordered_map involves considerations related to key-value pairs and the specific requirements of the task at hand.

Various ways to delete elements:

1. Using the erase Member Function
2. Using the Iterative Precision with erase() by Iterator
3. Empowering erase() with a Range
4. Swift Annihilation via clear()

Now let's look at each of these ways in detail down below -

1. Using the erase Member Function-
   The most common and straightforward way to delete an element from an unordered map is by using the erase member function. The erase function takes either an iterator or a key as an argument and removes the corresponding element.

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<int,string> map;

    // Insert some key-value pairs
    map[1] = "One";
    map[2] = "Two";
    map[3] = "Three";
    map[4] = "Four";

    // Erase an element with a specific key
    myMap.erase(2);

    // Display the map after deletion
    for (const auto& pair : myMap) {
    cout << pair.first << ": " << pair.second << endl;
    }
    return 0;
 }

OUTPUT-

1: One
3. Three
4. Four

In this example, the erase() function is used to remove the key-value pair with the key 2. After the deletion, the remaining elements are displayed.

Time Complexity-
Average Case: O(1)
Worst Case: O(n), where n is the number of elements in the container. This occurs when there are hash collisions, and the elements are stored in the same bucket.

2. Using the Iterative Precision with erase() by Iterator-

Iterators provide a more granular control over deletion, allowing for precise removal of specific elements. For some background, iterators are a fundamental concept in C++ that provide a way to iterate over elements in a container. They act as pointers to elements within a container, allowing you to navigate through the elements and perform various operations.

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
    unordered_map<int, string> myMap;

    // Inserting key-value pairs
    myMap[1] = "One";
    myMap[2] = "Two";
    myMap[3] = "Three";
    myMap[4] = "Four";

    // Deleting an element using erase() by iterator
    auto it = myMap.find(3);
    if (it != myMap.end()) {
         myMap.erase(it);
    }

    // Displaying the modified map
    for (const auto& pair : myMap) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

OUTPUT-

1. One
2.  Two
4. Four

In this example, an iterator is employed to target and delete the element with the key 3, showcasing the finesse of iterators in element removal.

Time Complexity-
O(M) as it will be linear in the number of elements in the specified range. O(m), where m is the number of elements in the range [startIterator, endIterator].

3. Empowering erase() with a Range-
   The erase() function's prowess extends to handling ranges specified by iterators. This proves advantageous when removing multiple elements.

#include <iostream>
#include <unordered_map>
using namespace std;
    
int main() {
    unordered_map<int, string> myMap;

    // Inserting key-value pairs
    myMap[1] = "One"
    myMap[2] = "Two";
    myMap[3] = "Three";
    myMap[4] = "Four";

    // Deleting elements using erase() with a range
    auto start = myMap.find(2);
    auto end = myMap.find(4);

    if (start != myMap.end() && end != myMap.end()) {
           myMap.erase(start, end);
    }

    // Displaying the modified map
    for (const auto& pair : myMap) {
          cout << pair.first << ": " << pair.second << endl;
    }

     return 0;
}

OUTPUT-

1. One
4. Four

In this example, elements with keys 2 and 3 gracefully exit the unordered_map.

Please Note: The element with key-value 4 will not get deleted here because the erase function in range does not include the last value provided in the range.

Time Complexity-
O(M) as it will be linear in the number of elements in the specified range. O(m), where m is the number of elements in the range [startIterator, endIterator].

4. Swift Annihilation via clear()-
   For a decisive sweep, the clear() function clears all elements, rendering the unordered_map empty.

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<int, string> myMap;

    // Inserting key-value pairs
    myMap[1] = "One";
    myMap[2] = "Two";
    myMap[3] = "Three";
    myMap[4] = "Four";

    // Clearing all elements from the map
    myMap.clear();

    // Displaying the modified map (now empty)
    for (const auto& pair : myMap) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

OUTPUT-

Nothing will be displayed as all the elements of the map is completely deleted so it has no element in it now to display as an output. Remember the map is not deleted.

The clear() function ensures a clean slate, leaving the unordered_map devoid of any remnants.

Time Complexity-
O(N) that is linear in the number of elements in the container. O(n), where n is the number of elements.

Conclusion

Deleting elements from an unordered_map in C++ can be achieved using various methods. The appropriate method depends on the specific requirements of your code. Whether you want to delete a single element, a range of elements, or clear the entire map, the C++ STL provides flexible and efficient options for managing an unordered_map in your programs. Understanding these methods allows you to write cleaner and more efficient code when working with hash tables in C++.