C++ unordered_set

---

Introduction

In C++, the std::unordered_set is an associative container that stores unique elements in an unordered fashion using a hash table. Unlike std::set, which maintains elements in sorted order, unordered_set does not guarantee any specific order for its elements. It offers constant-time average complexity (O(1)) for insertion, deletion, and lookup operations, making it efficient for use cases where you do not require the order of elements but need fast access.

This container is part of the C++ Standard Library, provided in the <unordered_set> header, and is best suited when you need to check for membership or perform other operations like insertion and deletion quickly, based on a unique set of keys.

---

Syntax

The syntax to declare an unordered_set is:

std::unordered_set<ElementType> unordered_set_name;

Where:

• ElementType: The type of the element stored in the set (e.g., int, std::string).

You can also specify a custom hash function and comparison function:

std::unordered_set<ElementType, Hash, Compare> unordered_set_name;

Where:

• Hash: A function or function object used for hashing the keys.
• Compare: A custom comparison function for comparing keys (though not typically needed as unordered_set uses a default comparator).

---

Declaring and Initializing an Unordered Set

Example 1: Basic Unordered Set Declaration

#include <iostream>
#include <unordered_set>

int main() {
    // Declare an unordered set with int elements
    std::unordered_set<int> uset;

    // Insert elements into the unordered set
    uset.insert(10);
    uset.insert(20);
    uset.insert(30);
    uset.insert(40);
    uset.insert(50);

    // Displaying the elements of the unordered set
    for (const auto& element : uset) {
        std::cout << element << std::endl;
    }

    return 0;
}

Output:

10
20
30
40
50

Note: The order in which the elements are displayed is not guaranteed because unordered_set does not maintain any specific order.

---

Operations on Unordered Sets

1. Insert Elements

You can insert elements into an unordered set using the insert() method:

uset.insert(60);  // Insert the element 60 into the unordered set

2. Find Elements

You can search for an element in the unordered set using the find() method. This returns an iterator to the element if found, or unordered_set::end() if the element is not present.

auto it = uset.find(30);  // Search for the element 30
if (it != uset.end()) {
    std::cout << "Found: " << *it << std::endl;
} else {
    std::cout << "Element not found!" << std::endl;
}

3. Erase Elements

You can remove an element by value or by iterator.

• Remove by value:

  uset.erase(20);  // Removes the element with value 20
  

• Remove by iterator:

  auto it = uset.find(40);
  uset.erase(it);  // Removes the element pointed to by the iterator
  

4. Count Elements

You can check whether a specific element exists in the unordered set using the count() method. Since the set stores unique elements, this method returns either 1 (if the element is found) or 0 (if not).

std::cout << "Count of 20: " << uset.count(20) << std::endl;  // Output: 0
std::cout << "Count of 30: " << uset.count(30) << std::endl;  // Output: 1

5. Size and Emptiness

You can check the size of the unordered set and whether it is empty using the size() and empty() methods:

std::cout << "Size of unordered set: " << uset.size() << std::endl;
std::cout << "Is unordered set empty? " << (uset.empty() ? "Yes" : "No") << std::endl;

6. Clear the Unordered Set

You can remove all elements from the unordered set using the clear() method:

uset.clear();  // Removes all elements from the unordered set

---

Iterating Over an Unordered Set

You can iterate over the elements of an unordered set using an iterator or a range-based for loop:

Example 1: Using Iterator

for (auto it = uset.begin(); it != uset.end(); ++it) {
    std::cout << *it << std::endl;
}

Example 2: Using Range-Based For Loop

for (const auto& element : uset) {
    std::cout << element << std::endl;
}

---

Custom Hash Function

If you're using a custom type as the element of the unordered set, you need to define a custom hash function.

Example: Custom Hash Function

Suppose you have a custom class Person and want to use it as an element in an unordered set.

#include <iostream>
#include <unordered_set>
#include <string>

class Person {
public:
    std::string name;
    int age;

    Person(std::string name, int age) : name(name), age(age) {}

    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

struct PersonHash {
    size_t operator()(const Person& p) const {
        return std::hash<std::string>()(p.name) ^ std::hash<int>()(p.age);  // Combine hashes of name and age
    }
};

int main() {
    std::unordered_set<Person, PersonHash> uset;

    uset.insert(Person("Alice", 30));
    uset.insert(Person("Bob", 25));

    for (const auto& person : uset) {
        std::cout << person.name << " (" << person.age << ")" << std::endl;
    }

    return 0;
}

Output:

Alice (30)
Bob (25)

---

Advantages of Using std::unordered_set

1. Fast Lookup: unordered_set offers O(1) average time complexity for insertion, deletion, and lookup operations, making it highly efficient for large datasets.
2. Unique Elements: Like std::set, it ensures that all elements are unique, so there are no duplicates.
3. No Order Guarantee: If order is not important for your use case, unordered_set provides a fast and memory-efficient solution.
4. Custom Hashing: You can use custom hash functions, allowing you to store custom types as elements.

---

When to Use std::unordered_set

Use std::unordered_set when:

• You need a fast membership test (checking if an element exists) and do not care about the order of the elements.
• You are working with unique elements, and duplicate entries should be automatically discarded.
• You need an efficient set-based data structure for large datasets with frequent insertions and deletions.

---

---