Understanding the unordered map in C++

Filed Under: C++
Unordered Map Cpp

In this article, we’ll take a look at using the unordered map data structure in C++.

This is a part of the C++ Standard Template Library (STL), and is a very useful data structure.

Let’s look at this in more detail, using some illustrative examples.


The Unordered Map Data Structure

This is an associative container that can store elements as a key-value pair.

Here, you associate a key with a mapped value. We can access this mapped value through this key.

The advantage of using this data structure is due to it’s very fast insertion and deletion time (O(1) time complexity on average).

Since an unordered map uses a Hash Table, this will directly provide us with very fast access times!

Let’s now understand this, using some illustrative examples.

Using an unordered map in C++ STL

This is a part of the STL in C++, defined at <unordered_map>.

#include <unordered_map>

template <class Key, class Value> class unordered_map;

The most common arguments are Key and Value, which is the key-value pair.

There are other arguments which you can pass to std::unordered_map, but for the sake of illustration, we won’t be using them. (You can refer to them here)

Let’s get started now!

Unordered Map in C++ STL – Some Examples

Let’s look at some examples of the unordered map in C++.

1. Inserting to an Unordered Map

Let’s first declare our container structure, by assigning it to a variable.

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    // We declare our unordered map (int, string)
    // Here, the key is an int, and the value is a string
    std::unordered_map<int, std::string> my_map;

    // Direct array-like access!
    my_map[10] = "Hello from JournalDev!";
    my_map[20] = "Sample String";

    std::cout << my_map[10] << std::endl;
    std::cout << my_map[20] << std::endl;

    return 0;
}

Notice the similarities between this and the array, with the same way of assigning and accessing!

Output

Hello from JournalDev!
Sample String

It looks very easy to assign and modify using array-like indexing. Now, we’ll look at iterating through an unordered map.

By definition, since an unordered map does not define any order, we cannot guarantee that the elements are printed in order.

Remember that this is a Hash Table. Due to that, the values will be inserted at a random position, based on it’s hash value.

2. Searching an Unordered Map

Since this is a part of the STL, we can use an iterator to iterate through it.

If we want to search the whole map, we can directly use a for-each loop.

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    // We declare our unordered map (int, string)
    // Here, the key is an int, and the value is a string
    std::unordered_map<int, std::string> my_map;

    // Directly array-like access!
    my_map[10] = "Hello from JournalDev!";
    my_map[20] = "Sample String";

    // We can traverse using a for-each loop
    for (const auto& it: my_map) {
        // Here, it.first -&gt; Key
        // and it.seconds -> Value
        std::cout << it.first << ": " << it.second << std::endl;
    }

    return 0;
}

Output

20: Sample String
10: Hello from JournalDev!

Notice that in my case, the order of the search is not maintained. This indeed shows that the map is unordered.

If you want to find if a particular key exists, you can use the find method, for an element lookup.

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    // We declare our unordered map (int, string)
    // Here, the key is an int, and the value is a string
    std::unordered_map<int, std::string> my_map;

    // Directly array-like access!
    my_map[10] = "Hello from JournalDev!";
    my_map[20] = "Sample String";

    std::cout << "Searching for element with key = 10\n";
    auto it = my_map.find(10);
    std::cout << it->first << ": " << it->second << std::endl;

    std::cout << "Searching for element with key = 30\n";
    it = my_map.find(30);
    std::cout << it->first << ": " << it->second << std::endl;

    return 0;
}

Output

Searching for element with key = 10
10: Hello from JournalDev!
Searching for element with key = 30
[1]    243 segmentation fault (core dumped)  ./a.out

While we were able to get the key-value pair for the first case (10), what happened in the second case?

Since the key 30 is not found in the map, the iterator doesn’t have a first or second member.

To avoid this, we must place a check if the key does not exist.

If the key doesn’t exist, we will get the special iterator std::unordered_map.end().

Let’s add the filter condition for our search.

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    // We declare our unordered map (int, string)
    // Here, the key is an int, and the value is a string
    std::unordered_map<int, std::string> my_map;

    // Directly array-like access!
    my_map[10] = "Hello from JournalDev!";
    my_map[20] = "Sample String";

    std::cout << "Searching for element with key = 10\n";
    auto it = my_map.find(10);
    if (it != my_map.end())
        std::cout << it->first << ": " << it->second << std::endl;
    else
        std::cout << "Key not found\n";

    std::cout << "Searching for element with key = 30\n";
    it = my_map.find(30);
    if (it != my_map.end())
        std::cout << it->first << ": " << it->second << std::endl;
    else
        std::cout << "Key not found\n";

    return 0;
}

Output

Searching for element with key = 10
10: Hello from JournalDev!
Searching for element with key = 30
Key not found

Now, we are able to correctly point out whenever a key is not found in the map.

3. Deleting from an Unordered Map

Similar to insertion and searching, we can also delete an element from an unordered map.

The STL gives us the erase() method to do that.

We can erase an element by multiple ways:

  • Using an iterator (my_map.erase(mymap.begin()))
  • Using a key (my_map.erase(key))
  • Via a range (my_map.erase(my_map.find(key), my_map.end()))

The first way will delete element at the first index, if it exists.

The second method will delete the key-value pair from the map, if it exists.

The third way will use a range-based iterator to erase all the elements between them!

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    // We declare our unordered map (int, string)
    // Here, the key is an int, and the value is a string
    std::unordered_map<int, std::string> my_map;

    // Directly array-like access!
    my_map[10] = "Hello from JournalDev!";
    my_map[20] = "Sample String";
    my_map[30] = "Text";

    std::cout << "Initially, map contains:\n";
    for (const auto& it: my_map) {
        std::cout << it.first << ": " << it.second << std::endl;
    }

    std::cout << "Deleting Key: 10...\n";

    my_map.erase(10);

    std::cout << "Map now contains:\n";
    for (const auto& it: my_map) {
        std::cout << it.first << ": " << it.second << std::endl;
    }

    // Erase everything! From beginning to the end
    my_map.erase(my_map.begin(), my_map.end());

    std::cout << "Map now contains:\n";
    for (const auto& it: my_map) {
        std::cout << it.first << ": " << it.second << std::endl;
    }

    return 0;
}

Output

Initially, map contains:
30: Text
20: Sample String
10: Hello from JournalDev!
Deleting Key: 10...
Map now contains:
30: Text
20: Sample String
Map now contains:

As you can see, we were able to get the correct output! After deleting the key 10, we only had two other pairs remaining.

After deleting using the range filter, we were able to delete everything from the map!


Conclusion

In this article, we learned how we could use the unordered map data structure in C++.

References


Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages