DEV Community

Cover image for Comparing `std::set` and `std::unordered_set` in C++
Dushyant Singh Rao
Dushyant Singh Rao

Posted on

Comparing `std::set` and `std::unordered_set` in C++

import Image from 'next/image'

🚀 Introduction

C++ gives you two powerful tools to store unique values: std::set and std::unordered_set. Both avoid duplicates, but the way they work under the hood—and how fast they are—differs quite a bit.

This post breaks down the differences in a way that’s easy to understand. Whether you’re coding for performance or clarity, you’ll know exactly which one to choose by the end.

🏗️ Under the Hood: How They Work

🔧 std::set

  • Internally built on a Red-Black Tree, which is a kind of balanced binary search tree.
  • Automatically keeps elements sorted in ascending order.
  • All basic operations—insert, find, erase—run in O(log n) time.

Imagine a bookshelf where books are always arranged in alphabetical order. That’s how std::set behaves.

⚡ std::unordered_set

  • Uses a hash table under the hood.
  • Doesn't guarantee any specific order of elements.
  • Offers average-case O(1) time for inserts, lookups, and deletions.

Think of it like tossing items into labeled bins. You can grab them quickly, but they're not arranged in any particular order.

👍 Pros & 👎 Cons

Feature std::set (Red-Black Tree) std::unordered_set (Hash Table)
Time Complexity O(log n) — consistent and predictable O(1) average, O(n) worst-case (collisions)
Element Order Maintains ascending order No order guaranteed
Memory Usage More efficient in memory Slightly heavier due to hash buckets
Supports Range Ops? Yes — lower/upper bounds, etc. No
Security Safe from DoS via hash attacks Vulnerable if custom hash is poor
Custom Key Support Works if < is defined Needs std::hash + ==

🧪 Performance in Real Life

  • For small datasets, std::set can actually be faster because it avoids hash setup overhead.
  • For large datasets, std::unordered_set shines with blazing fast average-time operations.
  • If you're working in real-time systems, std::set is more reliable thanks to its consistent performance.

Example Benchmark:

Benchmark Comparison

🧩 Quick Code Comparison

std::set Example 

#include <set>
std::set<int> s;
s.insert(5);
s.insert(1);
s.insert(3);
// Automatically sorted: 1, 3, 5
Enter fullscreen mode Exit fullscreen mode

std::unordered_set Example 

#include <unordered_set>
std::unordered_set<int> us;
us.insert(5);
us.insert(1);
us.insert(3);
// No guaranteed order: could be 5, 1, 3
Enter fullscreen mode Exit fullscreen mode

When Should You Use Each?

Use std::set when:

  • You care about the elements being sorted
  • You need functions like lower_bound() or upper_bound()
  • You’re in a real-time or security-sensitive environment

Use std::unordered_set when:

  • You want maximum performance
  • You’re storing lots of data and don’t care about order
  • You’ve defined good hash functions (or are using built-in types)

Summary

std::set is perfect when you need order, reliability, and predictability. It's slower than its counterpart, but consistent.

std::unordered_set is the go-to for raw speed and high-performance applications—just make sure you understand its hash-based limitations.

Need more STL breakdowns like this? Let me know which container you'd like explained next!

Top comments (0)