Unordered Set: Container, C++

Unordered Set Container in C++: Usage and Operations

In C++, the unordered_set container is part of the Standard Template Library (STL). It is a dynamic collection that stores unique elements in no particular order. An unordered_set is implemented using a hash table, which ensures that insertions, deletions, and lookups occur in average constant-time complexity. This makes unordered_set an ideal choice when you need to maintain a collection of unique items with fast access, and when the order of elements doesn't matter.

In this guide, we will explore everything about the unordered_set container, including how to construct unordered sets, perform common operations, and effectively utilize its capabilities in C++.

---

Table of Contents

1. Introduction to Unordered Set in C++
2. Different Ways to Construct an Unordered Set
3. Common Operations on Unordered Set
   • insert()
   • erase()
   • find()
   • count()
   • size()
   • empty()
   • clear()
4. Working with Custom Data Types
5. Iterators in Unordered Sets
6. Summary and Best Practices

---

1. Introduction to Unordered Set in C++

An unordered_set in C++ is a container that stores unique elements, with no specific order. It is designed for fast retrieval and manipulation of data, making it suitable for scenarios where the order of elements is not important.

Key Features:

• Unique Elements: Each element in an unordered_set is unique. Duplicates are not allowed.
• Fast Access: Average constant-time complexity for insertions, deletions, and lookups, due to its hash table-based implementation.
• No Order: Elements are not stored in any specific order, which can make operations faster compared to ordered containers like set.

When to Use:

• Use unordered_set when you need to store unique elements and require fast access without caring about the order.
• If you need elements to be in a sorted order, consider using set instead.

---

2. Different Ways to Construct an Unordered Set

You can create an unordered_set in several ways, depending on your requirements.

2.1 Default Constructor

The default constructor creates an empty unordered_set.

unordered_set<int> us;

This creates an empty unordered_set of integers, which can be populated later.

2.2 Constructor with Initializer List

You can initialize an unordered_set directly with a list of values.

unordered_set<int> us = {1, 2, 3, 4, 5};

This creates an unordered_set containing the values 1, 2, 3, 4, 5.

2.3 Constructor with Another Unordered Set

You can create an unordered_set by copying elements from another unordered_set.

unordered_set<int> us1 = {1, 2, 3, 4, 5};
unordered_set<int> us2(us1);  // Initializes us2 as a copy of us1

2.4 Constructor with Another Container

You can create an unordered_set by copying elements from another container, such as a vector or list.

vector<int> v = {1, 2, 3, 4, 5};
unordered_set<int> us(v.begin(), v.end());  // Initializes an unordered_set using iterators from a vector

2.5 Assignment Operator

The assignment operator allows you to copy elements from one unordered_set to another.

unordered_set<int> us1 = {1, 2, 3};
unordered_set<int> us2;
us2 = us1;  // Now us2 contains the same elements as us1

The assignment operator performs a deep copy, meaning the elements of us1 are fully copied into us2.

---

3. Common Operations on Unordered Set

3.1 insert()

The insert() function adds an element to the unordered_set. If the element already exists, it will not be added again.

Syntax:

• Insert a single element:

  us.insert(element);

• Insert multiple elements using an initializer list:

  us.insert({element1, element2, ...});

• Insert elements from another container:

  us.insert(container.begin(), container.end());

Example:

unordered_set<int> us;

// Insert a single element
us.insert(10);  // Inserts 10
us.insert(20);  // Inserts 20
us.insert(30);  // Inserts 30

// Insert multiple elements
us.insert({40, 50, 60});  // Inserts 40, 50, and 60

// Insert elements from another container
vector<int> v = {70, 80, 90};
us.insert(v.begin(), v.end());  // Inserts 70, 80, 90

After these operations, the unordered set us will contain: {10, 20, 30, 40, 50, 60, 70, 80, 90}.

3.2 erase()

The erase() function removes an element from the unordered_set.

Syntax:

• Erase a single element:

  us.erase(element);

• Erase an element using an iterator:

  us.erase(iterator);

• Erase a range of elements:

  us.erase(start_iterator, end_iterator);

Example:

unordered_set<int> us = {10, 20, 30, 40, 50};

// Erase a single element
us.erase(20);  // Removes 20

