Unordered Set

Leave a Comment / C++ STL / By

Hi everyone ✋

In this tutorial we will talk about Unordered Set

So, What is Unordered Set actually?

Unordered Set is an associative container of C++ STL that stores only unique elements, just like set. Each element is a key, and there are no associated values.

The big difference from set is that unordered set does not keep the elements in any sorted order. Instead, it uses a hash function to decide where to put each element. That is why it is called “unordered”.

Just like set, unordered set does not have the [ ] subscript operator or the at() method — there are no values to look up, only keys.

Unordered Set’s underlying data structure is a Hash Table. Because of hashing, all its major operations — insertion, deletion, search — take O(1) time on average. In the worst case (when many keys hash to the same bucket) the operations can go up to O(n), but in practice this is very rare.

Header File Inclusion for unordered_set

#include <unordered_set>

Declaration & Initialization

Declaring an empty unordered set —


unordered_set <int> numbers;

The unordered set is empty right now.

Declaring an unordered set with values —

From C++11 onwards, we can initialize an unordered set with values using curly braces —


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

After Initialization numbers may look like this —

 

30 50 10 40 20

 

Notice that the elements are not in the order we inserted them (10, 20, 30, 40, 50). Since unordered set does not keep elements sorted, the actual order depends on the hash function and can be different on different machines or compilers.

Declaring an unordered set with duplicate values —

If we try to initialize an unordered set with duplicate values, the duplicates are silently dropped —


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

numbers will still contain only 5 unique elements — 10, 20, 30, 40, and 50 — in some hash-dependent order. This is one of the most common uses of unordered set — fast deduplication of a collection of values.

Declaring unordered sets of different types —

Element type can be anything that has a valid hash function —


unordered_set <double> scores;
unordered_set <string> nameList;
unordered_set <char> letters;

💡 Quick tip on element types — Since unordered set relies on hashing, the element type must have a valid hash function. All built-in types (int, string, char, double, etc.) work out of the box. But for custom types or pair, we need to provide our own hash function. We will see this in a bit.

Insertion

Insertion using insert() method

The main way to add elements to an unordered set is the insert() method —


unordered_set <int> numbers;

numbers.insert(20);
numbers.insert(50);
numbers.insert(10);
numbers.insert(40);
numbers.insert(30);

Inserting a duplicate value

If we try to insert a value that already exists, the insertion is silently ignored —


numbers.insert(30);

The set still has the same 5 elements.

💡 Quick tip on insert() return value — insert() actually returns a pair<iterator, bool>. The bool tells us whether the insertion actually happened (true) or the value was already there (false). This is useful when we want to check for duplicates during insertion.


auto result = numbers.insert(30);

if (result.second)
{
    cout << "Inserted successfully" << endl;
}
else
{
    cout << "Already exists" << endl;
}

Insertion using emplace() method

emplace() constructs the element in place, avoiding an extra copy —


numbers.emplace(60);
numbers.emplace(70);

Inserting a range of values

We can also insert a range of values from another container —


vector <int> extra = { 80, 90, 100 };

numbers.insert(extra.begin(), extra.end());

Accessing the element

Unordered set does not support [ ] or at(). Access happens through iterators returned by find(), or by iterating through the unordered set directly.

find() method

find() returns an iterator to the element if it exists, otherwise it returns end() —


auto it = numbers.find(30);

if (it != numbers.end())
{
    cout << "Found " << *it << endl;
}
else
{
    cout << "Not found" << endl;
}

Output will be – Found 30

Checking if an element exists

count() method

Since unordered set elements are unique, count() returns either 0 (not present) or 1 (present) —


if (numbers.count(30))
{
    cout << "30 is in the set" << endl;
}

contains() method (C++20)

From C++20 onwards, we have a cleaner way —


if (numbers.contains(30))
{
    cout << "30 is in the set" << endl;
}

Iterating through an unordered set

Range-based for loop

The cleanest way to iterate through an unordered set is using a range-based for loop —


for (auto &value : numbers)
{
    cout << value << " ";
}

Output may be something like —

70 30 90 50 10 100 40 60 20 80

Using iterator

We can also iterate using iterators directly —


unordered_set <int>::iterator it;

for (it = numbers.begin(); it != numbers.end(); it++)
{
    cout << *it << " ";
}

💡 Note on iteration order — Unlike set, unordered set does not iterate elements in sorted order. The order depends on the hash values and the bucket layout, so it can feel random. If we need the elements sorted, we should use set instead.

Deletion

Deletion using erase() with value

We can delete a specific element by passing the value directly to erase() —


numbers.erase(30);

After deletion, the element 30 will be removed from the unordered set.

Deletion using erase() with iterator

We can also delete using an iterator —


auto it = numbers.find(40);

if (it != numbers.end())
{
    numbers.erase(it);
}

clear() method

If we want to remove all elements of the unordered set, we can use clear() —


numbers.clear();

After clear(), numbers will be empty.

Size and Empty


cout << numbers.size() << endl;

