std::unordered_multiset

An std::unordered_multiset is a container that stores elements in a way that allows fast access, insertion, and deletion.

It allows multiple occurrences of elements with the same value.

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

Table of Contents

std::unordered_multiset in C++

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

#include <unordered_set>

std::unordered_multiset<T> myUnorderedMultiset;

Here, T is the type of elements to be stored in the unordered_multiset. The hash function and key equality function are automatically deduced from the type T.

Functions in std::unordered_multiset

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

insert():

Inserts a new element into the unordered_multiset.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_multiset<int> myUnorderedMultiset;

    myUnorderedMultiset.insert(1);
    myUnorderedMultiset.insert(2);
    myUnorderedMultiset.insert(2);
    myUnorderedMultiset.insert(3);

    return 0;
}

count():

Returns the number of occurrences of a specific element in the unordered_multiset.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_multiset<int> myUnorderedMultiset;

    myUnorderedMultiset.insert(1);
    myUnorderedMultiset.insert(2);
    myUnorderedMultiset.insert(2);
    myUnorderedMultiset.insert(3);

    std::cout << "Number of occurrences of 2: " << myUnorderedMultiset.count(2) << std::endl;

    return 0;
}

find():

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

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_multiset<int> myUnorderedMultiset;

    myUnorderedMultiset.insert(1);
    myUnorderedMultiset.insert(2);
    myUnorderedMultiset.insert(2);
    myUnorderedMultiset.insert(3);

    auto it = myUnorderedMultiset.find(2);
    if (it != myUnorderedMultiset.end()) {
        std::cout << "Found element 2." << std::endl;
    } else {
        std::cout << "Element 2 not found." << std::endl;
    }

    return 0;
}

equal_range():

Returns a pair of iterators representing the range of elements with a specific value.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_multiset<int> myUnorderedMultiset;

    myUnorderedMultiset.insert(1);
    myUnorderedMultiset.insert(2);
    myUnorderedMultiset.insert(2);
    myUnorderedMultiset.insert(3);

    auto range = myUnorderedMultiset.equal_range(2);
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << "Found element 2." << std::endl;
    }

    return 0;
}

erase():

Removes elements from the unordered_multiset.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_multiset<int> myUnorderedMultiset;

    myUnorderedMultiset.insert(1);
    myUnorderedMultiset.insert(2);
    myUnorderedMultiset.insert(2);
    myUnorderedMultiset.insert(3);

    // Remove all occurrences of element 2
    myUnorderedMultiset.erase(2);

    return 0;
}

Iterating through the unordered_multiset:

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_multiset<int> myUnorderedMultiset;

    myUnorderedMultiset.insert(1);
    myUnorderedMultiset.insert(2);
    myUnorderedMultiset.insert(2);
    myUnorderedMultiset.insert(3);

    // Iterating through the unordered_multiset
    for (const auto& element : myUnorderedMultiset) {
        std::cout << "Element: " << element << std::endl;
    }

    return 0;
}

Time Complexity and Space Complexity

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

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

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

Conclusion

std::unordered_multiset is a versatile container in C++ that efficiently stores multiple occurrences of elements in an unordered manner. It is an excellent choice for applications where the order of elements doesn’t matter, and fast access to elements based on their values is essential. Understanding the functions and their time and space complexity helps in efficiently utilizing the std::unordered_multiset container for various scenarios.