// Erase using an iterator
auto it = us.find(30);
us.erase(it);  // Removes 30

// Erase a range of elements
us.insert({10, 20, 30, 40, 50});  // Reinsert elements for demonstration
auto start = us.find(10);
auto end = us.find(40);
us.erase(start, end);  // Removes 10 and 20

After these operations, the unordered set us will contain: {40, 50}.

Warning: Avoid using the range version of erase() with unordered_set as the concept of a range is not well-defined due to the unordered nature of the container. The order of elements is not guaranteed, which can lead to unexpected results when erasing a range.

3.3 find()

The find() function searches for an element in the unordered_set and returns an iterator to it if found, or end() if not found.

Syntax:

auto it = us.find(element);

Example:

unordered_set<int> us = {10, 20, 30};
auto it = us.find(20);
if (it != us.end()) {
    cout << "Element found: " << *it << endl;  // Outputs: Element found: 20
} else {
    cout << "Element not found." << endl;
}

3.4 count()

The count() function returns the number of occurrences of an element in the unordered_set. Since unordered_set only allows unique elements, it will return either 0 or 1.

Syntax:

size_t count = us.count(element);

Example:

unordered_set<int> us = {10, 20, 30};
cout << "Count of 20: " << us.count(20) << endl;  // Outputs: Count of 20: 1
cout << "Count of 40: " << us.count(40) << endl;  // Outputs: Count of 40: 0

3.5 size()

The size() function returns the number of elements in the unordered_set.

Syntax:

size_t size = us.size();

Example:

unordered_set<int> us = {10, 20, 30};
cout << "Size of unordered set: " << us.size() << endl;  // Outputs: Size of unordered set: 3

3.6 empty()

The empty() function checks whether the unordered_set is empty.

Syntax:

bool isEmpty = us.empty();

Example:

unordered_set<int> us;
cout << "Is unordered set empty? " << (us.empty() ? "Yes" : "No") << endl;  // Outputs: Yes
us.insert(10);
cout << "Is unordered set empty? " << (us.empty() ? "Yes" : "No") << endl;  // Outputs: No

3.7 clear()

The clear() function removes all elements from the unordered_set.

Syntax:

us.clear();

Example:

unordered_set<int> us = {10, 20, 30};
us.clear();  // Removes all elements

After calling clear(), the unordered_set will be empty.

---

4. Working with Custom Data Types

You can store custom data types in an unordered_set, provided that the type supports hashing and equality comparison. For custom types, you can define a hash function by specializing std::hash for your data type.

Example:

#include <iostream>
#include <unordered_set>
using namespace std;

struct Person {
    string name;
    int age;

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

// Custom hash function for Person
struct PersonHash {
    size_t operator()(

const Person& p) const {
        return hash<string>()(p.name) ^ hash<int>()(p.age);
    }
};

int main() {
    unordered_set<Person, PersonHash> people;

    people.insert({"Alice", 30});
    people.insert({"Bob", 25});
    people.insert({"Charlie", 35});

    for (const auto& person : people) {
        cout << person.name << " - " << person.age << endl;
    }
    return 0;
}

In this example, a custom Person type is stored in an unordered_set with a custom hash function PersonHash.

---

5. Iterators in Unordered Sets

You can iterate over the elements of an unordered_set using iterators, just like other STL containers.

Syntax:

for (auto it = us.begin(); it != us.end(); ++it) {
    // Access the element via *it
}

You can also use range-based for loops:

for (const auto& element : us) {
    // Access each element
}

---

6. Summary and Best Practices

Key Takeaways:

• unordered_set is ideal for storing unique elements with fast access and no specific order.
• Common operations like insert(), erase(), and find() are efficient due to the underlying hash table.
• Use unordered_set when you don't care about the order of elements.
• To store custom types, define a hash function using std::hash.

Best Practices:

• Ensure that your custom types are hashable by providing a correct hash function.
• Prefer unordered_set when performance is critical and order doesn't matter.
• Be mindful of the average constant-time complexity for insertions and lookups, but remember that in worst-case scenarios (e.g., many hash collisions), performance can degrade.

This concludes our guide on using unordered_set in C++. It's an essential tool for many common programming tasks where fast lookups are required.