Set vs unordered_set in C++: Key Differences and Usage

In C++, set stores elements in sorted order using a balanced tree, while unordered_set stores elements in no particular order using a hash table. set offers ordered traversal but slower average insertion and lookup, whereas unordered_set provides faster average access but no ordering.

Quick Comparison

Here is a quick side-by-side comparison of set and unordered_set in C++.

Feature	set	unordered_set
Underlying Data Structure	Balanced binary search tree (usually Red-Black Tree)	Hash table
Element Order	Sorted order (ascending by default)	No specific order
Average Time Complexity for Insert/Find/Erase	O(log n)	O(1) average, O(n) worst case
Memory Usage	Higher memory overhead due to tree pointers	Higher memory overhead due to hashing
Use Case	When order matters or range queries needed	When fast access without order is priority
Duplicates	No duplicates allowed	No duplicates allowed

Key Differences

The main difference between set and unordered_set lies in how they store and organize elements. set uses a balanced binary search tree, which keeps elements sorted automatically. This means you can iterate over a set and get elements in ascending order, which is useful when order matters or when you need to perform range queries.

On the other hand, unordered_set uses a hash table to store elements. This allows for faster average time complexity for insertion, lookup, and deletion operations, typically O(1). However, the elements are not stored in any particular order, so iteration order is unpredictable.

Memory usage also differs: unordered_set usually consumes more memory because it stores hash buckets and handles collisions. Meanwhile, set uses less memory but has slower operations due to tree balancing. Choose set when you need sorted data or order-dependent operations, and unordered_set when speed is more important than order.

Code Comparison

Here is how you insert and print elements using set in C++.

cpp

#include <iostream>
#include <set>

int main() {
    std::set<int> s;
    s.insert(30);
    s.insert(10);
    s.insert(20);

    for (int x : s) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    return 0;
}

Output

10 20 30 

unordered_set Equivalent

Here is the equivalent code using unordered_set to insert and print elements.

cpp

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> us;
    us.insert(30);
    us.insert(10);
    us.insert(20);

    for (int x : us) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    return 0;
}

Output

30 10 20 

When to Use Which

Choose set when you need elements sorted automatically or want to perform operations that depend on order, like finding ranges or minimum/maximum values easily. It is also better if you want predictable iteration order.

Choose unordered_set when you want the fastest possible insertion, lookup, and deletion and do not care about the order of elements. It is ideal for quick membership tests or when order does not affect your logic.

Key Takeaways

set keeps elements sorted with O(log n) operations using a balanced tree.

unordered_set offers faster average O(1) operations using a hash table but no order.

Use set when order or range queries matter.

Use unordered_set for faster access when order is not important.

Both containers do not allow duplicate elements.