What is an unordered_set?

std::unordered_set is an unordered associative container that stores unique elements in no particular order. Unlike its counterpart std::set, which maintains elements in sorted order, std::unordered_set employs a hash table data structure to achieve efficient storage and retrieval. Elements in the set are organized based on their hash values, allowing for fast insertion, deletion, and lookup operations.

An unordered_set in C++ is like a special box where you can put things. But it's not just any box - it's a magic box that can only hold unique things, meaning you can't put the same thing in the box twice.

Here's how it works:

1. No Duplicate Items: You can't put two identical items in the box. If you try to put something that's already in there, it won't get added again.
2. Fast Lookup: You can quickly check if something is in the box or not. It's like having a superpower to find things instantly.
3. No Particular Order: Unlike some other boxes that keep things in order, this box doesn't care about the order of things inside. It's like a jumbled collection where each item is just there, without any specific arrangement.

Key Characteristics and Features

1. Hash Table Implementation: Internally, std::unordered_set is typically implemented using a hash table, which provides constant-time average complexity for essential operations like insertion, deletion, and lookup.
2. Unordered Storage: Elements in an std::unordered_set are not stored in any particular order. Instead, they are arranged based on their hash values, resulting in a more efficient data structure for certain applications.
3. Unique Elements:std::unordered_set ensures that each element in the set is unique. Duplicate elements are not allowed, and attempting to insert a duplicate element will be ignored.
4. Custom Hash Function: Developers can provide a custom hash function to std::unordered_set to customize the hashing strategy for the element type. This flexibility allows for optimal performance based on specific application requirements.
5. Iterators:std::unordered_set provides iterators that enable traversal of its elements. Iterators can be used to access, modify, or remove elements from the set, offering granular control over data manipulation.
6. Efficient Operations: The average time complexity for essential operations such as insertion, deletion, and lookup in std::unordered_set is constant (O(1)). However, the worst-case time complexity is linear (O(n)), where n is the number of elements in the set.
7. Resizable:std::unordered_set automatically resizes its internal hash table to accommodate more elements as needed. This dynamic resizing ensures efficient memory utilization and allows the set to adapt seamlessly to varying workloads.

Functions of Unordered_Set

1 insert()

This  function is used to add elements to the unordered_set. If the element already exists in the set, the operation has no effect. This function returns a pair consisting of an iterator to the inserted element (or the element that prevented the insertion) and a Boolean value indicating whether the insertion took place.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet = {1, 2, 3};

    auto result = mySet.insert(4);
    if (result.second) {
        std::cout << "Insertion successful\n";
    } else {
        std::cout << "Element already exists in the set\n";
    }
    
    return 0;
}

// Ouput
Insertion successful

Complexity Analysis:

Time Complexity -

• Average Case: Constant time, O(1)
• Worst Case: Linear time, O(n) due to hash collisions, but with efficient hash functions, collisions are rare.

2 erase()

This function is used to remove elements format he unordered_set either by specifying the element itself or an iterator pointing to the element to be removed.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet = {1, 2, 3};

    mySet.erase(2); // Removes the element 2 from the set

    return 0;
}

Complexity Analysis:

Time Complexity -

• Average Case: Constant time, O(1)
• Worst Case: Linear time, O(n) due to hash collisions

3 find()

This function is used to search for an element within the unordered_set. It returns an iterator to the element if found, otherwise it returns an iterator pointing to the end of the set (end()).

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet = {1, 2, 3};

    auto it = mySet.find(2);
    if (it != mySet.end()) {
        std::cout << "Element found in the set\n";
    } else {
        std::cout << "Element not found\n";
    }

    return 0;
}

// Output
Element found in the set

Complexity Analysis:

Time Complexity -

• Average Case: Constant time, O(1)
• Worst Case: Linear time, O(n) due to hash collisions

4 size()

This function returns the number of element in the unordrered_set.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet = {1, 2, 3};
    std::cout << "Size of mySet: " << mySet.size();
    // Output: Size of mySet: 3
    return 0;
}

Complexity Analysis:

Time Complexity -

• Constant time, O(1)

5 clear()

This function removes all elements from the unordered_set leaving it with a size of 0.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet = {1, 2, 3};
    mySet.clear();
    // Now, mySet is empty
    return 0;
}

Complexity Analysis:

• Linear time, O(n), where n is the number of elements in the set.