std::unordered_multimap

An unordered_multimap is a container that stores key-value pairs in a way that allows fast access to elements based on their keys. It allows multiple elements with the same key, and each key-value pair is stored in a bucket based on the hash value of the key.

std::unordered_multimap in C++

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

#include <unordered_map>

std::unordered_multimap<Key, T, Hash, KeyEqual> myUnorderedMultimap;

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_multimap

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

insert():

Inserts a new key-value pair into the unordered_multimap.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_multimap<int, std::string> myUnorderedMultimap;

    myUnorderedMultimap.insert({{1, "One"}, {2, "Two"}, {1, "Another One"}});

    return 0;
}

equal_range():

Returns a pair of iterators representing the range of elements with a given key.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_multimap<int, std::string> myUnorderedMultimap;

    myUnorderedMultimap.insert({{1, "One"}, {2, "Two"}, {1, "Another One"}});

    auto range = myUnorderedMultimap.equal_range(1);
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }

    return 0;
}

count():

Returns the number of elements with a given key in the unordered_multimap.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_multimap<int, std::string> myUnorderedMultimap;

    myUnorderedMultimap.insert({{1, "One"}, {2, "Two"}, {1, "Another One"}});

    std::cout << "Number of elements with key 1: " << myUnorderedMultimap.count(1) << std::endl;

    return 0;
}

erase():

Removes elements with a given key from the unordered_multimap.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_multimap<int, std::string> myUnorderedMultimap;

    myUnorderedMultimap.insert({{1, "One"}, {2, "Two"}, {1, "Another One"}});

    myUnorderedMultimap.erase(1);

    return 0;
}

size():

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

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_multimap<int, std::string> myUnorderedMultimap;

    myUnorderedMultimap.insert({{1, "One"}, {2, "Two"}, {1, "Another One"}});

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

    return 0;
}

Iterating through the unordered_multimap:

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_multimap<int, std::string> myUnorderedMultimap;

    myUnorderedMultimap.insert({{1, "One"}, {2, "Two"}, {1, "Another One"}});

    for (const auto& pair : myUnorderedMultimap) {
        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_multimap operations is as follows:

• insert(): Average O(1), Worst case O(N)
• equal_range(): Average O(1), Worst case O(N)
• count(): 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_multimap.

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

Conclusion

std::unordered_multimap is a powerful container in C++ that allows multiple elements with the same key and provides constant-time average complexity for searching, insertion, and deletion operations. It is an excellent choice for applications where keys may have duplicate values. Understanding the functions and their time and space complexity helps in efficiently utilizing the std::unordered_multimap container in various scenarios.