std::unordered_map

An unordered_map is a container that stores key-value pairs in a way that allows fast access to elements based on their keys.

It uses a hash function to map the keys to their respective hash values, and then stores the elements in buckets corresponding to those hash values.

std::unordered_map in C++

To work with unordered_maps in C++, you can use the std::unordered_map class from the <unordered_map> header. The std::unordered_map class template has the following syntax:

#include <unordered_map>

std::unordered_map<Key, T, Hash, KeyEqual> myUnorderedMap;

Here, Key is the type of the keys, T is the type of the values, Hash is the hash function used to hash the keys, and KeyEqual is the function used to compare keys for equality. If Hash and KeyEqual are not provided, the default hash function (std::hash<Key>) and the default key equality function (std::equal_to<Key>) are used.

Functions in std::unordered_map

Let’s create an std::unordered_map and explore its important functions with code examples:

insert():

Inserts a new key-value pair into the unordered_map.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> myUnorderedMap;

    myUnorderedMap.insert({{1, "One"}, {2, "Two"}, {3, "Three"}});

    return 0;
}

at():

Accesses the value associated with a given key.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> myUnorderedMap;

    myUnorderedMap.insert({{1, "One"}, {2, "Two"}, {3, "Three"}});

    std::cout << "Value at key 2: " << myUnorderedMap.at(2) << std::endl;

    return 0;
}

find():

Searches for a key and returns an iterator to the element if found.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> myUnorderedMap;

    myUnorderedMap.insert({{1, "One"}, {2, "Two"}, {3, "Three"}});

    auto it = myUnorderedMap.find(2);
    if (it != myUnorderedMap.end()) {
        std::cout << "Found key 2, value: " << it->second << std::endl;
    } else {
        std::cout << "Key 2 not found." << std::endl;
    }

    return 0;
}

erase():

Removes the element with the given key from the unordered_map.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> myUnorderedMap;

    myUnorderedMap.insert({{1, "One"}, {2, "Two"}, {3, "Three"}});

    myUnorderedMap.erase(2);

    return 0;
}

size():

Returns the number of key-value pairs in the unordered_map.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> myUnorderedMap;

    myUnorderedMap.insert({{1, "One"}, {2, "Two"}, {3, "Three"}});

    std::cout << "Number of key-value pairs in the unordered_map: " << myUnorderedMap.size() << std::endl;

    return 0;
}

Iterating through the unordered_map:

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> myUnorderedMap;

    myUnorderedMap.insert({{1, "One"}, {2, "Two"}, {3, "Three"}});

    for (const auto& pair : myUnorderedMap) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
    }

    return 0;
}

Time Complexity and Space Complexity

The time complexity of the essential std::unordered_map operations is as follows:

• insert(): Average O(1), Worst case O(N)
• at(): Average O(1), Worst case O(N)
• find(): Average O(1), Worst case O(N)
• erase(): Average O(1), Worst case O(N)
• size(): O(1)

Here, N is the number of elements in the std::unordered_map.

The space complexity of an std::unordered_map is O(N), where N is the number of elements in the map.

Conclusion

std::unordered_map is a versatile container in C++ that provides constant-time average complexity for searching, insertion, and deletion operations. It is an excellent choice for applications where the order of elements doesn’t matter, and fast access to elements based on their keys is essential. Understanding the functions and their time and space complexity helps in utilizing the std::unordered_map container effectively for a wide range of applications.