What is Unordered Set in C++?

An unordered set is an associative container in the Standard Template Library (STL) that stores unique elements without maintaining any specific order.

Unlike std::set, which stores elements in sorted order using a tree structure, std::unordered_set stores elements using a hash table, making lookups much faster on average.

Think of an unordered set as a locker room. Every locker has a unique number (generated internally by a hash function), allowing quick access without arranging lockers alphabetically.

Why does Unordered Set exist?

Although std::set provides sorted data, maintaining that order requires extra work. If sorting is unnecessary, using an unordered set offers several benefits.

• Faster average search
• Faster average insertion
• Faster average deletion
• Automatic duplicate removal

Real-world use cases

• Removing duplicate records
• User authentication systems
• Caching unique objects
• Spell checkers
• Fast keyword lookups
• Graph algorithms (visited nodes)
• Database indexing
• Search engines

Prerequisites

• Variables and data types
• Arrays and loops
• Functions
• Templates
• Basic STL containers
• std::set (recommended)

Including the header

#include <unordered_set>

Creating an unordered set

unordered_set<data_type> set_name;

// Example:
unordered_set<int> numbers;

Initializing an unordered set

unordered_set<int> s = {5, 2, 8, 5, 1, 2};

// Stored values:
// 5 1 2 8

Note: the output order may differ each time because unordered sets do not maintain ordering.

Characteristics of unordered set

• Duplicate elements: not allowed
• Order: no guaranteed order
• Random access: not supported
• Search: average O(1)
• Insertion: average O(1)
• Deletion: average O(1)
• Implementation: hash table

Common operations

• insert() – add an element
• erase() – remove an element
• find() – search for an element
• count() – check if an element exists
• size() – number of elements
• empty() – check whether the set is empty
• clear() – remove all elements
• begin() – iterator to first element
• end() – iterator to one past the last element

Hash tables

An unordered set stores elements in buckets using a hash function.

When an element is inserted, a hash value is computed, the element is placed into a bucket, and future searches directly access the bucket instead of scanning every element. This makes most operations extremely fast.

Iterating through an unordered set

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

// Remember that the output order is unpredictable.

Example 1: Creating and displaying an unordered set

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

int main()
{
    unordered_set<int> numbers;

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

    for (int num : numbers)
    {
        cout << num << " ";
    }

    return 0;
}

// Possible output: 20 30 10
// Note: the order is not guaranteed.

Example 2: Searching for an element

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

int main()
{
    unordered_set<int> ids = {101,102,103};

    if(ids.find(102) != ids.end())
    {
        cout << "Found";
    }
    else
    {
        cout << "Not Found";
    }

    return 0;
}

Example 3: Removing elements

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

int main()
{
    unordered_set<int> values = {1,2,3,4,5};

    values.erase(3);

    for(int value : values)
    {
        cout << value << " ";
    }

    return 0;
}

Example 4: Removing duplicate words

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

int main()
{
    vector<string> words =
    {
        "apple",
        "banana",
        "apple",
        "orange",
        "banana"
    };

    unordered_set<string> uniqueWords;

    for(const string& word : words)
    {
        uniqueWords.insert(word);
    }

    cout << "Unique Words:\n";

    for(const string& word : uniqueWords)
    {
        cout << word << endl;
    }

    return 0;
}

Example 5: Website visitor tracking

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

int main()
{
    unordered_set<string> visitors;

    visitors.insert("User101");
    visitors.insert("User102");
    visitors.insert("User103");
    visitors.insert("User101");

    cout << "Unique Visitors: ";
    cout << visitors.size() << endl;

    return 0;
}

Common mistakes and pitfalls

• Expecting sorted output. Fix: remember that unordered_set does not maintain order
• Using index access (s[0]). Fix: iterate using loops or iterators
• Assuming duplicates are stored. Fix: duplicate values are automatically ignored
• Using unordered_set when sorted traversal is required. Fix: use std::set instead
• Ignoring custom hashing for user-defined types. Fix: provide a custom hash function when needed

Best practices

• Use unordered_set when sorted order is unnecessary
• Prefer find() over manually searching
• Reserve buckets with reserve() when inserting many elements to reduce rehashing
• Pass large unordered sets by const reference
• Use custom hash functions for user-defined classes
• Choose std::set if ordered traversal is important

When not to use this

• Elements must remain sorted
• You frequently need the smallest or largest element
• Deterministic iteration order is required
• Memory usage must be minimized (hash tables generally use more memory than tree-based containers)
• Worst-case lookup performance is a critical concern, as hash collisions can degrade operations to O(n)

Summary

• Unordered Set in C++ stores unique elements using a hash table
• Elements are not sorted
• Duplicate values are automatically ignored
• Search, insertion, and deletion are typically O(1) on average
• Use insert(), erase(), find(), count(), clear(), and size() for common operations
• unordered_set is ideal for fast membership tests and duplicate removal
• Use std::set instead when sorted order is required

Frequently asked questions

What is the difference between set and unordered_set?

std::set stores elements in sorted order using a tree, while std::unordered_set stores elements in no particular order using a hash table. As a result, unordered_set usually provides faster average lookup, insertion, and deletion.

Can an unordered set store duplicate values?

No. Like std::set, an unordered_set only stores unique elements. Duplicate insertions are ignored.

Why is the output order different each time?

Elements are stored based on their hash values and bucket placement, not insertion or sorted order. Therefore, iteration order is unspecified and may vary.

What is the time complexity of searching in an unordered set?

Searching with find() is typically O(1) on average. However, in the worst case (many hash collisions), it can degrade to O(n).

When should I use unordered_set instead of set?

Use std::unordered_set when you need fast average-case lookups and don't care about the order of elements. Choose std::set when maintaining sorted order or ordered traversal is important.