std::unordered_set

An unordered_set is a container that stores unique elements in a way that allows fast access to elements based on their values.

It uses a hash function to hash the elements and stores them in buckets corresponding to their hash values.

The elements are stored in no particular order.

std::unordered_set C++

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

#include <unordered_set>

std::unordered_set<T, Hash, KeyEqual> myUnorderedSet;

Here, T is the type of the elements to be stored in the unordered_set, Hash is the hash function used to hash the elements, and KeyEqual is the function used to compare elements for equality. If Hash and KeyEqual are not provided, the default hash function (std::hash<T>) and the default key equality function (std::equal_to<T>) are used.

Functions in std::unordered_set

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

insert():

Inserts a new element into the unordered_set.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> myUnorderedSet;

    myUnorderedSet.insert(5);
    myUnorderedSet.insert(2);
    myUnorderedSet.insert(8);

    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_set<int> myUnorderedSet;

    myUnorderedSet.insert(5);
    myUnorderedSet.insert(2);
    myUnorderedSet.insert(8);

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

    return 0;
}

erase():

Removes an element from the unordered_set.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> myUnorderedSet;

    myUnorderedSet.insert(5);
    myUnorderedSet.insert(2);
    myUnorderedSet.insert(8);

    myUnorderedSet.erase(2);

    return 0;
}

size():

Returns the number of elements in the unordered_set.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> myUnorderedSet;

    myUnorderedSet.insert(5);
    myUnorderedSet.insert(2);
    myUnorderedSet.insert(8);

    std::cout << "Number of elements in the unordered_set: " << myUnorderedSet.size() << std::endl;

    return 0;
}

Iterating through the unordered_set:

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> myUnorderedSet;

    myUnorderedSet.insert(5);
    myUnorderedSet.insert(2);
    myUnorderedSet.insert(8);

    for (const auto& element : myUnorderedSet) {
        std::cout << "Element: " << element << std::endl;
    }

    return 0;
}

Time Complexity and Space Complexity

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

• insert(): 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_set.

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

Conclusion

std::unordered_set is a powerful 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 values is essential. Understanding the functions and their time and space complexity helps in effectively utilizing the std::unordered_set container for various applications.