if (numbers.empty())
{
    cout << "Unordered set is empty" << endl;
}

size() returns the number of elements, and empty() returns true if the unordered set has no elements.

Swapping

swap() method

STL unordered set has a method named swap(), which swaps all the elements between two unordered sets —


unordered_set <int> setOne = { 1, 2, 3 };
unordered_set <int> setTwo = { 10, 20, 30, 40, 50 };

// swapping values between two unordered sets
setOne.swap(setTwo);

After swapping, setOne will have the elements of setTwo, and setTwo will have the elements of setOne.

Unordered Set with pair as element

Sometimes we want to use a pair as the element — for example, to store unique (x, y) coordinates. But if we try this directly —


// this will give a compile error
unordered_set < pair<int, int> > points;

We will get a compile error. The reason is that STL does not provide a default hash function for pair. We need to provide our own.

Writing a custom hash function —


struct pairHash
{
    size_t operator()(const pair<int, int> &p) const
    {
        // combine hashes of the two elements
        return hash<int>()(p.first) ^ (hash<int>()(p.second) << 1);
    }
};

unordered_set < pair<int, int>, pairHash > points;

points.insert({ 1, 2 });
points.insert({ 3, 4 });
points.insert({ 1, 2 }); // ignored, duplicate

Checking if a point exists —


if (points.count({ 1, 2 }))
{
    cout << "Point (1, 2) is in the set" << endl;
}

💡 Note on custom hash — The hash function must be deterministic (same input always gives same output) and should spread the elements as evenly as possible across buckets. A poor hash function can push the performance from O(1) down to O(n).

Bucket Interface

Unordered set stores its elements in buckets. Each bucket holds elements that hash to the same index. STL gives us a few methods to peek into this bucket structure.

bucket_count() method

Returns the total number of buckets currently in the unordered set —


cout << numbers.bucket_count() << endl;

bucket() method

Returns the bucket number where a given element is stored —


cout << numbers.bucket(30) << endl;

load_factor() method

Returns the average number of elements per bucket, calculated as size() / bucket_count(). A higher load factor means more collisions —


cout << numbers.load_factor() << endl;

max_load_factor() method

Returns (or sets) the maximum load factor that unordered set allows. When the actual load factor crosses this value, the unordered set automatically rehashes —


cout << numbers.max_load_factor() << endl;

// setting a new max load factor
numbers.max_load_factor(0.75);

rehash() method

Forces the unordered set to rebuild its internal bucket structure with at least the given number of buckets —


numbers.rehash(100);

reserve() method

Reserves enough buckets to hold at least the given number of elements without rehashing. This is very useful when we know how many elements we are about to insert —


// if we know we will insert around 10000 elements
numbers.reserve(10000);

💡 Quick tip on reserve() — Calling reserve() before a big batch of insertions prevents multiple rehashes during insertion and can give a noticeable speed boost.

Unordered Set vs Set

This is a common confusion, so it is worth a quick note —

 

Property unordered_set set
Underlying data structure Hash Table Red-Black Tree
Order of elements No specific order Sorted
Insertion / Deletion / Search O(1) average, O(n) worst O(log n)
lower_bound() / upper_bound() Not available Available
Access to smallest / largest Not directly available O(1) via begin() / rbegin()
Memory usage Higher (due to buckets) Lower
Use when We just need fast lookup, order does not matter We need sorted elements or ordered traversal

 

Time Complexity

 

Operation Description Time Complexity
insert() Insert an element O(1) average, O(n) worst
emplace() Construct and insert an element in place O(1) average, O(n) worst
erase() Remove an element by value or iterator O(1) average, O(n) worst
find() Find an element O(1) average, O(n) worst
count() Check if an element exists (returns 0 or 1) O(1) average, O(n) worst
contains() Check if an element exists (C++20) O(1) average, O(n) worst
size() Returns the number of elements O(1)
empty() Returns true if unordered set is empty O(1)
clear() Removes all elements O(n)
swap() Swaps contents of two unordered sets O(1)
bucket_count() Returns the number of buckets O(1)
load_factor() Returns average elements per bucket O(1)
rehash() Rebuilds the bucket structure O(n) average, O(n²) worst
reserve() Reserves buckets for expected element count O(n) average, O(n²) worst
begin() / end() Iterators to the beginning and end O(1)

 

Applications

        • Fast deduplication of a large collection of values
        • Checking if an element has been seen before (visited-set in BFS/DFS/graph problems)
        • Two-sum and subarray-sum problems where order does not matter
        • Storing a whitelist or blacklist for quick membership checks
        • Counting distinct elements when we do not need them sorted
        • Checking for cycles in linked lists or arrays using seen-element tracking
        • Storing unique IDs like user IDs, session tokens, or distinct IP addresses for fast lookup
        • Storing unique (x, y) coordinates in 2D grid problems using pair as element

In the next tutorial we will talk about another useful STL container.

Until then
Happy Coding 💻 🎵

Leave a Comment

Your email address will not be published. Required fields are marked *